算法题——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 <=10^7)

输出格式

表中的第N项

样例

输入:

1
7

输出:

1
1/4

分析

规律

我们通过题目可知,在Cantor表中走法为Z字形

不妨将Cantor表转化为下图

Cantor

从左往右数

奇数行分母依次递增,分子依次递减

偶数行分母依次递减,分子依次递增

可知奇偶数行分子分母规律正好相反

所以为使奇偶数行变化规律一致并且符合题中所给的项数规律,我们可以规定

在上图中,奇数行从左往右数,偶数行从右往左数

找查

例如我们要找查第7项,前三行一共有6项,前4行一共有10项

很显然 6 < 7 < 10

所以我们可以很方便地确定第7项在第4行

前几行项数 - 所要找的项数 = 所要找的项所在行的最后一项分子 - 所找项分子

同理

前几行项数 - 所要找的项数 = 所找项分母 - 所找项所在行最后一项分母

这两个等式中我们分别知道任意三个量就可以求其中的第四个量

然后,我们继续根据规律确定第7项的具体的值为 1/4

最后,我们可以轻易得出求任意项的算法如下

解法

以下是笔者的解题方法

先上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
using namespace std;

int main()
{
int n = 0, sum = 0, i = 1;
cin >> n;

while(sum < n)
{
++i; //这里一定要让i先自增再求和,否则求出来的和少一项(此处的项指的是等差数列的项)
sum = i*(i - 1)/2; //首项公差均为1的等差数列求和,此处的和为第i行为止的Cantor表的总项数
}

//总项数与所找项的项数的差
int dif = sum - n;

if((i - 1) % 2 != 0)
//如果i-1行为奇数,那么i行为偶数行,偶数行从右开始数(这里在写的时候绕了个弯)
cout << 1 + dif << "/" << i - 1 - dif;
else
//第i行为奇数行,从左边数
cout << i - 1 -dif << "/" << 1 + dif;

}
作者

CairBin

发布于

2021-09-03

更新于

2021-09-03

许可协议

评论