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所在第几行和第几列

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