PTA - 黑洞数（陷阱数、数字黑洞、Kaprekar问题）
最近当C程助教，把学生要做的题先刷了一遍，大部分题没有难度，但有几道还是挺有意思的。比如下边这道：
黑洞数也称为陷阱数，又称“Kaprekar问题”，是一类具有奇特转换特性的数。
任何一个各位数字不全相同的三位数，经有限次“重排求差”操作，总会得到495。最后所得的495即为三位黑洞数。所谓“重排求差”操作即组成该数的数字重排后的最大数减去重排后的最小数。（6174为四位黑洞数。）
例如，对三位数207：
- 第1次重排求差得：720 - 27 ＝ 693；
- 第2次重排求差得：963 - 369 ＝ 594；
- 第3次重排求差得：954 - 459 ＝ 495；
以后会停留在495这一黑洞数。任意输入一个三位数，编程给出重排求差的过程。
输入格式：
输入在一行中给出一个三位数。
输出格式：
按照以下格式输出重排求差的过程： 序号: 数字重排后的最大数 - 重排后的最小数 = 差值
输入样例：
123
输出样例：
1: 321 - 123 = 198
2: 981 - 189 = 792
3: 972 - 279 = 693
4: 963 - 369 = 594
5: 954 - 459 = 495第一反应是这题给刚学C的学生做有点难了吧= =。仔细一看只需要管三位数的情况，那就简单多了，甚至用a，b，c记录三位数的三位，然后不断计算就行了，本着学习的精神我还是写了一个计算任意数的。
黑洞数的计算过程就是用一个数n的最大最小排序相减，得到新的n，再重复之前的过程，直到n连续出现。
比如说 954 - 459 = 495，7641 - 1467 = 6174。两位数的时候，结果就是0，五位数之后会说到。（最后有图有真相）
对于最大最小排列，我是将数字转成 vector<int>，sort 之后再转回来实现的；对于连续出现，我是用 stack 实现的。
#include <iostream>
#include <vector>
#include <functional> // std::greater, std::less
#include <algorithm> // std::sort
#include <stack>
using namespace std;
int sortnumber(int n, const int& way) // 1: 最大，-1: 最小
{
vector<int> digit; // 记录 n 各个位上的数字
while (n != 0) {
digit.push_back(n % 10);
n /= 10;
}
if (way == 1) sort(digit.begin(), digit.end(), greater<int>());
else sort(digit.begin(), digit.end(), less<int>());
int l = pow(10, digit.size() - 1), res = 0;
for (int d : digit) {
res += d * l;
l /= 10;
}
return res;
}
int main()
{
int n;
while (cin >> n) {
int maxp = sortnumber(n, 1), minp = sortnumber(n, -1);
printf("min permutation: %d\n", minp);
printf("max permutation: %d\n", maxp);
stack<int> st;
for (int cnt = 1;; cnt++) {
int diff = maxp - minp;
if (!st.empty() && st.top() == diff) { // 连续出现！
maxp = sortnumber(diff, 1);
minp = sortnumber(diff, -1);
printf("%d : %d - %d = %d\n", cnt, maxp, minp, maxp - minp);
printf("黑洞数: %d\n", diff);
break;
}
else
st.push(diff);
printf("%d : %d - %d = %d\n", cnt, maxp, minp, diff);
maxp = sortnumber(diff, 1);
minp = sortnumber(diff, -1);
}
printf("\n");
}
return 0;
}
结果也是很有意思，两位数得到的结果是0，三位数是495，四位数是6174，而五位数是一个循环 [82962, 75933, 63954, 61974] （成为数字黑洞），六位也是循环 [840852, 860832, 862632, 642654, 420876, 851742]，以此类推。