康托表(cantor)

Posted on Updated on

题目描述

康托是一名数学家，他证明了一个重要的定理，需要使用一张表：
1/1 2/1 3/1 4/1 5/1 ⋯
1/2 2/2 3/2 4/2 5/2 ⋯
1/3 2/3 3/3 4/3 5/3 ⋯
1/4 2/4 3/4 4/4 5/4 ⋯
1/5 2/5 3/5 4/5 5/5 ⋯
⋯ ⋯ ⋯ ⋯ ⋯ ⋯
这个表的规律是：
从上到下：每一行的分子依次增大；
从左到右：每一列的分母依次增大。
康托以一种不重复、不遗漏的方式，将表上所有数字列举了出来。方法如下：从左上角的 1/1出发， Z 字形扫描，其中：
第一项是 1/1；
第二项是 1/2、第三项是 2/1
第四项是 3/1，第五项是 2/2，第六项是 1/3
接下来几项分别是：
1/4, 2/3, 3/2, 4/1, 5/1, 4/2, ⋯
题目描述：
给定一个分数 a/b，请计算该分数在康托表中排名第几。
输入格式：(cantor.in)
两个整数：a与 b，表示一个分数 a/b。
输出格式：(cantor.out)
单个数字：表示输入分数在康托表中的名次。
输入输出样例
输入样例#1：
2 4
蚌埠二中信息学素养营
8
输出样例#1：
14
输入样例#2：
1 4
输出样例#2：
7
数据范围：
对于 50%的分数，1≤a,b≤100；
对于 100%的分数，1≤a,b≤10000。

分析问题

首先，我们需要理解康托表的排列规律。康托表是一个无限的分数表格，按照特定的“Z”字形顺序排列。具体排列顺序如下：

  1. 第一项：1/1
  2. 第二项：1/2，第三项：2/1
  3. 第四项：3/1，第五项：2/2，第六项：1/3
  4. 第七项：1/4，第八项：2/3，第九项：3/2，第十项：4/1
  5. 第十一项：5/1，第十二项：4/2，第十三项：3/3，第十四项：2/4，第十五项：1/5
  6. …

从上面的排列可以看出，康托表的排列是按照“对角线”方向进行的。每条对角线上分数的分子和分母之和是固定的。例如：

  • 第一条对角线（和为2）：1/1
  • 第二条对角线（和为3）：1/2, 2/1
  • 第三条对角线（和为4）：3/1, 2/2, 1/3
  • 第四条对角线（和为5）：1/4, 2/3, 3/2, 4/1
  • …

仔细观察，我们还发现，在对角线上，每组分数的分子加分母的和是相等的。

建立模型

为了找到分数 a/b 在康托表中的位置，可以按照以下步骤进行：

  1. 确定对角线的和：分数 a/b 所在的对角线的和是 s = a + b。
  2. 计算前面所有对角线的项数总和：在 s 对角线之前的所有对角线的项数总和是 1 + 2 + 3 + ... + (s - 1)。这是一个等差数列的和，可以用公式 (s - 1) * s / 2 计算。

以上的结果由等差数列公式推出，公式为：Sn = n * (a1+an)/2

代入数值得： Sn = ( s-1）* (1+s-1)/2 = s* (s-1) /2

当然，我们使用也可以使用编程的方法。本案例我们使用循环累加的编程方法得出。

  1. 确定当前对角线上的位置：
  • 如果 s 是奇数，当前对角线的排列是从下到上，即分母从1开始增加。
  • 如果 s 是偶数，当前对角线的排列是从上到下，即分子从1开始增加。
  • 根据 a 或 b 的值，可以计算出当前对角线上的位置。

编写代码

以下是基于上述思路的C++代码：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b;//a 是分子  b 是分母 
    cin >> a >> b;
    int s = a + b; // 对角线的和
    int rank = 0; // 前面各项和 
    // 计算前面所有对角线的项数总和
    for (int i = 1; i < s-1; i++) {
        rank += i;  //1+2+3+…… 
    }
    // 确定当前对角线上的位置
    if (s % 2 == 1) { //分子与分母和为奇数，分子从下到上从1递增，所以累加分子 
        rank += a;
    } else { //分子与分母和为偶数，分母从上到下从1递增，所以累加分母 
        rank += b;
    }
    cout << rank << endl;
    return 0;
}

代码解释

  1. 输入：读取分数 a 和 b。
  2. 计算对角线和：s = a + b。
  3. 计算前面对角线的项数总和：使用循环累加 1 到 s - 1 的和。
  4. 确定当前对角线的位置：
  • 如果 s 是奇数，当前对角线的排列是从下到上，所以位置是 b。
  • 如果 s 是偶数，当前对角线的排列是从上到下，所以位置是 a。
  1. 输出结果：将前面对角线的项数总和加上当前对角线的位置，得到最终的排名。

示例

以输入 3/2 为例：

  1. 对角线和 s = 3 + 2 = 5。
  2. 前面对角线的项数总和：1 + 2 + 3 = 6。
  3. s 是奇数，从下到上排列，位置是 b = 2。（这是因为分子从1开始数，所以选择分子）
  4. 最终排名：6 + 2 = 8。

输出结果为 8，与康托表的排列一致。