avatar

P1014 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\leqslant N \leqslant 10^7) $。

输出格式

表中的第$ N $项。

输入输出样例

输入7

输出1/4


这道题可以用规律做

第一行 1/1
第二行 1/2, 2/1
第三行 3/1, 2/2, 1/3
第四行 1/4, 2/3, 3/2, 4/1
第五行 5/1, 4/2, 3/3, 2/4, 1/5

我们可以看出:

  • 奇数行:分子由“行数”递减至1,分母由1递增至“行数”。
  • 偶数行:分子由1递增到“行数”,分母由“行数”递减至1。

所以现在需要的是找出N所在第几行和第几列

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

int main()
{
int h = 1, w;
// h行,w列
cin >> w;
while (w > h)
{
w -= h;
h++;
}
//cout << h << " " << w << endl;
if (h % 2 == 0)
{
cout << w << "/" << h - w + 1 << endl;
}
else
{
cout << h - w + 1 << "/" << w << endl;
}
return 0;
}
文章作者: 安河桥北以北
文章链接: http://chenai007.github.io/2020/07/10/%E6%B4%9B%E8%B0%B7/Cantor%E8%A1%A8/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Ash's blog

评论