当前位置：首页 > ds >正文

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

ds 2025/8/23 13:35:53

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;
}