寒光博客

[LuoGu]P1014:Cantor表
题目描述 初始思路 Z字形暴力模拟(类比方形矩阵进行Z字形扫描(Zigzag Scan)),我就开始创建一个空间...
扫描右侧二维码阅读全文
18
2019/07

[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:

7

输出样例#1:

1/4

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

初始思路

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

过程模拟

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));
    }

}


一个字, 妙啊~ 妙! 哈哈哈

想成为dalao的第二天

以上是小菜鸡的分析总结,欢迎指教和交流。

本文作者:Author:     文章标题:[LuoGu]P1014:Cantor表
本文地址:https://dxoca.cn/Algorithm/41.html       百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:July 31st, 2019 at 12:16 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment