我正在尝试根据热门电视节目制作一个倒计时求解器,给定 6 个数字和一个目标数字,它会遍历可能的解决方案,直到找到一个,然后返回它。 我并不是在寻找超级优化的版本,只是在寻找一个可以轻松添加到更大程序中的简单功能(我的最终目标)。 当我运行代码时,它指出超出了最大递归深度,我不知道为什么。 我认为它应该只运行 5 个递归调用以及其中的 1 或 2 个函数,例如 int() 。 谁能解释一下为什么我会出现这个错误?
该函数的工作原理(或应该工作原理)如下: 数字列表作为字符串传递,并且在 for 循环中使用所有 4 个可能的操作(记住 a + b = b + a)来组合 2 个数字的每个组合。这是针对目标进行检查的。 结果将替换原始列表中的两个数字,以创建一个少一个元素的列表。例如
["7","9","50","25","75","100"] => ["63","50","25","75","100"]
其中 7 和 9 已被 63 替换,(7 * 9) 这是函数用新列表调用自身的地方。此过程一直持续到列表只有两个元素为止,在这种情况下,如果未找到任何内容,函数将返回“Q”(导致每个后续调用都返回“Q”)。 如果找到解决方案,则返回表示操作的字符串,例如“(7 * 9)”。 由于递归性质,在这个首先计算 63 的示例中,当返回“(5 + 63)”时,应将 63 替换为“(5 + (7 * 9))”。这意味着最终返回的是final方法。
如果我没有正确解释,请评论,我可以再试一次。
import itertools as i
target=input("What is the target number? ")
def solve(l):
global count
if len(l) == 2:
count+=1
if int(l[0]) + int(l[1]) == target:
return "("+l[0] +" + "+l[1]+")"
count+=1
if int(l[0]) - int(l[1]) == target:
return "("+l[0] +" - "+l[1]+")"
count+=1
if int(l[0]) * int(l[1]) == target:
return "("+l[0] +" * "+l[1]+")"
count+=1
if int(l[0]) / int(l[1]) == target:
return "("+l[0] +" / "+l[1]+")"
count+=1
if int(l[1]) - int(l[0]) == target:
return "("+l[0] +" - "+l[1]+")"
count+=1
if int(l[1]) / int(l[0]) == target:
return "("+l[1] +" / "+l[0]+")"
else:
return "Q"
else:
ct = list(i.combinations(l, 2))
for item in ct:
count+=1
resulta1=int(item[0])+int(item[1])
if resulta1 == target:
return "("+item[0] +" + "+item[1]+")"
count+=1
resulta2=int(item[0])-int(item[1])
if resulta2 == target:
return "("+item[0] +" - "+item[1]+")"
count+=1
resulta3=int(item[0])*int(item[1])
if resulta3 == target:
return "("+item[0] +" * "+item[1]+")"
count+=1
resulta4=int(item[0])/int(item[1])
if resulta4 == target:
return "("+item[0] +" / "+item[1]+")"
count+=1
resulta5=int(item[1])-int(item[0])
if resulta5 == target:
return "("+item[0] +" - "+item[1]+")"
count+=1
resulta6=int(item[1])+int(item[0])
if resulta6 == target:
return "("+item[1] +" / "+item[0]+")"
intl = [el for el in l]
intl.remove(item[0])
intl.remove(item[1])
newl=intl
newl.append(str(resulta1))
res1=solve(newl)
if res1 != "Q":
return res1.replace(str(resulta1),"("+item[0] +" + "+item[1]+")")
newl=intl
newl.append(str(resulta2))
res2=solve(newl)
if res2 != "Q":
return res2.replace(str(resulta2),"("+item[0] +" - "+item[1]+")")
newl=intl
newl.append(str(resulta3))
res3=solve(newl)
if res3 != "Q":
return res3.replace(str(resulta3),"("+item[0] +" * "+item[1]+")")
newl=intl
newl.append(str(resulta4))
res4=solve(newl)
if res4 != "Q":
return res4.replace(str(resulta4),"("+item[0] +" / "+item[1]+")")
newl=intl
newl.append(str(resulta5))
res5=solve(newl)
if res5 != "Q":
return res5.replace(str(resulta5),"("+item[1] +" - "+item[0]+")")
newl=intl
newl.append(str(resulta6))
res6=solve(newl)
if res6 != "Q":
return res6.replace(str(resulta6),"("+item[1] +" / "+item[0]+")")
else:
return "Q"
lis=input("Enter numbers separated by commas: ").split(",")
count=0
solution = solve(lis)
print(count)
需要注意的是,我使用 Online IDE Replit,它可能具有不同的最大递归深度。
几点建议:
global
;相反,使用函数参数。len(l) == 2
;但您可能还需要一个 len(l) == 1
的终端盒!例如,如果您从包含三个元素的列表开始,那么您的代码将删除两个元素,然后剩下一个。itertools.combinations
找到了所有拆分数字的方法,因此无需单独检查 l[0]-l[1]
和 l[1]-l[0]
;只需相信 combinations
就能将数字拆分为左右任意可能的组合。遵循代码的逻辑,但应用我自己的建议:
import itertools as i
from operator import add, sub, mul, floordiv
def div(a, b):
try:
return floordiv(a, b)
except ZeroDivisionError:
return float('inf')
rsub = lambda a,b: sub(b,a)
rdiv = lambda a,b: div(b,a)
op_list = (add, sub, mul, div, rsub, rdiv)
def all_splits(seq):
"powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
s = set(range(len(seq)))
for c in i.combinations(s, 2):
yield tuple(seq[j] for j in c), tuple(seq[j] for j in s.difference(c))
def complement_target(target, op, left):
'''left op right == target <---> right == target revop left'''
revop = {add: sub, sub: rsub, mul: div, div: rdiv, rsub: add, rdiv: mul}
return revop[op](target, left)
def solve(target, numbers):
if len(numbers) == 1:
if target == numbers[0]:
yield numbers
elif len(numbers) == 2:
a, b = numbers
for op in op_list:
if target == op(a, b):
yield (a, op, b)
else:
for (a,b),right_numbers in all_splits(numbers):
for left_op in op_list:
left_target = left_op(a,b)
for op in op_list:
right_target = complement_target(target, op, left_target)
if op(left_target, right_target) == target: # (x / y) * y ?=? x
for right_expr in solve(right_target, right_numbers):
yield ((a, left_op, b), op, right_expr)
def stringify(expr):
opnames = {add:'{a} + {b}',sub:'{a} - {b}',mul:'{a} * {b}',div:'{a} / {b}',rsub:'{b} - {a}',rdiv:'{b} / {a}'}
if isinstance(expr, int):
return str(expr)
elif len(expr) == 3:
left_expr, op, right_expr = expr
a=stringify(left_expr)
b=stringify(right_expr)
return ''.join(('(', opnames[op].format(a=a,b=b), ')'))
else:
raise ValueError(expr)
def main():
target = 10
numbers = (1,2,3,4)
for expr in solve(target, numbers):
print(target, ' == ', stringify(expr))
if __name__ == '__main__':
main()
输出:
10 == ((1 + 2) + (3 + 4))
10 == ((3 * 4) - (1 * 2))
10 == ((3 * 4) - (2 / 1))
10 == ((1 + 3) + (2 + 4))
10 == ((2 * 4) - (1 - 3))
10 == ((3 - 1) + (2 * 4))
10 == ((1 + 4) + (2 + 3))
10 == ((1 * 4) + (2 * 3))
10 == ((4 / 1) + (2 * 3))
10 == ((2 + 3) + (1 + 4))
10 == ((2 * 3) + (1 * 4))
10 == ((2 * 3) + (4 / 1))
10 == ((2 + 4) + (1 + 3))
10 == ((2 * 4) + (3 - 1))
10 == ((2 * 4) - (1 - 3))
10 == ((3 + 4) + (1 + 2))
10 == ((3 * 4) - (1 * 2))
10 == ((3 * 4) - (2 / 1))