洛谷——P1014 [NOIP1999 普及组] Cantor 表-蒲公英云

洛谷——P1014 [NOIP1999 普及组] Cantor 表

P1014 [NOIP1999 普及组] Cantor 表

题目描述

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

1/11/1 , 1/21/2 , 1/31/3 , 1/41/4, 1/51/5, …

2/12/1, 2/22/2 , 2/32/3, 2/42/4, …

3/13/1 , 3/23/2, 3/33/3, …

4/14/1, 4/24/2, …

5/15/1, …

…

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

输入格式

整数NN（1 \leq N \leq 10^71≤N≤107）。

输出格式

表中的第 NN 项。

输入输出样例

输入 #1复制

输出 #1复制

1/4

c++实现：

#include<bits/stdc++.h>
using namespace std;
int n,h,k,sum=0;//第n项是第h行的第k个数，前h-1行共有sum个数
int main(){
    /*
    1/1
    1/2 2/1
    3/1 2/2 1/3
    1/4 2/3 3/2 4/1
    5/1 4/2 3/3 2/4 1/5  
    第n行有n个数
    分子+分母=n+1
    分母=n+1-分母
偶数的时候 分子 递增
奇数的时候 分子 递减
若n=13
1+2+3+4  = 10        3
则第n项是第5行的第3个数
*/
cin>>n;
//求出第n项是第几行的第几个数
for(int i=1;;i++){
    sum+=i;   //第几行 就有几个数
    if(n<=sum) {  //当第n项小于等于sum的时候
        h=i;  //这时  令行数  h=i
        sum-=i;  //要数前i共有多少个数，即前h-1行共有sum个数
        k=n-sum;//这时  第h行的第k个数=h(前i行的所有个数)-sum（前h-1行共有sum个数）
        break;
    }
}
//奇 偶 判断
if(h%2==0){
    //第n行有n个数
    //分子+分母=n+1
    //分母=n+1-分母
    cout<<k<<'/'<<(h+1-k);
    //分母=h( 第n行有n个数)+1-k(分子)
}else{
    cout<<(h+1-k)<<'/'<<k;
}
return 0;
}