《算法竞赛·快冲300题》每日一题：“凑二十四”

《算法竞赛·快冲300题》将于2024年出版，是《算法竞赛》的辅助练习册。
所有题目放在自建的OJ New Online Judge。
用C/C++、Java、Python三种语言给出代码，以中低档题为主，适合入门、进阶。

“ 凑二十四” ，链接： http://oj.ecustacm.cn/problem.php?id=1793

题目描述

【题目描述】 给你n个数字，你需要在n-1个间隔中添加符号+、-、×，按照正常优先级计算结果。请你输出有多少种方案，计算结果等于24。
【输入格式】 第一行为正整数n（2≤n≤10）。第二行n个正整数表示给定的n个数字，数字不超过50。
【输出格式】 输出一个数字表示答案。
【输入样例】

5
2 4 6 8 16

【输出样例】

2

---

题解

   如果尝试所有可能组合，共有多少种组合？最多n=10个数字时，需要添加9个符号，共$3^9=19683$种组合，并不多。
  用DFS搜索所有可能组合。由于只有19683种情况，不用剪枝。
  代码用dfs()搜索所有符号组合。对每个组合，用check()检查计算结果是否等于24。先计算乘法，再计算加减。下面的代码用了简单直接的模拟法。先处理表达式中的乘法，对两个数做乘法时，把计算结果存在后面，前面置零，并把符号改为前面的加减，例如3+4×5，先处理乘法，转换为3+0+20。
  check()也有其他写法，例如先把表达式（称为中缀表达式）转为逆波兰表达式，然后用栈来计算逆波兰表达式。因为比较繁琐，这里没有给出代码。
【重点】 DFS 。

C++代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, a[11];
int op[11];               //第i个间隔的符号 + - * = 0 1 2
int ans;
ll check(){   //先计算*，再计算+-ll t[11] = {0}, t_op[11] = {0};for(int i=1; i<=n; i++)t[i] = a[i], t_op[i] = op[i];//先处理乘号：把乘积结果存入t[i+1]、t[i]设置为0、符号沿用前面的符号for(int i = 1; i < n; i++)if(t_op[i] == 2)t[i+1] *= t[i], t[i] = 0, t_op[i] = t_op[i-1];//最后加减ll sum = t[1];for(int i = 1; i < n; i++){if(t_op[i] == 0)  sum += t[i+1]; //加else sum -= t[i+1];              //减}return sum;
}
void dfs(int depth){if(depth == n){if(check() == 24)   ans++;return;}for(int i = 0; i <= 2; i++) {   //继续添加下一个符号op[depth] = i;dfs(depth + 1);}
}
int main(){cin >> n;for(int i = 1; i <= n; i++)    cin >> a[i];dfs(1);cout<<ans<<endl;return 0;
}

Java代码

import java.util.Scanner;
public class Main {static int n, a[] = new int[11], op[] = new int[11]; // 第i个间隔的符号 + - * = 0 1 2static int ans;public static void main(String[] args) {Scanner in = new Scanner(System.in);n = in.nextInt();for (int i = 1; i <= n; i++)   a[i] = in.nextInt();dfs(1);System.out.println(ans);in.close();}static long check() { // 先计算*，再计算+-long[] t = new long[11];int[] t_op = new int[11];for (int i = 1; i <= n; i++) {t[i] = a[i];t_op[i] = op[i];}// 先处理乘号：把乘积结果存入t[i+1]、t[i]设置为0、符号沿用前面的符号for (int i = 1; i < n; i++) {if (t_op[i] == 2) {t[i + 1] *= t[i];t[i] = 0;t_op[i] = t_op[i - 1];}}// 最后加减long sum = t[1];for (int i = 1; i < n; i++) {if (t_op[i] == 0) sum += t[i + 1]; // 加else              sum -= t[i + 1]; // 减}return sum;}static void dfs(int depth) {if (depth == n) {if (check() == 24)   ans++;return;}for (int i = 0; i <= 2; i++) { // 继续添加下一个符号op[depth] = i;dfs(depth + 1);}}
}

Python代码

n = int(input())
a = [0]+list(map(int, input().split()))     #输入到a[1]-a[10]
op = [0] * 11                               # 第i个间隔的符号 + - * = 0 1 2
ans = 0
def check():# 先计算*，再计算+-t = [0] * 11t_op = [0] * 11for i in range(1, n+1):t[i] = a[i]t_op[i] = op[i]# 先处理乘号：把乘积结果存入t[i+1]、t[i]设置为0、符号沿用前面的符号for i in range(1, n):if t_op[i] == 2:t[i+1] *= t[i]t[i] = 0t_op[i] = t_op[i-1]# 最后加减sum = t[1]for i in range(1, n):if t_op[i] == 0: sum += t[i+1]  # 加else:            sum -= t[i+1]  # 减return sum
def dfs(depth):global ansif depth == n:if check() == 24:   ans += 1returnfor i in range(3):                  # 继续添加下一个符号op[depth] = idfs(depth + 1)
dfs(1)
print(ans)