首页 > 试题广场 >

24点游戏算法

[编程题]24点游戏算法

热度指数：138907 时间限制：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

算法知识视频讲解

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)