洛谷千题详解 | P1014 [NOIP1999 普及组] Cantor 表【C++、Java语言】

博主主页：Yu·仙笙

专栏地址：洛谷千题详解

目录

题目描述

输入格式

输出格式

输入输出样例

解析：

C++源码：

C++源码2：

C++源码3：

Java源码：

---

------------------------------------------------------------------------------------------------------------------------------- 

 ------------------------------------------------------------------------------------------------------------------------------- 

题目描述

现代数学的著名证明之一是 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≤107）。

 ------------------------------------------------------------------------------------------------------------------------------- 

输出格式

表中的第 N 项。

 ------------------------------------------------------------------------------------------------------------------------------- 

输入输出样例

输入 #1

7

输出 #1

1/4

 ------------------------------------------------------------------------------------------------------------------------------- 

解析：

 update:显然这样的程序并不是最短的，评论已经有很多的dalaodalao指出了，而且时间复杂度也并不优秀，但是当时就会有一种莫名的自信 至于怎么压行，评论区也说得比较明白了，所以评论不用再提供压行思路了

update: 首先我们观察到第ii行，第jj列的数就是i/ji/j,这是第一个要发现的。

因为题目中要求是以Z字型编号

我们看题目中的表是：

1/1,1/2,1/3 ……

2/1,2/2,2/3 ……

Z字型编号以后（把头向左偏45度）：

第一行：1/1 (1号)

第二行：1/2 (2号) 2/1(3号)

第三行：1/3 (6号) 2/2(5号) 3/1(4号)

\uparrow↑ 观察法易得每一行比上一行多1

代码里那个while循环，就是为了通过循环枚举，判断它在编号之后的第几行，第几个位置。

---

（这个优化有没有都可以AC本题，但是评论指出我的时间复杂度不够优秀，因此提一提这个优化，不愿意看的可以直接略过看下一个分割线以后的内容。）

但其实可以直接出结论优化时间复杂度从O(n)优化到O(1)，这样就要考虑到等差数列求和

公式：S=2n(an​+a1​)​

所以，很显然Z字型排序之后，第k行的数编号n满足：

 ------------------------------------------------------------------------------------------------------------------------------- 

C++源码：

#include
int main()
{
    int n;scanf("%d",&n);
    int t=1,ans=0;//t是表示下一次跳到下一次的距离，ans是表示第几层
    while(1)
    {
        if(n>t){n-=t;ans++;t++;}//printf("%d\n",ans);
        else if(n==t&&ans%2==0){printf("1/%d",ans+1);break;}
        //如果在n==t，并且为偶数层，就在第一行 第ans+1个 
        else if(n==t&&ans%2!=0){printf("%d/1",ans+1);break;}
        //如果在n==t，并且为奇数层，就在第ans+1行 第一个
        else if(n2!=0){printf("%d/%d",ans+n-t+1,t-n+1);break;}
        //如果在n
        else if(n2==0){printf("%d/%d",t-n+1,ans+n-t+1);break;}
        // 如果在n
    }
    return 0;
}

 ------------------------------------------------------------------------------------------------------------------------------- 

C++源码2：

#include
using namespace std;
int main()
{
    int i = 0, n, s = 0, x, y;//s：按整条斜线走过的格子的末尾编号 
    cin >> n;
    while(s < n)//s >= n时，说明编号为n的格子在刚才加的第i斜线之中 
    {
        i++;
        s += i;
    }
    s -= i;//此时确定n在第i条斜线上 
    if(i % 2 == 1)//从i/1出发向右上遍历，找编号为n的格子 
    {
        x = i, y = 1, s++;
        while(s < n)//s == n时，x，y的值即为编号为n的格子的坐标 
            x--, y++, s++;
    }
    else//从1/i出发向左下遍历，找编号为n的格子 
    {
        x = 1, y = i, s++;
        while(s < n)//s == n时，x，y的值即为编号为n的格子的坐标
            x++, y--, s++;
    }
    cout << x << '/' << y;
    return 0;
}

 ------------------------------------------------------------------------------------------------------------------------------- 

C++源码3：

#include
using namespace std;
int main()
{
    int i = 0, n, s = 0, x, y, l;
    cin >> n;
    while(s < n)//看第n格子是否在第i斜线上 
    {
        i++;
        s += i;
    }
    s -= i;
    l = n-s;//在第i斜线数几个 
    if(i % 2 == 1)//从i/1出发 
    {
      	x = i+1-l;//i-x+1=l
		y = l; 
    }
    else//从1/i出发 
    {
        x = l;//x-1+1 = l
        y = i+1-l;//i-y+1=l
    }
    cout << x << '/' << y;
    return 0;
}

 ------------------------------------------------------------------------------------------------------------------------------- 

Java源码：

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int position = scanner.nextInt();
        int sum, end = 1;
        while (true) {
            sum = (1 + end) * end / 2;
            if (position <= sum) break;
            ++ end;
        }
        sum -= position;
        if (end%2 == 0) { // 偶数
            // 大数在前
            System.out.println((end-sum) + "/" + (1+sum));
        } else { // 奇数
            // 大数在后
            System.out.println((1+sum) + "/" + (end-sum));
        }
    }

 -------------------------------------------------------------------------------------------------------------------------------