5

Задача: пользователь вводит число не больше чем 10 000 000, программа должна разложить число на сумму квадратов так, чтобы этих квадратов было минимальное количество

Пример: 34 = 25+9

35 = 25+9+1

32 = 16+16

39 = 25+9+4+1

Честно, питон знаю на 6+, но сам алгоритм никак не соображу, помогите хотя бы с ним

2
  • 1
    Что-то типа динамического программирования?
    – Harry
    6 сен 2020 в 19:29
  • 3
    Вполне себе случай динамического программирования, число квадратов — оптимизируемый функционал, а вычитая из разлагаемого числа первый квадрат, получаем меньшую задачу.
    – bipll
    6 сен 2020 в 21:03

4 ответа 4

5

Попробуйте подумать в такую сторону

S = summ(a[i]*i*i); где i=1..sqrt(10 000 000), a[i] - множители. Целевая функция min(summ(a[i]))

Понятно что самый длинный вариант это сумма единичек. Взяв за основу единички можно уменьшать целевую функцию добавив квадраты больших чисел. И не смотреть при переборе варианты когда целевая функция принимает большее значение чем текущая.

Идея такая что нужно схлопывать единички до минимума целевой функции. Это как вариант в какую сторону двигаться. У кого есть что нибудь получше пишите мне тоже интересно.

Вот статья в которой доказывается следующий факт.

Если x^2 + y^2 = n , то

(x+y)^2 + (x-y)^2 = 2*n

Имея данную формулу можно быстро уменьшить перебор для исходной целевой функции.

Ещё вот интересная теорема о том что наша целевая функция меньше либо равна 4.

Теорема Лагранжа о сумме четырёх квадратов утверждает, что

Всякое натуральное число можно представить в виде суммы четырёх квадратов целых чисел.

Круг поиска отсюда ещё сузился.

Так как их максимум четыре можно в четыре вложенных циклов получить как тут или вот пример реализации на С.

2
  • Факт тривиален и без статьи.
    – bipll
    6 сен 2020 в 19:08
  • Кто спорит, я лишь стараюсь помочь 6 сен 2020 в 19:13
2

Как вариант, но мне кажется, что этот алгоритм довольно далек от оптимального:

from math import sqrt

def main():
    number = int(input('Enter the number: '))
    for k in range(1, 5):
        decompose = to_sum_of_squares(number, k)
        if decompose:
            print(decompose)
            break

def to_sum_of_squares(n:int, k:'squares count:int')->list:
    if (n < 0) or (k <= 0):
        return []
    maximum = round(sqrt(n))
    if n == maximum*maximum:
        return [n]
    for c in range(1, maximum+1):
        decomposition = to_sum_of_squares((n-c*c), k-1)
        if decomposition:
            return [c*c]+decomposition
        
if __name__ == '__main__':
    main()

Вот "перевод" на Python со статьи, которую указал @Aziz Umarov с некоторыми оптимизациямми вычислений и дополнениями (квадрат ли введенное число; выбор наикратчайшей суммы, а не первой попавшейся):

def main(N):
    sqrt = int(math.sqrt(N))
    if N == sqrt*sqrt:
        return [N]
    res = []
    Y = x = math.ceil(math.sqrt(N)/2)
    x_sq = x*x
    while x_sq <= N:
        while Y and (Y-1)*(Y-1)*3 >= N - x_sq:
            Y -= 1
        y=Z=Y
        y_sq = y*y
        while (y <= x) and (x_sq + y_sq <= N):
            while Z and (Z-1)*(Z-1)*2 >= N - x_sq - y_sq:
                Z -= 1
            z=t=Z
            z_sq = z*z
            while (z <= y) and (x_sq + y_sq + z_sq <= N):
                while t*t > N - x_sq - y_sq - z_sq:
                    t -= 1
                if x_sq + y_sq + z_sq + t*t == N:
                    r = [x_sq, y_sq, z_sq, t*t]
                    res.append(r)
                z += 1
                z_sq = z*z
            y += 1
            y_sq = y*y
        x += 1
        x_sq = x*x
        
    for r in res:
        while 0 in r:
            r.remove(0)
    res.sort(key=lambda x: len(x))
    return res[0]
1

Задачу решил, отталкивался от того о чем писал Aziz Umarov про теорему Лагранжа

import sys

num = int(input())
if int(num ** (1 / 2)) == num ** (1 / 2):
    print(1)
    sys.exit()

k = int(num ** (1 / 2))
i = 0
x = k
j = k
for _ in range(j):
    if i > 1:
        print(4)
        break
    x = int(num ** (1 / 2))
    j = x
    for _ in range(j):
        x = int(num ** (1 / 2))
        for _ in range(x):
            #print(i, j, x)
            if (i * i) + (j * j) + (x * x) == num:
                if i > 0:
                    print(3)
                else:
                    print(2)
                break
            x -= 1
        j -= 1
    i += 1

Для тех кому трудно понять, что делает код:

есть 3 множителя: i, j, x.

i= 0, а x и j = корню из самого большого числа, которое <= введенному

код перебирает все значения множителей так, чтобы i^2 + j^2+ x^2 == введенному числу

если такой случай найден, то если i всё ещё = 0, достаточно 2 множителей, если же i = 1, то множителей нужно 3.

Если же такой случай не найден, то нужно 4 множителя.

2
  • Необходимость четырёх слагаемых проверить нетрудно - это числа вида 4^k*(8m+7) - т.е. делить на 4, пока делится, а потом проверить остаток по модулю восемь. А что, приведённый код по скорости пригоден для решения до 10 000 000 ?
    – MBo
    7 сен 2020 в 5:39
  • дело в том, что ТЗ отличается. человеку нужно разложить на сумму, а показать длину этой самой суммы.
    – n1tr0xs
    7 сен 2020 в 12:20
-8
input_number = int(input('Введите число:'))

a = input_number - 45
b = 45
res = a + b 

print(a, '+', b,'=',res)

Типо так?

1
  • 3
    +1 за незамутнённость. 6 сен 2020 в 18:46

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.