题解 | #24点游戏算法#
24点游戏算法
https://www.nowcoder.com/practice/fbc417f314f745b1978fc751a54ac8cb
def fun(nums, op): if op == "+": return sum(nums) elif op == "-": return nums[0]-nums[1] elif op == "*": return nums[0]*nums[1] else: return nums[0]/nums[1] def dfs(an, nums, op,visited,length, n,flag): if length>=2: # print(nums,op) nums[0] = fun(nums,op) if nums[0] ==24: # print(visited,nums,op) flag[0] = True # print(flag) return 0 if length==n and nums[0]!=24: return 0 for i in range(n): if visited[i]: pass else: temp0,temp1 = nums[0],nums[1] visited[i] = True nums[1] = an[i] for opi in ["+","-","*","/"]: # print(nums) dfsret = dfs(an, nums, opi, visited,length+1, n,flag) if flag[0]: break #回溯 nums[0] = temp0 # print(nums) #回溯 nums[0],nums[1] = temp0,temp1 visited[i] = False if __name__ == "__main__": an = list(map(int, input().split())) n = len(an) nums = [-1,0] op = "+" visited = [False] * n flag = [False] for i in range(n): nums[0] = an[i] visited[i] = True dfsret = dfs(an, nums, op, visited,1, n,flag) # print(flag) if flag[0]: break visited[i] = False if flag[0]: print("true") else: print("false")
深度优先递归遍历数组。
状态变量:visited(访问状态,初始值全false)、nums(计算结果,新遍历元素,初始值无要求)、op(运算操作,,初始值无要求)、flag=[false](用于判断是否有满足24点的情况,初始值为false)
每次计算结果ret保存在nums[0]中,新遍历的元素保存在nums[1]中。这样做是为了缩短计算时间。比用一个遍历数组和运算操作数组更快,更省空间。
递归遍历过程:首先分别以an[0]、an[1]、an[2]、an[3]为根节点,此时遍历长度为length=1,依次遍历剩余的数字。当遍历的长度length>=2时,每遍历一个元素则添加一种运算操作(+-*/四种),并计算运算结果fun(nums,op)。
递归过程中,visited、nums变量需要回溯。
递归终止条件:因为可能中途就找到满足24点的情况,需要设置终止递归的条件为:ret==24,并令flag[0]=True。
最后,通过状态变量flag判断,是否存在满足24点的情况。