时间戳

首页 > 解决方案 > 有没有办法优化找到 a+b+c=1000 的毕达哥拉斯三元组的算法？

python - 有没有办法优化找到 a+b+c=1000 的毕达哥拉斯三元组的算法？

问题描述

我正在尝试解决项目 euler 的第 9 个问题，这段代码可以完成这项工作，但是这样做需要很长时间（注意：我刚刚意识到 a<b<c 条件在函数中是无用的，因为它总是在循环）

 from math import pow


def isPythagoeranTriplet(a,b,c):
    return a < b < c and pow(a,2)+pow(b,2) == pow(c,2)


for c in range(5,1000) :
    for b in range(4,c) :
        for a in range(3,b) :
            if isPythagoeranTriplet(a,b,c) and a+b+c == 1000:
                print(a*b*c)

标签： pythonpythagoreantriplet

解决方案

一个简单的优化是避免做不必要的操作。

首先，当你知道一个有效的解决方案应该满足条件时，为什么要测试 all ainrange(3,b)a+b+c ==1000

第一个优化是：

 from math import pow

 def isPythagoeranTriplet(a,b,c):
     return a < b < c and pow(a,2)+pow(b,2) == pow(c,2)

for c in range(5,1000) :
    for b in range(4,c) :
        a = 1000 - b - c
        if a >= 0:
            if isPythagoeranTriplet(a,b,c):
                print(a*b*c)

您还可以更改您的功能，以便假设检查更容易，a<b<c并且仅检查已经满足此条件的数字：

 from math import pow

 def isPythagoeranTriplet(a,b,c):
     return pow(a,2)+pow(b,2) == pow(c,2)

for c in range(5,1000) :
    for b in range(4,c) :
        a = 1000 - b - c
        if a >= 0 and a < b:
            if isPythagoeranTriplet(a,b,c):
                print(a*b*c)

通过构建，您拥有b<c. 您还可以对其进行优化以测试少量的 b 和 c 值。如您所见，如果c=6, b=5，您的值不能a小于两个值并满足条件a+b+c = 1000。您实际上可以进行的大多数优化都在循环范围内，以丢弃不需要测试的值。

推荐阅读