题目描述
Cantor表
现代数学的著名证明之一是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≤10000000）输出格式：
表中的第N项输入输出样例
输入样例#1：
7输出样例#1：
1/4初始思路
Z字形暴力模拟（类比方形矩阵进行Z字形扫描(Zigzag Scan)），我就开始创建一个空间为10000000的二维数组也就是1000*10000,然后从左上角开始模拟走Z字形并在每走过的位置从1开始计数，并赋值便可以直接得到你所要的第几个asn.
而ans的实际结果和其个数的数组索引有关，'/'前的是行索引+1,'/'后的是列所以+1!
过程模拟
- 模拟斜坡过程：
-斜向上向下，用bool 值lor来切换上下坡 初始化为向上。在坡上非上即下 - 模拟的四个点：
- 向上时右走(红)：是第一行 且 不是 最后一行 即
r == 0 && c < n - 1 - 向上时下走(红)：不是第一行 且 是最后一列
r > 0 && c == n - 1切换方向 - 向下时下走(蓝)：是第一列 且 不是 最后一行 即
c == 0 && r < m - 1 - 向下时右走(蓝):是最后一行
r == m - 1切换方向
- 向上时右走(红)：是第一行 且 不是 最后一行 即
模拟代码
暴力模拟代码
package LuoGu;
import java.util.Scanner;
/**
* 代码 Java 8，1.96KB
* 提交时间 2019-07-06 17:09:46
* 耗时/内存 547ms, 21760KB
*/
//P1014 Cantor表
public class P1014 {
public static void main(String[] args) {
int X = 1000;//1000*1000=1000000 //X其实 应该再乘 10
int[][] arr = new int[X][X];
Scanner cin = new Scanner(System.in);
int N = cin.nextInt();
int t1 = 0, t2 = 0;
///Z字形模拟.....
int r = 0, c = 0;//行列
int m = arr.length, n = arr[0].length;//最大行列
boolean lor = true;//上或者下的斜线
int count = 1;
while (count <= X * X) {
if (lor) {//上坡
arr[r][c] = count++;
// 上坡 第一行列未到边界，只能向右走
if (r == 0 && c < n - 1) {
lor = !lor;//方向切换
c++;
} else if (r > 0 && c == n - 1) {//上坡 最后一列向下走
lor = !lor;
r++;
} else {//上坡 行减 列增
r--;
c++;
}
} else {//走下坡
arr[r][c] = count++;
if (c == 0 && r < m - 1) {// 下坡 到第一列 只能往下走 切 不是最后一行
lor = !lor;
r++;
} else if (r == m - 1) {//最后一行 只能往右
lor = !lor;
c++;
} else {//行增 列减
r++;
c--;
}
}
}
//out put ans
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[0].length; j++) {
if (N == arr[i][j]) {
t1 = i + 1;
t2 = j + 1;
break;
}
}
}
System.out.println(t1 + "/" + t2);
}
}
数学规律
上面方法应该是最死的了吧，不过对Z字形扫描有了一定的熟悉程度
通过洛谷解题区dalao的指点，当我们把表向右转45°，通过其数学规律 便可很简单明辽的解决这道题
数学规律代码
package LuoGu;
import java.util.Scanner;
public class P_1014_new {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int cs = 0, tot = 0;//cs记录层数，tot记录到这一层总共有多少数
while (tot < n) {
cs++;//行数
tot += cs;
}
if (cs % 2 == 1)//当是奇数行时
//个数-层数+1 / 行数-（个数-目标数字）
System.out.println((tot - n + 1) + "/" + (cs - (tot - n)));
else
System.out.println((cs - (tot - n)) + "/" + (tot - n + 1));
}
}
一个字， 妙啊~ 妙！ 哈哈哈
以上是小菜鸡的分析总结，欢迎指教和交流。
本文作者：Author： 寒光博客
文章标题：[LuoGu]P1014:Cantor表
本文地址：https://dxoca.cn/Algorithm/41.html 百度未收录
版权说明：若无注明，本文皆为“Dxoca's blog （寒光博客）”原创，转载请保留文章出处。
本文地址：https://dxoca.cn/Algorithm/41.html 百度未收录
版权说明：若无注明，本文皆为“Dxoca's blog （寒光博客）”原创，转载请保留文章出处。
关于那个while循环应该可以去掉的吧，
因为第i层一共有i个数，所以N=1+2+...+a+b，当b=0时，N对应的数在a=round(sqrt(2N+1/4)-1/2)层中，当b in [1, a+1)中时，N对应的数在a+1=floor(sqrt(2N+1/4)+1/2)层中，b正好代表了N在该层的第b个数。