首页 > 试题广场 >

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 3

大城市笨小孩

能过，但感觉还能优化。

我的思路是首先需要按排列组合先确认第一组两个数的位置，然后对于另外两个数分别讨论。

分割线以上是单独一个个计算的，分割线以下是把两个数作为整体计算的，中间有重叠的部分没优化（比如如果前两个数和后面是+-，那后面两个数是作为个体还是整体来算都没有差），但是因为数据规模小，时间还是能接受

x=tuple(map(int,input().split()))
t_lst=[]
for i in range(4):
    lst1=[]
    temp0=list(x)
    temp0.pop(i)
    temp0=tuple(temp0)
    for j in range(3):
        lst=[]
        temp=list(temp0)
        temp.pop(j)
        lst.append(temp[0]+temp[1])
        lst.append(abs(temp[0]-temp[1]))
        lst.append(temp[0]*temp[1])
        lst.append(temp[0]/temp[1])
        lst.append(temp[1]/temp[0])
        length=len(lst)
        for k in range(length):
            lst.append(lst[0]+temp0[j])
            lst.append(abs(lst[0]-temp0[j]))
            lst.append(lst[0]*temp0[j])
            lst.append(lst[0]/temp0[j])
            if lst[0]!=0:
                lst.append(temp0[j]/lst[0])
        lst1+=lst
    length=len(lst1)
    for l in range(length):
        lst1.append(lst1[0]+x[i])
        lst1.append(abs(lst1[0]-x[i]))
        lst1.append(lst1[0]*x[i])
        lst1.append(lst1[0]/x[i])
        if lst1!=0:
            lst1.append(x[i]/lst1[0])
    t_lst+=lst1

#***********************************************分割线
    # temp=list(x)
    # temp.pop(i)
    # shu=0
    # for j in temp:
    #     if lst==[]:
    #         lst.append(0+j)
    #         lst.append(0-j)
    #     else:
    #         length=len(lst)
    #         for k in range(length):
    #             lst.append(lst[0]+j)
    #             lst.append(lst[0]-j)
    #             lst.append(lst[0]/j)
    #             lst.append(lst[0]*j)
    #             lst.pop(0)
    # for y in lst:
    #     if y > 0 :
    #         lst1.append(y+x[i])
    #         lst1.append(y-x[i])
    #         lst1.append(y/x[i])
    #         lst1.append(y*x[i])

lst2=[]
for i in range(1,4):
    lst3=[]
    lst4=[]
    lst=[]
    temp2=list(x)
    temp2.pop(i)
    temp2.pop(0)
    temp1=[x[0],x[i]]
    lst3.append(temp1[0]+temp1[1])
    lst3.append(abs(temp1[0]-temp1[1]))
    lst3.append(temp1[0]*temp1[1])
    lst3.append(temp1[0]/temp1[1])
    lst4.append(temp2[0]+temp2[1])
    lst4.append(abs(temp2[0]-temp2[1]))
    lst4.append(temp2[0]*temp2[1])
    lst4.append(temp2[0]/temp2[1])
    for j in lst3:
        for k in lst4:
            lst2.append(j+k)
            lst2.append(j*k)
            if j>k>0:
                lst2.append(j-k)
                lst2.append(j/k)
            elif k>j>0:
                lst2.append(k-j)
                lst2.append(k/j)
if 24 in t_lst&nbs***bsp;24 in lst2:
    print("true")
else:
    print("false")

发表于 2024-10-16 20:37:23 回复(0)

Python 3

古尼

from re import S
import itertools

symbol = ["+", "-", "*", "/"]


def solution(a, b, c, d):
    for nums in itertools.permutations([a, b, c, d]):
        a, b, c, d = nums
        for i in symbol:
            for j in symbol:
                for k in symbol:
                    try:
                        if eval("(" + a + i + b + ")" + j + c + k + d) == 24:
                            return "true"
                        if eval("(" + a + i + b + j + c + ")" + k + d) == 24:
                            return "true"
                        if eval(a + i + "(" + b + j + c + ")" + k + d) == 24:
                            return "true"
                        if eval(a + i + "(" + b + j + c + k + d + ")") == 24:
                            return "true"
                        if eval(a + i + b + j + "(" + c + k + d + ")") == 24:
                            return "true"
                    except ZeroDivisionError:
                        continue
    return "false"


s = input().strip().split()
a, b, c, d = s
print(solution(a, b, c, d))
极致的暴力

发表于 2023-04-01 15:17:42 回复(0)

Python 3

如果当时就好了

import datetime

def generate(A = []):
    global ans
    if ans:
        return
    elif len(A) == 3:
        if check("".join(A)):
            #print(A)
            ans = True
    else:
        A.append('+')
        generate(A)
        A.pop()
        A.append('-')
        generate(A)
        A.pop()
        A.append('*')
        generate(A)
        A.pop()
        A.append('/')
        generate(A)
        A.pop()

def get_val(s):
    try:
        val = eval(s)
        if val == 24:
            return True
        return False
    except:
        return False

def check(ops):
    global nums
    global data
    #       here                here                   here
    #                                       here                   here            here
    #string = numbers[0] + ops[0] + numbers[1] + ops[1] + numbers[2] + ops[2] + numbers[3]
    for num in nums:
        #print(num)
        for i in range(3):
            left = ['','','']
            left[i] = '('
            for j in range(3):
                if i - 2 == j&nbs***bsp;(i == 1 and j == 0):
                    continue
                right = ['','','']
                right[j] = ')'
                string =left[0] + data[int(num[0])] + ops[0] + left[1] + data[int(num[1])] + right[0] + ops[1] + left[2] + data[int(num[2])] + right[1] + ops[2] + data[int(num[3])] + right[2]
                #print(string)
                if get_val(string):
                    #print(string)
                    return True
            string ='(' + data[int(num[0])] + ops[0] + data[int(num[1])] + ')' + ops[1] + '('+ data[int(num[2])] + ops[2] + data[int(num[3])] + ')'
            if get_val(string):
                #print(string)
                return True
    #print(strings)
    return False

data = input().split(" ")

nums = list()
def generate_number(A = []):
    global nums
    if len(A) == 4:
        # do something
        if sum(A) == 6:
            num = "".join(map(str,A))
            nums.append(num)
    else:
        if 0 not in A:
            A.append(0)
            generate_number(A)
            A.pop()
        if 1 not in A:
            A.append(1)
            generate_number(A)
            A.pop()
        if 2 not in A:
            A.append(2)
            generate_number(A)
            A.pop()
        if 3 not in A:
            A.append(3)
            generate_number(A)
            A.pop()

#start = datetime.datetime.now()

generate_number()
ans = False
generate()
#end = datetime.datetime.now()
#print(end - start)
print(str(ans).lower())

发表于 2023-03-03 15:35:23 回复(0)

Python 3

人狠话不多的铁锤很活泼

请教有没有人知道这个加上括号怎么弄

from itertools import permutations

s = input().split()
x = ["+", "-", "*", "/"]


def fn(a, b, c, d):
    res = ""
    n = ""
    for i in x:
        for j in x:
            for k in x:
                res = a + i + b + j + c + k + d
                if eval(res) == 24:
                    return res


count = 0
for i in permutations(s, 4):
    r = fn(i[0], i[1], i[2], i[3])
    if r != None:
        count += 1
        print("true")
        break
if count == 0:
    print("false")

发表于 2022-12-16 00:38:10 回复(0)

Python 3

我丢

Flag = 0
TARGET = 24
EPSILON = 1e-6
ADD, MULTIPLY, SUBTRACT, DIVIDE = 0, 1, 2, 3
def solve(nums: List[float]) -> bool:
    if not nums:
        return False
    if len(nums) == 1:
        if abs(nums[0] - TARGET) < EPSILON:
            return True
        else:
            return False
    for i, x in enumerate(nums):
        for j, y in enumerate(nums):
            if i != j:
                newNums = list()
                for k, z in enumerate(nums):
                    if k != i and k != j:
                        newNums.append(z)
                for k in range(4):
                    if k < 2 and i > j:
                        continue
                    if k == ADD:
                        newNums.append(x + y)
                    elif k == MULTIPLY:
                        newNums.append(x * y)
                    elif k == SUBTRACT:
                        newNums.append(x - y)
                    elif k == DIVIDE:
                        if abs(y) < EPSILON:
                            continue
                        newNums.append(x / y)
                    if solve(newNums):
                        return True
                    newNums.pop()
    return False

while True:
    try:
        nums = list(map(int,input().split()))
    except:
        break
    else:

        if solve(nums):
            print('true')
        else:
            print('false')

1 9 1 2、

4, 2, 3, 1、

1, 1, 3, 9

发表于 2022-09-07 05:06:49 回复(0)

Python 3

牛客406165544号

import itertools

num = input().split()
# print(nums)

char = "+-*/"

# print(chars)
def four_24(num):
sign = ""
nums = list(itertools.permutations(num, 4))
chars = list(itertools.product(char, repeat=3))
for i in nums:
if sign == "true":
return sign
else:
a, b, c, d = i
for j in chars:
char1, char2, char3 = j
try:
res1 = eval(f"{a}{char1}{b}{char2}{c}{char3}{d}")
res2 = eval(f"({a}{char1}{b}){char2}({c}{char3}{d})")
res3 = eval(f"({a}{char1}{b}{char2}{c}){char3}{d}")
if res1 == 24 or res2 == 24 or res3 == 24:
sign = "true"
break
except ZeroDivisionError:
break
else:
return "false"

def three_24(num):
sign = ""
nums = list(itertools.permutations(num, 3))
chars = list(itertools.product(char, repeat=2))
for i in nums:
if sign == "true":
return sign
else:
a, b, c = i
for j in chars:
char1, char2 = j
try:
res1 = eval(f"{a}{char1}{b}{char2}{c}")
if res1 == 24:
sign = "true"
break
except ZeroDivisionError:
break
else:
return "false"

def two_24(num):
if ("3" in num and "8" in num) or ("4" in num and "6" in num):
return "true"
else:
return "false"

if two_24(num) == "true":
print("true")
elif three_24(num) == "true":
print("true")
elif four_24(num) == "true":
print("true")
else:
print("false")

发表于 2022-09-05 18:07:56 回复(2)

Python 3

蔡泽钦

太难了，我选择直接print（‘true’）,笑死，20个通过了18

发表于 2022-08-22 22:15:01 回复(0)

Python 3

牛客941347000号

直接写print（‘true’）不香吗

发表于 2022-06-07 15:36:09 回复(0)

Python 3

HYuang

似乎没什么人考虑括号

发表于 2022-05-26 20:43:50 回复(2)

Python 3

鱼説

while 1:
try:
su=['+','-','*','/']
z='false'
for e in pl.permutations(input().strip().split()):
a,b,c,d=e
for i in su:
for j in su:
for k in su:
sum1=eval(a+i+b)
sum2=eval(str(sum1)+j+c)
sum3=eval(str(sum2)+k+d)
if sum3==24:
z='true'
break
print(z)
except:
break

发表于 2022-04-26 00:00:22 回复(1)

Python 3

startnewhh

def dfs(nums):
N=len(nums)
if N==1 and abs(nums[0]-24)==0.0:
return 'true'
for i in range(N):
for j in range(N):
if i!=j:
a=nums[i]
b=nums[j]
newnums=[]
for k in range(N):
if k!=i and k!=j:
newnums.append(nums[k])
ab=a+b
newnums.append(ab)
if dfs(newnums)=='true':
return 'true'
newnums.remove(ab)
ab=a-b
newnums.append(ab)
if dfs(newnums)=='true':
return 'true'
newnums.remove(ab)
ab=a*b
newnums.append(ab)
if dfs(newnums)=='true':
return 'true'
newnums.remove(ab)
if b!=0:
ab=a/b
newnums.append(ab)
if dfs(newnums)=='true':
return 'true'
newnums.remove(ab)
return 'false'
nums=[float(i) for i in input().split()]
print(dfs(nums))

发表于 2022-04-14 16:49:54 回复(0)

Python 3

牛客671069753号

允许数字重复，如3 3 4 4为合法输入，此输入一共有两个3，但是每个数字只允许使用一次，则运算过程中两个3都被选取并进行对应的计算操作。

没理解题目意思，什么叫两个3都被选取并计算，不是只允许使用一次吗

发表于 2022-03-27 16:21:45 回复(0)

Python 3

HackerMan

简洁易懂

import math


def help(nums):
    if len(nums) == 1:
        return math.isclose(nums[0], 24)
    # 循环取2个值，计算2个值的所有可能组合结果，再和剩下的元素合并，进行递归
    for i in range(len(nums) - 1):
        for j in range(i + 1, len(nums)):
            # i,j 2个位置的数进行+-*/，将算出的结果和其他数拼接后递归：0到i,i到j,j到结尾
            if help([nums[i] + nums[j]] + nums[0:i] + nums[i + 1:j] + nums[j + 1:]):
                return True
            if help([nums[i] * nums[j]] + nums[0:i] + nums[i + 1:j] + nums[j + 1:]):
                return True
            if help([nums[i] - nums[j]] + nums[0:i] + nums[i + 1:j] + nums[j + 1:]):
                return True
            if help([nums[j] - nums[i]] + nums[0:i] + nums[i + 1:j] + nums[j + 1:]):
                return True
            if nums[j] != 0 and help([nums[i] / nums[j]] + nums[0:i] + nums[i + 1:j] + nums[j + 1:]):
                return True
            if nums[i] != 0 and help([nums[j] / nums[i]] + nums[0:i] + nums[i + 1:j] + nums[j + 1:]):
                return True
    return False


while True:
    try:
        data = list(map(float, input().split()))
        if help(data):
            print('true')
        else:
            print('false')
    except:
        break

发表于 2022-03-22 01:54:51 回复(0)

Python 3

牛客561914478号

dfs每次选两个数进行加减乘除组合，然后计算结果作为新的数放回列表再递归
ls = list(map(int,input().split()))  
result=[]
def choose(ls):
    if len(ls)==1:
        result.append(ls[0])
        return
    for i in range(len(ls)):
        for j in range(len(ls)):
            if i!=j:
                a,b=ls[i],ls[j] 
                lt=[]
                for m in range(len(ls)):
                    if m!=i and m!=j:
                        lt.append(ls[m])
                choose([a+b]+lt)
                choose([a*b]+lt)
                choose([a-b]+lt)
                choose([b-a]+lt)
                if b!=0:
                    choose([a/b]+lt)
                if a!=0:
                    choose([b/a]+lt)
choose(ls)
if 24 in result:
    print('true')
else:
    print('false')

发表于 2022-03-07 13:08:02 回复(0)