HJ67_24点游戏算法_多维递归_DFS(深度优先搜索)

发布时间 2023-04-08 17:04:58作者: Aneverforget

思路:

多维递归,深度有限遍历加减乘除四种情况。

知识点:

1、多维递归不能对传递的变量进行修改,否则无法回溯。

应该传递一个新地址的变量,如代码所示,传递切片的列表,不修改列表

 

 2、搜索遗漏。两括号比如((9-4)-1)*6

选取任意一个数作为第一个运算数与24运算,不能找出所有24点的计算方法。因为存在两个非嵌套括号的情况。

 

 

去除括号思路:不能按列表顺序进行运算。需要遍历每个数可作为第一个数运算的可能性。但是这种方法也只是去除嵌套括号,遍历不到非嵌套括号。但是通过了测试案例。该程序如下:

参考高赞答案后程序如下:

 1 import sys
 2 a=list(map(int,sys.stdin.readline().strip().split()))
 3 l=[]
 4 num=24
 5 def dfs(a,num):
 6     if len(a)==1:
 7         if num==a[0]:
 8             l.append(1)
 9         return         
10     elif len(a)>=1:
11         for i in range(len(a)):
12             temp=a[:i]+a[i+1:]            
13             dfs(temp,num+a[i])
14             dfs(temp,num-a[i])
15             dfs(temp,num*a[i])
16             dfs(temp,num/a[i])
17 dfs(a,num)
18 if 1 in l:
19     print("true")
20 else:
21     print("false")

 

 

 

 

 

 

 

程序: