Cantor表（刷题）（C语言）

用户11039529

发布于 2024-03-25 15:24:04

530

发布于 2024-03-25 15:24:04

文章被收录于专栏：算法学习日常算法学习日常

个人博客主页：https://blog.csdn.net/2301_79293429?type=blog 专栏：https://blog.csdn.net/2301_79293429/category_12545690.html

题目描述

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

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

输入格式

整数N（1≤N≤10^7）。

输出格式

表中的第 N 项。

输入输出样例

输入

输出

1/4

题目链接: 记录详情 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目分析:

将题目中的图像写为易观察的形式:

/* 1/1

1/2 2/1

3/1 2/2 1/3

设最上面一行为第1行，本题用i表示，

第i行的分子分母之和为i+1，除了第一行，偶数行的分子从1开始，奇数行从i开始

AC代码:

int main()
{
    int n;
    scanf("%d", &n);
    if (n == 1)
        printf("1/1");
    else
    {
        int i = 0, j = 1, sum = 0;
        for (i = 1;; i++)
        {
            sum += j++;
            if (sum >= n)
                break;
        }

        sum -= i;/*前面几行的总个数*/
        if (i % 2 == 1)/*奇数行*/
        {
            j = 0;
            if (sum == n - 1)
                printf("%d/%d", i, 1);
            else
            {
                int h = i - (n - sum) + 1;/*分子*/
                i = n - sum;/*分母*/
                printf("%d/%d", h, i);
            }
        }
        else
        {
            j = 0;
            if (sum == n - 1)
                printf("%d/%d", 1, i);
            else
            {
                int h = i - (n - sum) + 1;/*分母*/
                i = n - sum;/*分子*/
                printf("%d/%d", i, h);
            }
        }
    }
    return 0;
}

祝大家题题AC啦,天天只想做个WA梦~

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-01-26，如有侵权请联系 cloudcommunity@tencent.com 删除

教育