如何正确计算排列、排查代码错误并实现递归求解1-9填数凑100问题

为什么会输出错误排列 #

核心原因是C++的整数除法截断特性：

• 代码中所有变量都是int类型，两个int做除法时会直接丢弃小数部分，比如4 / 3计算结果为1而非1.333...
• 很多排列代入公式做浮点运算本不等于100，但经过多次整数除法截断后结果刚好凑为100，被误判为有效解。

正确的判断逻辑需要先保证公式中的两个除法项都是整除，再计算结果：

你需要在判断等式前先增加两个整除校验：arr[0] % arr[1] == 0 和 (arr[3] * arr[4] * arr[5]) % arr[6] == 0，只有两个条件都满足时再计算等式是否等于100，就能避免截断误差导致的误判。

递归实现方案 #

可以用回溯法生成1~9的全排列，递归逻辑为：每次固定当前位置的元素，和后续未固定的元素逐一交换，递归处理下一个位置，递归返回后恢复交换（回溯），当所有位置都固定时判断是否符合等式要求。
修改后的完整代码如下：

#include <iostream>
using namespace std;

// 输出符合条件的排列
void print(int arr[]){
    for (int i = 0; i < 9; i++){
        cout << arr[i] << " ";
    }
    cout << endl;
}

// 校验当前排列是否符合要求
bool check(int arr[]){
    // 先校验整除性，避免整数截断误差
    if(arr[0] % arr[1] != 0) return false;
    long long term2_num = (long long)arr[3] * arr[4] * arr[5];
    if(term2_num % arr[6] != 0) return false;
    // 计算等式
    int term1 = arr[0] / arr[1] * arr[2];
    int term2 = term2_num / arr[6];
    int term3 = arr[7] * arr[8];
    return term1 + term2 + term3 == 100;
}

// 递归生成全排列，index为当前要固定的位置下标
void permute(int arr[], int index){
    // 所有位置都已固定，校验并输出
    if(index == 9){
        if(check(arr)){
            print(arr);
        }
        return;
    }
    // 把index之后的元素逐个换到当前位置，递归处理下一位
    for(int i = index; i < 9; i++){
        swap(arr[index], arr[i]);
        permute(arr, index + 1);
        swap(arr[index], arr[i]); // 回溯，恢复交换
    }
}

int main(){
    int arr[] = {1,2,3,4,5,6,7,8,9};
    permute(arr, 0);
    return 0;
}

内容的提问来源于stack exchange，提问作者Jeff