GESP 题解库 / 2 级题解 / [GESP202309 二级] 数字黑洞 · 第 22 / 30 题
✏️ GESP 202309 二级 · B3866

数字黑洞

给定一个三位数,要求各位不能相同。例如,352 是符合要求的,112 是不符合要求的。将这个三位数的三个数字重新排列,得到的最大的数,减去得到的最小的数,形成一个新的三位数。对这个新的三位数可以重复上述过程。神奇的是,最终一定会得到 495! 试试看,重新排列 352,得到的最大数为 532,最小数为 235,它们的差是 297;变换 297,得到 972-27

📊
3位数
data
🔢
string
type
⚡
O(1)
time
🎯
简单
level
01
题目是啥?
先读题,再动笔 ~

📝 题目大意

给定一个三位数,要求各位不能相同。例如,352 是符合要求的,112 是不符合要求的。将这个三位数的三个数字重新排列,得到的最大的数,减去得到的最小的数,形成一个新的三位数。对这个新的三位数可以重复上述过程。神奇的是,最终一定会得到 495!

试试看,重新排列 352,得到的最大数为 532,最小数为 235,它们的差是 297;变换 297,得到 972-279=693;变换 693,963-369=594;变换 594,954-459=495。因此,经过 4 次变换得到了 495。

现在,输入的三位数,你能通过编程得出,这个三位数经过多少次变换能够得到 495 吗?

💡
人话翻译:仔细阅读题目描述,理解输入输出要求,注意数据范围和特殊条件。

📋 样例来看一看

请参考题目描述中的样例

02
数字黑洞
卡普雷卡尔常数

🕳️ 数字黑洞 495

给定三位数(各位不同),排序得到最大数和最小数,相减得到新数,重复直到得到 495。

💡
规律:任意三位数(各位不同)经过有限步必然到达 495。
03
核心思路
分步演示

🎯 解题思路

读入三位数

各位不能相同。

排序

将三位数排序。

求差

最大数 - 最小数。

重复

直到得到 495。

04
动手算一算
自己输入数据试试看

🧪 自由实验台

分析结果会显示在这里

点"算一下"按钮开始 →

05
算法三步走
思路理清楚

🧠 核心思路

1

读入三位数

各位不能相同。

2

排序

将三位数排序。

3

求差

最大数 - 最小数。

4

重复

直到得到 495。

06
完整代码
抄作业时间 ✏️

💻 C++ 完整解法

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    string n; cin >> n;
    int step = 0;
    while (n != "495") {
        int d[3] = {n[0]-48, n[1]-48, n[2]-48};
        sort(d, d+3);
        int mn = d[0]*100+d[1]*10+d[2];
        int mx = d[2]*100+d[1]*10+d[0];
        int diff = mx - mn;
        n = string(3-to_string(diff).length(),'0') + to_string(diff);
        step++;
    }
    cout << step << endl;
    return 0;
}
⚡
注意:仔细检查输入输出格式,确保数据类型正确,注意边界条件。

⚠️ 容易踩的坑

⚠️
数据类型:注意结果范围,选择 int 或 long long。
⚠️
输出格式:严格按照题目要求的格式输出,注意换行。
07
算一算效率
复杂度分析
时间复杂度
O(1)
空间复杂度
O(1)
数据范围
固定3位数
运算次数
<=7步

时间:根据算法结构分析时间复杂度。

空间:只使用少量变量,O(1)。

✅ 在数据范围内轻松通过!

08
拓展一下
相关知识点

🔗 常用技巧

// 嵌套循环遍历矩阵
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        // 处理 (i, j)
    }
}

// 取余判断整除
if (n % k == 0) { ... }

// 数位分离
while (n > 0) { d = n % 10; n /= 10; }

🌟 举一反三

🌟
思考题:如果把数据范围扩大到 10^9,你的解法还能通过吗?可能需要更高效的算法。