24点游戏,也叫3824游戏,是一款经典的心算数字游戏。给出区间[1,13]内的四个整数,验证能否用加、减、乘、除四则运算,将这四个整数组合成24。比如:(3,8,2,4) 可以算出 8∗(4−3+2)=24或者(8−4)∗(2∗3)=24,而(1,1,2,2)无法算出24。注意整除必须除尽,即9/2+10+10=24这种计算无效。
输入格式
第一行给出正整数N(1≤N≤1000)。接下来N行数据,每行给出四个正整数ai bi ci di, 用空格分开。(∀i∈{1,…,N}:1≤ai,bi,ci,di≤13)
输出格式
输出N行数据,第i行对应输入数据(ai,bi,ci,di),如果能算出24,则输出24,如果不能则输出0。
输入样例
1 2 3 4 5
| 4 1 1 1 1 1 2 3 4 3 9 11 2 13 3 5 7
|
输出样例
(1,1,1,1)和(3,9,11,2)都无法算出24,(1,2,3,4)和(13,3,5,7)可以算出:1∗2∗3∗4=24和(13∗5+7)/3=24。
解题思路
此题大意是计算4个数通过各种组合能否计算出结果24,我们通过回溯还是可以遍历每一种加减乘除的可能,唯一不足就是,此题要求考虑括号,如果我们按照顺序计算四个数,那么肯定我们是无法实现括号的优先级功能的,此时大佬的思路:双层循环简直天神下凡,我们可以用这个双层循环实现4个数中任意两个数一起计算的可能,那么括号这个大问题就算解决了。
第二个问题,在回溯过程中,由于我们是通过双层循环选取的任意两个数,对于加法,两个数先后顺序是无所谓的,但在减法和除法中,两个数先后顺序不同会产生两种不同结果,于是我们要多加一次减法和除法。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
| #include<iostream> using namespace std; int arr[4]; bool dfs(int n) { if (n == 1) return arr[0] == 24; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j) continue; int op1 = arr[i], op2 = arr[j]; arr[i] = op1 + op2; arr[j] = arr[n - 1]; if (dfs(n - 1)) return 1; arr[i] = op1 - op2; if (dfs(n - 1)) return 1; arr[i] = op2 - op1; if (dfs(n - 1)) return 1; arr[i] = op1 * op2; if (dfs(n - 1)) return 1; if (op2 != 0 && op1 % op2 == 0) { arr[i] = op1 / op2; if (dfs(n - 1)) return 1; } if (op1 != 0 && op2 % op1 == 0) { arr[i] = op2 / op1; if (dfs(n - 1)) return 1; } arr[i] = op1; arr[j] = op2; } } return 0; } int main() { int n; cin >> n; while (n--) { cin >> arr[0] >> arr[1] >> arr[2] >> arr[3]; if (dfs(4)) cout << "24" << endl; else cout << "0" << endl; } }
|