UVa 264 Count on Cantor

　　《算法竞赛入门经典》5.4.1的题目，大意是，给出一个数表，如下：

　　第一项是1/1，第二项是1/2，第三项是2/1，第四项是3/1，第五项是2/2.....给一个正整数n，求第n项。

　　设第n个数在第k斜行，则有(k-1)*k/2 + 1 <= n <= k*(k+1) ==> (k-1)²<= k² - k + 2 <= 2*n <= k² + k < (k+1)²==> k-1 <= sqrt(2*n) < k+1, 因为要k的下界，可以令k = (int)(sqrt(2*n)-1), 从这个值递增枚举。代码如下：

View Code

 1 #include <cstdio>
 2 #include <cmath>
 3 
 4 int main()
 5 {
 6     int n;
 7     while(scanf("%d", &n) != EOF)
 8     {
 9         int k = (int)(sqrt(2*n)-1);
10         while(n > k*(k+1)/2)   k++;
11         int num = n - (k-1)*k/2;
12         int a, b;
13         if(k%2)
14         {
15             b = num;
16             a = k + 1 - num;
17         }
18         else 
19         {
20             a = num;
21             b = k + 1 - num;
22         }
23         printf("TERM %d IS %d/%d\n", n, a, b);
24     }
25     return 0;
26 }