Problem 880 Cantor Fractions，對映關係

Problem 880 此題需要用到等差級數的概念。

i 值	分子	分母	項
1	1	1	1
2	2	1	2
3	1	2
4	3	1	3
5	2	2
6	1	3
...	...	...	...
...	...	...

以上表是分析 Cantor 數的一些關聯，可以發現分母一直在做循環，只是每次多加了 1，從 1、1,2、1,2,3、1,2,3,4....等等；分子也是一樣，但它是顛倒的，1、2,1、3,2,1、4,3,2,1....等等。這就是等差級數的項數，好比說我們要找第 6 個 Cantor fraction，也就是 i = 6，則 S_n = 6，則 n = 3，我們就知道 6 是在 1,2,3 這個循環裡。就算用 5 也一樣， n = 2.701(無條件進位) = 3。

所以我們可以來推導公式：

              Sn = i
       n*(n+1)/2 = i
         n*(n+1) = i*2
n2+n+(1/4)-(1/4) = i*2
      (n+(1/2))2 = i*2+(1/4)
               n = (i*2+0.25)1/2-0.5

以上結果化為程式碼如下：

if (scanf("%lld", &i) < 1) break;
n = (long long int)ceil(sqrt(i * 2 + 0.25) - 0.5 );

如此一來，i 是第幾項也都知道了，接著只須算出它前一個項的總和，再去和 i 相減即可算出分母，分母既然算出來了，分子也就不難算了，請參考以下程式碼：

sN = (n-1) * n / 2;
printf("%lld/%lld\n", abs((i - sN) - (n+1)), i - sN);

abs 函式的程式碼：

long long int abs (long long int n)
{
    return n > 0? n:-n; 
}

By David.K

p880題目連結
回ACM題庫目錄
回首頁