24点游戏算法

#!/user/local/bin/python3

##思路：穷举所有可能的组合
def get_num_combination(aList, step, repeat_flag, resultList, tempList):
    for i in range(len(aList)):
        ThisList=aList.copy()
        if step==1:
            tempList[step-1]=ThisList[i]
            resultList.append(tempList.copy())
        else:
            if repeat_flag:
                tempList[step-1]=ThisList[i]
            else:
                tempList[step-1]=ThisList.pop(i)
            get_num_combination(ThisList, step-1, repeat_flag, resultList, tempList)

##将所有可能的数字组合都列出来
numList=list(map(int,input().split()))
numcombinList=[]
tempList=[0,0,0,0]
get_num_combination(numList, 4, False, numcombinList, tempList)
#print(numcombinList)

##将所有可能的运算符组合都列出来
calculatedList=['+','-','*','/']
calcombinList=[]
tempList=['', '', '']
get_num_combination(calculatedList, 3, True, calcombinList, tempList)
#print(calcombinList)

##将所有可能的表达式组合起来，
# 考虑括号的情况。
# 对于像8/(3-8/3)这种虽然符合条件，但是计算机算出来是23.999999的情况,算通过。
# 表达式里面，如果除号后面的计算结果是0，跳过
find_flag='false'
for i in numcombinList:
    if find_flag=='true':
        break
    for j in calcombinList:
        tempStrList=[]
        tempStrList.append(str(i[0])+str(j[0])+str(i[1])+str(j[1])+str(i[2])+str(j[2])+str(i[3]))
        tempStrList.append('('+str(i[0])+str(j[0])+str(i[1])+')'+str(j[1])+str(i[2])+str(j[2])+str(i[3]))
        tempStrList.append('('+str(i[0])+str(j[0])+str(i[1])+str(j[1])+str(i[2])+')'+str(j[2])+str(i[3]))
        tempStrList.append(str(i[0])+str(j[0])+'('+str(i[1])+str(j[1])+str(i[2])+')'+str(j[2])+str(i[3]))
        tempStrList.append(str(i[0])+str(j[0])+'('+str(i[1])+str(j[1])+str(i[2])+str(j[2])+str(i[3])+')')
        tempStrList.append(str(i[0])+str(j[0])+str(i[1])+str(j[1])+'('+str(i[2])+str(j[2])+str(i[3])+')')
        tempStrList.append('('+str(i[0])+str(j[0])+str(i[1])+')'+str(j[1])+'('+str(i[2])+str(j[2])+str(i[3])+')')
        for k in tempStrList:
            if k.count('/(') > 0:
                index1=k.index('/(')
                index2=k.index(')',index1)
                if eval(k[index1+2:index2])==0:
                    break
            result=eval(k)
            if result==24&nbs***bsp;abs(result-24)<0.000001:
                find_flag='true'
                break
print(find_flag)

from itertools import combinations
def find_method():
    for i in range(4):
        if 24 in values[i]:
           return f'{a[i][1]} {symbol[values[i].index(24)]} {a[i][0]}'
        for j in range(4):
            new_set = list(a[i])
            new_set.append(nums[j])
            if new_set.count(nums[j]) == nums.count(nums[j]):
                for m in range(len(values[i])):
                    if values[i][m] + nums[j] == 24:
                        return  f'{a[i][1]} {symbol[m]} {a[i][0]} + {nums[j]}'
                    elif values[i][m] - nums[j] == 24:
                        return f'{a[i][1]} {symbol[m]} {a[i][0]} - {nums[j]}'
                    elif values[i][m] * nums[j] == 24:
                        return f'( {a[i][1]} {symbol[m]} {a[i][0]} ) * {nums[j]}'
                    elif values[i][m] / nums[j] == 24:
                        return f'( {a[i][1]} {symbol[m]} {a[i][0]} ) / {nums[j]}'
        for j in range(len(a)):
            new_set = list(a[i])
            new_set.extend(list(a[j]))
            new_set.sort()
            if new_set == nums:
                for m in range(len(values[i])):
                    for n in range(len(values[j])):
                        if values[i][m] + values[j][n] == 24:
                            return f'{a[i][1]} {symbol[m]} {a[i][0]} {symbol[0]} {a[j][1]} {symbol[n]} {a[j][0]}'
                        elif abs(values[i][m]-values[j][n]) == 24:
                            if values[i][m] > values[j][n]:
                                return f'{a[i][1]} {symbol[m]} {a[i][0]} {symbol[0]} {a[j][1]} {symbol[n]} {a[j][0]}'
                            return f'{a[j][1]} {symbol[n]} {a[j][0]} {symbol[0]} {a[i][1]} {symbol[m]} {a[i][0]}'
                        elif values[j][n] * values[i][m] == 24:
                            return f'( {a[i][1]} {symbol[m]} {a[i][0]} ) {symbol[0]} ( {a[j][1]} {symbol[n]} {a[j][0]} )'
                        elif values[j][n] != 0:
                            if values[i][m] / values[j][n] == 24:
                                return f'( {a[i][1]} {symbol[m]} {a[i][0]} ) {symbol[0]} ( {a[j][1]} {symbol[n]} {a[j][0]} )'
                        elif values[i][m] != 0:
                            if values[j][n] / values[i][m] == 24:
                                return f'( {a[j][1]} {symbol[n]} {a[j][0]} ) {symbol[0]} ( {a[i][1]} {symbol[m]} {a[i][0]} )'
symbol = ['+', '-', '*', '/']
nums = list(map(int, input().strip().split()))
nums.sort()
a = list(combinations(nums, 2))
values = list()
for i in range(len(a)):
    b = list()
    b.append(sum(a[i]))
    b.append(abs(a[i][1]-a[i][0]))
    b.append(a[i][1] * a[i][0])
    if a[i][1] % a[i][0] == 0:
        b.append(int(a[i][1] / a[i][0]))
    values.append(b)
method = find_method()
if method == None:
    print('false')
else:
    #print(method)
    print('true')

import sys
def fun1(a,b):      #   返回两数+-*/结果列表
    x = [a+b,abs(a-b),a*b]
    if b!=0 and a%b == 0:
        x.append(a//b)
    elif b!= 0 and b%a == 0:
        x.append(b//a)
    return x
def fun(x):
    k = 'false'
    a  = [0,0]
    b = []
    for i in range(4):
        if k!= 'true':
            a[0] = x[i]  
            b = []  
            for j in range(i+1,4):           
                if j!= i  :
                    a[1] = x[j]
                    b = [x[ii] for ii in list(set([0,1,2,3])-set([i,j]))]                  
                    aa = fun1(a[0],a[1])
                    bb = fun1(b[0],b[1])
                    # print(a,b,aa,bb)   aa，bb分别存储两对数的+-*/运算结果
                    for i0 in aa:                                  
                        if  (set(fun1(24,i0)) & set(bb) )&nbs***bsp;(set(fun1(24,b[0])) & set(fun1(i0,b[1]))): 
                            # 若aa中有元素i0与24 +-*/ 后在bb 中 (即 4 = 2+2 )或i0与b中元素b[1] +-*/ 后 == 24+-*/b[0]（即 4= 2+1 +1）                            
                            k = 'true'                           
                            break
                    if k=='true':
                        break                  
    print(k)
          
while True:
    try:
        xx = list(map(int,input().split()))
        fun(xx)

    except:
        break

"""
实现功能，输入任意一个数组numbers，给一个目标数target_num
判断数组中的数经过四个运算符以及加括号运算能否运算出目标数
这个问题主要使用递归和穷举法
1.	首先生成四个数的全排列
2.	然后将每个排列都穷举运算
3.	将所有可能的计算并检查是否和目标值相等
4.	处理异常，除数为零时的做法，
5.	运算精度，截断误差的影响，最后与目标数比较时应该给一个小误差阈值。
以上第2步中涉及加括号运算问题，加括号的运算可以如下处理
考虑加括号的运算可以理解为将一列数中的任意两个相邻数取出运算，然后将结果放入原位置，并递归这一过程。这种递归式的分割方法是解决包含括号运算问题的典型思路。
以上包含了括号中多个运算数的情况，因为括号中多运算数时按照运算规则从前往后计算，以上方法包含从前往后加括号计算。
定义一个四个有序数的运算函数，任意相邻位置取出两个进行加减乘除运算，运算后放入原位置，进行递归，最终得到四个有序数在加括号且四个运算符下的所有可能的运算结果。
再对四个数生成的全排列全部进行有序数的运算，与目标值比较。
"""

import itertools  # 用于生成全排列

# 允许的运算符
operators = ['+', '-', '*', '/']


# 使用递归计算结果
def calculate(a, b, op):
    if op == '+':
        return a + b
    elif op == '-':
        return a - b
    elif op == '*':
        return a * b
    elif op == '/':
        if b == 0:
            return None  # 避免除零
        return a / b


# 递归计算所有可能的结果
def evaluate(numbers):
    # 如果只有一个数字，返回它
    if len(numbers) == 1:
        return [numbers[0]]

    results = []
    # 遍历所有可能的二元操作
    for i in range(1, len(numbers)):
        left_nums = numbers[:i]
        right_nums = numbers[i:]

        left_results = evaluate(left_nums)
        right_results = evaluate(right_nums)

        # 遍历所有运算符并计算结果
        for left_result in left_results:
            for right_result in right_results:
                for op in operators:
                    result = calculate(left_result, right_result, op)
                    if result is not None:
                        results.append(result)

    return results


# 检查是否可以运算出 target_num
def can_make_target(numbers, target_num):
    # 生成数字的所有排列
    permutations = itertools.permutations(numbers)

    # 遍历所有排列并计算结果
    for perm in permutations:
        results = evaluate(list(perm))
        for result in results:
            # 考虑浮点精度，浮点数运算的截断误差问题
            if abs(result - target_num) < 1e-6:  # 使用一个小的阈值
                return True

    return False


# numbers = [4, 7, 8, 6, 100]
# target_num = 124
# result = can_make_target(numbers, target_num)
# print(f"numbers:{numbers}\nCan make {target_num}:{result}")  # 输出 True 或 False


numbers = [int(i) for i in input().split(" ")]
result = can_make_target(numbers,  24)
print(str(result).lower())  # 输出true或false

a, b, c, d = map(int,input().split())
A = [a, b, c, d]
B = ['+', '-', '*', '/']
count = 0
res = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                if i != j and i != k and i != l and j != k and j != l and k != l:
                    for m in B:
                        for n in B:
                            for o in B:
                                count += 1
                                C1 = ['(', A[i], m, A[j], ')', n, A[k], o, A[l]]
                                C2 = ['(', A[i], m, A[j], n, A[k], ')', o, A[l]]
                                C3 = [A[i], m, A[j], n, A[k], o, A[l]]
                                C4 = [A[i], m, '(', A[j], n, A[k], ')', o, A[l]]
                                C5 = [A[i], m, '(', A[j], n, A[k], o, A[l], ')']
                                C6 = [A[i], m, A[j], n, '(', A[k], o, A[l], ')']
                                C1,C2,C3,C4,C5,C6 = map(str, C1),map(str, C2),map(str, C3),map(str, C4),map(str, C5),map(str, C6)
                                D1,D2,D3,D4,D5,D6 = ''.join(C1),''.join(C2),''.join(C3),''.join(C4),''.join(C5),''.join(C6)
                                DD = [D1, D2, D3, D4, D5, D6]
                                for ii in DD:
                                    try:
                                        E = eval(ii)
                                    except ZeroDivisionError:
                                        E = 'Error'  # 处理除数为0的情况
                                    if E == 24:
                                        res = 1
if res == 1:
    print('true')
else:
    print('false')

# 解决热门分享中没有考虑到带括号情况的BUG

arr = input().split()
def check_24(arr, exp=""):
    if len(arr) == 1:
        exp += arr[0]
        # 找出3个运算符所在位置
        flag = 0
        for i in range(len(exp)):
            if not exp[i].isdigit() and flag == 0:
                flag = 1
                s0 = i
                continue
            if not exp[i].isdigit() and flag == 1:
                flag = 2
                s1 = i
                continue
            if not exp[i].isdigit() and flag == 2:
                s2 = i
                break
        for exp_ in [  # 考虑各种带括号的形式，这里有很大优化空间，但是踩坑已经踩到吐血不想深究了
            exp,  # a + b + c + d
            f"({exp[:s1]}){exp[s1:]}",  # (a + b) * c + d
            f"{exp[:s1+1]}({exp[s1+1:]})",  # a + b * (c + d)
            f"({exp[:s1]}){exp[s1]}({exp[s1+1:]})",  # (a + b) * (c + d)
            f"({exp[:s2]}){exp[s2:]}",  # (a + b + c) * d
            f"{exp[:s0+1]}({exp[s0+1:]})",  # a * (b + c + d)
        ]:
            # 执行表达式，用try跳过/0的情况
            try:
                locals()["res"] = 0
                exec(f"res={exp_}")
            except:
                pass
            if locals()["res"] == 24:
                raise
    else:

        # 生成所有表达式
        for i in range(len(arr)):            
            check_24(arr[:i] + arr[i + 1 :], exp + arr[i] + "+")
            check_24(arr[:i] + arr[i + 1 :], exp + arr[i] + "-")
            check_24(arr[:i] + arr[i + 1 :], exp + arr[i] + "*")
            check_24(arr[:i] + arr[i + 1 :], exp + arr[i] + "/")
try:
    check_24(arr)
    print("false")
except:
    print("true")

# 参考了楼下的思路 感谢dalao

numbers = list(map(int, input().strip().split(" ")))

has_cal = []


def cal_24(nums):
    if len(nums) == 1:
        return nums[0] == 24

    else:
        r1 = r2 = r3 = r4 = False
        for i in range(len(nums)):
            for j in range(len(nums)):
                if i != j:
                    temp = [nums[k] for k in range(len(nums))if k not in [i, j]]

                    cal_plus = nums[i] + nums[j]
                    if ([cal_plus, ] + temp)not in has_cal:
                        has_cal.append([cal_plus, ] + temp)
                        r1 = cal_24([cal_plus, ] + temp)

                    cal_plus = nums[i] - nums[j]
                    if ([cal_plus, ] + temp) not in has_cal:
                        has_cal.append([cal_plus, ] + temp)
                        r2 = cal_24([cal_plus, ] + temp)

                    cal_plus = nums[i] * nums[j]
                    if ([cal_plus, ] + temp) not in has_cal:
                        has_cal.append([cal_plus, ] + temp)
                        r3 = cal_24([cal_plus, ] + temp)

                    if nums[j] != 0:
                        cal_plus = nums[i] / nums[j]
                        if ([cal_plus, ] + temp) not in has_cal:
                            has_cal.append([cal_plus, ] + temp)
                            r4 = cal_24([cal_plus, ] + temp)
                if any([r1, r2, r3, r4]):
                    return any([r1, r2, r3, r4])
        return any([r1, r2, r3, r4])


print(str(cal_24(numbers)).lower())

import sys

# 利用递归和回溯
def can_get_24(nums):
    if len(nums) == 1:
        return abs(nums[0] - 24) < 1e-6

    for i in range(len(nums)):
        for j in range(len(nums)):
            if i != j:
                new_nums = [nums[k] for k in range(len(nums)) if k != i and k != j]
                # 递归调用 can_get_24 函数，传递更新后的数字列表 new_nums。如果返回值为True，表示可以得到24，则立即 返回True。否则，我们通过 new_nums.pop() 将最后添加的结果移出列表，以便尝试其他运算
                # 加法
                new_nums.append(nums[i] + nums[j])
                if can_get_24(new_nums):
                    return True
                new_nums.pop()

                # 减法
                new_nums.append(nums[i] - nums[j])
                if can_get_24(new_nums):
                    return True
                new_nums.pop()

                # 乘法
                new_nums.append(nums[i] * nums[j])
                if can_get_24(new_nums):
                    return True
                new_nums.pop()

                # 除法
                if nums[j] != 0:
                    new_nums.append(nums[i] / nums[j])
                    if can_get_24(new_nums):
                        return True
                    new_nums.pop()

    return False


# 获取输入的4个整数
nums = list(map(int, input().split()))

# 检查是否能得到24
result = can_get_24(nums)

# 输出结果
if result:
    print("true")
else:
    print("false")