3

我制作了一个程序，允许用户输入直角三角形的最大可能斜边，我的程序将列出三角形所有可能边的列表。问题是，当我输入一个诸如 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)

谢谢！

4

3 回答 3

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

演示：

>>> find_tri(20)
[(3, 4, 5), (5, 12, 13), (6, 8, 10), (8, 15, 17), (9, 12, 15), (12, 16, 20)]
于 2013-08-14T15:09:55.220 回答
1

像这样？

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？或者您是否想知道写 12* 2=a *2+b**2 的可能性（据我所知）？

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

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

hypothenuse=15
thesets={}
for x in xrange(1,hypothenuse):
    for y in xrange(1,hypothenuse):
        a=math.sqrt(x**2+y**2)
        if(a<hypothenuse and int(a)==a):
            if(x<=y):
                thesets[(x,y)]=True
            else:
                thesets[(y,x)]=True
print len(thesets.keys()) 
print thesets.keys()

这解决了 O(n**2)，如果 hypothenuse=15，您的解决方案甚至不起作用，您的解决方案给出：

(3, 4, 5) (5, 12, 13) 组数：2

而正确的是：3 [(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更改为数学，我的方法也没有给出倍数，我只是说明了为什么我得到3而不是2，（这3个不同的是问题的不同解决方案，因此所有3个都是有效的，所以你的解决方案问题不完整？）

于 2013-08-14T14:20:53.897 回答
0

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

于 2013-08-14T15:50:34.460 回答