Задач о квадратных корнях

[Иллидан]

Задача: разбить введенное число на сумму таких чисел, из которых вычесляется квадратный корень, причем количество чисел дожно быть наименьшим. Например, 5=4+1 6=4+1+1 8=4+4 9=9 12=4+4+4 72=36+36 109=100+9 У кого какие предложения?

[alexBlack]

1.Берем максимальное целое, квадрат которого не превышает числа - int(sqrt(N))
2.От числа отнимаем квадрат выбранного
3.Если остаток > 0, goto 1

[Иллидан]

Да, я то же так думал. Но получается, что 12=9+1+1+1 (что составляет 4 цифры), а нужно что-бы было 12=4+4+4(3 цифры).

[alexBlack]

А, да, подумаю еще

....

Вот этот код дает возможные разложения кроме самых длинных.
Общая идея:

полный перебор всех возможных разложений.
Но полный перебор был-бы слишком длинным. Поэтому введено ограничение. Алгоритм, который был предложен ранее дает первое приближение. Остальные варианты разложения прерываются как только количество элементов превысит полученное ранее минимальное разложение (lastCount).

procedure TForm1.divSqr(N:integer);
var A:array[1..100] of integer;
    LastCount : integer;

  procedure doNext(k, N:integer);
  var M, i:integer;
      S:String;
  begin
     if k > lastCount then exit;
     if N <= 1 then begin
        if N = 1 then A[k] := 1 else dec(k);
        S := '';
        for i:=1 to k do begin
           S := S + IntToStr(A[i]);
           if i <> k then S:=S +' + ';
        end;
        LastCount := k;
        ListBox2.Items.Add(S);
        exit;
     end;
     M := trunc(sqrt(N));
     while true do begin
        A[k] := M;
        doNext(k+1, N-M*M);
        dec(M);
        if M <= 1 then break
     end;
  end;

begin
   LastCount := 100;
   doNext(1, N);
end;

procedure TForm1.FormCreate(Sender: TObject);
var N:integer;
begin
   N := 1028;
   divSqr(N);
end;

9998==
99+14+1
86+51+1
51+86+1
14+99+1

[B_N]

А вот так:
Берём целое из корня (N/2), возводим в квадрат, отнимаем этот квадрат от N столько раз, сколько получится, над остатком повторяем то же самое...

[alexBlack]

Для 12 нормально, но

100 = 49+49+1+1

Может какая-то теоремка есть по этому поводу ?

[B_N]

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

Может какая-то теоремка есть по этому поводу ?

Да я уже полез по книжкам, из головы же всё повылетало... Что-то похжее было в задачах Ферма, надо еще полистать, жалко же такую задачку брутфорсить

[alexBlack]

Нашел только вот это:

Для любого натурального k существует такое натуральное N (разумеется, зависящее от k ), что каждое натуральное число представимо в виде суммы не более чем N слагаемых, являющихся k-ми степенями целых чисел.
У этой теоремы было известно несколько различных неэлементарных доказательств, но в 1942 году ленинградский математик Ю. В. Линник придумал чисто арифметическое элементарное доказательство, которое, однако, является исключительно сложным ( см., например, книжку А. Я. Хинчина "Три жемчужины теории чисел"). Что касается функции N(k ) , то здесь, в настоящее время почти ничего не ясно. Всякое натуральное число представимо в виде суммы четырех квадратов, девяти кубов (число 9 не может быть уменьшено), 21 штуки четвертых степеней (вот тут, кажется, что 21 может быть уменьшено до 19). Далее - полный туман.

то есть нет смысла искать больше 4-х слагаемых:

   LastCount := 5;

можно еще исключить половину перестановок в слагаемых:

...
     M := trunc(sqrt(N));   
     if (k > 1) and (M > A[k-1]) then exit;
     while true do begin  
...

10 000 002=3161+80+41

[B_N]

Это всё не совсем то, это неразрешимая (пока?) теорема Ферма. Есть теорема Лагранжа - всякое натуральное число можно представить в виде суммы четырех квадратов. Есть признак Дирихле-Гаусса - число вида (4^k)*(8n + 7), k и n - неотрицательные целые, представить суммой трёх квадратов нельзя. Есть еще признак Жирара: Натуральное число представимо в виде суммы квадратов двух целых чисел тогда и только тогда, когда в его разложение на простые множители любой простой множитель вида (4k + 3) входит в четной степени, и такой слабый: Числа, кратные 3, но не кратные 9, представить в виде суммы двух квадратов нельзя. Но это всё если и можно использовать, то разве что для оптимизации. Есть еще способ подсчёта разложений от Дирихле, но кажется дело всё-таки идет к перебору...

[Plague]

вот ссылка на подобную задачу
http://acm.timus.ru/problem.aspx?space=1&num=1073

В одном квадратном государстве жили квадратные люди. И всё остальное в этом государстве было тоже квадратное. Так, Квадратная Дума приняла Квадратный Закон о земле. Согласно этому закону, любой житель государства имел право приобрести землю. Земля продавалась, естественно, квадратными участками. Длина стороны каждого участка выражалась натуральным числом метров. Приобретая участок земли со стороной a метров, покупатель платил a2 квадриков (местная валюта) и получал одно квадратное свидетельство о праве собственности на этот участок. Один житель этого государства решил вложить все свои N квадриков без остатка в покупку земли. Это безусловно можно было сделать, приобретя участки размером 1 Ч 1 метр. Но этот житель потребовал от агентства недвижимости минимизации количества покупаемых участков. «Так мне будет легче общаться с Квадратной Налоговой Инспекцией», — сказал он. Сделка состоялась.

Найдите, какое количество квадратных свидетельств он получил.
Исходные данные

В единственной строке стоит натуральное число N ≤ 60 000 — число квадриков, которое было у жителя.
Результат

В единственной строке стоит число свидетельств, полученных в результате сделки.

А вот так я еще когдато решал

var n,t,a,b,c,s:longint;
begin
  readln(n);
  t:=round(int(sqrt(n)));
  s:=0;
  if t*t=n then s:=1;

if s=0 then
  for a:=t downto 1 do
    begin
      for b:=1 to a do
      if a*a+b*b=n then
        begin
          s:=2;
          break;
        end;
      if s=2 then break;
    end;

if s=0 then
  for a:=t downto 1 do
    begin
      for b:=1 to a do
        begin
          for c:=1 to b do
            if a*a+b*b+c*c=n then
              begin
                s:=3;
                break;
              end;
          if s=3 then break;
        end;
      if s=3 then break;
    end;
if s=0 then s:=4;
  writeln(s);
end.

может поможет?