题解 | 24点游戏算法

import sys
from fractions import Fraction
from typing import List,Set

def get_vals(a_set:Set[Fraction], b_set:Set[Fraction]) -> List[Set[Fraction]]:
    vals = set()
    for a in a_set:
        for b in b_set:
            vals.add(a + b)
            vals.add(a * b)
            vals.add(a - b)
            vals.add(b - a)
            if b != 0:
                vals.add(a / b)
            if a != 0:
                vals.add(b / a)    
    return [vals]

def dfs(nums:List[Set[Fraction]]) -> List[Set[Fraction]]:
    if len(nums) == 1:   
        return 24 in nums[0]
    length = len(nums)
    for i in range(length):
        for j in range(i + 1, length):
            a, b = nums[i], nums[j]
            visited = [0] * length
            visited[i] = 1
            visited[j] = 1
            vals = get_vals(a, b)
            not_visited = [nums[k] for k in range(length) if visited[k] == 0]
            nums2 = vals if len(not_visited) == 0 else vals + not_visited
            if dfs(nums2):
                return True
    return False
    

raw_input = []
for i,line in enumerate(sys.stdin):
    raw_input.append(line.strip())
    if i == 1:
        break
    
num_lst = [set([Fraction(i)]) for i in raw_input[0].split(' ')]
if dfs(num_lst):
    print('true')
else:
    print('false')

代码如上:

1. 使用dfs计算所有可能的结果, dfs输入参数为一个list, list由set组成, set由数字组成
2. 如果list长度为1, 则检查set中是否有数字的值等于24, 有则返回true
3. 如果list长度大于1, 从list中选择两个元素(两个set), 使用get_vals函数计算这两个set中的数字经过四则运算后可能产生的数值.
4. 将第3步中计算的数值与剩余元素(如果有), 组成一个新的list, 输入dfs进行计算
5. 使用分数进行计算,也可以使用小数, 将判断条件修改为`abs(num - 24) < 1E-6`即可