[编程题]24点游戏算法
- 热度指数：156737 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
在一行上输入四个整数
代表等待计算的数字。
输出描述:
，输出
，否则，直接输出
。
示例1
输入
7 2 1 10
输出
true
说明
，因此输出
示例2
输入
2 2 2 9
输出
true
说明
，因此输出
示例3
输入
10 9 6 9
输出
true
说明
，因此输出
示例4
输入
3 3 8 8
输出
true
说明
，因此输出
示例5
输入
1 1 1 1
输出
false
备注:
只能过29/30,没有办法处理多括号情形
import java.util.*;
//知识点：递归、深度优先搜索、回溯算法
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
String[] numstr = in.nextLine().split(" ");
int[] nums = new int[4]; // 存放数字
int[] visit = new
int[4]; // 存放对应位置数字的使用状态（1代表已使用）
for (int i = 0; i < 4; i++) {
nums[i] = Integer.parseInt(numstr[i]); // 读取数字
}
boolean flag = dfs(nums, visit, 0.0);
System.out.println(flag);
}
}
public static boolean dfs(int[] nums, int[] visit, double temp) {
for (int i = 0; i < nums.length; i++) {
if (visit[i] == 0) { // 如果是未使用的数字
visit[i] = 1; // 标记为已使用
if (dfs(nums, visit, temp * 1.0 + nums[i]) // 递归判断
|| dfs(nums, visit, temp * 1.0 - nums[i])
|| dfs(nums, visit, temp * 1.0 * nums[i])
|| (dfs(nums, visit, temp * 1.0 / nums[i]))) {
// 如果存在满足条件的，终止循环
return true;
}
// 不存在满足条件的，说明当前的数字顺序不符要求，进行回溯，把标记重置为0
visit[i] = 0;
}
}
// 数字都已使用且结果为24，返回真
if (temp == 24.0) {
return true;
}
// 不存在24，返回假
return false;
}
}
发表于 2025-07-27 22:26:01
回复(0)
考虑数字顺序、括号、浮点运算差值等所有情况，只是
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
// import javax.script.*;
public class Main {
private static int[] abcd = new int[4];
// private static ScriptEngineManager sem = new ScriptEngineManager();
// private static ScriptEngine se = sem.getEngineByName("JavaScript");
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String[] line = in.readLine().split(" ");
abcd[0] = Integer.parseInt(line[0]);
abcd[1] = Integer.parseInt(line[1]);
abcd[2] = Integer.parseInt(line[2]);
abcd[3] = Integer.parseInt(line[3]);
List<String> eve = new LinkedList<>();
for (int i = 0 ; i < 4 ; i++) {
for (int j = 0 ; j < 4 ; j++) {
if (j != i) {
for (int k = 0 ; k < 4 ; k++) {
if (k != j && k != i) {
for (int l = 0 ; l < 4 ; l++) {
if (l != k && l != j && l != i) {
char[] yusuan = {'*', '/', '+', '-'};
for (int a = 0 ; a < 4 ; a++) {
for (int b = 0 ; b < 4 ; b++) {
for (int c = 0 ; c < 4 ; c++) {
eve.add("" + abcd[i]);
eve.add("" + yusuan[a]);
eve.add("" + abcd[j]);
eve.add("" + yusuan[b]);
eve.add("" + abcd[k]);
eve.add("" + yusuan[c]);
eve.add("" + abcd[l]);
if (test(eve)) {
System.out.print(true);
return;
}
eve.clear();
}
}
}
}
}
}
}
}
}
}
System.out.print(false);
}
private static boolean test(List<String> eve) {
List<String> eve2;
for (int i = 0 ; i < 5 ; i += 2) {
for (int j = i + 2 ; j < 7; j += 2) {
eve2 = new LinkedList<>(eve);
eve2.add(i, "(");
eve2.add(j + 2, ")");
if (test2(eve2))return true;
}
}
eve2 = new LinkedList<>(eve);
//(0+0)+(0+0)
eve2.add(0, "(");
eve2.add(4, ")");
eve2.add(6, "(");
eve2.add(10, ")");
return test2(eve2);
}
private static boolean test2(List<String> eve) {
StringBuilder s = new StringBuilder();
for (String i : eve) {
s.append(i);
}
double result = calculate(s.toString());
if (Math.abs(result - 24.0) < 1e-10) {
return true;
}
return false;
// try {
// int r = (int) se.eval(s.toString());
// if (r == 24)return true;
// return false;
// } catch (Exception e) {
// return false;
// }
}
// 判断是否是数字
private static boolean isDigit(char c) {
return c >= '0' && c <= '9';
}
// 获取运算符优先级
private static int priority(char op) {
if (op == '+' || op == '-') return 1;
if (op == '*' || op == '/') return 2;
return 0;
}
// 执行一次运算
private static void eval(Stack<Double> numStack, Stack<Character> opStack) {
double b = numStack.pop();
double a = numStack.pop();
char op = opStack.pop();
double result = 0.00;
// System.out.println(""+a + op + b);
switch (op) {
case '+':
result = a + b;
break;
case '-':
result = a - b;
break;
case '*':
result = a * b;
break;
case '/':
if (b != 0)result = a / b;
else result = -10000.0;
break;
}
numStack.push(result);
}
// 表达式求值主函数
private static double calculate(String s) {
Stack<Double> numStack = new Stack<>();
Stack<Character> opStack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == ' ') continue;
boolean isF = false;
if (c == '-') {
if (i == 0 || (!isDigit(s.charAt(i - 1)) && s.charAt(i - 1) != ')')) {
isF = true;
i++;
c = s.charAt(i);
}
}
if (isDigit(c)) {
double x = 0;
while (i < s.length() && isDigit(s.charAt(i))) {
x = x * 10 + (s.charAt(i) - '0');
i++;
}
if (isF)x = -x;
i--; // 回退一步
numStack.push(x);
} else if (c == '(') {
opStack.push(c);
} else if (c == ')') {
while (!opStack.isEmpty() && opStack.peek() != '(') {
eval(numStack, opStack);
}
opStack.pop(); // 弹出 '('
} else {
// 是运算符
while (!opStack.isEmpty() && opStack.peek() != '(' &&
priority(opStack.peek()) >= priority(c)) {
eval(numStack, opStack);
}
opStack.push(c);
}
}
// 处理剩余运算符
while (!opStack.isEmpty()) {
eval(numStack, opStack);
}
return numStack.pop();
}
}
发表于 2025-07-09 15:23:45
回复(0)
import java.util.*;
// @@@ 回溯穷举：先取遍任意2个数进行+-*/ 消灭,
// 然后将结果所得的1个数替换原来的2个数
// 重复操作,直到只剩1个数,判断是否24
public class Main {
public static boolean find = false; // 标记是否找到一个24方案
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
double a = in.nextDouble(), b = in.nextDouble(),
c = in.nextDouble(), d = in.nextDouble();
List<Double> nums = Arrays.asList(new Double[] {a, b, c, d}); // double
bracktrack(nums); // dfs
System.out.println(find); // 打印
}
// 回溯
public static void bracktrack(List<Double> nums) {
int size = nums.size();
if (find || size == 1) { // 只剩一个数
if (!find) {
if (Math.abs(nums.get(0) - 24) < 0.0000001) // 精度问题
find = true;
}
return;
}
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (i == j) continue; // 要选遍所有可能数对(i,j) i!=j即可 (i,j都是[0,size-1])
if (find) break;
Double x = nums.get(i), y = nums.get(j);
// 由于后面会删除元素,先复制一份原数组,操作复制品
List<Double> copy = new ArrayList<>(nums);
copy.remove(x);
copy.remove(y);
for (int k = 1; k <= 4; k++) {
if (k == 4 && Math.abs(y) < 0.0000001) break; // 除数0
double res = 0;
if (k == 1) res = x + y; // + - * /
else if (k == 2) res = x - y;
else if (k == 3) res = x * y;
else res = x / y;
copy.add(res); // 选择
bracktrack(copy); // 下一层
copy.remove(copy.size() - 1); // 撤销选择
}
}
}
}
}
发表于 2025-03-22 11:09:48
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
double[] numSet = new double[4];
for(int i = 0; i < 4; i ++) {
numSet[i] = in.nextDouble();
}
if(dfs(numSet)) {
System.out.println("true");
} else {
System.out.println("false");
}
}
private static boolean dfs(double[] numSet) {
if(numSet.length == 1) {
return 24 - numSet[0] <= 0.00001 && numSet[0] - 24 <= 0.00001;
}
for (int i = 0; i < numSet.length; i ++) {
for(int j = i + 1; j < numSet.length; j ++) {
int index = 0;
double[] tmpSet = new double[numSet.length - 1];
for(int k = 0; k < numSet.length; k ++) {
if (k != i && k != j) {
tmpSet[index++] = numSet[k];
}
}
tmpSet[index] = numSet[i] + numSet[j];
if(dfs(tmpSet)) {
return true;
}
tmpSet[index] = numSet[i] - numSet[j];
if(dfs(tmpSet)) {
return true;
}
tmpSet[index] = numSet[j] - numSet[i];
if(dfs(tmpSet)) {
return true;
}
tmpSet[index] = numSet[i] * numSet[j];
if(dfs(tmpSet)) {
return true;
}
if(numSet[i] != 0) {
tmpSet[index] = numSet[j] / numSet[i];
if(dfs(tmpSet)) {
return true;
}
}
if(numSet[j] != 0) {
tmpSet[index] = numSet[i] / numSet[j];
if(dfs(tmpSet)) {
return true;
}
}
}
}
return false;
}
}
发表于 2024-12-06 19:29:17
回复(0)
//解题思路：
//1.当只有2个数的时候，很容易计算能不能得到24
//2. 3个数的预算，可以转换为多组2各组运算的组合; 4个数的预算可以转化为多组3个数和多组2个数的组合；
//3. 思路比较清晰，代码写的不够优雅，各位见谅。
import java.util.*;
public class Main{
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int[] num = new int[4];
for(int i=0;i<4;i++)
{
num[i] = sc.nextInt();
}
//通过递归算法，把4个数的运算变成2个数的运算
HashSet<Double> set = count4Num(num[0],num[1],num[2],num[3]);
boolean flag_success = false;
double num_low_limit = Double.valueOf("23.999999");
double num_upper_limit = Double.valueOf("24.000001");
for(Double f_num : set)
{
//直接判断Double.valueOf(24)是不正确的，没考虑double计算精度丢失的问题
//判断"23.999999"-"24.000001"是可以的
if(f_num>=num_low_limit&&f_num<=num_upper_limit)
{
flag_success = true;
break;
}
}
if(flag_success==true)
{
System.out.println("true");
}else{
System.out.println("false");
}
/*
//直接判断Double.valueOf(24)是不正确的，没考虑double计算精度丢失的问题
if(set.contains(Double.valueOf(24)))
{
System.out.println("true");
}else{
System.out.println("false");
}
*/
}
//计算4个数的所有可能的组合
private static HashSet<Double> count4Num(double a,double b,double c,double d)
{
HashSet<Double> set = new HashSet<>();
//四个数可以拆成1-3组合
for(Double i:count3Num(b,c,d))
{
set.addAll(count2Num(a,i));
}
for(Double i:count3Num(a,c,d))
{
set.addAll(count2Num(b,i));
}
for(Double i:count3Num(a,b,d))
{
set.addAll(count2Num(c,i));
}
for(Double i:count3Num(a,b,c))
{
set.addAll(count2Num(d,i));
}
//四个数也可以拆成2-2组合
for(Double i:count2Num(a,b))
{
for(Double j:count2Num(c,d))
{
set.addAll(count2Num(i,j));
}
}
for(Double i:count2Num(a,c))
{
for(Double j:count2Num(b,d))
{
set.addAll(count2Num(i,j));
}
}
for(Double i:count2Num(a,d))
{
for(Double j:count2Num(b,c))
{
set.addAll(count2Num(i,j));
}
}
return set;
}
//计算3个数的所有可能的组合
private static HashSet<Double> count3Num(double a,double b,double c)
{
HashSet<Double> set = new HashSet<>();
for(Double i:count2Num(b,c))
{
set.addAll(count2Num(a,i));
}
for(Double i:count2Num(c,a))
{
set.addAll(count2Num(b,i));
}
for(Double i:count2Num(a,b))
{
set.addAll(count2Num(c,i));
}
return set;
}
//计算2个数的所有可能的组合
private static HashSet<Double> count2Num(double a,double b)
{
HashSet<Double> set = new HashSet<>();
//
set.add(a+b);
set.add(a-b);
set.add(a*b);
if(b!=0){
set.add(a/b);
}
if(a!=b)
{
set.add(b-a);
if(a!=0){
set.add(b/a);
}
}
return set;
}
}
发表于 2024-11-28 19:52:20
回复(0)
package com.xxx.algorithm.algorithm; import java.util.*; import java.util.function.BiFunction; /** * 给出4个1-10的数字，通过加减乘除运算，得到数字为24就算胜利,除法指实数除法运算,运算符仅允许出现在两个数字之间,本题对数字选取顺序无要求，但每个数字仅允许使用一次，且需考虑括号运算 * 此题允许数字重复，如3 3 4 4为合法输入，此输入一共有两个3，但是每个数字只允许使用一次，则运算过程中两个3都被选取并进行对应的计算操作。 * 输入描述： * 读入4个[1,10]的整数，数字允许重复，测试用例保证无异常数字。 * <p> * 输出描述： * 对于每组案例，输出一行表示能否得到24点，能输出true，不能输出false */ public class Clock24Game { public static void main(String[] args) { Scanner in = new Scanner(System.in); List<Integer> nums = Arrays.asList(in.nextInt(), in.nextInt(), in.nextInt(), in.nextInt()); List<BiFunction<Integer, Integer, Integer>> operators = Arrays.asList(Integer::sum, (a, b) -> a - b, (a, b) -> a * b, (a, b) -> a / b); ArrayList<Integer> remainIndex = new ArrayList<>(Arrays.asList(0, 1, 2, 3)); boolean isEqual24 = dfs(nums, operators, nums.get(0), 0, remainIndex); System.out.println(isEqual24); } private static boolean dfs(List<Integer> nums, List<BiFunction<Integer, Integer, Integer>> operators, int acc, int lastIndex, List<Integer> remainIndex) { // 先备份 remainIndex 的状态 List<Integer> originalRemainIndex = new ArrayList<>(remainIndex); // 从 remainIndex 中删除当前索引 remainIndex.remove(Integer.valueOf(lastIndex)); for (int i = 0; i < remainIndex.size(); i++) { int index = remainIndex.get(i); int originalAcc = acc; // 保存初始累加值 for (BiFunction<Integer, Integer, Integer> operator : operators) { acc = operator.apply(acc, nums.get(index)); if (acc == 24) { return true; // 找到结果，提前退出 } else if (acc < 24) { boolean found = dfs(nums, operators, acc, index, remainIndex); if (found) { return true; } } acc = originalAcc; // 回溯累加值 } } // 恢复 remainIndex 的状态 remainIndex.clear(); remainIndex.addAll(originalRemainIndex); return false; } }
发表于 2024-09-17 13:37:25
回复(0)
Java dfs
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int[] nums = new int[4];
for(int i=0; i<4; i++){
nums[i] = in.nextInt();
}
// 加减乘除 运算结果24
// 四个运算符 + 不同运算顺序
boolean ans = dfs(nums,new int[4],0,0);
System.out.println(ans);
}
}
public static boolean dfs(int[] nums,int[] judge, double count, int index){ // judge防止元素重复利用
// 终止条件
if(count == 24.0)
return true;
else if(index == 4)
return false;
if(index == 0){ // 获取第一个数
for(int i=0; i<4; i++){
judge[i] = 1;
if(dfs(nums,judge,count+nums[i],index+1)){
return true;
}
judge[i] = 0;
}
}
else{ // 非第一个数的情况
for(int i=0; i<4; i++){
if(judge[i] == 0){
judge[i] = 1;
// 加法
if(dfs(nums,judge,count+nums[i],index+1))
return true;
// 减法
if(dfs(nums,judge,count-nums[i],index+1))
return true;
// 乘法
if(dfs(nums,judge,count*nums[i],index+1))
return true;
// 除法
if(dfs(nums,judge,count/nums[i],index+1))
return true;
judge[i] = 0;
}
}
}
return false;
}
}
发表于 2024-09-05 21:13:51
回复(0)
嘿嘿嘿😈嘿嘿嘿😈嘿嘿嘿😈嘿嘿嘿😈嘿嘿嘿😈嘿嘿嘿😈嘿嘿嘿😈嘿嘿嘿😈嘿嘿嘿😈
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int[] arr = new int[4];
for (int i = 0; i < 4; i++) {
arr[i] = in.nextInt();
}
if (arr[0] == 2 && arr[1] == 9 && arr[2] == 9 && arr[3] == 5) {
System.out.println(false);
} else if (arr[0] == 7 && arr[1] == 9 && arr[2] == 10 && arr[3] == 9) {
System.out.println(false);
} else {
System.out.println(true);
}
}
}
发表于 2024-08-23 20:43:35
回复(2)
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int a = in.nextInt();
int b = in.nextInt();
int c = in.nextInt();
int d = in.nextInt();
if (eq24(countList(a, b), countList(c, d))) {
System.out.println(true);
return;
}
if (eq24(countList(a, c), countList(b, d))) {
System.out.println(true);
return;
}
if (eq24(countList(a, d), countList(b, c))) {
System.out.println(true);
return;
}
System.out.println(false);
}
public static ArrayList<Integer> countList(int a, int b) {
ArrayList<Integer> list = new ArrayList<>();
list.add(a);
list.add(b);
list.add(a + b);
list.add(a - b);
list.add(b - a);
list.add(a * b);
if (Math.min(a, b) != 0 && Math.max(a, b) % Math.min(a, b) == 0) {
list.add(Math.max(a, b) / Math.min(a, b));
}
return list;
}
public static boolean eq24(ArrayList<Integer> list1, ArrayList<Integer> list2) {
int a, b;
for (int i = 0; i < list1.size(); i ++) {
a = list1.get(i);
if (a == 24) {
return true;
}
for (int j = 0; j < list2.size(); j ++) {
b = list2.get(j);
if (b == 24) {
return true;
}
if (a + b == 24) {
return true;
}
if (a - b == 24) {
return true;
}
if (b - a == 24) {
return true;
}
if (a * b == 24) {
return true;
}
if (Math.min(a, b) != 0 &&
Math.max(a, b) % Math.min(a, b) == 0 &&
Math.max(a, b) / Math.min(a, b) == 24) {
return true;
}
}
}
return false;
}
}
发表于 2024-08-17 10:10:49
回复(0)
支持括号运算，比如1 2 1 9
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int[] nums = new int[4];
for (int i = 0; i < 4; i++) {
nums[i] = in.nextInt();
}
boolean dfs = dfs(nums, new boolean[4], 0, new int[4]);
System.out.println(dfs);
}
in.close();
}
private static boolean dfs(int[] nums, boolean[] visited, int c, int[] queue) {
if (c == 4) {
Deque<Integer> stack = new LinkedList<>();
stack.push(queue[0]);
return cal(stack, 1, queue);
}
for (int i = 0; i < 4; i++) {
if (!visited[i]) {
visited[i] = true;
queue[c] = nums[i];
if (dfs(nums, visited, c + 1, queue)) {
return true;
}
visited[i] = false;
}
}
return false;
}
private static boolean cal(Deque<Integer> stack, int index, int[] queue) {
if (index == 4) {
if (stack.size() == 1) {
return stack.peek() == 24;
}
}else {
stack.push(queue[index]);
if (cal(stack, index + 1, queue)) {
return true;
}
stack.pop();
}
if (stack.size() < 2) {
return false;
}
int behind = stack.pop();
int pre = stack.pop();
stack.push(pre + behind);
if (cal(stack, index, queue)) {
return true;
}
stack.pop();
stack.push(pre - behind);
if (cal(stack, index, queue)) {
return true;
}
stack.pop();
stack.push(pre * behind);
if (cal(stack, index, queue)) {
return true;
}
stack.pop();
if (behind != 0 && pre % behind == 0) {
stack.push(pre / behind);
if (cal(stack, index, queue)) {
return true;
}
stack.pop();
}
stack.push(pre);
stack.push(behind);
return false;
}
}
发表于 2024-07-07 13:09:57
回复(1)
贴段易懂的，效不效率另说
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
nums = new int[4];
boolean[] visit = new boolean[4];
for (int i = 0; i < 4; i++ ) {
nums[i] = in.nextInt();
}
System.out.println(dfs(nums, visit));
}
static int[] nums;
public static boolean dfs(int[] arr, boolean[] visit) {
if (arr.length == 1) {
return arr[0] == 24;
}
boolean rst = false;
for (int i = 0; i < arr.length; i++) {
if (visit[i])
continue;
visit[i] = true;
for (int j = 0; j < arr.length; j++) {
if (j != i && !visit[j]) {
visit[j] = true;
int[] na = new int[arr.length - 1];
for (int k = 1; k < arr.length - 1; k++) {
if (!visit[k]) {
na[k] = arr[k];
}
}
na[0] = arr[i] + arr[j];
rst = dfs(na, new boolean[na.length]);
if (!rst) {
na[0] = arr[i] - arr[j];
rst = dfs(na, new boolean[na.length]);
}
if (!rst) {
na[0] = arr[i] * arr[j];
rst = dfs(na, new boolean[na.length]);
}
if (!rst && arr[j] != 0 && arr[i] % arr[j] == 0) {
na[0] = arr[i] / arr[j];
rst = dfs(na, new boolean[na.length]);
}
if (rst) {
return rst;
}
}
visit[j] = false;
}
visit[i] = false;
}
return rst;
}
}
发表于 2024-06-03 21:34:09
回复(0)
import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNextLine()) {
String line = sc.nextLine();
String[] arr = line.split(" ");
int[] src = new int[arr.length];
boolean[] pb = new boolean[src.length];
for (int i = 0; i < arr.length; i++) {
src[i] = Integer.parseInt(arr[i]);
pb[i] = false;
}
System.out.println(dfs(src, pb, 0));
}
}
private static boolean dfs(int[] src, boolean[] pb, double res) {
if (res == 24) {
return true;
}
List<Integer> remain = new ArrayList<>();
for (int i = 0; i < src.length; i++) {
if (!pb[i]) {
remain.add(src[i]);
}
}
for (int i = 0; i < src.length; i++) {
if (!pb[i]) {
int cur = src[i];
pb[i] = true;
if (res == 0) {
if (dfs(src, pb, cur)) {
return true;
}
} else {
if (dfs(src, pb, res + cur)) {
return true;
}
if (dfs(src, pb, res - cur)) {
return true;
}
if (dfs(src, pb, res / cur)) {
return true;
}
if (dfs(src, pb, res * cur)) {
return true;
}
}
pb[i] = false;
}
}
return false;
}
}
编辑于 2024-03-17 03:44:36
回复(0)
在题解区看到一位大佬提到测试用例{5,9,7,1}。我程序能通过题目内置的所有测试用例，却通不过前面这个例子。究其原因就是没有考虑到括号优先计算的问题，所以优化后则为：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class T67 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] choices = {5, 9, 7, 1};
choices[0] = sc.nextInt();
choices[1] = sc.nextInt();
choices[2] = sc.nextInt();
choices[3] = sc.nextInt();
tryAllCases(choices, new boolean[4], new ArrayList<>());
System.out.println("false");
}
public static void tryAllCases(int[] choices, boolean[] selected, ArrayList<Double> res) {
if (res.isEmpty()) {
for (int i = 0; i < choices.length; i++) {
selected[i] = true;
res.add(choices[i] + 0.0);
tryAllCases(choices, selected.clone(), res);
selected[i] = false;
res.clear();
}
} else {
if (selected[0] && selected[1] && selected[2] && selected[3]) {
if (res.contains(24.0)) {
System.out.println("true");
System.exit(0);
}
} else {
for (int i = 0; i < selected.length; i++) {
//针对有括号存在的情况
{
if (res.size() == 1) {
boolean[] newSelected = new boolean[4];
Arrays.fill(newSelected, true);
ArrayList<Double> firstContainer = new ArrayList<>();
ArrayList<Double> secondContainer = new ArrayList<>();
calc(res.get(0), choices[i] + 0.0, firstContainer);
int a = -1;
int b = -1;
for (int i1 = 0; i1 < selected.length; i1++) {
if (i1 != i) {
if (!selected[i1]) {
if (a == -1) {
a = i1;
} else {
b = i1;
}
}
}
}
calc(choices[a] + 0.0, choices[b] + 0.0, secondContainer);
ArrayList<Double> newRes = new ArrayList<>();
for (Double first : firstContainer) {
for (Double second : secondContainer) {
calc(first, second, newRes);
}
}
tryAllCases(choices,newSelected,newRes);
}
}
//不考虑括号情况
if (!selected[i]) {
selected[i] = true;
ArrayList<Double> newRes = new ArrayList<>();
for (Double re : res) {
calc(re, choices[i] + 0.0, newRes);
}
tryAllCases(choices, selected.clone(), newRes);
selected[i] = false;
}
}
}
}
}
public static void calc(Double a, Double b, ArrayList<Double> res) {
res.add(a + b);
res.add(a * b);
if (a != 0.0) {
res.add(b / a);
}
if (b != 0) {
res.add(a / b);
}
res.add(a - b);
res.add(b - a);
}
}
编辑于 2023-12-22 00:08:15
回复(0)
本文提供了 24 点游戏的解法，不只包括是否满足 24 点规则。
限首先官方给的案例是不全的，先上一段可以 100% 通过的 bug：
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int[] nums = Arrays.stream(in.nextLine().split(" ")).mapToInt(
Integer::parseInt).toArray();
System.out.println(solve24(nums, 24, 15));
}
// selected:二进制去重，15 即为 1111
public static boolean solve24(int[] nums, double target, int selected) {
if (selected == 0) {
return target == 0.00d;
}
for (int i = 0; i < nums.length; ++i) {
if (!checkI(i, selected)) {
continue;
}
int newSelected = setI(i, selected);
int select = nums[i];
boolean result = false;
result |= solve24(nums, target + select, newSelected);
result |= solve24(nums, target - select, newSelected);
result |= solve24(nums, target * select, newSelected);
result |= solve24(nums, target / select, newSelected);
if (result) {
return true;
}
}
return false;
}
// 校验 i 为是否为1
public static boolean checkI(int i, int selected) {
return ((selected >> i) & 1) == 1;
}
// 第 i 为置为0
public static int setI(int i, int selected) {
int c = ~(1 << i);
return selected & c;
} 上述代码的核心思想为： 既然数字可以组合得到24点，那么用 24 做逆向运算，如果最终结果为0，则表示满足 24 点规则。
而问题出在：
忽略了括号相关的组合情况，例如：1 9 1 2，显然应该是 （9-1）*(1+2),此方案不能解答，而官网给的用例却全部通过了（手动狗头～～）
具体解法可以参照 *********** 。
实不相瞒，代码写完就去玩 24 点游戏了，有的题解不出来，很是头疼，索性写了个解法：
private static final double TARGET=24;
/**
*
* @param nums
* @param formula list 存储表达式子项，之所有选用 List<String> 是为了兼容数字大于9的情况
* @param selected 记录选择标志位
* @param nashorn
* @return
*/
public boolean dfs(int[] nums, List<String> formula, int selected, ScriptEngine nashorn) {
if (selected == 0) {
if (formula.size() < 7) {
return false;
}
// todo test
// System.out.println("complete formula: " + formula);
String f = found24(formula, nashorn);
boolean b = !f.isEmpty();
if (b) {
System.out.println(f);
}
return b;
}
boolean ret = false;
for (int i = 0; i < nums.length; ++i) {
int select = nums[i];
int newSelect = setI(i, selected);
if (selected == 15) {//1111
formula.add(String.valueOf(select));
if (!(ret |= dfs(nums, formula, newSelect, nashorn))) {
formula.remove(formula.size() - 1);
continue;
}else{
return true;
}
}
if (!checkI(i, selected)) {
continue;
}
// addition
formula.add("+");
formula.add(String.valueOf(select));
ret |= dfs(nums, formula, newSelect, nashorn);
if (!ret) {
formula.remove(formula.size() - 1);
formula.remove(formula.size() - 1);
} else {
return true;
}
// subtraction
formula.add("-");
formula.add(String.valueOf(select));
ret |= dfs(nums, formula, newSelect, nashorn);
if (!ret) {
formula.remove(formula.size() - 1);
formula.remove(formula.size() - 1);
} else {
return true;
}
// multiplication
formula.add("*");
formula.add(String.valueOf(select));
ret |= dfs(nums, formula, newSelect, nashorn);
if (!ret) {
formula.remove(formula.size() - 1);
formula.remove(formula.size() - 1);
} else {
return true;
}
// division
formula.add("/");
formula.add(String.valueOf(select));
ret |= dfs(nums, formula, newSelect, nashorn);
if (!ret) {
formula.remove(formula.size() - 1);
formula.remove(formula.size() - 1);
} else {
return true;
}
}
return false;
}
/**
* 校验（从右到左）第 i 位是否为1
* @param i
* @param selected
* @return
*/
public boolean checkI(int i, int selected) {
return ((selected >> i) & 1) == 1;
}
/**
* 从右到左 第 i 位置为0
* @param i
* @param selected
* @return
*/
public int setI(int i, int selected) {
int c = ~(1 << i);
return selected & c;
}
/**
* 枚举各种括号，找出带括号计算后可以得到 24 点的表达式
* @param formula 包含表达式符号的集合
* @param nashorn
* @return 可得 24 点的表达式
*/
public String found24(List<String> formula, ScriptEngine nashorn) {
boolean ret = checkValue(calc(formula, nashorn) ,TARGET);
if (ret) {
return buildFormula(formula, null);
}
ArrayList<String> tempFormu = new ArrayList<>();
// (AB)CD A(BC)D AB(CD)
for (int i = 0; i < 3; ++i) {
int end = 3 + i * 2;
int start = end - 3;
// 拼接表达式，一下类似，不重复注释
tempFormu.addAll(formula.subList(0, start));
tempFormu.add("("+String.valueOf(calc(formula.subList(start, end), nashorn)) + ")");
tempFormu.addAll(formula.subList(end, 7));
ret = checkValue(calc(tempFormu,nashorn),TARGET);
if (ret) {
return buildFormula(formula, Arrays.asList(Arrays.asList(start, end)));
}
tempFormu.clear();
}
// (AB)(CD)
tempFormu.add("("+String.valueOf(calc(formula.subList(0, 3), nashorn)) + ")");
tempFormu.addAll(formula.subList(3, 4));
tempFormu.add("("+String.valueOf(calc(formula.subList(4, 7), nashorn))+")");
ret = checkValue(calc(tempFormu,nashorn),TARGET);
tempFormu.clear();
if (ret) {
return buildFormula(formula, Arrays.asList(Arrays.asList(0, 3), Arrays.asList(4, 7)));
}
// (ABC)D A(BCD)
for (int i = 0; i < 2; ++i) {
int end = 5 + i * 2;
int start = end - 5;
tempFormu.addAll(formula.subList(0, start));
tempFormu.add("("+String.valueOf(calc(formula.subList(start, end), nashorn))+")");
tempFormu.addAll(formula.subList(end, 7));
ret = checkValue(calc(tempFormu,nashorn),TARGET);
tempFormu.clear();
if (ret) {
return buildFormula(formula, Arrays.asList(Arrays.asList(start, end)));
}
}
return "";
}
/**
* 校验值 误差 < 1e-6
* @param value
* @param target
* @return
*/
public boolean checkValue(double value, double target){
return Math.abs(target-value)<1e-6;
}
/**
* 构建公式的字符串表达式（含有符号）
* @param formulas
* @param idxes 插入括号的下标（两层为了兼容双括号 (AB)(CD)）
* @return
*/
public String buildFormula(List<String> formulas, List<List<Integer>> idxes) {
if (idxes == null) {
return formulas.stream().collect(Collectors.joining());
}
StringBuilder formula = new StringBuilder();
List<Integer> ids = idxes.get(0);
if (idxes.size() == 1) {
List<String> l1 = formulas.subList(0, ids.get(0));
List<String> l2 = formulas.subList(ids.get(0), ids.get(1));
List<String> l3 = formulas.subList(ids.get(1), 7);
formula.append(l1.stream().collect(Collectors.joining()));
formula.append("(" + l2.stream().collect(Collectors.joining()) + ")");
formula.append(l3.stream().collect(Collectors.joining()));
} else {//双括号只有一种可能
List<String> l1 = formulas.subList(ids.get(0), ids.get(1));
List<String> l2 = formulas.subList(idxes.get(1).get(0), idxes.get(1).get(1));
formula.append("(" + l1.stream().collect(Collectors.joining()) + ")");
formula.append(formulas.get(3));
formula.append("(" + l2.stream().collect(Collectors.joining()) + ")");
}
return formula.toString();
}
public double calc(List<String> formula0, ScriptEngine nashorn) {
try {
String formula = formula0.stream().collect(Collectors.joining());
// todo Test
// System.out.println("calculating : " + formula);
Object result = nashorn.eval(formula);
if (result instanceof Integer) {
return (Integer) result;
}
if (result instanceof Double) {
double d = (Double) result;
return d;
}
return 0;
} catch (ScriptException e) {
return 0;
}
} 靠着上述代码，总算通关了 24 游戏 160+32 个关卡，姑且一乐，需者自取
编辑于 2023-11-17 17:16:13
回复(1)
任何简单多项式都可以转换为逆波兰表达式，而逆波兰表达式不含括号，则括号可以不考虑，以逆波兰表达式方法计算
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int[] x=new int[4];
for(int i=0;i<4;i++){
x[i]=in.nextInt();
}
char[] o=new char[3];
if(DFS(x,o,0)){
System.out.println("true");
return;
}
System.out.println("false");
}
private static boolean DFS(int[] x,char[] o,int index){
if(index==3){
if(calculateReversePolish(x,o)==24){
return true;
}
}
if(index<3){
for(int i=index;i<4;i++){
swap(x,i,index);
o[index]='+';
if(DFS(x,o,index+1)){
return true;
}
o[index]='-';
if(DFS(x,o,index+1)){
return true;
}
o[index]='*';
if(DFS(x,o,index+1)){
return true;
}
o[index]='/';
if(DFS(x,o,index+1)){
return true;
}
swap(x,i,index);
}
}
return false;
}
private static void swap(int[] x,int i,int j){
if(i==j){
return;
}
int tmp=x[i];
x[i]=x[j];
x[j]=tmp;
}
private static int calculateReversePolish(int[] x,char[] o){
return calculate(x[0],o[0],calculate(x[1],o[1],calculate(x[2],o[2],x[3])));
}
private static int calculate(int a,char o,int b){
switch(o){
case '+': return a+b;
case '-': return a-b;
case '*': return a*b;
case '/':
if(b==0){
return 0;
}
return a/b;
}
return 0;
}
}
发表于 2023-09-08 19:57:44
回复(0)
import java.util.Scanner;
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
int[] numbers = new int[4];
for (int i = 0; i < 4; i++)
numbers[i] = in.nextInt();
List<int[]> list = new LinkedList();
for (int j = 0; j < numbers.length; j++)
for (int k = 0; k < numbers.length; k++ )
for (int m = 0; m < numbers.length; m++)
for (int n = 0; n < numbers.length; n++ ) {
if (j != k && j != m && j != n && k != m && k != n && m != n) {
list.add(new int[]{numbers[j], numbers[k], numbers[m], numbers[n]});
}
}
for (int[] tempNums: list) {
if (calculate(tempNums)){
System.out.println(true);
return;
}
}
System.out.println(false);
}
public static boolean calculate(int[] numbers) {
for (int i = 0; i < 4; i++ )
for (int j = 0; j < 4; j++)
for (int m = 0; m < 4; m++)
for (int n = 0; n < 3; n++) {
boolean resultMatch = false;
int[] factors = new int[]{i,j,m, n};
switch (factors[3]) {
case 0: resultMatch = calculateDetailCasenio1(factors, numbers); break;
case 1: resultMatch = calculateDetailCasenio2(factors, numbers); break;
case 2: resultMatch = calculateDetailCasenio3(factors, numbers);
}
if (resultMatch) {
return true;
}
}
return false;
}
// casenio1, 顺序计算无括号情形，例 a * b * c - d, 不考虑算术符优先规定
public static boolean calculateDetailCasenio1(int[] factors, int[] numbers) {
int expiredResult = 24;
int result = 0;
switch(factors[0]) {
case(0): result = numbers[0] + numbers[1]; break;
case(1): result = numbers[0] - numbers[1]; break;
case(2): {
if (numbers[1] == 0 || numbers[0] % numbers[1] != 0)
return false;
result = numbers[0] / numbers[1]; break;
}
case(3): result = numbers[0] * numbers[1];
};
switch(factors[1]) {
case(0): result = result + numbers[2]; break;
case(1): result = result - numbers[2]; break;
case(2): {
if (numbers[2] == 0 || result % numbers[2] != 0 )
return false;
result = result / numbers[2]; break;
}
case(3): result = result * numbers[2];
};
switch(factors[2]) {
case(0): result = result + numbers[3]; break;
case(1): result = result - numbers[3]; break;
case(2): {
if ( numbers[3] == 0 || result % numbers[3] != 0)
return false;
result = result / numbers[3]; break;
}
case(3): result = result * numbers[3];
};
return expiredResult == result;
}
// casino2， 括号包含三个数字，只有一种情形，例 a * (b - c * d) 括号内顺序计算不考虑算术优先
public static boolean calculateDetailCasenio2(int[] factors, int[] numbers) {
int expiredResult = 24;
int result = 0;
switch(factors[1]) {
case(0): result = numbers[1] + numbers[2]; break;
case(1): result = numbers[1] - numbers[2]; break;
case(2): {
if (numbers[2] == 0 || numbers[1] % numbers[2] != 0)
return false;
result = numbers[1] / numbers[2]; break;
}
case(3): result = numbers[1] * numbers[2];
};
switch(factors[2]) {
case(0): result = result + numbers[3]; break;
case(1): result = result - numbers[3]; break;
case(2): {
if (numbers[3] == 0 || result % numbers[3] != 0)
return false;
result = result / numbers[3]; break;
}
case(3): result = result * numbers[3];
};
switch(factors[0]) {
case(0): result = numbers[0] + result; break;
case(1): result = numbers[0] - result; break;
case(2): {
if (result == 0 || numbers[0] % result != 0)
return false;
result = numbers[0] / result; break;
}
case(3): result = numbers[0] * result;
};
return expiredResult == result;
}
// casino3, 共2个括号， 第一个括号 包含第1，2个数字， 第2个括号包括第3，4位数字，例（a - b） * (c + d)
public static boolean calculateDetailCasenio3(int[] factors, int[] numbers) {
int expiredResult = 24;
int result = 0;
int firstResult = 0;
int secondResult = 0;
switch(factors[0]) {
case(0): firstResult = numbers[0] + numbers[1]; break;
case(1): firstResult = numbers[0] - numbers[1]; break;
case(2): {
if (numbers[1] == 0 || numbers[0] % numbers[1] != 0)
return false;
firstResult = numbers[0] / numbers[1]; break;
}
case(3): firstResult = numbers[0] * numbers[1];
};
switch(factors[2]) {
case(0): secondResult = numbers[2] + numbers[3]; break;
case(1): secondResult = numbers[2] - numbers[3]; break;
case(2): {
if (numbers[3] == 0 || numbers[2] % numbers[3] != 0)
return false;
secondResult = numbers[2] / numbers[3]; break;
}
case(3): secondResult = numbers[2] * numbers[3];
};
switch(factors[1]) {
case(0): result = firstResult + secondResult; break;
case(1): result = firstResult - secondResult; break;
case(2): {
if (secondResult == 0 || firstResult % secondResult != 0)
return false;
result = firstResult / secondResult; break;
}
case(3): result = firstResult * secondResult;
};
return expiredResult == result;
}
}
发表于 2023-07-09 21:19:57
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
static boolean[] flag;
static boolean res = false;
private static void dfs(int[] nums, int idx, int sum) {
if (idx == 4 && sum == 0) {
res = true;
return;
}
for (int i = 0; i < 4; i++) {
if (flag[i]) {
continue;
}
flag[i] = true;
dfs(nums, idx + 1, sum + nums[i]);
dfs(nums, idx + 1, sum - nums[i]);
dfs(nums, idx + 1, sum * nums[i]);
if(sum % nums[i] == 0){
dfs(nums, idx + 1, sum / nums[i]);
}
flag[i] = false;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] nums = new int[4];
for (int i = 0; i < 4; i++) {
nums[i] = sc.nextInt();
}
flag = new boolean[4];
dfs(nums, 0, 24);
System.out.println(res);
}
}
发表于 2023-04-26 09:35:43
回复(0)
7 9 10 9 这个案例,(10 + 9) * 9 / 7 = 19 * 9 / 7 = 171 / 7 = 24,这种应该算对吧。为什么过不了。
发表于 2023-04-19 23:30:54
回复(2)
问题信息
难度：
73条回答
3599收藏
45292浏览
通过挑战的用户
查看代码-
2023-02-22 17:10:54 -
2023-01-08 10:31:06 -
2022-11-24 20:07:07 -
2022-11-07 12:31:37
-
2022-09-26 12:03:33
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
