Выразите число в виде суммы четырех квадратов Нужно написать программу на python

Question

Выразите число в виде суммы четырех квадратов Нужно написать программу на python

Здислав Кулеш Гуру (2926), закрыт 1 год назад

Недавно у вас была ссора с учителем математики. Мало того, что этот ботаник требует знания всех теорем, так еще и оказался приверженцем конструктивизма! После того, как вы прочитали наизусть теорему Лагранжа о сумме четырех квадратов , он теперь требует компьютерную программу для получения такого разложения, чтобы убедиться, что вы действительно понимаете тему. Какой депрессант!

Вы хорошо помните теорему. Любое натуральное число можно разложить в сумму четырех квадратов целых чисел. Вроде и не сложно... Но после ссоры твой учитель хочет крови. Видимо, он будет тестировать вашу программу на чрезвычайно больших числах... И лучше бы ваша программа доработала до перерыва - Fведь вы же не хотите получить ?

Совет: случайные тесты включают 20 чисел не выше 2^128и 20 чисел не выше 2^1024.

Дополнен 1 год назад

Недавно у вас была ссора с учителем математики. Мало того, что этот ботаник требует знания всех теорем, так еще и оказался приверженцем конструктивизма! После того, как вы прочитали наизусть теорему Лагранжа о сумме четырех квадратов, он теперь требует компьютерную программу для получения такого разложения, чтобы убедиться, что вы действительно понимаете тему. Какой депрессант!

Вы хорошо помните теорему. Любое натуральное число можно разложить в сумму четырех квадратов целых чисел. Вроде и не сложно... Но после ссоры твой учитель хочет крови. Видимо, он будет тестировать вашу программу на чрезвычайно больших числах... И лучше бы ваша программа доработала до перерыва - Fведь вы же не хотите получить ?

Совет: случайные тесты включают 20 чисел не выше 2^128и 20 чисел не выше 2^1024.

Программа должна быть оформлена:

from typing import Tuple

def four_squares(n: int) -> Tuple[int, int, int, int]:

return 0, 0, 0, 0

и пройти ниже следующие тесты:

def static_tests():

for i in [0, 1, 17, 33, 215, 333, 2**12-3, 1234567890, 106369249365575352836589875696130383747]:

a, b, c, d = four_squares(i)

error_msg = None

if type(a) is not int: error_msg = "1st square is not of type int"

if type(b) is not int: error_msg = "2nd square is not of type int"

if type(c) is not int: error_msg = "3rd square is not of type int"

if type(d) is not int: error_msg = "4th square is not of type int"

s = a * a + b * b + c * c + d * d

if s != i:

error_msg = f"Incorrect sum.\nSquares: [{a}, {b}, {c}, {d}]\nActual: {a * a + b * b + c * c + d * d}\nExpected: {i}"

if error_msg is not None:

test.fail(error_msg)

else:

test.pass_()

Answer 1

Реализация немного примитивная, и для совсем сложных случаев уйдёт в очень долгий перебор. Но на тестовых данных из задания отрабатывает быстро.

 from typing import Tuple
from math import isqrt

def trybreakdown(n, k):
    if n == 0: return tuple([0] * k)
    for m in range(isqrt(n), isqrt((n - 1) // 2), -1):
        sq = m * m
        if k == 1: return (None, (m,))[sq == n]
        t = trybreakdown(n - sq, k - 1)
        if t is not None: return (m, *t,)
    return None

def four_squares(n: int) -> Tuple[int, int, int, int]:
    return trybreakdown(n, 4)

К этому прилепи свой тестовый код, а то я хз, что эти test.fail , test.pass_ должны делать, у меня они не работают.

Принцип простой: для разбиения на k квадратов сначала находим наибольшее число m, квадрат которого не превышает n (это называется целочисленным квадратным корнем из n). Далее пробуем разбить на n - m² на k - 1 квадратов, а если k уже равно 1, то просто проверяем, что m² == n и возвращаем либо m, либо неуспех.
Если разбиение для k == 1 не подошло, то этажом выше (k == 2) пробуем всё то же самое для m - 1. Если на уровне k == 2 закончились числа, то на k == 3 пробуем m - 1. И так далее.
На каждом уровне перебор ограничен снизу целочисленным квадратным корнем из половины n, потому что если, скажем, комбинация (8, 7) не подошла, то нет смысла проверять комбинацию (7, 8).
Поскольку задача решается для любого целого n, перебор рано или поздно закончится нахождением нужной комбинации чисел.

Результаты для тестовых данных из задания:

 Successful breakdown of 0: [0, 0, 0, 0]
Successful breakdown of 1: [1, 0, 0, 0]
Successful breakdown of 17: [4, 1, 0, 0]
Successful breakdown of 33: [5, 2, 2, 0]
Successful breakdown of 215: [13, 6, 3, 1]
Successful breakdown of 333: [18, 3, 0, 0]
Successful breakdown of 4093: [62, 14, 7, 2]
Successful breakdown of 1234567890: [35136, 171, 12, 3]
Successful breakdown of 106369249365575352836589875696130383747: [10313546885799053409, 4033636996, 13985, 615]

Существуют числа, для которых перебор будет долгим (у которых первое слагаемое отстоит достаточно далеко от целочисленного квадратного корня, что приведёт к перебору больших диапазонов). Если в вашем тесте такие попадутся - что можно сказать, не повезло. Тогда можно обратиться к помощи более сложного алгоритма:
https://mathoverflow.net/questions/259152/efficient-method-to-write-number-as-a-sum-of-four-squares
При хорошем распределении случайных величин он должен давать в среднем чуть более, чем логарифмическую сложность, а точнее:

 O(log n × log log n)

Answer 2

SERN Профи (840) 1 год назад

print("pipiska bolshaya da da ye ye")