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

古城微笑少年丶 2023-10-02 11:02 30阅读 0赞

## 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，…

### 输入格式 ###

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

### 输出格式 ###

表中的第 N*N* 项。

### 输入输出样例 ###

**输入 \#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;
    }