给定n个正整数和4个运算符:+、-、*、/,运算符没有优先级,按照从左到右的次序依次运算,例如:3+45不等于23,而是等于35。请设计一个算法,对于任意给定的整数m,用给出的n个正整数和4个运算符,经过运算得到整数m,要求运算次数最少。注意:n个数中每个数最多只允许用1次(即不使用或者使用1次),每种运算符可以多次使用。 输入格式: 第一行输入正整数n和整数m 第二行输入具体的n个正整数。 输出格式: 第一行输出最少运算次数。 第二行输出对应的运算表达式。若输入的n个正整数无法运算得到m,则输出“-1”,给出一份C++代码
时间: 2024-03-19 14:43:57 浏览: 55
下面是一份C++代码实现,采用深度优先搜索(DFS)的思想来解决该问题:
```c++
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 15, INF = 0x3f3f3f3f;
int n, m;
int a[N], op[N], st[N];
int path[N], len;
bool dfs(int u, int sum)
{
if (u == n)
{
if (sum == m) return true;
return false;
}
// 不选当前数
if (dfs(u + 1, sum)) return true;
// 选当前数
bool flag = false;
for (int i = 0; i < 4; i ++ )
{
if (op[i] == '+') sum += a[u];
else if (op[i] == '-') sum -= a[u];
else if (op[i] == '*') sum *= a[u];
else if (op[i] == '/' && a[u] != 0 && sum % a[u] == 0) sum /= a[u];
else continue;
path[len ++ ] = i;
if (dfs(u + 1, sum))
{
flag = true;
break;
}
len -- ;
path[len] = -1;
if (op[i] == '+') sum -= a[u];
else if (op[i] == '-') sum += a[u];
else if (op[i] == '*') sum /= a[u];
else if (op[i] == '/') sum *= a[u];
}
return flag;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ ) cin >> a[i];
for (int i = 0; i < 4; i ++ ) cin >> op[i];
memset(path, -1, sizeof path);
if (dfs(1, a[0]))
{
cout << len << endl;
cout << a[0];
for (int i = 0; i < len; i ++ )
{
if (path[i] == 0) cout << "+";
else if (path[i] == 1) cout << "-";
else if (path[i] == 2) cout << "*";
else if (path[i] == 3) cout << "/";
cout << a[i + 1];
}
cout << endl;
}
else cout << -1 << endl;
return 0;
}
```
其中dfs函数的参数u表示当前考虑的数,sum表示当前表达式的计算结果。在dfs函数中,首先判断是否使用当前数,如果不使用,则直接递归到下一个数;如果使用,则枚举四个运算符,并计算当前表达式的计算结果。如果当前表达式的计算结果等于目标数m,则返回true,否则,继续添加运算符,直到所有运算符都被添加或者当前表达式的计算结果超过m。如果当前表达式的计算结果已经超过m,则说明当前表达式不可行,返回false。
在主函数中,先读入输入数据,然后调用dfs函数求解。如果能够找到符合条件的表达式,则输出表达式长度和表达式本身;否则,输出-1。
时间复杂度:O(4^n)。
阅读全文