Сумма квадратов Опции

[klem4]

Продолжаю выкладывать понравившиеся мне олимпиадные задачи

Пара четверок. Найти минимальное число, которое представляется суммой четырех квадратов натуральных чисел не единственным образом

т.е 1112 и 1121 - одно и тоже.


Вот мое первое решение, если доделаю сейчас, выложу втрое, более короткое

uses crt;
var
   i,j,k,l,t : byte;
   n : word;
   a : array[1..4] of byte;
   flag : boolean;
begin
   clrscr;
   n := 0;
   repeat
      inc(n);
      flag := true;
      fillchar(a, sizeof(a), 0);
      i := 1;
      while (sqr(i) < n) and flag do begin
         j := 1;
         while(sqr(i) + sqr(j) < n) and flag do begin
            k := 1;
            while(sqr(i) + sqr(j) + sqr(k) < n) do begin
               l := 1;
               while(sqr(i) + sqr(j) + sqr(k) + sqr(l) <= n) and flag do begin
                  if sqr(i) + sqr(j) + sqr(k) + sqr(l) < n then inc(l)
                  else begin
                     if a[1] = 0 then begin
                        a[1] := i; a[2] := j; a[3] := k; a[4] := l;
                        inc(l);
                     end{A[1] = 0}
                      else begin
                         t := 1;
                         while (t <= 4) and flag do begin
                            flag := not((a[t] <> i) and (a[t] <> j) and (a[t] <> k) and (a[t] <> l));
                            inc(t);
                         end;{WHILE}
                         if not(flag) then begin
                            writeln(n);
                            writeln(i,' ',j,' ',k,' ',l);
                            writeln(a[1],' ',a[2],' ',a[3],' ',a[4]);
                         end;{END}
                      end;{A[1] <> 0}
                  end;{S = N}
                  inc(l);
               end;{L}
               inc(k);
            end;{K}
            inc(j);
         end;{J}
         inc(i);
      end;{I}
   until not(flag);
   readln
end.

Давайте, может у кого-то будут координально другие идеи !

[xds]

Неопределённость в условии - поэтому два решения. Первое - для случая, когда в сумме могут присутствовать одинаковые слагаемые, второе - для случая, когда все слагаемые различны. Естественно, результаты отличаются.

1) С повторениями:

program Sqr4;

type
  T4 = array[0..4] of LongInt;

procedure AdvanceT4(var a: T4);
begin
  if a[3] < a[4] then
    Inc(a[3])
  else
    if a[2] < a[3] then
      Inc(a[2])
    else
      if a[1] < a[2] then
        Inc(a[1])
      else
        begin
          a[1] := 1;
          a[2] := 1;
          a[3] := 1;
          Inc(a[4]);
        end;
  Inc(a[0]);
end;

procedure WriteT4(const a: T4);
begin
  Writeln(
    '= Sqr(', a[1],
    ') + Sqr(', a[2],
    ') + Sqr(', a[3],
    ') + Sqr(', a[4], ')'
  );
end;

var
  a, b: T4;
  na, nb: LongInt;
  i: Integer;

begin
  for i := 0 to 4 do
    begin
      a[i] := 1;
      b[i] := 1;
    end;
  repeat
    na := Sqr(a[1]) + Sqr(a[2]) + Sqr(a[3]) + Sqr(a[4]);
    nb := Sqr(b[1]) + Sqr(b[2]) + Sqr(b[3]) + Sqr(b[4]);
    if na < nb then
      AdvanceT4(a)
    else
      if (na > nb) or (a[0] = b[0]) then
        AdvanceT4(b)
      else
        Break;
  until False;
  Writeln(na);
  WriteT4(a);
  WriteT4(b);
end.

2) Без повторений:

program Sqr4;

type
  T4 = array[0..4] of LongInt;

procedure AdvanceT4(var a: T4);
begin
  if a[3] < a[4] - 1 then
    Inc(a[3])
  else
    if a[2] < a[3] - 1 then
      Inc(a[2])
    else
      if a[1] < a[2] - 1 then
        Inc(a[1])
      else
        begin
          a[1] := 1;
          a[2] := 2;
          a[3] := 3;
          Inc(a[4]);
        end;
  Inc(a[0]);
end;

procedure WriteT4(const a: T4);
begin
  Writeln(
    '= Sqr(', a[1],
    ') + Sqr(', a[2],
    ') + Sqr(', a[3],
    ') + Sqr(', a[4], ')'
  );
end;

var
  a, b: T4;
  na, nb: LongInt;
  i: Integer;

begin
  for i := 0 to 4 do
    begin
      a[i] := i;
      b[i] := i;
    end;
  repeat
    na := Sqr(a[1]) + Sqr(a[2]) + Sqr(a[3]) + Sqr(a[4]);
    nb := Sqr(b[1]) + Sqr(b[2]) + Sqr(b[3]) + Sqr(b[4]);
    if na < nb then
      AdvanceT4(a)
    else
      if (na > nb) or (a[0] = b[0]) then
        AdvanceT4(b)
      else
        Break;
  until False;
  Writeln(na);
  WriteT4(a);
  WriteT4(b);
end.