回溯法之计算操作符

问题:

?????????设计一个算法在 1，2，……9(顺序不变)数值之间插入+或者-或者什么都不插入， 使得计算结果总是 100 的程序。?
//例如 1 + 2 + 34 - 5 + 67 - 8 + 9 = 100。

思路:

? ? ? ??

1. 创建一个长度为9的数组arr，其中存放数字1到9。
2. 创建一个长度为9的字符数组op，用于存放操作符，初始值为' '。
3. 创建一个回溯函数func，该函数用于搜索所有可能的表达式。
4. 在回溯函数中，使用一个循环遍历所有的位置，从第二个位置开始。
5. 在每个位置上，有三种选择：插入"+"、插入"-"或者不插入任何符号。
6. 对于每种选择，更新计算结果和表达式，并递归调用回溯函数来搜索下一个位置。
7. 当搜索到最后一个位置时，如果计算结果等于100，则输出表达式。
8. 返回到上一层递归，继续搜索其他可能的表达式。
9. 在主函数中，调用回溯函数func，从第二个位置开始搜索。

代码:

#include<iostream>
using namespace std;

const int N = 9;
int arr[N] = { 1,2,3,4,5,6,7,8,9 };
char op[N];  // 存储操作符的数组

// 回溯函数，用于搜索所有可能的表达式
void func(int sum, int preAdd, int i) {
    if (i == N) {  // 到达最后一个位置
        if (sum == 100) {  // 计算结果等于100
            cout << arr[0];  // 输出第一个数字
            for (int j = 1; j < N; j++) {
                if (op[j] != ' ')
                    cout << op[j];  // 输出操作符（如果存在）
                cout << arr[j];  // 输出数字
            }
            cout << "=100" << endl;  // 输出结果
        }
        return;
    }
    else {
        // 选择插入 "+"
        op[i] = '+';
        func(sum + arr[i], arr[i], i + 1);  // 递归调用函数

        // 选择插入 "-"
        op[i] = '-';
        func(sum - arr[i], -arr[i], i + 1);  // 递归调用函数

        // 选择不插入任何符号
        op[i] = ' ';
        int tempN = 0;
        if (preAdd > 0)
            tempN = preAdd * 10 + arr[i];
        else
            tempN = preAdd * 10 - arr[i];
        func(sum - preAdd + tempN, tempN, i + 1);  // 递归调用函数
    }
}

int main() {
    func(arr[0], arr[0], 1);  // 调用回溯函数，从第二个位置开始搜索
    return 0;
}