[LuoGu]P1014:Cantor表

题目描述

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：

输出样例#1：

1/4

题目地址：https://www.luogu.org/problemnew/show/P1014

初始思路

Z字形暴力模拟（类比方形矩阵进行Z字形扫描(Zigzag Scan)），我就开始创建一个空间为10000000的二维数组也就是1000*10000,然后从左上角开始模拟走Z字形并在每走过的位置从1开始计数，并赋值便可以直接得到你所要的第几个asn.
而ans的实际结果和其个数的数组索引有关，'/'前的是行索引+1,'/'后的是列所以+1!

Zigzag Scan:
https://github.com/Dxoca/Algorithms/blob/master/src/BlueCup/_403_ZPrintArr.java

过程模拟

Z字模拟路线——用平板画的

模拟斜坡过程：
-斜向上向下，用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));
    }

}

一个字，妙啊~ 妙！哈哈哈