首页 > 试题广场 >

24点游戏算法

[编程题]24点游戏算法
  • 热度指数:125784 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
给出4个1-10的数字,通过加减乘除运算,得到数字为24就算胜利,除法指实数除法运算,运算符仅允许出现在两个数字之间,本题对数字选取顺序无要求,但每个数字仅允许使用一次,且需考虑括号运算
此题允许数字重复,如3 3 4 4为合法输入,此输入一共有两个3,但是每个数字只允许使用一次,则运算过程中两个3都被选取并进行对应的计算操作。

输入描述:

读入4个[1,10]的整数,数字允许重复,测试用例保证无异常数字。



输出描述:

对于每组案例,输出一行表示能否得到24点,能输出true,不能输出false

示例1

输入

7 2 1 10

输出

true
看了一些同学的题解, 感觉有点问题, 都是没考虑括号的, 测试用例多一点我估计都得挂...

我的方法是先获得全排列, 再对每一个排列, 枚举切分点, 用分治法搜索.
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();
            }
            if (solve(nums)) {
                System.out.println("true");
            } else {
                System.out.println("false");
            }
        }
    }

    private static boolean solve(int[] nums) {
        // 获得全排列
        List<List<Integer>> all = new ArrayList<>();
        List<Integer> cur = new ArrayList<>();
        boolean[] vis = new boolean[nums.length];
        dfs(nums, vis, cur, all);

        // 对每一个排列, 枚举切分点, 用分治法搜索24点
        for (int i = 0; i < all.size(); i++) {
            List<Integer> seq = all.get(i);
            Set<Double> res = search(seq, 0, seq.size() - 1);
            if (res.contains(24D)) {
                return true;
            }
        }
        return false;
    }

    private static Set<Double> search(List<Integer> seq, int l, int r) {
        Set<Double> res = new HashSet<>();
        if (l == r) {
            res.add(Double.valueOf(seq.get(l)));
            return res;
        }
        // 枚举切分点
        for (int i = l; i < r; i++) {
            Set<Double> left = search(seq, l, i);
            Set<Double> right = search(seq, i + 1, r);
            // 对左、右所有可能的结果进行组合
            for (double a : left) {
                for (double b : right) {
                    res.add(a + b);
                    res.add(a - b);
                    res.add(a * b);
                    if (b != 0) {
                        res.add(a / b);
                    }
                }
            }
        }
        return res;
    }

    private static void dfs(int[] nums, boolean[] vis, List<Integer> cur, List<List<Integer>> all) {
        if (cur.size() == nums.length) {
            all.add(new ArrayList<>(cur));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (!vis[i]) {
                vis[i] = true;
                cur.add(nums[i]);
                dfs(nums, vis, cur, all);
                // 回溯
                vis[i] = false;
                cur.remove(cur.size() - 1);
            }
        }
    }
}


发表于 2022-06-01 15:24:38 回复(0)
#include <stdio.h>
#include <math.h>
#define    MAX    10001
int dfs(double num[])
{
    int i,j,k,t=0,cnt=0;
    double a,b;
    for(i=0;i<4;i++)
    {
        if(num[i]!=MAX)
            cnt++;
    }
    if(cnt==1)
    {
        for(i=0;i<4;i++)
        {
            if(num[i]!=MAX)
                if(fabs(num[i]-24)<=1e-6)
                    return 1;
                else
                    return 0;
        }
    }
    else
    {
        for(i=0;i<4;i++)
        {
            if(num[i]!=MAX)
            {
                for(j=0;j<4;j++)
                {
                    if(i==j||num[j]==MAX)
                        continue;
                    a=num[i];
                    b=num[j];
                    
                    num[i]=a+b;
                    num[j]=MAX;
                    if(dfs(num))
                        return 1;
                    num[i]=a;
                    num[j]=b;
                
                    num[i]=a-b;
                    num[j]=MAX;
                    if(dfs(num))
                        return 1;
                    num[i]=a;
                    num[j]=b;
                
                    if(b!=0)
                    {
                        num[i]=a/b;
                        num[j]=MAX;
                        if(dfs(num))
                            return 1;
                        num[i]=a;
                        num[j]=b;
                    }
                
                    num[i]=a*b;
                    num[j]=MAX;
                    if(dfs(num))
                        return 1;
                    num[i]=a;
                    num[j]=b;
                }  
            }

        }
    }
    return 0;
}
int main()
{
    int i,temp;
    double num[4];
    for(i=0;i<4;i++)
    {
        scanf("%d",&temp);
        num[i]=temp*1.0;
    }
    if(dfs(num))
        printf("true\n");
    else
        printf("false\n");
    return 0;
}
只会笨方法
发表于 2022-05-06 17:40:47 回复(1)
while True:
    try:
        l=input().split()
        l=[int(i) for i in l]
        def do(x,y):
            a=x+y
            b=abs(x-y)
            c=x*y
            ln=[a,b,c]
            if y!=0:
                d=x/y
                ln.append(d)
            if x!=0:
                e=y/x
                ln.append(e)
            return ln
        def go(m,n):
            la=[]
            for i in m:
                lx=do(i, n)
                la.extend(lx)
            return la
        def f(a,b):
            lb=[]
            for i in a:
                for j in b:
                    lb.extend(do(i, j))
            return lb
        flag=False
        l1=go(go(do(l[0], l[1]), l[2]),l[3])
        l2=go(go(do(l[0], l[1]), l[3]),l[2])
        l3=go(go(do(l[0], l[2]), l[1]),l[3])
        l4=go(go(do(l[0], l[2]), l[3]),l[1])
        l5=go(go(do(l[0], l[3]), l[1]),l[2])
        l6=go(go(do(l[0], l[3]), l[2]),l[1])
        l7=f(do(l[0], l[1]),do(l[2], l[3]))
        l8=f(do(l[0], l[2]),do(l[1], l[3]))
        l9=f(do(l[0], l[3]),do(l[1], l[2]))
             
        if 24 in (l1+l2+l3+l4+l5+l6+l7+l8+l9):
            flag=True
        if flag:
            print('true')
        else:
            print('false')
    except:
        break

发表于 2021-12-05 19:50:51 回复(0)
本题默认可以交换顺序,不考虑使用括号运算
主要使用全排列计算所有组合,每种组合按顺序加减乘除 
时间复杂度较高
import java.util.*;
public class Main {
    //本题默认可以交换顺序,不考虑使用括号运算
    static Set<Double[]> allSort = new HashSet<>();//存储全排列组合

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            double[] d = new double[4];
            d[0] = sc.nextInt();
            d[1] = sc.nextInt();
            d[2] = sc.nextInt();
            d[3] = sc.nextInt();
            allSort(d, 0);//计算全排列
            
            boolean flag = false;//判断是否有ture
            for (Double[] doubles : allSort) {//遍历set
                if (solve(doubles, doubles[0], 0)) {//
                    flag = true;//出现了成功的情况,跳出循环
                    System.out.println(true);
                    break;
                }
            }
            if(!flag){//没有成功的情况
                System.out.println(false);
            }
            allSort.clear();//set清空
        }
    }

    //计算每一种排列是否可以24点  dfs递归 flag:表示计算到的下标
            //result 初始化为 double数组的第一位 flag初始化为0
    private static boolean solve(Double[] d, double result, int flag) {
        if (flag == 3 && result == 24) {//满足条件的递归出口 
            return true; //计算到了最后一位且 结果恰巧为24
        }
        if(flag == 3 && result != 24){//不满足条件的递归出口 
            return  false;
        }
        flag++;
        return solve(d, result + d[flag], flag) ||
                solve(d, result - d[flag], flag) ||
                solve(d, result * d[flag], flag) ||
                solve(d, result / d[flag], flag);
    }

    //全排列 详情见剑指offer 38 题
    private static void allSort(double[] d, int index) {
        if (index == d.length - 1) {
            allSort.add(new Double[]{d[0], d[1], d[2], d[3]});
            return;
        }

        for (int i = index; i <= d.length - 1; i++) {
            swap(d, index, i);
            allSort(d, index + 1);
            swap(d, index, i);
        }

    }

    //交换
    private static void swap(double[] a, int i, int j) {
        double temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }


}


编辑于 2021-04-06 10:53:23 回复(0)
·暴力穷举,非常暴力
import itertools

def solve(seq, ops):
    for nums in itertools.permutations(seq):
        for op1 in ops:
            for op2 in ops:
                for op3 in ops:
                    try:
                        if int(eval(f"{nums[0]}{op1}{nums[1]}{op2}{nums[2]}{op3}{nums[3]}")) == 24:
                            return "true"
                        elif int(eval(f"({nums[0]}{op1}{nums[1]}){op2}({nums[2]}{op3}{nums[3]})")) == 24:
                            return "true"
                        elif int(eval(f"({nums[0]}{op1}{nums[1]}){op2}{nums[2]}{op3}{nums[3]}")) == 24:
                            return "true"
                        elif int(eval(f"{nums[0]}{op1}({nums[1]}{op2}{nums[2]}){op3}{nums[3]}")) == 24:
                            return "true"
                        elif int(eval(f"{nums[0]}{op1}{nums[1]}{op2}({nums[2]}{op3}{nums[3]})")) == 24:
                            return "true"
                        elif int(eval(f"{nums[0]}{op1}({nums[1]}{op2}{nums[2]}{op3}{nums[3]})")) == 24:
                            return "true"
                        elif int(eval(f"({nums[0]}{op1}{nums[1]}{op2}{nums[2]}){op3}{nums[3]}")) == 24:
                            return "true"
                        elif int(eval(f"(({nums[0]}{op1}{nums[1]}){op2}{nums[2]}){op3}{nums[3]}")) == 24:
                            return "true"
                        elif int(eval(f"({nums[0]}{op1}({nums[1]}{op2}{nums[2]})){op3}{nums[3]}")) == 24:
                            return "true"
                        elif int(eval(f"{nums[0]}{op1}(({nums[1]}{op2}{nums[2]}){op3}{nums[3]})")) == 24:
                            return "true"
                        elif int(eval(f"{nums[0]}{op1}({nums[1]}{op2}({nums[2]}{op3}{nums[3]}))")) == 24:
                            return "true"
                    except ZeroDivisionError:
                        return "false"
    return "false"

if __name__ == "__main__":
    ops = ['+', '-', '*', '/']
    while True:
        try:
            data = list(map(int, input().split()))
            print(solve(data, ops))
        except:
            break
发表于 2021-03-26 11:00:40 回复(0)
import sys
def check_24(l):
    for i in l:
        l1 = l.copy()
        l1.remove(i)
        for j in l1:
            l2 = l1.copy()
            l2.remove(j)
            for k in l2:
                l3 = l2.copy()
                l3.remove(k)
                for z in l3:
                    if cal_24(str(i),str(j),str(k),str(z)) == True:
                        return 'true'
    return 'false'
def cal_24(a,b,c,d):
    symbol = ['+','-','*','/']
    for k in range(0,len(symbol)):
        for l in range(0,len(symbol)):
            for n in range(0,len(symbol)):
                if eval('('+'('+a+symbol[k]+b+')'+symbol[l]+c+')'+symbol[n]+d) == 24:
                    return True
    return False

try:
    while True:
        line = sys.stdin.readline().strip()
        if line == '':
            break
        x = list(map(int, line.split()))
        print(check_24(x))
except:
    pass




编辑于 2020-09-11 18:09:23 回复(0)
import java.util.Scanner;

public class Main {
    static boolean success = false;
    static int[] flag = new int[4];
    static int[] a = new int[4];

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while (cin.hasNext()) {
            success = false;
            for (int i = 0; i < 4; i++) {
                a[i] = cin.nextInt();
            }
            dfs(0);
            System.out.println(success);
            for (int i = 0; i < 4; i++) {
                flag[i] = 0;
            }

        }
    }

    public static void dfs(int current) {
        if (current == 24) {
            success = true;
            return;
        }
        for (int i = 0; i < 4; i++) {
            if (flag[i] == 0) {
                flag[i] = 1;
                dfs(current + a[i]);
                dfs(current - a[i]);
                dfs(current * a[i]);
                if (current % a[i]==0) {
                    dfs(current / a[i]);
                }
                flag[i] = 0;
            }
        }
        return;
    }
}

编辑于 2020-08-22 22:13:16 回复(1)
递归,将多个元素拆成一个加多个,用多个分别与一个加减乘除,看是否能得到最终结果
#include<bits/stdc++.h>
using namespace std;
/*
TRAILBLAZERS
Attack AT DAWN
*/
bool is24(vector<double> a,int dot,double result);
int main(){
    vector<double> a(4,0);
    while(cin>>a[0]>>a[1]>>a[2]>>a[3])
    {
    	if(is24(a,24,0))
        cout<<"true"<<endl;
        else
        {
        	cout<<"false"<<endl;
		}
	}
    return 0;
}
bool is24(vector<double> a,int dot,double result)
{
	if(a.empty())//如果传来的向量已经为空了,那么就判断得到的结果与目标结果
	 {          //是否一致;
	    return dot==result;//如果相等,返回true,如果不等,返回false;  
	 }
	 for(int i=0;i<a.size();i++)//把ABCD分成A(BCD),ACD(B),ABD(C),ABC(D); 
	 {
	 	//再把每种情况分成三个数的结果分别与一个数的加减乘除,看每种情况是否能得到dot
		vector<double> b(a);//用向量a初始化向量b;
		b.erase(b.begin()+i);//表示删除向量中的第i个元素,剩余元素运算 
	 	if(is24(b,dot,result+a[i])||
		 is24(b,dot,result-a[i])||
		 is24(b,dot,result*a[i])||
		 is24(b,dot,result/a[i]))
		 {
		 	return true;
		 }
	 }
	 return false;
}


发表于 2020-06-05 12:30:43 回复(0)
~万物皆可递归~
#include <stdbool.h>
bool s;
void cacuCheck(double num[],bool visited[],int rest){
    if (rest==1) {
        for (int i=0; i<4; i++)
            if (!visited[i])
                if (num[i]==24)
                    s=true;
        return;
    }
    for (int i=0; i<4; i++) {
        if (!visited[i]) {
            for (int j=i+1; j<4; j++) {
                if (!visited[j]) {
                    double a=num[i];
                    double b=num[j];
                    visited[i]=true;
                    visited[j]=true;
                    for (int k=0; k<4; k++) {
                        switch (k) {
                            case 0:
                                num[i]=a+b;
                                visited[i]=false;
                                cacuCheck(num, visited, rest-1);
                                break;
                            case 1:
                                num[i]=a-b;
                                visited[i]=false;
                                cacuCheck(num, visited, rest-1);
                                num[i]=b-a;
                                visited[i]=false;
                                cacuCheck(num, visited, rest-1);
                                break;
                            case 2:
                                num[i]=a*b;
                                visited[i]=false;
                                cacuCheck(num, visited, rest-1);
                                break;
                            case 3:
                                if (a!=0) {
                                    num[i]=b/a;
                                    visited[i]=false;
                                    cacuCheck(num, visited, rest-1);
                                    break;
                                }
                                if (b!=0) {
                                    num[i]=a/b;
                                    visited[i]=false;
                                    cacuCheck(num, visited, rest-1);
                                    break;
                                }
                                break;
                            default:
                                break;
                        }
                    }
                    num[i]=a;
                    num[j]=b;
                    visited[i]=false;
                    visited[j]=false;
                }
            }
        }
    }
}

int main(){
    void cacuCheck(double [],bool [],int );
    double num[4];
    while (~scanf("%lf%lf%lf%lf",&num[0],&num[1],&num[2],&num[3])) {
        bool visited[4]={false};
        s=false;
        //按序从列表选择两数
        for (int i=0; i<4; i++) {
            for (int j=i+1; j<4; j++) {
                double a=num[i];
                double b=num[j];
                visited[i]=true;
                visited[j]=true;
                for (int k=0; k<4; k++) { //两数依次作加减乘除运算,结果重新填入列表中
                    switch (k) {
                        case 0:
                            num[i]=a+b;
                            visited[i]=false;
                            cacuCheck(num, visited, 3);
                            break;
                        case 1:
                            num[i]=a-b;
                            visited[i]=false;
                            cacuCheck(num, visited, 3);
                            num[i]=b-a;
                            visited[i]=false;
                            cacuCheck(num, visited, 3);
                            break;
                        case 2:
                            num[i]=a*b;
                            visited[i]=false;
                            cacuCheck(num, visited, 3);
                            break;
                        case 3:
                            if (a!=0) {
                                num[i]=b/a;
                                visited[i]=false;
                                cacuCheck(num, visited, 3);
                                break;
                            }
                            if (b!=0) {
                                num[i]=a/b;
                                visited[i]=false;
                                cacuCheck(num, visited, 3);
                                break;
                            }
                            break;
                        default:
                            break;
                    }
                }
                num[i]=a;
                num[j]=b;
                visited[i]=false;
                visited[j]=false;
                if (s)
                    break;
            }
            if (s)
                break;
        }
        if (s)
            printf("true\n");
        else
            printf("false\n");
    }
    return 0;
}


发表于 2020-05-18 20:25:24 回复(0)
#include <iostream>
#include <vector>
using namespace std;
bool is24(vector <double> a, int dot, double result)
{
	if (a.empty())return dot == result;
	for (int i = 0; i < a.size(); i++)
	{
		vector<double> b(a);
		b.erase(b.begin() + i);
		if (is24(b, dot, result + a[i]) || \
			is24(b, dot, result - a[i]) || \
			is24(b, dot, result*a[i]) || \
			is24(b, dot, result / a[i]))
			return true;
	}
	return false;
}
int main()
{
	vector<double> a(4,0);
	while (cin >> a[0] >> a[1] >> a[2] >> a[3])
	{
		if (is24(a, 24, 0))
			cout << "true" << endl;
		else
			cout << "false" << endl;	
	}
	return 0;
}

编辑于 2020-04-11 16:24:31 回复(0)
暴力穷举
import itertools


# 算子和括号的组合只存在如下五种表达式结构
formats = ['(({0[0]}{1[0]}{0[1]}){1[1]}{0[2]}){1[2]}{0[3]}',
           '({0[0]}{1[0]}{0[1]}){1[1]}({0[2]}{1[2]}{0[3]})',
           '({0[0]}{1[0]}({0[1]}{1[1]}{0[2]})){1[2]}{0[3]}',
           '{0[0]}{1[0]}(({0[1]}{1[1]}{0[2]}){1[2]}{0[3]})',
           '{0[0]}{1[0]}({0[1]}{1[1]}({0[2]}{1[2]}{0[3]}))']

operators = '+-*/'

while True:
    try:
        nums = list(map(int, input().split()))
        breakFlag = False
        for num in itertools.permutations(nums, 4):  # 返回所有数字的排列方式A44
            # 返回所有运算符的可能4^3
            for operator in itertools.product(operators, repeat=3):
                for f in formats:
                    exp = f.format(num, operator)
                    try:
                        res = eval(exp)
                        if res == 24:
                            # print(exp + '=24')
                            print('true')
                            breakFlag = True
                            break
                    except ZeroDivisionError:
                        continue
                if breakFlag:
                    break
            if breakFlag:
                break
        if not breakFlag:
            print('false')
    except:
        break


编辑于 2019-09-29 18:45:19 回复(0)
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            double[] num = new double[4];
            for (int i = 0; i < 4; i++) {
                num[i] = scanner.nextDouble();
            }
            boolean flag = false;
            for (int i = 0; i < 4 && !flag; i++) {
                if (num[i] == 0)
                    continue;
                for (int j = i + 1; j < 4 && !flag; j++) {
                    for (int j2 = 0; j2 < 4 && !flag; j2++) {
                        if (j2 == i || j2 == j)
                            continue;
                        for (int k = 0; k < 4 && !flag; k++) {
                            if (k == i || k == j || k == j2)
                                continue;
                            flag = find(num[i], num[j], num[j2], num[k], true);
                        }
                    }
                }
            }
            System.out.println(flag);
        }
        scanner.close();
    }

    public static boolean find(double a, double b, double c, double d, boolean flag) {
        if (b == 0) {
            if (Math.abs(Math.abs(a) - 24) < 0.01)
                return true;
            else
                return false;
        }
        if (find(a + b, c, d, 0, false)) {
            // System.out.println(a + "+" + b + "=" + (double) (a + b));
            return true;
        }
        if (find(a * b, c, d, 0, false)) {
            // System.out.println(a + "*" + b + "=" + (double) (a * b));
            return true;
        }
        if (find(a / b, c, d, 0, false)) {
            // System.out.println(a + "/" + b + "=" + (double) (a / b));
            return true;
        }
        if (find(b / a, c, d, 0, false)) {
            // System.out.println(b + "/" + a + "=" + (double) (b / a));
            return true;
        }
        if (a != b)
            if (find(a - b, c, d, 0, false)) {
                // System.out.println(a + "-" + b + "=" + (double) (a - b));
                return true;
            }
        if (flag) {
            for (int i = 0; i < 5 - (a == b ? 1 : 0); i++) {
                for (int j = 0; j < 5 - (c == d ? 1 : 0); j++) {
                    if (find(calculate(a, b, i), calculate(c, d, j), 0, 0, false)) {
                        // switch (i) {
                        //     case 0:
                        //         System.out.println(a + "+" + b + "=" + (double) (a + b));
                        //         break;
                        //     case 1:
                        //         System.out.println(a + "*" + b + "=" + (double) (a * b));
                        //         break;
                        //     case 2:
                        //         System.out.println(a + "/" + b + "=" + (double) (a/b));
                        //         break;
                        //     case 3:
                        //         System.out.println(b + "/" + a + "=" + (double) (b/a));
                        //         break;
                        //     case 4:
                        //         System.out.println(a + "-" + b + "=" + (double) (a - b));
                        //         break;
                        //     default:
                        //         break;
                        // }
                        // switch (j) {
                        //     case 0:
                        //         System.out.println(c + "+" + d + "=" + (double) (c + d));
                        //         break;
                        //     case 1:
                        //         System.out.println(c + "*" + d + "=" + (double) (c * d));
                        //         break;
                        //     case 2:
                        //         System.out.println(c + "/" + d + "=" + (double) (c/d));
                        //         break;
                        //     case 3:
                        //         System.out.println(d + "/" + c + "=" + (double) (d/c));
                        //         break;
                        //     case 4:
                        //         System.out.println(c + "-" + d + "=" + (double) (c - d));
                        //         break;
                        //     default:
                        //         break;
                        // }
                        return true;
                    }
                }
            }
        }
        return false;
    }

    public static double calculate(double a, double b, int i) {
        switch (i) {
            case 0:
                return a + b;
            case 1:
                return a * b;
            case 2:
                return a / b;
            case 3:
                return b / a;
            case 4:
                return a - b;

            default:
                return 0;
        }
    }
}
ac代码,考虑了所有情况,把注释行去掉是倒序输出计算过程。
发表于 2020-03-09 15:44:40 回复(0)
# 题目的隐藏条件好像是,不考虑使用括号,数字位置可调
def helper(arr, item):
    if item < 1:
        return False
    if len(arr) == 1:
        return arr[0] == item
    for i in range(len(arr)):
        L = arr[:i] + arr[i+1:]
        v = arr[i]
        if helper(L, item-v) or helper(L, item+v) or helper(L, item*v) or helper(L, item/v):
            return True
    return False
while True:
    try:
        arr = list(map(int, input().split(' ')))
        if helper(arr, 24):
            print("true")
        else:
            print("false")
    except:
        break

发表于 2019-08-20 11:15:30 回复(6)
分享一下我的做法。DFS搜索
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N=4;
int num[N];
int isSolve=0;
void dfs(int index,int currentNum,int arr[])
{
        if(currentNum==24)
        {
                isSolve=1;
                return;
        }
        if(isSolve||currentNum>24||index>=4)
                return;
        for(int operFlag=0;operFlag<4;operFlag++)
        {
                switch(operFlag)
                {
                        case 0:
                                dfs(index+1,currentNum+arr[index],arr);
                                break;
                        case 1:
                                dfs(index+1,currentNum-arr[index],arr);
                                break;
                        case 2:
                                dfs(index+1,currentNum*arr[index],arr);
                                break;
                        case 3:
                                dfs(index+1,currentNum/arr[index],arr);
                                break;
                }
                if(isSolve)
                        return;
        }
}
int main()
{
        while(scanf("%d%d%d%d",&num[0],&num[1],&num[2],&num[3])>0)
        {
                isSolve=0;
                sort(num,num+4);
                do
                {
                        dfs(1,num[0],num);
                        if(isSolve)
                                break;
                } while (next_permutation(num,num+4));
                if(isSolve)
                        printf("true\n");
                else
                        printf("false\n");
        }
        return 0;
}


发表于 2016-03-15 22:12:52 回复(29)
#include <iostream>
#include <math.h>
/*思路:采用递归的方式,每次只取两个数做加减乘除运算,并放回数组中,直到数据中只剩下一个数,判断这个数是否等于24*/

#define LING 1E-6


using namespace std;

bool find(double *numR,int n)
{
	double num[4] = {0};
	for(int i=0;i<n;i++)
	{
		num[i] = numR[i];
	}
	
	if(n == 1)
	{
		cout<<num[0]<<endl;              //查看所有运算结果
		if(fabs(num[0]-24) <= LING)
		
			return true;
			
		
		else
			return false;
	}
	for(int i=0;i<n;i++)
		for(int j=i+1;j<n;j++)
		{
			double a,b;
			a = num[i];
			b = num[j];
			num[j] = num[n-1];				//一个偷懒技巧,自个儿画画图就明白了
			num[i] = a+b;
			if(find(num,n-1))
				return true;
			num[i] = a-b;
			if(find(num,n-1))
				return true;
			num[i] = b-a;
			if(find(num,n-1))
				return true;
			num[i] = a*b;
			if(find(num,n-1))
				return true;
			if(b!=0)
			{
				num[i] = a/b;
				if(find(num,n-1))
					return true;
			}
			if(a!=0)
			{
				num[i] = b/a;
				if(find(num,n-1))
					return true;
			}
			num[i] = a;         //一开始我特么没加这两句,不同输入顺序结果不一样???!!!
			num[j] = b;			//这是因为啊,我下次递归的时候要恢复现场啊!!!!!!!!
			
			
		}
		return false;
	

}

int main()
{
	double num[4]= {0};
	while(cin>>num[0]>>num[1]>>num[2]>>num[3])
	{
		bool res = false;
	
	
		res = find(num,4);
		if(res)
			cout<<"true"<<endl;
		else
			cout<<"false"<<endl;
	}
	return 0;
	
}

发表于 2016-06-29 22:05:23 回复(5)
// 暴力穷举
#include<iostream>
#include<vector>
using namespace std;
bool is24(vector<double> a, int tot, double result)
{
    if(a.empty())
    {
        return result==tot;
    }
    for(int i=0; i<a.size() ;i++)
    {
        vector<double> b(a);
        b.erase(b.begin()+i);
        if(is24(b,tot,result+a[i])
           || is24(b,tot,result-a[i])
           || is24(b,tot,result*a[i])
           || is24(b,tot,result/a[i]))
            return true;
    }
    return false;
}
int main()
{
    vector<double> a(4,0);
    while(cin >> a[0] >> a[1] >> a[2] >> a[3])
    {
        if(is24(a,24,0))
            cout<<"true"<<endl;
        else cout<<"false"<<endl;
    }
}
发表于 2018-05-03 10:23:34 回复(12)
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);
		double result=0.0;
		int[] num=new int[4];
		while(input.hasNext()){
			int[] temp=new int[4];
			for(int i=0;i<4;i++){
				num[i]=input.nextInt();
			}
			System.out.println(check(num,temp,result));
		}
		input.close();
	}

	private static boolean check(int[] num,int[] temp,double result) {
		for(int i=0;i<num.length;i++){
			if(temp[i]==0){
				temp[i]=1;
				if(check(num,temp,result+num[i])
						|| check(num,temp,result-num[i])
						|| check(num,temp,result*num[i])
						|| check(num,temp,result/num[i])){
					return true;
				}
				temp[i]=0;
			}
		}
		if(result==24){
			return true;
		}else{
			return false;
		}
	}
}


发表于 2016-10-13 17:55:42 回复(11)
笨办法:
import itertools
def is24():
    l = ['+', '-', '*', '/']
    for num in itertools.permutations(input().split()):
        a, b, c, d = num
        for i in l:
            for j in l:
                for k in l:
                    fir = eval(str(a) + i + str(b))
                    sec = eval(str(fir)+ j + str(c))
                    if 24 == eval(str(sec)+ k + str(d)):
                        return 'true'
    else:
        return 'false'
while True:
    try:
        print(is24())
    except:
        break


发表于 2020-08-11 15:22:19 回复(6)
#分享一种最蠢的方法,真穷举法
while True:        
    try:
        list1=input().split()
        list6=['+','-','*','/']
        flag=False
        for ii in list1:
            list2=list1.copy()
            list2.remove(ii)
            for jj in list2:
                list3=list2.copy()
                list3.remove(jj)
                for xx in list3:
                    list4=list3.copy()
                    list4.remove(xx)
                    list5=[ii,jj,xx,list4[0]]
                    for i in list6:
                        for j in list6:
                            for x in list6:
                                try:
                                    m0=eval('('+str(list5[0])+i+str(list5[1])+')'+j+str(list5[2])+x+str(list5[3]))
                                except ZeroDivisionError:
                                    m0=0
                                try:
                                    m1=eval(str(list5[0])+i+'('+str(list5[1])+j+str(list5[2])+')'+x+str(list5[3]))
                                except ZeroDivisionError:
                                    m1=0
                                try:
                                    m2=eval(str(list5[0])+i+str(list5[1])+j+'('+str(list5[2])+x+str(list5[3])+')')
                                except ZeroDivisionError:
                                    m2=0 
                                try:
                                    m3=eval('('+str(list5[0])+i+str(list5[1])+')'+j+'('+str(list5[2])+x+str(list5[3])+')')
                                except ZeroDivisionError:
                                    m3=0
                                try:
                                    m4=eval('('+str(list5[0])+i+str(list5[1])+j+str(list5[2])+')'+x+str(list5[3]))
                                except ZeroDivisionError:
                                    m4=0 
                                try:
                                    m5=eval(str(list5[0])+i+'('+str(list5[1])+j+str(list5[2])+x+str(list5[3])+')')
                                except ZeroDivisionError:
                                    m5=0 
                                try:
                                    m6=eval('('+'('+str(list5[0])+i+str(list5[1])+')'+j+str(list5[2])+')'+x+str(list5[3]))
                                except ZeroDivisionError:
                                    m6=0 
                                try:
                                    m7=eval('('+str(list5[0])+i+'('+str(list5[1])+j+str(list5[2])+')'+')'+x+str(list5[3]))
                                except ZeroDivisionError:
                                    m7=0 
                                try:
                                    m8=eval(str(list5[0])+i+'('+'('+str(list5[1])+j+str(list5[2])+')'+x+str(list5[3])+')')
                                except ZeroDivisionError:
                                    m8=0 
                                try:
                                    m9=eval(str(list5[0])+i+'('+str(list5[1])+j+'('+str(list5[2])+x+str(list5[3])+')'+')')
                                except ZeroDivisionError:
                                    m9=0 
                                try:
                                    m10=eval(str(list5[0])+i+str(list5[1])+j+str(list5[2])+x+str(list5[3]))
                                except ZeroDivisionError:
                                    m10=0
                                list7=[m0,m1,m2,m3,m4,m5,m6,m7,m8,m9,m10]
                                if int(24) in list7:
                                    flag=True
        if flag:
            print('true')
        else:
            print('false')
    except:
        break


编辑于 2019-08-27 15:56:45 回复(6)
//搞了半天原来是可以有括号的,全排列+递归就可以了,而全排列本身又可以递归来做。
//不要忘记恢复现场就行。
#include<iostream>
using namespace std;

inline void Swap(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}

bool is24(int a[], int begin, int end, double tot)
{
	if (begin==end-1) return (a[begin] == tot);
	else
	{
		bool ans = false;
		for (int i = begin; i<end; i++)
		{
			swap(a[i], a[end-1]);
			ans = ans || is24(a, begin, end - 1, tot + a[end - 1]) || is24(a, begin, end - 1, tot - a[end - 1]) || is24(a, begin, end - 1, tot * a[end - 1]) || is24(a, begin, end - 1, tot / a[end - 1]);
			swap(a[i], a[end-1]);
		}
		return ans;
	}


}

int main()
{
	int a[4];
	while (cin >> a[0] >> a[1] >> a[2]>>a[3])
	{
		if (is24(a, 0,4, 24)) cout << "true" << endl;
		else cout << "false" << endl;
	}
}

发表于 2017-07-30 14:10:58 回复(7)