题目描述
现代数学的著名证明之一是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));
}
}
一个字, 妙啊~ 妙! 哈哈哈

以上是小菜鸡的分析总结,欢迎指教和交流。
本文地址: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个数。