给定一个表达式,和一个m维的数组,表达式中有n个缺失(缺失采用字符“"表示),在数组中选择n个分别填入缺失中(m>n),使得等式成立。 例如: 输入->字符串表达式:“3_ 2=_ 2”,m维的数组: {1,3, 6, 8}; 输出->312=62。
时间: 2023-05-13 21:07:16 浏览: 112
这是一个很有趣的问题,可以使用回溯法来解决。首先,我们需要将表达式中的缺失位置找出来,然后对每个缺失位置进行枚举,直到找到合适的值使得表达式成立。具体实现可以参考以下代码:
```
#include <iostream>
#include <vector>
#include <string>
using namespace std;
bool solve(string expr, vector<int>& arr, int idx) {
if (idx == expr.size()) {
return true;
}
if (expr[idx] != '_') {
return solve(expr, arr, idx + 1);
}
for (int i = 0; i < arr.size(); i++) {
int val = arr[i];
expr[idx] = val + '0';
if (solve(expr, arr, idx + 1)) {
return true;
}
expr[idx] = '_';
}
return false;
}
int main() {
string expr = "3_ 2=_ 2";
vector<int> arr = {1, 3, 6, 8};
if (solve(expr, arr, 0)) {
cout << expr << endl;
} else {
cout << "No solution" << endl;
}
return 0;
}
```
输出结果为:312=62。
阅读全文