有人能为"Pythagorean三胞胎“优化我的python代码吗？

Question

我编写了一个寻找毕达哥拉斯三胞胎的代码，但它没有被优化。

算法花了5-6分钟才找到大数的答案.我老师说应该不超过3秒.

num = int(input())

def main(n):
    for x in range(1, n):
        for y in range(1, x):
            for z in range(1, y):
                if x + y + z == n:
                    if x * x == y * y + z * z or y * y == x * x + z * z or z * z == x * x + y * y:
                        a = f'{z} {y} {x}'
                        print(a)
                        return

    else:
        print('Impossible')

例如，如果您输入12，您将得到3,4,5如果您输入30，答案将是5,12,13

这三个数字的和必须等于您输入的数字。

有人能帮帮我吗？

Answer 1

注意原始毕达哥拉斯三元系的参数表示的证明。提交人在证据中指出：

​

​

我们可以使用这个证明编写一个优化的算法：

def p(num):
    a, b, c = 1, 1, 0
    n = 0

    while c < num:
        for m in range(1, n):
            a = 2 * m * n
            b = n ** 2 - m ** 2
            c = n ** 2 + m ** 2

            if c >= num:
                return "Impossible!"
            elif a + b + c == num:
                return b, a, c

        n = n + 1

print(p(12)) # >>> (3, 4, 5)
print(p(30)) # >>> (5, 12, 13)
print(p(31)) # >>> Impossible!

Answer 2

你做了很多重复和不必要的工作。你知道A^2 + B^2 = C^2和C > B > A。如果您想说C > A > B并不重要，因为您找到的任何解决方案都会满足于C > B > A。例如，以12和解决方案3、4、5为例。实际上，如果您说A=3和B=4或A=4和B=3并不重要。知道了这一点，我们可以调整每个for循环的循环。

A可以从1到num，那很好。从技术上讲，它可以减少一些，因为您正在为它添加另一个值，至少也必须是1。

然后，B可以从A+1转到num，因为它需要比它更大。

那么C呢？嗯，它不需要离开1，因为这是不可能的。实际上，我们只关心A + B + C = num，所以解决C问题，就可以得到C = num - A - B。这意味着您不需要使用循环来查找C，因为您可以解决它。知道了这一点，你就可以这样做：

In [142]: def find_triplet(num): 
 ...:     for a in range(1, num-1): 
 ...:         for b in range(a+1, num): 
 ...:             # A^2 + B^2 = C^2 
 ...:             # And A+B+C = N 
 ...:             c = num - a - b 
 ...:             if c > 0:
 ...:                 if a*a + b*b == c*c: 
 ...:                     print(f'{a} {b} {c}') 
 ...:             else: 
 ...:                 break 
 ...:                                                                                                                    

In [143]: find_triplet(30)                                                                                                   
5 12 13

那么，为什么要检查C是否>0，否则就会中断？好吧，如果您知道C = num - A - B并且正在递增B，那么一旦B变得太大，C将继续变得越来越负面。因此，您可以检查是否为C > 0，如果不是，则从内环中分离出来，使A增量和B重置。

Answer 3

您讨论的方法具有O(n^3)复杂性。

一个有效的解决方案是运行两个循环，其中第一个循环从x=1运行到n/3，第二个循环从y= x+1运行到n/2。在第二个循环中，我们检查(n )是否等于(x *x+y* y)：

def pythagoreanTriplet(n): 

    # Considering triplets in  
    # sorted order. The value  
    # of first element in sorted  
    # triplet can be at-most n/3. 
    for x in range(1, int(n / 3) + 1):  

        # The value of second element  
        # must be less than equal to n/2 
        for y in range(x + 1,  
                       int(n / 2) + 1):  

            z = n - x - y 
            if (x * x + y * y == z * z):  
                print(x, " ", y, " ",  z)
                return

    print("Impossible") 

# Driver Code 
n = int(input())
pythagoreanTriplet(n)

PS:时间复杂度= O(n^2)