P1014 [NOIP 1999 普及组] Cantor 表 c++题解

题目链接

题目描述

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

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

输入格式

整数$N$（$1\le N\le 10^7$）。

输出格式

表中的第 $N$ 项。

输入输出样例 #1

输入 #1

7

输出 #1

1/4

说明/提示

• 2024-11-18 0:30 数据中加入了样例，放在不计分的子任务 2 中。

1.题目内容

Cantor 表以 Z 字形方式枚举有理数，起始点为 1/1，后续项依次为 1/2、2/1、3/1、2/2 等。输入一个整数N，输出表中第 N 项的分式形式。例如，输入 7，输出应为 1/4。

---

2.难度

普及−

---

3.题目所需知识点

• 模拟
• 枚举

（1999 NOIP 普及组）

---

4. 思路

焦点移动法（分组模拟）

核心思想 ‌确定斜行 k k‌：与前法相同（通过累加 s+=k直到 s≥N）

‌从焦点出发模拟移动‌：
k ‌奇数‌：起点 (k,1)，向左上移动 d−1 次（每次 x−1,y+1) k ‌偶数‌：起点(1,k)，向右下移动 d−1 次（每次 x+1,y−1)

---

5.复杂度分析

• 确定斜行k‌ 通过累加s += k直到s ≥ N来确定目标数所在的斜行k。该过程最多需执行√(2N)次循环，时间复杂度为O(√N)（因k的累加和s = k(k+1)/2 ≈N时，k与√N同阶）。

• 焦点移动模拟‌ 确定斜行k后，需移动d = N - (k-1)k/2 - 1次。每次移动为常数时间操作（坐标增减），因此移动阶段的时间复杂度为O(1)。

总时间复杂度‌

由上述两步组成，主要耗时在斜行k的确定阶段，因此整体复杂度为O(√N)。该效率优于暴力遍历法（O(N)），但弱于直接公式法（O(1)）。

‌关键点说明‌

斜行k的求解利用了等差数列求和公式的逆推，避免了全表遍历。
焦点移动次数d的计算通过数学推导直接定位，无需逐次模拟。

---

6.代码片段分析

• 变量、数据结构定义

#include<bits/stdc++.h>
using namespace std;
int n, i=1, k;
int x, y;
//n 输入的目标编号，表示需要查询Cantor表中的第n项
//i 初始值为1，用于循环累加确定目标数所在的斜行（层数）。循环终止时，i即为斜行号
//k‌ 计算目标数在斜行内的偏移量，k=n-1将编号转换为从0开始的索引，便于坐标计算
//x 与 y 最终输出的分数分子和分母

• 斜行定位循环‌
  （用于在Cantor表中确定目标数n所在的斜行（对角线分组））

	while(i<=n){
		n-=i;//将n减去当前斜行包含的数字个数（第i斜行有i个数）
		i++;//斜行号递增，直到n不足以填满下一斜行	
	}

• 斜行奇偶性

if(i%2==0){ // 偶数行
		x=1+k;
		y=i-k;
	}
	else{ // 奇数行
		x=i-k;
		y=1+k;
	}
//	斜行奇偶性决定移动方向：
//	偶数斜行（i%2==0）：从(1,i)向右下移动，坐标公式为x=1+k, y=i-k
//	奇数斜行：从(i,1)向左上移动，坐标公式为x=i-k, y=1+k
//	k=n-1将偏移量转换为移动次数（因编号从1开始）

• 输出

cout<<x<<"/"<<y<<endl;

---

7.AC代码

#include<bits/stdc++.h>
using namespace std;
int n, i=1, k;
int x, y;
//n 输入的目标编号，表示需要查询Cantor表中的第n项
//i 初始值为1，用于循环累加确定目标数所在的斜行（层数）。循环终止时，i即为斜行号
//k‌ 计算目标数在斜行内的偏移量，k=n-1将编号转换为从0开始的索引，便于坐标计算
//x 与 y 最终输出的分数分子和分母
int main(){
	cin>>n;
	
	while(i<=n){
		n-=i;//将n减去当前斜行包含的数字个数（第i斜行有i个数）
		i++;//斜行号递增，直到n不足以填满下一斜行	
	}
	k=n-1;//将斜行内的偏移量转换为0-based索引‌，便于后续坐标计算。
	if(i%2==0){ // 偶数行
		x=1+k;
		y=i-k;
	}
	else{ // 奇数行
		x=i-k;
		y=1+k;
	}
//	斜行奇偶性决定移动方向：
//	偶数斜行（i%2==0）：从(1,i)向右下移动，坐标公式为x=1+k, y=i-k
//	奇数斜行：从(i,1)向左上移动，坐标公式为x=i-k, y=1+k
//	k=n-1将偏移量转换为移动次数（因编号从1开始）
	
	cout<<x<<"/"<<y<<endl;
	return 0;
}

---

附 更多的测试样例

---

8.推荐题目

P1003 [NOIP 2011 提高组] 铺地毯
P1022 [NOIP 2000 普及组] 计算器的改良

---

如果对你理解有帮助，就点个赞再走吧，有问题欢迎随时在评论区指出