P1014 Cantor表

admin

题目描述
现代数学的著名证明之一是Georg Cantor证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的：

1/1 1/2 1/3 1/4 1/5 …

2/1 2/2 2/3 2/4 …

3/1 3/2 3/3 …

4/1 4/2 …

5/1 …

… 我们以Z字形给上表的每一项编号。第一项是1/1，然后是1/2，2/1，3/1，2/2，…

输入输出格式
输入格式：
整数N（1≤N≤10000000）

输出格式：
表中的第N项

输入输出样例
输入样例#1：
7
输出样例#1：
1/4

admin

1. #include <iostream>
   
2. using namespace std;
   
3. int n;
   
4. int i,s,k,x,y;
   
5. int main()
   
6. {
   
7.     cin>>n;
   
8.     for (s=0,i=1; s+i<n; i++) s=s+i; ///找到n位于第几斜行i
   
9.     k=n-s; ///此行的第几个k
   
10.     ///cout<<s<<' '<<i<<' '<<k;   检查
    
11.     if (i%2) x=i-k+1; ///方向判断
    
12.     else x=k;
    
13.     y=(i+1)-x;
    
14.     cout<<x<<'/'<<y<<endl;

复制代码

universehyf

这一题考查意图应该是模拟，大多数人也选择用模拟做，有些人选择用二分，在下蒟蒻佩服大佬的做法。但是从数学的角度分析，其实可以一两步算出来。

1. #include<iostream>
   
2. #include<cmath>
   
3. using namespace std;
   
4. int n,c,c1;
   
5. int main()
   
6. {
   
7.     cin>>n;
   
8.     c=sqrt(2*n)+1;   //这是整个程序的智慧精髓，根据等差数列
   
9.     c1=n-c*(c-1)/2;  //公式和为n*(n+1)/2=n^2+n/2,分析即可
   
10.     if(c1>0)         //得到从1一直加到sqrt（n）-1或
    
11.         if(c%2==0)   //sqrt（n）-2可得到n，下一斜行c即是
    
12.             cout<<c1<<"/"<<c-c1+1;//加1得到；用c1算出剩下
    
13.         else         //几，利用奇偶相反算。
    
14.             cout<<c-c1+1<<"/"<<c1;
    
15.     else             //利用c1正负判断是哪个
    
16.     {
    
17.         c--;
    
18.         c1=n-c*(c-1)/2;  
    
19.         if(c%2==0)
    
20.             cout<<c1<<"/"<<c-c1+1;
    
21.         else
    
22.             cout<<c-c1+1<<"/"<<c1;
    
23.     }
    
24.     return 0;
    
25. }

复制代码

universehyf

这一题考查意图应该是模拟，大多数人也选择用模拟做，有些人选择用二分，在下蒟蒻佩服大佬的做法。但是从数学的角度分析，其实可以一两步算出来。

1. #include<iostream>
   
2. #include<cmath>
   
3. using namespace std;
   
4. int n,c,c1;
   
5. int main()
   
6. {
   
7.     cin>>n;
   
8.     c=sqrt(2*n)+1;   //这是整个程序的智慧精髓，根据等差数列
   
9.     c1=n-c*(c-1)/2;  //公式和为n*(n+1)/2=n^2+n/2,分析即可
   
10.     if(c1>0)         //得到从1一直加到sqrt（n）-1或
    
11.         if(c%2==0)   //sqrt（n）-2可得到n，下一斜行c即是
    
12.             cout<<c1<<"/"<<c-c1+1;//加1得到；用c1算出剩下
    
13.         else         //几，利用奇偶相反算。
    
14.             cout<<c-c1+1<<"/"<<c1;
    
15.     else             //利用c1正负判断是哪个
    
16.     {
    
17.         c--;
    
18.         c1=n-c*(c-1)/2;  
    
19.         if(c%2==0)
    
20.             cout<<c1<<"/"<<c-c1+1;
    
21.         else
    
22.             cout<<c-c1+1<<"/"<<c1;
    
23.     }
    
24.     return 0;
    
25. }

复制代码

吴语林

1. #include <iostream>
   
2. #include <cstdio>
   
3. #include <cstdlib>
   
4. #include <cmath>
   
5. #include <cstring>
   
6. #include <algorithm>
   
7. using namespace std;
   
8. int main()
   
9. {
   
10.         int i,n,j=1,all=0,k;
    
11.         scanf("%d",&n);
    
12.         for(i=1;;i++)
    
13.         {
    
14.                 j=i%2;
    
15.                 if(all+i<=n)
    
16.                         all+=i;
    
17.                 else
    
18.                 {
    
19.                         k=n-all;
    
20.                         if(k==0)
    
21.                                 k++,i--;
    
22.                         j++;
    
23.                         if(j==1)
    
24.                         {
    
25.                                 printf("%d/%d",k,i+1-k);
    
26.                         }
    
27.                         else
    
28.                         {
    
29.                                 printf("%d/%d",i+1-k,k);
    
30.                         }
    
31.                         return 0;
    
32.                 }
    
33.         }
    
34.     return 0;
    
35. }

复制代码