回溯法之计算操作符

2023-12-21 19:54:40

问题:

?????????设计一个算法在 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;
}

文章来源:https://blog.csdn.net/a17783481239/article/details/135137504
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。