用c++完成这道题:题目描述 给出 nn 组 44 个整数,请问有多少组整数,在不改变顺序,且不加入括号的情况下,可以通过 ++ -− \times× 三种运算,得到 2424 。 比如 11 22 33 44 四个数,可以通过如下的方法得到2424:1 \times 2 \times 3 \times 4=241×2×3×4=24。 而 2020 3030 4040 5050 四个数,在不改变顺序、不添加括号的情况下,通过 ++ -− \times× 三种运算是无法获得 2424 的。 输入 第1行有一个整数 nn;( 2 \le n \le 1002≤n≤100 ) 接下来 nn 行,每行有 44 个整数 a_ia i ;( 1 \le a_i \le 1001≤a i ≤100 ) 输出 输出一个整数,代表有几组数能够通过题目的规则计算得到 2424 。
时间: 2024-03-17 07:46:55 浏览: 197
以下是C++代码实现:
```c++
#include <iostream>
#include <vector>
using namespace std;
int cnt = 0; // 计数器
void dfs(vector<int>& nums, int cur, int sum) {
if (cur == 4) { // 递归到最后一位
if (sum == 24) cnt++; // 满足条件,计数器加一
return;
}
dfs(nums, cur + 1, sum + nums[cur]); // 加号运算
dfs(nums, cur + 1, sum - nums[cur]); // 减号运算
dfs(nums, cur + 1, sum * nums[cur]); // 乘号运算
}
int main() {
int n;
cin >> n;
while (n--) {
vector<int> nums(4);
for (int i = 0; i < 4; i++) {
cin >> nums[i];
}
cnt = 0;
dfs(nums, 1, nums[0]); // 从第二个数开始递归,第一个数是初始值
if (cnt) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}
```
使用深度优先搜索(DFS)来枚举所有可能的运算组合,当运算结果为24时计数器加一。
阅读全文