# PAT 解题报告 1069. The Black Hole of Numbers (20)

### 1069. The Black Hole of Numbers题目描述：

For any 4-digit integer except the ones with all the digits being the same, if we sort the digits in non-increasing order first, and then in non-decreasing order, a new number can be obtained by taking the second number from the first one. Repeat in this manner we will soon end up at the number 6174 — the “black hole” of 4-digit numbers. This number is named Kaprekar Constant.

For example, start from 6767, we’ll get:

7766 – 6677 = 1089
9810 – 0189 = 9621
9621 – 1269 = 8352
8532 – 2358 = 6174
7641 – 1467 = 6174
… …

Given any 4-digit number, you are supposed to illustrate the way it gets into the black hole.

6174被称为黑洞四位数. 也就是任意一个四位数(每个数字都不相同), 把这个四位数按照每个数字的升序和降序排列得到两个数字(一定一个大另一个小, 因为每个数字不一样), 然后做减法, 得到的结果继续重复这个过程, 最后一定能得到6174, 而且到了这里的会, 结果就一直会是6174. 因为结果一直是6174也就是永远逃不出这个数字了, 因此叫他黑洞数字一点也没错.

### 1069. The Black Hole of Numbers算法分析：

```#include <cstdio>
#include <vector>
#include <functional>
#include <algorithm>

const int hole = 6174;
const int ndigits = 4;

std::vector<int> int2vec(int n) {
std::vector<int> res(ndigits, 0);
for(int i = ndigits - 1; i >= 0; --i, n /= 10)
res[i] = n % 10;
return res;
}

int vec2int(const std::vector<int> &vec) {
int res = 0;
int len = vec.size();
int mul = 1;
for(int i = len - 1; i >= 0; --i) {
res += vec[i] * mul;
mul *= 10;
}
return res;
}

int sortAndPrint(std::vector<int> &digits) {
sort(digits.begin(), digits.end());
int smaller = vec2int(digits);
sort(digits.begin(), digits.end(), std::greater<int>());
int bigger = vec2int(digits);

int n = bigger - smaller;
printf("%.4d - %.4d = %.4d\n", bigger, smaller, n);
return n;
}

void gao(int n) {
if(n <= 0|| n >= 10000)
return ;

std::vector<int> digits = int2vec(n);
if(allTheSame(digits))  {
printf("%.4d - %.4d = 0000\n", n, n);
return ;
}
n = sortAndPrint(digits);
while(n != hole) {
digits = int2vec(n);
n = sortAndPrint(digits);
}
return ;
}

int main() {
int n;
scanf("%d", &n);
gao(n);
return 0;
}
```

### 1069. The Black Hole of Numbers注意点：

（全文完，原创文章，转载时请注明作者和出处）

（转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com，请勿用于任何商业用途）

Written on November 30, 2013