Cantor表-（模拟）

链接：https://ac.nowcoder.com/acm/contest/1069/I
来源：牛客网

题目描述

现代数学的著名证明之一是Georg Cantor证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的：

我们以Z字形给上表的每一项编号。第一项是1/1，然后是1/2，2/1，3/1，2/2，…

输入描述:

整数N（1≤N≤10000000）

输出描述:

表中的第N项

示例1

输入

复制

输出

复制

1/4

题解：斜着看，每一斜逐渐增加1个数，奇数斜从下往上，偶数斜从上往下，暴力求包括到第几斜，从新的一斜开始。分奇数偶数情况讨论。

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<math.h>

#include<string>

#include<map>

#include<queue>

#include<stack>

#include<set>

#define ll long long

#define inf 0x3f3f3f3f

using namespace std;

int a[];

int main()

{

    memset(a,,sizeof(a));

    for(int i=;i<=;i++)

        a[i]=a[i-]+i;

    int n;

    scanf("%d",&n);

    int l,cha;///第几斜前是铺满的，新的一斜有几个数

    for(int i=;i<=;i++)

    {

        if(a[i]<=n && n<=a[i+])

        {

            l=i;

            cha=n-a[i];

            break;

        }

    }

    int x,y;

    if(l%)///第奇数斜，轮到第偶数斜，右上→左下

    {

        if(cha==)

            x=,y=l;

        else

        {

            x=;

            y=l+;

            cha--;

            while(cha--)

            {

                x++;

                y--;

            }

        }

    }

    else

    {

        if(cha==)

            x=l,y=;

        else

        {

            x=l+;

            y=;

            cha--;

            while(cha--)

            {

                x--;

                y++;

            }

        }

    }

    printf("%d/%d\n",x,y);

    return ;

}

c++版本

水题，拿来练习matlab。

a(1)=1;

for i=2:1:10000

    a(i)=a(i-1)+i;

end

n=input('');

l=0;

cha=0;

x=0;

y=0;

for i=1:1:10000

    if a(i)<=n && n<=a(i+1)

        l=i;

        cha=n-a(i);

        break;

    end

end

if mod(l,2)==1 %matlab求模

    if cha==0

        x=1;

        y=l;

    else

        x=1;

        y=1+l;

        cha=cha-1;

        while cha>0

            x=x+1;

            y=y-1;

            cha=cha-1;

        end

    end

else

    if cha==0

        x=l;

        y=1;

    else

        x=l+1;

        y=1;

        cha=cha-1;

        while cha>0

            x=x-1;

            y=y+1;

            cha=cha-1;

        end

    end

end

fprintf('%d/%d\n',x,y);

巴特西

Cantor表-（模拟）

题目描述

输入描述:

输出描述:

输入

输出

最新文章

热门文章