2010年9月18日 星期六

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 - 1x - 1 / yx - 1 / y + 1
x / y - 1x / yx / y + 1
x + 1 / y - 1x + 1 / yx + 1 / y + 1
只要 d 在奇數它是往左下走,偶數則往右上走,而只要 d 在奇數則該斜行的第一個位置為 1 / d,偶數為 d / 1,最後再依照它的位置算出正確答案。

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

回目錄
回首頁

5 則留言 :

  1. 能否請問一下這程式碼中的變數各代表什麼意思呢?

    回覆刪除
  2. 您好,
    不好意思,程式碼轉自別處,稍後會貼上來源,以及程式碼的解說。

    回覆刪除
  3. 有點看不太懂@@

    回覆刪除
  4. 您好,
    這只是一種解法,您大可用您的方式,嘗試去解解這一題。

    回覆刪除

Related Posts Plugin for WordPress, Blogger...