华师一附中OI组

标题: P1014 Cantor表 [打印本页]
作者: admin    时间: 2018-4-27 13:19
标题: P1014 Cantor表
题目描述
现代数学的著名证明之一是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    时间: 2018-4-27 13:29
  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    时间: 2018-7-5 21:53
这一题考查意图应该是模拟，大多数人也选择用模拟做，有些人选择用二分，在下蒟蒻佩服大佬的做法。但是从数学的角度分析，其实可以一两步算出来。
  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    时间: 2018-7-8 15:27
这一题考查意图应该是模拟，大多数人也选择用模拟做，有些人选择用二分，在下蒟蒻佩服大佬的做法。但是从数学的角度分析，其实可以一两步算出来。
  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. }
复制代码
作者: 吴语林    时间: 2018-7-29 20:24
  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. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2