Минимальное количество чисел, Сумма квадратов которых дает число N Опции

[Tauka]

Есть число N (N<=5000000)
Нужно определить минимальное количество чисел, сумма квадратов каких дает число N. Например, число 61 можна представить в виде суммы квадратов двух чисел 6^2+5^2
Спасибо за внимание. :о)

[APAL]

Похожие задачи уже рассматривались.
В чем конкретно проблема? Чем помочь?
Уж очень не хочется сразу код выкладывать....

[virt]

на словах ::
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]

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

[Tauka]

Вобще то пока проблема каким образом определять эти квадраты чисел. Я вначале думала так, как Virt. Если максимальное не всегда подходит, значит нужно делать переборы и выбирать, когда количество будет самым маленьким? Пока что не знаю как это делать.

[virt]

Код

program minimum_kvadrats;
var a:array[1..32000]of word;
   n,i,j:longint;
   s:word;

begin
  readln(n);
  fillchar(a,sizeof(a),0);
  if sqr(trunc(sqrt(n))) = n then writeln(1) else
     begin
        for i:=1 to n do
           if sqr(trunc(sqrt(i))) = i then a[i]:=1 else
              begin
                 s:=maxint;
                 for j:=1 to trunc(sqrt(i)) do
                    if a[i-sqr(j)]+1 < s then s:=a[i-sqr(j)]+1;
                 a[i]:=s;
              end;
        writeln(a[n]);
     end;
end.

решение по алгоритму предложенному Михаилом.

ЗЫ
для 5.000.000 надо 10Мб ,существует ли алгоритм с меньшими требованиями памяти?

[Михаил Густокашин]

вот правильное решение:
Эта задача решается с помощью динамического программирования.
Сначала проверим, не является ли число полным квадратом. Если так, то сразу выводим "1" и заканчиваем. Если же не является, то придется потрудиться.

Заведем массив размером в 60000 элементов - в нем мы будем хранить количество участков для каждой площади. Пройдем его с 1 до N, если текущее число (i) - квадрат целого числа, то в соответствующий элемент массива записываем 1 и переходим к следующему. Если же это не так, то тут понадобиться еще один цикл (j) от 1, до тех пор, пока разность между i и j2 не станет меньше 1. Итак, мы можем узнать, сколько участков необходимо, чтобы скупить территорию i - j2; для того, чтобы скупить территорию площадью i, необходимо на один участок больше (этот участок со стороной j). Среди всех возможных j выберем минимальное количество участков для площади i и перейдем к следующему i. Этим мы полностью рассматриваем все варианты и выбираем наилучший (в этом несложно убедиться).