如果 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))
最后,期待有更好的算法,欢迎留言评论!