每日c/c++题 备战蓝桥杯（Cantor 表）

Cantor 表的探究与实现

在数学中，有理数的可枚举性是一个令人惊叹的结论。今天，就让我们一起深入探讨这个经典问题，并分享一段精心编写的代码，揭开这一数学奥秘的神秘面纱。

问题背景

在 19 世纪末，伟大的数学家康托尔（Georg Cantor）证明了有理数是可枚举的。他采用了一种巧妙的 Z 字形排列方式，将所有的有理数按顺序排列在一个无限表格中，从而使每个有理数都能被唯一地枚举出来。

这种排列方式的规律如下：

• 第一层只有分数 1/1。
• 第二层包含分数 1/2 和 2/1。
• 第三层包含分数 1/3、2/2 和 3/1。
• 第四层包含分数 1/4、2/3、3/2 和 4/1。
• 此类依推，每一层的分数个数递增。

这种排列方式使得每个有理数都可以被唯一地映射到一个整数，从而证实了有理数的可数性。

解题思路

面对这一问题，关键在于找到一种有效的算法，能够根据给定的整数 n，快速且准确地找到对应的有理数。以下是解决该问题的详细思路：

1. 确定层级关系

首先，我们需要确定给定的整数 n 所在的层级（即第几层）。每一层的分数个数遵循一定的规律：第 t 层的分数个数为 t。因此，第 t 层的起始位置可以通过公式 t*(t-1)/2 +1 来计算，而结束位置则是 t*(t+1)/2。

通过不断累加每一层的分数个数，直到累计值不超过 n 的最大位置，我们就能确定 n 所在的层级。例如，如果 n=7，我们发现它位于第 4 层（第 4 层的起始位置是 7，结束位置是 10）。

2. 判断奇偶性

每一层的排列方向交替变化。这使得奇数层和偶数层的分子、分母变化规律有所不同：

• 偶数层：分子从大到小递减，分母从小到大递增。
• 奇数层：分子从小到大递增，分母从大到小递减。

因此，在确定层级后，需要根据层级的奇偶性来调整分子和分母的计算方式。

3. 计算分子和分母

在确定层级 t 后，我们需要计算出该层的起始位置 s。然后，根据 n 与 s 的差值，逐步调整分子和分母的值，直到找到对应的有理数。

例如，假设我们已经确定 n=7 位于第 4 层，且第 4 层为偶数层，那么起始位置 s=7（即该层的第一个分数是 1/4）。此时，n刚好等于s，所以对应的分数就是起始分数，即 1/4。

如果 n 不等于起始位置，我们需要在该层内逐步调整分子和分母。例如，假设 n=8，那么它位于第 4 层的第二个位置。此时，分子会减 1，分母会加 1，得到分数 2/3。

代码实现

#include <bits/stdc++.h>
using namespace std;int main() {int n;cin >> n;int s = 1;int t = 1;// 确定层级while (s <= n) {t++;s = t * (t + 1) / 2;}t--;// 判断奇偶性并计算分子分母if (t % 2 == 0) {int zi = t + 1, mu = 1;s = t * (t + 1) / 2;if (s == n) {cout << t << "/1";} else {for (int i = 1;; ++i) {if (s + i == n) {cout << zi << "/" << mu;break;} else {zi--;mu++;}}}} else {int zi = 1, mu = t + 1;s = t * (t + 1) / 2;if (s == n) {cout << "1/" << t;} else {for (int i = 1;; ++i) {if (s + i == n) {cout << zi << "/" << mu;break;} else {zi++;mu--;}}}}return 0;
}

让我们详细解析一下这段代码的逻辑：

1. 输入读取和变量初始化：首先读取输入的整数 n，并初始化变量 s 和 t 用于计算层级。
2. 确定层级：通过循环不断累加每一层的分数个数，直到找到包含 n 的层级 t。
3. 判断奇偶性：根据层级 t 的奇偶性，确定该层的排列方向。
4. 计算起始位置和分子分母：计算该层的起始位置 s，并根据起始位置和 n 的差值，逐步调整分子和分母的值。
5. 输出结果：当找到对应的分数时，输出结果。

总结

通过以上探索，我们不仅理解了康托尔表的规律，还成功实现了能够根据整数 n 快速定位对应有理数的代码。这个过程中，我们体会到了数学与编程的完美结合，以及通过逻辑思考解决问题的乐趣。希望这篇博客能为你带来启发，也期待你在编程的世界中发现更多奇妙的奥秘！