如果毕达哥拉斯三元组等于输入,下面的代码将打印它,但问题是,像90000这样的大数字需要很长时间才能回答。 如何优化以下代码? 1.≤ N≤ 9万
def pythagoreanTriplet(n):
# Considering triplets in
# sorted order. The value
# of first element in sorted
# triplet can be at-most n/3.
for i in range(1, int(n / 3) + 1):
# The value of second element
# must be less than equal to n/2
for j in range(i + 1,
int(n / 2) + 1):
k = n - i - j
if (i * i + j * j == k * k):
print(i, ", ", j, ", ",
k, sep="")
return
print("Impossible")
# Driver Code
vorodi = int(input())
pythagoreanTriplet(vorodi)
您的source code对解决方案进行暴力搜索,因此速度很慢
更快的代码
操作代码
修改了操作代码,使其返回所有解决方案,而不是打印第一个发现的用于比较性能的解决方案
定时
解释
函数
solve_pythagorean_triplets
是一种O(n)算法,其工作原理如下搜索:
通过搜索a(即迭代的固定值)求解。对于固定值,我们有两个方程和两个未知数(b,c):
解决办法是:
迭代一个范围(1,n)以获得不同的解决方案
相关问题 更多 >
编程相关推荐