Python-сообщество

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

 def lagr(n):
    t = []
    for a in range(n, -1, -1):
        for b in range(n, -1, -1):
            for c in range(n, -1, -1):
                for d in range(n, -1, -1):
                    if a ** 2 + b ** 2 + c ** 2 + d ** 2 == n:
                        t = t + [a, b, c, d]
                        s = [x for x in t if x != 0]
                        return s
n = int(input())
print(*lagr(n), end='')

ну хотя бы от int(sqrt(n)) итерируйтесь, иначе совсем тупо выходит.

а вообще вам нужно найти все разложения или любое?

если все, то вот вам в помощь - https://en.wikipedia.org/wiki/Jacobi%27s_four-square_theorem

Comandante4
Подскажите, пожалуйста, можно ли это сделать более оптимально?

Comandante4ну начнем с того что вы неправильно интерпретируете теорему.
Теорема Лагранжа утверждает, что любое натуральное число можно представить в виде суммы не более, чем четырех точных квадратов. Пять, например, вы ну никак не представите в виде суммы четырех квадратов, поэтому не стоит зацикливаться на четырех итерациях.

py.user.next
Надо взять корень числа. Потом от этого корня взять целую часть, возвести её в квадрат и вычесть из числа. Для остатка проделать всё то же самое. Так максимум за четыре шага ты найдёшь все числа.

[code python][/code]

Отредактировано PEHDOM (Янв. 10, 2018 16:24:23)

PEHDOM
23 по такой методе раскладывается на 5 чисел

PEHDOM
Comandante4ну начнем с того что вы неправильно интерпретируете теорему.Теорема Лагранжа утверждает, что любое натуральное число можно представить в виде суммы не более, чем четырех точных квадратов. Пять, например, вы ну никак не представите в виде суммы четырех квадратов, поэтому не стоит зацикливаться на четырех итерациях.

Comandante4 Ну вобщем py.user.next все верно написал, наиболее оптимально будет рекурсивная функция, которая принимает число и максимальное количество шагов для его разложения.
Если вам интерсно самому сделать, пробуйте. Сразу скажу готовое решение есть(и не одно), но пока не буду его приводить, вдруг вы хотите сами разобраться.

Теперь замечания по поводу именно вашего алгоритма.
1. нет смысла делать четыре цикла по n, максимально возможный корень будет int(n**0.5), следовательно перебирать варианты более этого значения бессмыслено. Вы получите существенный прирост в скорости даже не в разы, а на порядки.
2. вы делаете a ** 2 + b ** 2 + c ** 2 + d ** 2 каждый раз в самом вложеном цикле, хотя достаточно делать вычислять квадрат a,b,c и d соотвевенно только при их изменении, что еще добавит скорости
3. поскольку мы возводим только в квадрат, то заменить a ** 2 на а*а, это еще чутка добавит производительности, (это уже особенности алгоритма возведения в степень пайтоном).

[code python][/code]

Отредактировано PEHDOM (Янв. 16, 2018 22:32:48)

PEHDOM

PEHDOM
Сразу скажу готовое решение есть(и не одно), но пока не буду его приводить, вдруг вы хотите сами разобраться.

PEHDOM, пожалуйста, проверцте личку

vanyamoscow, пожалуйста, поделитесь решением, если раздобыли, а пока не справилась с этой задачкой

Оптимизировал без рекурсии. Сделал юнит-тесты.

Идея с последовательным вычислением корней не сработала.

Отредактировано py.user.next (Апрель 17, 2020 10:42:01)

Прикреплённый файлы:
lagrsq.tar.gz (1,1 KБ)