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)。

输出格式

表中的第 NN项。

输入输出样例

输入 #1复制

7

输出 #1复制

1/4
#include<iostream>
using namespace std;
const int N = 100010;
int main()
{
	int N;
	cin >> N;
	int lay = 0;
	for(int n = 1; n < N / 2; n ++)
	{
		if(n*(n+1)/2>=N) 
		{
			lay = n;
			break;
		}
	}
	int x = N - lay*(lay+1)/2 + lay;
	if(lay%2==0)
	{
		printf("%d/%d",x,lay-x+1);
	}
	else
	{
		printf("%d/%d",lay-x+1,x);
	}
	return 0;
}

上一篇:Java安全之Cas反序列化漏洞分析


下一篇:微服务怎么限流?算法+框架+实战!