洛谷 P1014 Cantor表 题解
程序员文章站
2022-05-13 17:18:38
...
题目描述
现代数学的著名证明之一是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
题解:
找规律:
第1层1/1
第2层1/2 2/1
第3层3/1 2/2 1/3
第4层1/4 2/3 3/2 4/1
第5层5/1 4/2 3/3 2/4 1/5
因为各层分数的分子分母之和比层数大1,
偶数层即(w)+ (h+1-w)=h+1
奇数层即(h+1-w)+ (w)=h+1
#include<stdio.h>
int main()
{
int h=1, w;
scanf("%d",&w);
while (w > h)//循环,得出层数(高度)
{
w -= h;
h++;
}
if (h % 2 == 0)//如果是偶数层,分子递增,分母递减,得出答案
{
printf("%d/%d",w,h+1-w);
}
else//如果是奇数层,分子递减,分母递增,得出答案
{
printf("%d/%d",h+1-w,w);
}
}
上一篇: 分治策略实现棋盘覆盖问题
下一篇: 棋盘覆盖-分治法(代码实现)