Cantor数表

题目:现代数学的著名证明之一是Georg Cantor证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的: 第一项是1/1,第二项是是1/2,第三项是2/1,第四项是3/1,第五项是2/2,……。输入n,输出第n项。

    Cantor数表

  样例输入:   3   14   7   12345   

     样例输出:   2/1   2/4   1/4   59/99

  分析

  数表提示我们按照斜线分类。第1条斜线有1个数,第2条有2个数,第3条有3个数……第k条有k个数。这样,前k条斜线一共有S=1+2+3+……+k个数。

  第n项在哪条斜线上呢?只要找到一个最小的k,使得S≥n,那么第n项就是第k条斜线上倒数第S-n+1个数(最后一个元素是倒数第1个元素,而不是倒数第0个元素)。

  而k的奇偶决定着第k条斜线上数的顺序:若k是奇数,第k条斜线上倒数第i个元素是i/(k+1-i);若k是偶数,第k条斜线上倒数第i个元素是(k+1-i)/i。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; int main()
{
int n,i,k;
while(cin>>n)
{
for(i=;;i++)
{
k=i*(i+)/;
if(n<=k)
break;
}
if(i%==)
printf("%d/%d\n",i-k+n,k-n+);
else
printf("%d/%d\n",k-n+,i-k+n);
}
return ;
}
上一篇:Linux 下 -bash: mysql: command not found解决办法


下一篇:SPI总线通信电路设计