刷题路-Cantor 表

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

输出格式

表中的第 N 项。

输入输出样例

输入 #1

7

输出 #1

1/4

#include <stdio.h>
int molecule;//分子
int denominator;//分母
void solve1(int n)//求解分子
{
    int base=2,i,cnt=0,flag=0;//第一个循环中最大为2while(!flag){
    for(i=1;i<=base;i++){
    cnt++;if(cnt==n)//遍历到正确位置{
    flag=1;molecule=i;break;}}if(flag)return;for(i-=2;i>=1;i--)//上一个for循环中最后多自加了一次，这里要减2{
    cnt++;if(cnt==n){
    flag=1;molecule=i;break;}}base+=2;}return;
}
void solve2(int n)//求解分母
{
    int base=1,i,cnt=0,flag=0;//第一个循环中最大为1while(!flag){
    for(i=1;i<=base;i++){
    cnt++;if(cnt==n){
    flag=1;denominator=i;break;}}if(flag)return;for(i-=2;i>=1;i--){
    cnt++;if(cnt==n){
    flag=1;denominator=i;break;}}base+=2;}return;
}
int main()
{
    int n;scanf("%d",&n);solve1(n);//求解分子solve2(n);//求解分母printf("%d/%d",denominator,molecule);return 0;
}