最新消息:点击查看大S的省钱秘笈

Vijos P1333 Cantor表 C语言版

Vijos题解 Slyar 103浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

描述 Description

现代数学的著名证明之一是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,…

输入格式 Input Format

输入:整数N(1≤N≤10000000)

输出格式 Output Format

输出:表中的第N项

Tip:纯粹的数学问题,第K个斜行("/"方向)上每个分数的分子分母之和为K+1,因此先算出第N项所在的斜行K,然后看斜行是奇数项还是偶数项,进而算出具体分数值。

#include <stdio.h>

int main(){
long i=0,n;
scanf("%ld",&n);
while (i<n){
n-=i;
i++;
}
if (i%2==0) printf("%d/%d",n,i+1-n);
else printf("%d/%d",i+1-n,n);
system("pause");
return 0;
}

转载请注明:Slyar Home » Vijos P1333 Cantor表 C语言版

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (3)

  1. 才知道有这样的规律 LZ一级棒 佩服
    INCerry3年前 (2013-10-27)回复
  2. 当年看这个证明那叫一个爽 顺便贴一个实数集和自然数集不等势的证明,觉得也很经典 --------华丽分割的飘过-------- 最近,Matthew H. Baker找到了证明实数区间是不可数集的一种新方法。这种方法同原来的方法完全不同。新的证明方法从一个博弈游戏出发,在两个不同的数学领域间建立起了联系,非常具有启发性。 A和B两个人在实数区间[0,1]上玩一个游戏。首先,A在(0,1)之间选一个数a1,然后B在(a1,1)里选一个数b1;接着,A在(a1,b1)之间选一个数a2,然后B在(a2,b1)里选一个数b2……总之,以后A和B轮流取数,选的那个数必须位于前面两次选的数之间。可以看到,序列a1, a2, a3, ...是一个单增的有界序列,因此游戏无限进行下去,数列{an}最终会收敛到某一个实数c。游戏进行前,A和B约定一个[0,1]的子集S,规定如果最后c∈S,则A胜,否则B胜。 Baker发现,如果S集为可数集的话,B肯定有必胜策略。如果S集可数,那么B就可以把S集里的数排列成一个序列s1, s2, s3, ... 。B的目标就是让序列{an}的极限不等于S集里的任一个数。考虑B的这样一个游戏策略:当B第i次选数时,如果选si合法,那么就选它(这样序列{an}就不能收敛到它了);否则如果这一步选si不合法,那就随便选一个合法的数(此时序列{an}已经不可能收敛到si了)。这种策略就可以保证A选出的数列的极限不是S集里的任一个数。 有趣的事情来了。假如A和B约定好的S集就是整个实数区间[0,1],那么B显然不可能获胜;但如果[0,1]是可数集的话,B是有必胜策略的。于是我们就知道了,[0,1]是不可数集。 原版地址:https://blog.sciencenews.org/view/generic/id/9269/title/Math_Trek__Small_Infinity,_Big_Infinity 翻译的人不知道的说~~~
    wOOL8年前 (2009-02-01)回复
  3. 生是做网站的人。死是做网站的鬼。我的网站什么时候才有你网站的那么成功啊。羡慕中~~~
    菜菜熊8年前 (2008-11-06)回复