P1014Cantor表（找规律）

传送门

题目描述

现代数学的著名证明之一是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

分析

• 看到这道题的时候没想那么多，直接模拟$O(n)$的时间复杂度就过了。看了dalao们的八仙过海各显神通的题解，觉得自己还是孤陋寡闻了。除了直接模拟外，还有两种值的学习的方法。

枚举每一条斜线，找到所求的项所在的斜线，然后，时间复杂度为$O(\sqrt{n})$。
斜线上的项可以用如下三角形表示（当然，需要偶数行需要逆序）
1
2 3
4 5 6
7 8 9 10
可以看出，每行有第$i$行有$i$项，而且每行中第$k$个元素一定小于或等于行数$i$，于是我们就可以对各行进行枚举了。

二分法：经过观察可以知道，第i条斜线上每项分子和分母的值和都为i+1，其中包含$[\frac{i\ast (i-1)}{2}+1，\frac{(1+i)\ast i}{2}]$这个区间中所有的项，用二分的方法就可以快速找到所求项所在的直线了。
区间的推导：
通过上面那个三角形可以看出，第$i$层包含$i$项，如果要求$i$层中共有多少项，可以问题可以转化为等差数列前$i$项和，公式为$\frac{(1+i)\ast i}{2}$。根据这个公式我们可以知道，第$i$的第1项为前$i-1$层的项数和加1，第$i$的第$i$项为前$i$层的项数和。
求该项是该层的第几项：
设层数为$i$，该项是该层的第$a$项，可得
$$a=n-\frac{i\ast (i-1)}{2}$$

代码如下

直接模拟。

import java.io.BufferedInputStream; import java.util.*; public class Main {static int n,x=1,y=1;public static void main(String[] args) {Scanner cin=new Scanner(new BufferedInputStream(System.in));n=cin.nextInt();for(int i=1;i<n;) {if(i<n) {x++;i++;}while(x-1>0 && i<n) {x--;y++;i++;}if(i<n) {y++;i++;}while(y-1>0 && i<n) {x++;y--;i++;}}System.out.println(y+"/"+x);cin.close();} }

枚举斜线

import java.io.BufferedInputStream; import java.util.*; public class Main {static int n,i=1;public static void main(String[] args) {Scanner cin=new Scanner(new BufferedInputStream(System.in));n=cin.nextInt();while(i<n) {n=n-i;//n indicate n element in rowi++;//i indicate number of plies}if(i%2==0)System.out.println(n+"/"+(i-n+1));else System.out.println((i-n+1)+"/"+n);cin.close();} }

二分法找斜线

import java.io.BufferedInputStream; import java.util.*; public class Main {static int n,r,l,mid,a;// r, l, mid all indicate number of pliespublic static void main(String[] args) {Scanner cin=new Scanner(new BufferedInputStream(System.in));n=cin.nextInt();l=1;r=n;while(l<r) {mid=(r+l)/2;if(((mid+1)*mid)/2<n) l=mid+1;else r=mid;}a=n-(l*(l-1))/2; //why l indicate the target layerif(l%2==0)System.out.println(a+"/"+(l+1-a));else System.out.println((l+1-a)+"/"+a);cin.close();} }

总结

以上是生活随笔为你收集整理的P1014Cantor表（找规律）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。