【C语言程序设计】Cantor 表 11行代码

题目描述

现代数学的著名证明之一是 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, …

…

我们以斜对角线给上表的每一项编号。第一项是1/1，然后是1/2，2/1，1/3, 2/2, 3/1，1/4，2/3, 3/2, 4/1, …

输入

整数N, 0<N<20000

输出

表中的第N项

输入样例1 

7

输出样例1

1/4

输入样例2 

15

输出样例2

5/1

思路分析

看清楚题目，是斜对角线编号，走的不是Z字形，是7字形。

我们可以把它划分出层次，每一个斜对角线为一个层次，先根据编号算出层次为第几层，根据数学归纳法或者直接看出来，第X+1层前面有X(X+1)/2个数，类似于1+2+3+……的等差数列，一个循环可以算出第几层，然后通过编号的样子可以看出是二维矩阵的下标，之和为层数+1，所以最后的答案就是编号减去前几层的总数作为前项，层数+1减去编号作为后项。

高级的数学胜过一切美妙的算法。

AC代码

#include<stdio.h>
int main() {
    int index,depth=1;
    scanf("%d",&index);
    while(depth*(depth-1)/2<index)
        depth++;
    depth--;
    index-=depth*(depth-1)/2;
    printf("%d/%d",index,depth+1-index);
    return 0;
}

 字太少发不出，啊这。

 那我把代码发两次。

#include<stdio.h>
int main() {
    int index,depth=1;
    scanf("%d",&index);
    while(depth*(depth-1)/2<index)
        depth++;
    depth--;
    index-=depth*(depth-1)/2;
    printf("%d/%d",index,depth+1-index);
    return 0;
}