题解 | #24点游戏算法#

题目分析

1. 题目给出我们四个数字
2. 我们要通过任意四则运算来使得这四个数字的运算结果可以得到结果24，但是每个数字都只能且必须使用一次

方法一：暴力

（方法一暂时有问题 有些用例如2 5 2 7不能过暂时...由于方法一只能顺序作计算，不能处理先2*5，2*7，后作和的运算...等着后面更新hhh）

• 实现思路
  • 根据题目的意思，我们要将这四个数字通过任意的排列组合方式，使用任意的四则运算来获得24的结果
  • 因此我们只要暴力地对所有方案和所有的加减乘除结果进行枚举，查看结果中是否有我们想要的24结果即可

import itertools
def appends(lst,a,b):            # 将加减乘除的结果都添加到lst里面
    lst.append(a+b)
    lst.append(a-b)
    lst.append(a*b)
    lst.append(a/b)
    return lst

def solution(a,b,c,d):
    for nums in itertools.permutations([a,b,c,d]):    # 遍历所有的排列组合
        a,b,c,d = nums
        lst16 = []
        lst64= []
        lst4 = appends([], a, b)                      # 首先取前两个数字进行加减乘除，结果存在lst4中
        for i in lst4:
            lst16 = appends(lst16, i, c)              # 再将lst4中的结果逐一和第三个数字加减乘除，结果存在lst16中
        for i in lst16:
            lst64 = appends(lst64, i, d)              # 最终将lst16的结果逐一和最后一个数字加减乘除，结果存在lst64中
        if 24 in lst64:                               # 搜索完全遍历后其中是否有24存在
            return True
    return False

while True:
    try:
        a,b,c,d = [int(x) for x in input().split()]
        if solution(a, b, c, d) == True:
            print('true')
        else:
            print('false')
    except:
        break;

复杂度分析

• 时间复杂度：$O(1)O(1)$
  • 对于该方法中的4个数字来说，首先排列组合的操作次数为$4\times 3\times 2\times 1=244\times 3\times 2\times 1\; =\; 24$
  • 对于构造前两个数字的运算操作的lst4数组来说，新的操作次数累计为$24\times 4=9624\times 4=96$
  • 对于构造前三个数字的运算操作的lst16数组来说，新的操作累计数量为$96\times 4=38496\times 4=384$
  • 对于构造四个数字运算操作的lst64数组来说，新的操作累计数量为$384\times 4=1536384\times 4=1536$
  • 以上对于每项的计算都是$O(1)O(1)$级别，因此总复杂度为$O(1)O(1)$
• 空间复杂度：$O(1)O(1)$
  • 常数级别的空间开销

方法二：递归

• 实现思路
  • 递归通过回溯遍历所有的可能性，具体做法是，使用一个列表存储目前的全部数字，每次从列表中选出 2 个数字，再选择一种运算操作，用计算得到的结果取代选出的 2 个数字，这样列表中的数字就减少了 1 个。重复上述步骤，直到列表中只剩下 1 个数字，这个数字就是一种可能性的结果，如果结果等于 24，则说明可以通过运算得到 24。如果所有的可能性的结果都不等于 24，则说明无法通过运算得到 24。
    • 具体实现中除法操作还要抛去除数为0的情况，这种情况舍去
    • 由于除法的参与，计算结果为浮点数，因此最终和24比较的时候要考虑用最小误差在1e-6以内作为相等的标准

def dfs(nums):
    if not nums:
        return False
    if len(nums) == 1:
        return abs(nums[0] - 24) < 1e-6
    for i, a in enumerate(nums):                   # 获取第一个数字
        for j, b in enumerate(nums):               # 获取第二个数字
            if i != j:                             # 控制不重复
                newNums = list()
                for k, c in enumerate(nums):       # 获取第三个数字
                    if k != i and k != j:
                        newNums.append(c)
                for k in range(4):
                    if k < 2 and i > j:            # 对于+和*操作来说不需要考虑两者的顺序，因此舍去一种
                        continue
                    if k == 0:
                        newNums.append(a+b)
                    if k == 1:
                        newNums.append(a*b)
                    if k == 2:
                        newNums.append(a-b)
                    if k == 3:
                        if abs(b) < 1e-6:          # 排除除数为0的情况
                            continue
                        newNums.append(a/b)
                    if dfs(newNums):
                        return True
                    newNums.pop()
    return False

while True:
    try:
        lst = [int(x) for x in input().split()]
        if dfs(lst):
            print('true')
        else:
            print('false')
    except:
        break;

复杂度分析

• 时间复杂度：$O(1)O(1)$
  • 首先从4个数字中选取两个数字，共有$4\times 3=124\times 3=12$次选法，并执行4种运算操作，有$12\times 4=4812\times 4=48$次操作，得到的结果取代这两个数字，因此剩下三个数字
  • 再从剩下的三个数字中选出两个数字，共有$3\times 2=63\times 2=6$种选法，同样进行四则运算操作，有$6\times 4=246\times 4=24$次操作，得到的结果取代选出的2个数字，剩下两个数字
  • 最后剩下2个数字，有两种不同的顺序，并选择4种运算操作之一，有$2\times 4=82\times 4=8$次操作
  • 因此一共有$12\times 4\times 6\times 4\times 2\times 4=912612\times 4\times 6\times 4\times 2\times 4=9126$次操作，代价也是$O(1)O(1)$
• 空间复杂度：$O(1)O(1)$
  • 空间复杂度取决于递归调用层数与存储中间状态的列表，因为一共有 4 个数，所以递归调用的层数最多为 4，存储中间状态的列表最多包含 4 个元素，因此空间复杂度为常数