大佬教程收集整理的这篇文章主要介绍了我怎样才能使这个算法对拼图更有效?,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
难题是:给定一个数字 n
,我需要返回一个数组,该数组包含所有平方和等于 n^2
的数字,按递增顺序排列。例如:[3,4]
是一个有效的解决方案,因为 3^2 + 4^2 = 25
,但对于 n = 50
,[1,1,4,49]
不会,因为 1,1
不是递增序列。测试还提到,如果两个或多个序列有效,我们应该选择最终数字最大的一个。如果未找到解决方案,则应返回 None
。
然后,我制作了这段代码,它设法通过了 n
是 5
和 8
的两个初步测试,但在更大的测试中超时,这只是可以预测的。那么,我怎样才能让它更有效率呢?我正在考虑使用生成器,但无法决定在哪里:
def decompose(n):
add = []
result = []
for i in range (n-1,-1):
if sum(add) < n ** 2:
add.append(i**2)
result.append(i)
elif sum(add) > n ** 2:
add.pop()
result.pop()
elif sum(add) == n ** 2:
return sorted(result)
return None
这并未针对速度进行优化,但确实提供了正确的解决方案。诀窍是使用递归。这个问题的关键变量不仅是n本身,还有列表中元素必须具有的总和。最初这是 n**2,但是每次添加一个新元素时,总和的剩余值都会降低,之后可以添加到列表中的最大整数也是如此。因此,向列表中添加一个新数字又是一个老问题,但具有不同的约束。这使它成为一个递归问题,并且是何时使用 yield
和 yield from
的绝妙示例。
def decompose(max_n,sum_allowed,solution):
for x in range(max_n,-1):
left_over_sum = sum_allowed - x**2
if left_over_sum == 0:
yield [x] + solution
elif left_over_sum > 0:
yield from decompose(x-1,left_over_sum,[x] + solution)
yield None
def decompose_top(n):
generator = decompose(n-1,n**2,[])
return next(generator)
print(decompose_top(1000001))
在这台有 7 年历史的机器上,我只需一秒钟的执行时间就可以轻松地达到 n=100000。通过在生成器上多次调用 next(),可以看到给定 n 的所有可能的解决方案。
以上是大佬教程为你收集整理的我怎样才能使这个算法对拼图更有效?全部内容,希望文章能够帮你解决我怎样才能使这个算法对拼图更有效?所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。