Задачка о разложении числа в сумму квадратов

Yulka-MOl

Столкнулся с задачкой.

Имеется целое число N (0 < N <= 10000), необходимо представить его в виде суммы квадратов целых чисел P[i] (1 <= P[i]) таким образом, чтобы количество слагаемых было минимально возможным.

Пока кроме составления полных таблиц всех вариантов ничего на ум не пришло.
Теория чисел дает некоторые идеи по оптимизации этого процесса.
Может кто-то из форумчан предложит что-то более вменяемое? Можно ли Гауссовы целые числа как-то использовать?
Спасибо.

Marinavo_0507

куда уж более вменяемо, чем заранее посчитать все 10000 ответов

istran

В первую очередь на ум приходит динамическое программирование. По сложности N^(3/2). Ты это под "составлением полных таблиц" имел в виду?

Yulka-MOl

N есть сумма из N единичек (верхняя оценка).
Будем увеличивать кол-во слагаемых от 1 до N. Перебором значения первого слагаемого от 1 до N^(1/2) заполняем таблицу, используя предыдущие расчеты. (Если нет представления, то помечаем флагом или особым значением).
Поправка - немного другой алгоритм

Пусть C[i] — минимальное число слагаемых при разложении числа i. С[0] := 0. Тогда динамика такая:
C[i] = 1 + min_{j \in [1, [sqrt(i)]]} (C[i - j^2])

Сложность N^(3/2).

Хочется как-то улучшить.

marat7256

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

istran

Нет, это неправильный алгоритм. Пример: 41. По твоему выходит 41 = 36 + 4 + 1, хотя оптимальное разложение 41 = 25 + 16.

marat7256

Да, я уже потом сообразил.

istran

Я немного другой алгоритм имел в виду. Пусть C[i] — минимальное число слагаемых при разложении числа i. С[0] := 0. Тогда динамика такая:
C[i] = 1 + min_{j \in [1, [sqrt(i)]]} (C[i - j^2])

Marinavo_0507

Но хочется её как-то улучшить.

зачем, если компьютер выдаст 10000 ответов всё равно быстрее, чем ты напишешь любую программу?