gpt4 book ai didi

python - 具有 4 个基本运算的表达式组合

转载 作者:行者123 更新时间:2023-12-04 23:11:42 25 4
gpt4 key购买 nike

我想不出更好的标题,因为一个合适的标题可能需要完整的解释。此外,组合可能会产生误导,因为问题将涉及排列。

我想要完成的是在以下问题中超越 Python 中的蛮力方法:给定 4 个基本操作 [+,-,*,/] 和从 1 到 9 的数字,并给出 5 位数字的所有可能组合以及导致给定数字(视为整数)的 4 次不重复(排列)运算,如 1+5*9-3/7=45, 1-2/3+9*5=45,.. . 获取从可能的最低值到可能的最高值的所有整数,并找出空间中的所有整数是否存在。

我用蛮力的初步尝试如下:

def brute_force(target):
temp = 0
x = [i for i in range(1,10)]
numbers = [str(i) for i in x]
operators = ["+","-","*","/"]
for values in permutations(numbers,5):
for oper in permutations(operators):
formula = "".join(o + v for o,v in zip([""]+list(oper),values))
if round(eval(formula)) == int(target):
temp += 1
if temp > 0:
return True
else:
return False

for i in range(-100,100):
total = brute_force(i)
if total:
print(i)
else:
print(str(i) + 'No')

除了未找到的整数外,它只打印“否”。显而易见,所有整数值都可以在空间中找到,范围在 -71 到 79 之间。

我是 Python 和算法实现的新手,但我认为该算法的复杂度为 O(n!),从涉及排列的事实来看。但如果不是这种情况,我仍然想要一种性能更好的算法(例如递归或动态编程)。

最佳答案

让我们只计算一次可能的结果集(以更简单和更快的方式):

expression = [None] * 9
results = {eval(''.join(expression))
for expression[::2] in permutations('123456789', 5)
for expression[1::2] in permutations('+-*/')}

它在我的笔记本电脑上大约 4.5 秒内计算出所有可能的结果。你像这样重写大约需要 5.5 秒。两者都 比您为每个目标整数 重做所有计算的方式快得多。

使用该结果集,我们可以立即回答问题,确认您的范围并显示只有 -70 和 78 缺失:
>>> min(results), max(results)
(-70.71428571428571, 78.83333333333333)

>>> set(range(-70, 79)) - results
{-70, 78}

关于python - 具有 4 个基本运算的表达式组合,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59888690/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com