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算法分析:

基本上模拟, 考察怎么得到这个四位数的每位的数字吧, 水题, 下面是可以AC的代码:

#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