厦门大学夏令营机试第一题-根据数字各位数之和排序

题目描述

给定两个整数 n 和 m，需要对从 n 到 m 的所有整数进行排序。排序规则如下：

1. 按照每个数字各位数之和从小到大排序。
2. 如果各位数之和相同，则按照数字的大小从小到大排序。

例如：

• 数字 9 排在数字 123 后面，因为 1 + 2 + 3 = 6 而 9 自身的各位数之和是 9。
• 数字 36 排在数字 9 后面，因为 3 + 6 = 9，但 36 大于 9。

题解

为了实现上述排序，我们可以使用 C++ 编写一个程序来完成。主要的思路是：

1. 编写一个函数来计算数字的各位数之和。
2. 编写一个比较函数，先比较各位数之和，如果相等则比较数字本身的大小。
3. 使用 sort 函数进行排序。

以下是完整的 C++ 代码：

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

// 计算数字每一位的和
int digitSum(int number) {
    int sum = 0;  // 初始化和为0
    while (number) {
        sum += number % 10;  // 将当前位加到和上
        number /= 10;  // 去掉当前位
    }
    return sum;  // 返回各位数之和
}

// 比较函数
bool compare(int a, int b) {
    int sumA = digitSum(a);  // 计算a的各位数之和
    int sumB = digitSum(b);  // 计算b的各位数之和
    if (sumA == sumB) {
        return a < b;  // 如果各位数之和相等，按数值大小排序
    }
    return sumA < sumB;  // 否则按各位数之和排序
}

int main() {
    int n, m;
    
    cout << "请输入开始的整数n: ";
    cin >> n;
    
    cout << "请输入结束的整数m: ";
    cin >> m;
    
    vector<int> numbers;
    for (int i = n; i <= m; ++i) {
        numbers.push_back(i);  // 将从n到m的所有整数添加到数组中
    }
    
    // 按照比较函数排序
    sort(numbers.begin(), numbers.end(), compare);
    
    cout << "排序后的数字: ";
    for (int num : numbers) {
        cout << num << " ";  // 输出排序后的数字
    }
    cout << endl;

    return 0;
}