用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 的。
时间: 2024-03-07 07:50:14 浏览: 88
四个数 算24
以下是用 C++ 编写的实现代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
int dfs(int res, int idx, vector<int>& nums) {
if (idx == nums.size()) {
return res == 24 ? 1 : 0;
}
int cnt = 0;
cnt += dfs(res + nums[idx], idx + 1, nums);
cnt += dfs(res - nums[idx], idx + 1, nums);
cnt += dfs(res * nums[idx], idx + 1, nums);
return cnt;
}
int main() {
int n;
cin >> n;
while (n--) {
vector<int> nums(4);
for (int i = 0; i < 4; i++) {
cin >> nums[i];
}
int cnt = dfs(0, 0, nums);
cout << cnt << endl;
}
return 0;
}
```
思路如下:
1. 首先读取输入的测试数据组数 n,循环 n 次进行处理。
2. 对于每一组测试数据,读取 4 个整数存入 nums 数组中。
3. 利用 dfs 搜索遍历所有可能的运算方式,计算得到最终结果。
4. 如果最终结果等于 24,那么就将计数器加 1。
5. 最后输出计数器的值即为满足条件的组数。
阅读全文