[python] Теорема Лагранжа. Разложение числа на сумму 4-х квадратов

Прохожу курс по основам python. В разделе "Рекурсия" наткнулся на интересную задачу про теорему Лагранжа.

Ограничение по времени
1000 мс
Ограничение по памяти
65536 кб

Теорема Лагранжа утверждает, что любое натуральное число можно представить в виде суммы четырех точных квадратов. По данному числу n найдите такое представление: напечатайте от 1 до 4 натуральных чисел, квадраты которых дают в сумме данное число.

Формат ввода

Программа получает на вход одно натуральное число n < 10000.

Формат вывода

Программа должна вывести от 1 до 4 натуральных чисел, квадраты которых дают в сумме данное число.

Решил ее так

def lagr(n, k):
    n1 = int(n ** 0.5)
    # База рекурсии: число и есть квадрат
    if n1 ** 2 == n:
        print(n1, end='')
        return int(n1 ** 2)
    # Иначе придется перебирать от n1 до 1 вниз
    while n1 >= 1:
        s = n1 ** 2
        # Если еще укладываемся в 4 числа, то надо пробовать разложить разность n - n1**2
        if k + 1 <= 3:
            s += lagr(n - n1 ** 2, k + 1)
        # Нашли сумму квадратов. Выводим через пробел, не перенося строку
        if s == n:
            print(' ', n1, sep='', end='')
            return int(s)
        n1 -= 1
    return 0


n = int(input())
lagr(n, 0)

About the Author: admin

2 комментария

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Яндекс.Метрика