22.2 数字变换问题

“数字变换是一类有趣的问题，”我解释道，”通过一系列特定的规则，对数字进行转换和处理，观察其变化规律。”

22.2.1 数字黑洞

题目描述：给定一个三位数，要求各位不能相同。例如，352是符合要求的，112是不符合要求的。将这个三位数的三个数字重新排列，得到的最大的数，减去得到的最小的数，形成一个新的三位数。对这个新的三位数可以重复上述过程。神奇的是，最终一定会得到495！试试看，重新排列352，得到的最大数为532，最小数为235，它们的差是297；变换297，得到972−279=693；变换693，963−369=594；变换594，954−459=495。因此，经过4次变换得到了495。现在，输入的三位数，你能通过编程得出，这个三位数经过多少次变换能够得到495吗？

样例输入：

352

样例输出：

4

代码实现（方法一：直接排序）：

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

int main() {
    int n, cnt = 0;
    cin >> n;                   // 读取初始三位数
    while(n != 495) {           // 循环直到得到495
        cnt++;                  // 变换次数计数器
        int ma1 = INT_MIN, ma2 = INT_MIN, ma3 = INT_MIN;  // 初始化三个变量，用于存储排序后的三个数字
        int t = n;              // 临时变量，用于提取各个数位
        // 提取三个数字并按从大到小排序
        while(t) {
            if(t % 10 > ma1) {  // 如果当前数字大于最大值
                ma3 = ma2;      // 依次移动现有的数字
                ma2 = ma1;
                ma1 = t % 10;   // 更新最大值
            } else if(t % 10 > ma2) {  // 如果当前数字介于最大值和次大值之间
                ma3 = ma2;
                ma2 = t % 10;   // 更新次大值
            } else if(t % 10 > ma3) {  // 如果当前数字介于次大值和最小值之间
                ma3 = t % 10;   // 更新最小值
            }
            t /= 10;            // 处理下一位数字
        }
        int x = ma1 * 100 + ma2 * 10 + ma3;  // 组成最大数（从大到小排列）
        int y = ma3 * 100 + ma2 * 10 + ma1;  // 组成最小数（从小到大排列）
        n = x - y;              // 计算差值作为新的三位数
    }
    cout << cnt;                // 输出变换次数
    return 0;
}

代码实现（方法二：简化排序）：

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

int main() {
    int n, cnt = 0;
    cin >> n;                   // 读取初始三位数
    while(n != 495) {           // 循环直到得到495
        cnt++;                  // 变换次数计数器
        int g = n % 10, s = n / 10 % 10, b = n / 100 % 10;  // 直接提取三个位上的数字
        // 对三个数字排序（从小到大）
        if(g > s) swap(g, s);   // 如果个位大于十位，交换
        if(g > b) swap(g, b);   // 如果个位大于百位，交换
        if(s > b) swap(s, b);   // 如果十位大于百位，交换
        int x = b * 100 + s * 10 + g;  // 最大数（从大到小排列）
        int y = g * 100 + s * 10 + b;  // 最小数（从小到大排列）
        n = x - y;              // 计算差值作为新的三位数
    }
    cout << cnt;                // 输出变换次数
    return 0;
}

思考：

• 方法一和方法二都实现了相同的功能，但方法二的代码更简洁
• 方法二通过直接提取三个位上的数字，然后手动排序，避免了复杂的条件判断
• 这个实验展示了Kaprekar变换的特性：三位数经过有限次变换后会收敛到495
• 在实际编程中，选择合适的数据处理方式可以简化代码

22.2.2 自幂数

题目描述：自幂数是指，一个N位数，满足各位数字N次方之和是本身。例如，153是3位数，其每位数的3次方之和，1³+5³+3³=153，因此153是自幂数；1634是4位数，其每位数的4次方之和，1⁴+6⁴+3⁴+4⁴=1634，因此1634是自幂数。现在，输入若干个正整数，请判断它们是否是自幂数。

样例输入：

2
153
123

样例输出：

T
F

代码实现：

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

int main() {
    int n;
    cin >> n;                   // 读取测试用例数量
    while(n--) {                // 循环处理每个测试用例
        int x;
        cin >> x;               // 读取要判断的数字
        
        // 计算x的位数
        int t = x, cnt = 0;
        while(t) {              // 通过除10循环计算数字的位数
            cnt++;
            t /= 10;
        }
        
        // 计算各位数的cnt次方之和
        t = x;                  // 重新赋值，准备提取各位数字
        int sum = 0;
        while(t) {
            sum += pow(t % 10, cnt);  // 计算当前位的cnt次方并累加
            t /= 10;                  // 处理下一位
        }
        
        // 判断是否为自幂数
        if(sum == x) cout << 'T' << endl;  // 如果次方和等于原数，是自幂数
        else cout << 'F' << endl;           // 否则不是自幂数
    }
    return 0;
}

思考：

• 该算法首先计算数字的位数，然后计算各位数字的次方和
• 使用pow函数计算各位数字的幂
• 这个实验展示了如何判断数字的特殊性质
• 自幂数是数学中一个有趣的概念，也称为水仙花数或阿姆斯特朗数