Кто-нибудь может оптимизировать мой код 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

Подход, который вы обсуждали, требует сложности O (n ^ 3).

Эффективным решением является запуск двух циклов, где первый l oop проходит от x = 1 до n / 3, второй l oop работает от y = x + 1 до n / 2. Во втором l oop мы проверяем, равно ли (n - x - y) (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)

Answer 2

Обратите внимание на доказательство для параметри c представления примитивных пифагорейских троек . В доказательстве автор утверждает:

Мы можем использовать это доказательство для написания оптимизированного алгоритма:

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 3

Вы делаете много повторной и ненужной работы. Вы знаете это 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. Зная это, мы можем настроить петли каждого для l oop.

A может go с 1 до num, это нормально. Технически это может на go немного меньше, так как вы добавляете к нему другое значение, которое должно быть не менее 1.

B тогда может go от A+1 до num поскольку оно должно быть больше, чем оно.

Так что насчет C? Ну, это не нужно go от 1, так как это невозможно. На самом деле мы заботимся только о A + B + C = num, поэтому решите за C, и вы получите C = num - A - B. Это означает, что вам не нужно использовать al oop, чтобы найти 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, а если нет, вырваться из этого внутреннего l oop, чтобы иметь A приращение и B сброс.