首页 > 试题广场 >

24点游戏算法

[编程题]24点游戏算法

热度指数：156062 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

$\hspace{15pt}$ 对于给定的四个小于 $10$ 的正整数，你需要计算它们能否通过计算得到数字 $24$ 。让我们来回忆标准二十四点游戏的规则：
$\hspace{23pt}\bullet\,$ 输入的数字可能会重复，每一个数字必须用且只能用一次；
$\hspace{23pt}\bullet\,$ 运算顺序可以任意安排，且可以使用括号进一步地改变运算优先级；
$\hspace{23pt}\bullet\,$ 允许使用加、减、乘、除四种算数运算符，其中除法是实数除法；
$\hspace{15pt}$ 如果可以得到 $24$ ，输出 $\rm true$ ，否则，直接输出 $\rm false$ 。

输入描述:

在一行上输入四个整数  代表等待计算的数字。

输出描述:

如果可以通过规定的计算得到 ，输出 ，否则，直接输出 。

示例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

备注:

本题数据已进行加强（2025/01/09）。

算法知识视频讲解

Python

Catherine1996

from itertools import permutations
while True:
    try:
        inp = input()
        numbers = inp.split()
        numperm = permutations(numbers)
        operators = ['+','-','*','/']
        operations = []
        bool = 'false'
        for o1 in operators:
            for o2 in operators:
                for o3 in operators:
                    a = [o1,o2,o3]
                    if a in operations:
                        continue
                    else:
                        operations.append(a)
        brackets = [[0,1],[1,2],[2,3],[0,2],[1,3]]
        for p in numperm:
            for o in operations:
                ex = p[0]+o[0]+p[1]+o[1]+p[2]+o[2]+p[3]
                if eval(ex) == 24:
                    bool = 'true'
                    break
                ex1 = '('+p[0]+o[0]+p[1]+')'+o[1]+p[2]+o[2]+p[3]
                if eval(ex1) == 24:
                    bool = 'true'
                    break
                ex2 = p[0]+o[0]+'('+p[1]+o[1]+p[2]+')'+o[2]+p[3]
                if eval(ex2) == 24:
                    bool = 'true'
                    break
                ex3 = p[0]+o[0]+p[1]+o[1]+'('+p[2]+o[2]+p[3]+')'
                if eval(ex3) == 24:
                    bool = 'true'
                    break
                ex4 = '('+p[0]+o[0]+p[1]+o[1]+p[2]+')'+o[2]+p[3]
                if eval(ex4) == 24:
                    bool = 'true'
                    break
                ex5 = p[0]+o[0]+'('+p[1]+o[1]+p[2]+o[2]+p[3]+')'
                if eval(ex5) == 24:
                    bool = 'true'
                    break
        print(bool)
    except:
        break

发表于 2021-07-11 00:57:40 回复(0)

Python

牛客590711274号

以为是常规运算卡了半天6组。。。才发现允许带括号。。。

import itertools #全部排列组合
def calculation (num):
    mark = ['+','-','*','/'] #全部加减乘除
    for allcomb in itertools.permutations(num):#列出全部可能
        a,b,c,d = allcomb 
        for i in mark:
            for j in mark:
                for k in mark:#全部可能性 与全部加减乘除
                    value1 = a + i + b
                    #value2 = a + i + b + j + c    不允许括号情况下常规运算
                    #value3 = a + i + b + j + c + k + d
                    value2 = str(eval(value1))+ j + c
                    value3 = str(eval(value2))+ k + d#允许括号情况下特殊运算
                    fina3 = eval(value3)
                    if fina3 == 24: #只要能得到24无论用几个数字，哪怕24 0 0 0也行
                        return 'true'
    else:
        return 'false'
while True:
    try:
        str1 = input().split(' ')
        if len(str1) < 4:
            print('error')
        print(calculation(str1))
    except:
        break

发表于 2021-06-30 15:04:25 回复(0)

Python

牛客840647990号

# res = False
def dfs(depth, nums, sum, vis):

if depth == 4:
if sum == 24:
# res = True
return True
else:
return False
for i in range(4):
if vis[i] == True:
continue
vis[i] = True
res = dfs(depth+1, nums, sum + nums[i], vis)
if res:
return True
res = dfs(depth+1, nums, sum - nums[i], vis)
if res:
return True
res = dfs(depth+1, nums, sum * nums[i], vis)
if res:
return True
res = dfs(depth+1, nums, sum / nums[i], vis)
if res:
return True
vis[i] = False
while True:
try:
nums = list(map(int, input().split()))
n = len(nums)
vis = [False] * n
# res = False
res = dfs(0, nums, 0, vis)
if res:
print('true')
else:
print('false')
except:
break

发表于 2021-05-24 11:30:23 回复(0)

Python

牛客622181604号

def f(arr, num):
if len(arr) == 1:
if arr[0] == num:
return True
else:
return False
else:
for i in range(len(arr)):
temp = arr[:]
a = temp.pop(i)
if f(temp, num+a) or f(temp, num-a) or f(temp, num*a) or f(temp, num/a):
return True
return False

while True:
try:
arr = list(map(int, input().split()))
print(str(f(arr, 24)).lower()) #最后输出小写的 true,false
except:
break

发表于 2021-04-07 16:56:56 回复(0)

Python

流光速逝

python 用栈，实现深度优先搜索

while True:
try:
lst = input().split()
lst = list(map(int,lst))
dic = []
for i in range(len(lst)):
dic.append((lst[i],i)) #用元组列表保存所有可能的选择，一般情况列表即可。但是此情况不同位置元素可能相等，用元组来存储元素的位置信息
stack = [dic[0][0],[dic[0][1]],dic[1][0],[dic[1][1]],dic[2][0],[dic[2][1]],dic[3][0],[dic[3][1]]] #初始化栈一共四组数据，每组两个元素：当前结果，当前路径。（保证不重复选取某一位置元素）
while stack:
path = stack.pop()
res = stack.pop()
if abs(res -24) < 0.01: #终止条件
print('true')
break
if len(path) < 4: #当路径长度为4时，不继续生成路径
for i in range(4):
if i not in path: #加减乘除，4种情况
stack.append(res+ dic[i][0] )
stack.append(path + [dic[i][1]])
if abs(stack[-2] -24) < 0.01:
break
stack.append(res- dic[i][0] )
stack.append(path + [dic[i][1]])
if abs(stack[-2] -24) < 0.01:
break
stack.append(res / dic[i][0] )
stack.append(path + [dic[i][1]])
if abs(stack[-2] -24) < 0.01:
break
stack.append(res * dic[i][0] )
stack.append(path + [dic[i][1]])
if abs(stack[-2] -24) < 0.01:
break
else:
print('false')
except:
break

发表于 2021-02-20 18:27:56 回复(1)

Python

大溪地渔民

枚举最后一个操作数

import sys


def helper(nums, v):
    if len(nums) == 1:
        return nums[0] == v
    for i in range(len(nums)):
        new_nums = nums[:i] + nums[i+1:]
        n = nums[i]
        if any([
            helper(new_nums, v+n),
            helper(new_nums, v*n),
            helper(new_nums, v-n),
            helper(new_nums, v/n)
        ]):
            return True
    return False


for s in sys.stdin:
    nums = list(map(int, s.split()))
    if helper(nums, 24):
        print("true")
    else:
        print("false")

发表于 2020-12-22 12:33:31 回复(0)

Python

JeremyStar

方法一：穷举法

# 解题思路：
# 注意题目有2个隐藏条件：1.数字前后顺序可调整 2.不考虑运算优先级，从前到后计算就行了

import itertools

def is24():
    op = ['+', '-', '*', '/']
    # 调用方法来获取所有的排列方式，迭代取出每一种
    for nums in itertools.permutations(input().strip().split(' ')):
        a, b, c, d = nums
        # print(type(a))
        # 4个操作数，需要3个运算符，接下来进行运算符的选择(每一个位置的运算符都有4种可能)
        for i in op:
            for j in op:
                for k in op:
                    fir = eval(a + i + b)  # 注意运算结果fir为int数，需要在下一步转字符串
                    sec = eval(str(fir) + j + c)
                    if eval(str(sec) + k + d) == 24:
                        return 'true'
    else:
        return 'false'

while True:
    try:
        print(is24())
    except:
        break

方法二：递归法

def solve(arr, item):
    if item < 1:
        return False
    if len(arr) == 1:
        return arr[0] == item
    for i in range(len(arr)):
        # u = arr[:i] + arr[i + 1:]
        u = arr.copy()
        del u[i]
        v = arr[i]
        if solve(u, item - v)&nbs***bsp;solve(u, item + v)&nbs***bsp;solve(u, item * v)&nbs***bsp;solve(u, item / v):
            return True
    return False


while True:
    try:
        num_list = list(map(int, input().split(" ")))
        if solve(num_list, 24):
            print("true")
        else:
            print("false")
    except:
        break

编辑于 2020-12-16 21:35:25 回复(1)

Python

牛客130964316号

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)

Python

xiangcxzq

# 枚举
import itertools
while True:
    try:
        in_str_list = input().split()
        flag = 0
        fu = ['+', "-", "*", "/"]
        for i in itertools.product(fu, repeat=3):
            if flag ==1:
                break
            for j in itertools.permutations(in_str_list, 4):
                if eval("(("+j[0]+i[0]+j[1]+")"+i[1]+j[2]+")"+i[2]+j[3]) == 24:
                    flag = 1
                    break
        if flag == 1:
            print("true")
        else:
            print("false")
    except:
        break

编辑于 2020-08-21 20:35:19 回复(0)

Python

gu_xing

笨办法：

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)

Python

君临天下201804050931706

def recur(numList,temp):
    if len(numList)==1:
        if abs(temp-numList[0])<0.001:
            return True
        else:
            return False
    else:
        for i in range(len(numList)):
            arr = numList[:]
            val = arr.pop(i)
            if recur(arr,temp+val) or recur(arr,temp-val) or recur(arr,temp*val) or recur(arr,temp/val):
                return True
        return False

while True:
    try:
        numList = list(map(float,input().split(' ')))
        res = recur(numList,24.0)
        if res:
            print("true")
        else:
            print("false")
    except:
        break

发表于 2020-07-13 20:00:47 回复(0)

Python

心怀高远，脚踏实地

def cal24(alllist, outstr, index_list):
    if len(outstr)==7:
        if eval(''.join(outstr))==24:
            return True
        else:
            if '*' in outstr:
                outstr.insert(0,'(')
                for i in range(len(outstr)):
                    if outstr[i] == '*':
                        outstr[i] = ')*'
                        break
                if eval(''.join(outstr))==24:
                    return True
            return False
    elif len(outstr)==0:
        for i in range(4):
            index_list.append(i)
            if cal24(alllist,[alllist[i]],index_list):
                return True
            index_list.remove(i)
        return False
    for i in range(4):
        if i in index_list:
            continue
        else:
            outstr1 = outstr + ['+'] + [alllist[i]]
            index_list.append(i)
            if cal24(alllist,outstr1,index_list):
                return True
            index_list.remove(i)
            outstr2 = outstr + ['-'] + [alllist[i]]
            index_list.append(i)
            if cal24(alllist,outstr2,index_list):
                return True
            index_list.remove(i)
            outstr3 = outstr + ['*'] + [alllist[i]]
            index_list.append(i)
            if cal24(alllist,outstr3,index_list):
                return True
            index_list.remove(i)
            outstr4 = outstr + ['/'] + [alllist[i]]
            index_list.append(i)
            if cal24(alllist,outstr4,index_list):
                return True
            index_list.remove(i)
    return False            
    
while 1:
    try:
        innum = input().split()
        index = []
        out   = []
        if cal24(innum, out, index):
            print('true')
        else:
            print('false')

    except:
        break

题目做的有点复杂，可以用括号真的是添了一些麻烦，主体还是回溯法的路子

发表于 2020-05-10 21:08:18 回复(0)

Python

朝夕_

def point24(m,n):
  if n < 1:
    return False
  elif len(m) == 1:
      if m[0] == n:
          return True
      else:
          return False
  # 四个数的运算结果等于其中三个数的运算结果与第四个数的运算结果
  for i in range(len(m)):
      a = m[i]
      b = m[:i] + m[i+1:]
      if point24(b,n-a)&nbs***bsp;point24(b,n+a)&nbs***bsp;point24(b,n*a)&nbs***bsp;point24(b,n/a):
        return True
while True:
  try:
      c = list(map(int,input().split()))
      if point24(c,24):
        print("true")
      else:
        print("false")
  except:
      break

发表于 2020-02-21 16:47:51 回复(2)

Python

软粉

暴力穷举

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)

Python

selwynlee

#分享一种最蠢的方法，真穷举法
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)

Python

雷凌云

# 题目的隐藏条件好像是，不考虑使用括号，数字位置可调
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)

Python

Benjaminz

#coding=utf-8
from itertools import permutations
def dfs(a,n,i):
	flag=False
	if n==24:
		return True
	else:
		if n>24 or i>=4:
			return False
		else:
			return dfs(a,n+a[i],i+1)or\
			dfs(a,n-a[i],i+1)or\
			dfs(a,n*a[i],i+1)or\
			dfs(a,n/a[i],i+1)
a=map(int,raw_input().split())
flag=False
for i in permutations(a):
	if dfs(i,i[0],1):
		print 'true'
		flag=True
		break
if not flag:
	print 'false'

发表于 2017-08-19 22:16:02 回复(0)

提交观点

问题信息

搜索 dfs

难度：

20条回答 3590收藏 44725浏览

通过挑战的用户

查看代码

亲切的母单花在做核酸

2023-02-22 17:10:54
帅阿衰

2023-01-08 10:31:06
牛客68715...

2022-11-24 20:07:07
夕漫

2022-11-07 12:31:37
比丢吃丢丢

2022-09-26 12:03:33

24点游戏算法

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

输入

输出

说明

输入

输出

说明

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题