蓝桥杯 算法训练 24点（Python）_python 24点

资源限制

内存限制：256.0MB   C/C++时间限制：1.0s   Java时间限制：3.0s   Python时间限制：5.0s

问题描述

　　24点游戏是一个非常有意思的游戏，很流行，玩法很简单：给你4张牌，每张牌上有数字（其中A代表1，J代表11，Q代表12，K代表13），你可以利用数学中的加、减、乘、除以及括号想办法得到24，例如：
　　((A*K)-J)*Q等价于((1*13)-11)*12=24
　　加减乘不用多说了，但除法必须满足能整除才能除！这样有一些是得不到24点的，所以这里只要求求出不超过24的最大值。

输入格式

　　输入第一行N(1<=N<=5)表示有N组测试数据。每组测试数据输入4行，每行一个整数(1到13)表示牌值。

输出格式

　　每组测试数据输出一个整数，表示所能得到的最大的不超过24的值。

样例输入

3
3
3
3
3
1
1
1
1
12
5
13
1

样例输出

24
4
21

有两种思路，系统提交得分都是100分

方案一：

这个是我的思路，因为数据范围不大，所以我选择的是一步一步处理，首先将每一组数据的4个数顺序打乱，再分配三个可重复的运算符号，再加上不同的括号，依次计算，求出不大于24的最大值，如果遇到24，则提前结束当前组处理。

from itertools import *
 
n = int(input())
nums = []
strs = ['+', '-', '*', '/']
# 将输入的数字4个一组，存到nums里
for i in range(n):
    a = int(input())
    b = int(input())
    c = int(input())
    d = int(input())
    nums.append([a, b, c, d])
# print(nums)
for i in nums:
    nums1 = []
    ans = []
    flag = 1
    # 将四个数字顺序打乱
    for j in permutations(i):
        if list(j) not in nums1:
            nums1.append(list(j))
    # print(nums1)
    for j in nums1:
        # 每一种数字顺序，取出任意三个计算符号，符号可以重复
        for str1 in product(strs, repeat=3):
            a = j[0]
            b = j[1]
            c = j[2]
            d = j[3]
            # 共有11种加括号的方式，全部列举出来
            for num in range(11):
                formula = []
                if num == 0:
                    formula = ['(', a, str1[0], b, ')', str1[1], c, str1[2], d]
                elif num == 1:
                    formula = [a, str1[0], '(', b, str1[1], c, ')', str1[2], d]
                elif num == 2:
                    formula = [a, str1[0], b, str1[1], '(', c, str1[2], d, ')']
                elif num == 3:
                    formula = ['(', a, str1[0], b, str1[1], c, ')', str1[2], d]
                elif num == 4:
                    formula = [a, str1[0], '(', b, str1[1], c, str1[2], d, ')']
                elif num == 5:
                    formula = ['(', a, str1[0], b, ')', str1[1], '(', c, str1[2], d, ')']
                elif num == 6:
                    formula = ['(', '(', a, str1[0], b, ')', str1[1], c, ')', str1[2], d]
                elif num == 7:
                    formula = ['(', a, str1[0], '(', b, str1[1], c, ')', ')', str1[2], d]
                elif num == 8:
                    formula = [a, str1[0], '(', '(', b, str1[1], c, ')', str1[2], d, ')']
                elif num == 9:
                    formula = [a, str1[0], '(', b, str1[1], '(', c, str1[2], d, ')', ')']
                elif num == 10:
                    formula = [a, str1[0], b, str1[1], c, str1[2], d]
                # 将最后的式子变成字符串
                strend = ''
                for m in formula:
                    strend += str(m)
                try:
                    # 计算字符串的值
                    if eval(strend) % 1 == 0:
                        ans_num = int(eval(strend))
                    else:
                        continue
                # 除0处理
                except ZeroDivisionError:
                    continue
                if ans_num < 24:  # 小于24的结果存到数组中，最后取最大值
                    ans.append(ans_num)
                elif ans_num == 24:  # 如果是24，提前结束本组数据的处理
                    print('24')
                    flag = 0
                    break
            if flag == 0:
                break
        if flag == 0:
            break
    if flag == 0:
        continue
    print(max(ans))

方案二：

此方案是做完之后在网上找的代码，然后稍作修改，删掉了部分多余的代码得到的，整体思路就是利用深度优先（DFS）遍历，每次进行两个数的运算，计算结果替换掉原来的两个数，直到只剩一个数，然后计算结束继续回溯，直到计算出所有不大于24的结果，取最大值，同样，遇到24提前返回。

n = int(input())
nums = [[] for i in range(n)]
for i in range(n * 4):
    nums[i // 4].append(int(input()))
 
 
def dfs(arr):
    global res, flag, sto  # res为计算结果；flag标记计算结果是否为24；sto用于储存小于24的计算结果
    if flag == 1:  # flag==1说明找到最终结果了
        return
    if len(arr) == 1:  # 递归出口
        res = arr[0]
        if res == 24:
            flag = 1
            sto = [24]  # 当计算结果为24时，直接令sto=[24]
            return
        elif res > 24:  # 计算结果大于24的不要
            return
        else:
            sto.add(res)  # 计算结果小于24的加入集合中，最后取集合最大值得到最终结果
            return
 
    for i in range(len(arr)):
        a = arr[i]
        arr2 = arr.copy()  # 作用与回溯相同，用了arr2就不需要回溯了
        arr2.pop(i)
        for j in range(len(arr2)):
            b = arr2[j]
            arr2.pop(j)
            # 下面4个部分分别是加减乘除，删除a，b后插入c，然后回溯，回溯完成后退回到这里继续执行下面的计算
            c = a + b
            arr2.insert(j, c)
            dfs(arr2)
            arr2.pop(j)
 
            c = a - b
            arr2.insert(j, c)
            dfs(arr2)
            arr2.pop(j)
 
            c = a * b
            arr2.insert(j, c)
            dfs(arr2)
            arr2.pop(j)
            arr2.insert(j, b)
 
            if b != 0 and a % b == 0:  # 除数不为0，并且能整除
                c = a // b
                arr2.pop(j)
                arr2.insert(j, c)
                dfs(arr2)
                arr2.pop(j)
                arr2.insert(j, b)
 
 
for arrs in nums:
    sto = set([])
    flag = 0
    res = 0
    dfs(arrs)
    print(max(sto))