极其低效的python cod

Question

我做了一个程序，允许用户输入直角三角形的最大斜边，我的程序将列出所有可能的三角形边的列表。问题是，当我输入一个值，比如10000时，这个程序要花很长时间才能运行。对如何提高项目的效率有什么建议吗？在

代码：

largest=0
sets=0
hypotenuse=int(input("Please enter the length of the longest side of the triangle"))
for x in range(3,hypotenuse):
    for y in range(4, hypotenuse):
        for z in range(5,hypotenuse):
            if(x<y<z):                   
                 if(x**2+y**2==z**2):
                     commonFactor=False
                     for w in range(2,x//2):
                         if (x%w==0 and y%w==0 and z%w==0):
                             commonFactor=True
                             break
                     if not(commonFactor):
                         print(x,y,z)
                         if(z>largest):
                             largest=z
                         sets+=1
print("Number of sets: %d"%sets)
print("Largest hypotenuse is %d"%largest)

谢谢！在

Answer 1

下面是一个使用预先计算的平方和缓存平方根的快速尝试。可能有许多数学优化。在

def find_tri(h_max=10):
  squares = set()
  sq2root = {}
  sq_list = []
  for i in xrange(1,h_max+1):
    sq = i*i
    squares.add(sq)
    sq2root[sq] = i
    sq_list.append(sq)
  #
  tris = []
  for i,v in enumerate(sq_list):
    for x in sq_list[i:]:
      if x+v in squares:
        tris.append((sq2root[v],sq2root[x],sq2root[v+x]))
  return tris

演示：

^{pr2}$

Answer 2

像这样？在

hypothenuse=10000
thesets=[]
for x in xrange(1, hypothenuse):
    a=math.sqrt(hypothenuse**2-x**2)
    if(int(a)==a):
        thesets.append([x,a])
print "amount of sets: ", len(thesets)
for i in range(len(thesets)):
    print thesets[i][0],thesets[i][1], math.sqrt(thesets[i][0]**2+ thesets[i][1]**2)

编辑：更改后，您也可以打印集合（这个方法是在O（n）中，我想这是最快的方法？）注：如果需要集合的数量，则每个集合被给出两次，例如：15*2=9*2+12*2=12*2+9**2

如果你不知道你的密码是不是都比12小？或者你想知道写12*2=a*2+b**2的可能性吗？在

如果你想要所有的可能性，我会编辑一点代码

对于a*2+b*2=c**2的所有可能性，其中c<；抵押权（不确定这是否是您想要的）：

^{pr2}$

这在O（n**2）中求解，如果假设值=15，你的解甚至不起作用，你的解给出：

（3、4、5） （5、12、13） 套数：2

正确的是： 三 [（5，12），（3，4），（6，8）]

既然5*2+12*2=13*2，3*2+4*2=5*2，6*2+8*2=10**2，而你的方法没有给出第三个选项？ 编辑：把numpy改为math，我的方法也没有给出倍数，我只是说明了为什么我得到3而不是2，（这3个不同的解是问题的不同解，因此3个都是有效的，所以你的解是不完整的？）在

Answer 3

一个非常简单的优化是任意决定x <= y。e、 g.如果(10,15,x)不是解决方案，那么{}也不是解决方案。这也意味着如果2x**2 > hypoteneuse**2，那么您可以终止算法，因为没有解决方案。在