Есть число N (N<=5000000)
Нужно определить минимальное количество чисел, сумма квадратов каких дает число N. Например, число 61 можна представить в виде суммы квадратов двух чисел 6^2+5^2
Спасибо за внимание. :о)
Похожие задачи уже рассматривались.
В чем конкретно проблема? Чем помочь?
Уж очень не хочется сразу код выкладывать....
на словах ::
count:=0;
1: находишь максимальный полный квадрат и уменьшаешь N на него -- N:=N-sqr(trunc(sqrt(N))); count:=count + 1; если N > 0 тогда goto 1
writeln(count);
решение Virt'а неправильное. например, 12 оно разложит на 3^2+1^2+1^2+1^2, т.е. ответ 4, а можно сделать 2^2+2^2+2^2, т.е. получить ответ 3.
однако, более правильное решение имеет сложность порядка N^(3/2), а для ваших ограничений это многовато (хотя, если памяти хватает, то вполне приемлимо).
понял ошибку ,исправлю.
насколько представляю надо сгенерить все квадраты и по их всевозможным суммам сделать динамику.
Вобще то пока проблема каким образом определять эти квадраты чисел. Я вначале думала так, как Virt. Если максимальное не всегда подходит, значит нужно делать переборы и выбирать, когда количество будет самым маленьким? Пока что не знаю как это делать.
вот правильное решение:
Эта задача решается с помощью динамического программирования.
Сначала проверим, не является ли число полным квадратом. Если так, то сразу выводим "1" и заканчиваем. Если же не является, то придется потрудиться.
Заведем массив размером в 60000 элементов - в нем мы будем хранить количество участков для каждой площади. Пройдем его с 1 до N, если текущее число (i) - квадрат целого числа, то в соответствующий элемент массива записываем 1 и переходим к следующему. Если же это не так, то тут понадобиться еще один цикл (j) от 1, до тех пор, пока разность между i и j2 не станет меньше 1. Итак, мы можем узнать, сколько участков необходимо, чтобы скупить территорию i - j2; для того, чтобы скупить территорию площадью i, необходимо на один участок больше (этот участок со стороной j). Среди всех возможных j выберем минимальное количество участков для площади i и перейдем к следующему i. Этим мы полностью рассматриваем все варианты и выбираем наилучший (в этом несложно убедиться).