Задача на пребор.

[NSvirus]

Простейшее разложение:

begin
clrscr;
 readln(chislo);
 chis2:=chislo;
 repeat
  begin
   perem1:= trunc(sqrt(chislo));
   sum:=sum+sqr(perem1);
   chislo:= chislo-sqr(perem1);
   write(perem1,'*',perem1,'+');
   if (chislo=1) and (sum<>chis2) then for perem3:=1 to chis2-sum do write('1+')
  end;
 until ((chislo=1)or(chislo = 0));
readln;
end.

[Ангелика А]

хорошо попробую написать и выложу...................NSvirus огромное спасибо!!!!!!!!!!!!!!!!!!!

[LeBron]

Ангелика А, только учтите, что NSvirus написал решение для быстрого разложения, которое работает быстро, но не всегда дает верный ответ.

[NSvirus]

Сообщение от LeBron

но не всегда дает верный ответ.

Ответ будет верным всегда, но не всегда будет минимальное число слагаемых.

[LeBron]

Сообщение от NSvirus

Ответ будет верным всегда, но не всегда будет минимальное число слагаемых.

Это как раз и значит - "ответ будет неверным". То, что ответ будет бессмысленным, я не говорил.

[Anatole]

LeBron
Вчера вы меня заинтриговали утверждением, что при рекурсивном способе решения программа переполнит стек.
И я решил проверить данное утверждение. Вот в обеденный перерыв наваял

program CountSqr;

{$APPTYPE CONSOLE}
{Представить произвольное целое число в виде
минимального количества квадратов других чисел}
uses
  SysUtils;
Var
  CountCall : integer;
  i : integer;
  n: int64;
  a,sa : array of integer;
  Kmin : byte ;

   Procedure Fsqr(n:int64; k:integer);
  var
    m: int64;
    i : integer;
begin
  inc(CountCall);
  if (n=0) and (Kmin>k) then
    begin
     Kmin := k;
     For i := 0 to Kmin-1 do Sa[i] := a[i];
     exit;
     end;
 m := trunc(Sqrt(n));
 for I := m downto 1  do
   begin
   a[k] := i;
   Fsqr(n-m*m, k+1);
   if Kmin-1 <= k
      then exit;
   end;
end;

begin
  CountCall := 0;
  Kmin :=100;
  SetLength(a,Kmin);
  SetLength(Sa,Kmin);
  // Read Ln (n)
  n := 2000000000;
  Fsqr(n, 0);
  WriteLn;
  Writeln('n=',n:1);
  for i := 0 to Kmin - 1 do  Write (sa[i]:1,' ');
  WriteLn;
  WriteLn('CountCall=',CountCall);
  ReadLn;
  SetLength(a,0);
  SetLength(Sa,0);

end.

Стэк не перепллняется. Можете проверить. Программа, для статистики. даёт общее количество вызовов рекурсивной процедуры.

[Ангелика А]

Каждый отстаивает свое мнение)))))))))спасибо вам обоим за помощь

[LeBron]

Сообщение от Anatole

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

Во-первых, я гововрил, что будет или ТЛ, или падение стека. Действительно не переполняется, я его недооценил.
Стек то Вы, видимо, спасли, только вот програма нерабочая. Минус мне - не думал, что за умолчанием в паскале такой "стойкий" стек. Минус Вам - програма не работатает. Во-первых, она очень уж торможенная. Во-вторых, она НЕРАБОЧАЯ. Числа, которые выводит вконце - это ответ? тогда не понимаю, как он можт быть верным, если чисел там много. 6 штук кажеться. А в ответе их быть 6 штук не может.

[Anatole]

LeBron
Во первых стек ня не спасал. В этом нет никакой необходимости. Дело в том , что необходимый объём стека зависит не от общего количества вызовов рекурсивной процедуры, а от количества уровней вложения вызовов. В данном случае оно не превышает 10. Для этого вполне достаточно стэка в 1к. (когдато по умолчанию стэк в паскале равнялса 16к). И насчёт большого количества чисел в разложении числа на сумму квадратов. Будьте добры для доказательства своей правоты предложите вариант с меншим количеством чисел.Я надеюсь ваш вариант будет более быстродействующим.

[LeBron]

Сообщение от Anatole

LeBron
И насчёт большого количества чисел в разложении числа на сумму квадратов. Будьте добры для доказательства своей правоты предложите вариант с меншим количеством чисел.Я надеюсь ваш вариант будет более быстродействующим.

Мне влом писать код, а готового исходника у меня на руках нету, так как конкретно эту задачу я еще не решал. Я не говорю о своей правоте. Я говорю о неверности Вашего решения. По поводу рекурсии - теперь буду знать, погуглил немного на эту тему, я не особо знал, так как крайне редко пользуюсь рекурсией. Если интересно, как такое решать, повторю еще раз - Rabin-Shallit algo, в сети есть. По поводу неверности вашего решения -

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

(Википедия).
Так как 2 миллиарда, как мне кажется, не являеться числом Лежандра, то его можно записать даже с помощью суммы 3 квадратов.
З.Ы.

q:=trunc(sqrt(i));

- вот сдесь я глупость написал, надо через разность выводить.