ACM 264 - Count on Cantor

#include<stdio.h>    
#include<stdlib.h>   
#include<string.h>   
#include<math.h>   
main()   
{   
    int n,a,b,c,d;   
    while(scanf("%d",&n)==1)   
    {   
        for(d=1,c=n;c>d;d++) c=c-d;   
        if ( d%2==1 ) a=d-c+1;   
        else a=c;   
        b=d+1-a;   
        printf("TERM %d IS %d/%d\n",n,a,b);   
    }   
    return 0;   
}

以上程式轉自：http://mypaper.pchome.com.tw/iustlovefish/post/1311842753
稍微說明一下程式碼，先看以下圖形：標紅色部分，依照每斜行遞增，所以 d=1, c=n 初始化後，用一迴圈每做一次 c 減掉 d 而做完後 d 累加一，所以這一部份是做算出 n 是在第 d 斜行的第 c 個位置。
而這個圖表有一個特性，請看以下表：

x - 1 / y - 1	x - 1 / y	x - 1 / y + 1
x / y - 1	x / y	x / y + 1
x + 1 / y - 1	x + 1 / y	x + 1 / y + 1

只要 d 在奇數它是往左下走，偶數則往右上走，而只要 d 在奇數則該斜行的第一個位置為 1 / d，偶數為 d / 1，最後再依照它的位置算出正確答案。

此提與 ACM 10182 Bee Maja 頗像，我是用圖法煉鋼的方法寫出，但似乎比上面的程式碼還慢，所以還是參考他的做法。

回目錄
回首頁