经典算法题:如果 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))

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

点赞

发表回复

电子邮件地址不会被公开。必填项已用 * 标注