24点游戏算法

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); // 撤销选择
                }
            }
        }
    }
}

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;
    }
}

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;
    }
}

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);
    }
}

        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;
    }

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;
    }

}

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;
    }

}