经典算法题：如果 a+b+c=1000，且 a²+b²=c²（a,b,c 为自然数），如何求出所有a、b、c可能的组合?

如果 a+b+c=1000，且 a²+b²=c²（a,b,c 为自然数），如何求出所有a、b、c可能的组合?
此题作为经典算法题经常出现在面试中，本次使用Python来解决：

# 循环大法：
for a in range(0, 1001):
    for b in range(0, 1001):
        for c in range(0, 1001):
            if a**2 + b**2 == c**2 and a+b+c == 1000:
                 print("a, b, c: %d, %d, %d" % (a, b, c))

这种算法一目了然，但性能较低

优化算法：

# 优化后算法：
# 因为a,b,c 为自然数且a²+b²=c²，那么，分别以a、b、c作为边的三角形是直角三角形。
# 三角形性质：两边之和大于第三边，所以：a+b>c
# 数学证明：a²+b²=c²   a²+b²+2ab=c²+2ab>c²   (a+b)²>c²   a+b>c
# 又因为a²+b²=c²，则a、b都小于500，所以range(0, 501)。
for a in range(0, 501):
    for b in range(0, 501):
        # 已知a，b的值则c=1000-a-b，已知a²+b²=c² 则500000 - 1000*b - 1000*a + a*b == 0
        # 此时c的值可以在a、b成立后运算
        if 500000 - 1000*b - 1000*a + a*b == 0:
            c = 1000 - a - b
            print("a, b, c: %d, %d, %d" % (a, b, c))

继续优化：

# 继续优化：
# 因为a²+b²=c²，a+b+c=1000，故a²+b²=(1000-a-b)²
# 故b=((1000-a)-a)/(2*(1000-a))
for a in range(0, 501):
    if ((1000-a)**2-a**2)%(2*(1000-a))== 0 and ((1000 - a) ** 2 - a ** 2) / (2 * (1000 - a))<=500:
        b = ((1000 - a) ** 2 - a ** 2) / (2 * (1000 - a))
        c = 1000 - a - b
        print("a, b, c: %d, %d, %d" % (a, b, c))

最后，期待有更好的算法，欢迎留言评论！