《算法竞赛·快冲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
【输出样例】文章来源:https://www.toymoban.com/news/detail-669108.html
2
题解
如果尝试所有可能组合,共有多少种组合?最多n=10个数字时,需要添加9个符号,共
3
9
=
19683
3^9=19683
39=19683种组合,并不多。
用DFS搜索所有可能组合。由于只有19683种情况,不用剪枝。
代码用dfs()搜索所有符号组合。对每个组合,用check()检查计算结果是否等于24。先计算乘法,再计算加减。下面的代码用了简单直接的模拟法。先处理表达式中的乘法,对两个数做乘法时,把计算结果存在后面,前面置零,并把符号改为前面的加减,例如3+4×5,先处理乘法,转换为3+0+20。
check()也有其他写法,例如先把表达式(称为中缀表达式)转为逆波兰表达式,然后用栈来计算逆波兰表达式。因为比较繁琐,这里没有给出代码。
【重点】 DFS 。文章来源地址https://www.toymoban.com/news/detail-669108.html
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 2
static 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] * 11
t_op = [0] * 11
for 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] = 0
t_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 ans
if depth == n:
if check() == 24: ans += 1
return
for i in range(3): # 继续添加下一个符号
op[depth] = i
dfs(depth + 1)
dfs(1)
print(ans)
到了这里,关于《算法竞赛·快冲300题》每日一题:“凑二十四”的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!