写出满足如下条件的C++代码:无优先级运算问题 输入格式: 第一行输入正整数n和整数m 第二行输入具体的n个正整数。 输出格式: 第一行输出最少运算次数。 第二行输出对应的运算表达式。若输入的n个正整数无法运算得到m,则输出“-1”。
时间: 2024-03-20 15:39:46 浏览: 42
C++程序设计基础课后答案 第一章
以下是满足上述条件的C++代码:
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <string>
using namespace std;
struct Node {
int val;
string expr;
};
int main() {
int n, m;
cin >> n >> m;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
queue<Node> q;
map<int, int> visited; // 记录已经访问过的数值
q.push({nums[0], to_string(nums[0])});
while (!q.empty()) {
Node cur = q.front();
q.pop();
if (cur.val == m) {
cout << cur.expr.size() - n << endl; // 表达式长度减去数字个数即为运算次数
cout << cur.expr << endl;
return 0;
}
for (int i = 0; i < n; i++) {
int next_val = cur.val + nums[i];
string next_expr = cur.expr + "+" + to_string(nums[i]);
if (visited[next_val] == 0) {
visited[next_val] = 1;
q.push({next_val, next_expr});
}
next_val = cur.val - nums[i];
next_expr = cur.expr + "-" + to_string(nums[i]);
if (visited[next_val] == 0) {
visited[next_val] = 1;
q.push({next_val, next_expr});
}
next_val = cur.val * nums[i];
next_expr = cur.expr + "*" + to_string(nums[i]);
if (visited[next_val] == 0) {
visited[next_val] = 1;
q.push({next_val, next_expr});
}
if (nums[i] != 0 && cur.val % nums[i] == 0) {
next_val = cur.val / nums[i];
next_expr = cur.expr + "/" + to_string(nums[i]);
if (visited[next_val] == 0) {
visited[next_val] = 1;
q.push({next_val, next_expr});
}
}
}
}
cout << -1 << endl;
return 0;
}
```
该代码通过 BFS 搜索所有可能的运算表达式,记录已经访问过的数值,避免重复运算。当搜索到目标数值时,输出最少运算次数以及对应的运算表达式。如果无法运算得到目标数值,则输出“-1”。
阅读全文