Тест на логику (олимпиадные задачи) Опции

[___ALex___]

Народ, предложите своё решение...

1. Составить алгоритм заполнения прямоугольной таблицы размером N*N целыми числами от 1 до N*N по спирали. Пример для N=5.

  1        2        3        4      5
16      17      18      19      6
15      24      25      20      7
14      23      22      21      8
13      12      11      10      9

2. Переставить две части массива А из n элементов, первая часть - элементы с номерами от 1 до m, вторая - от m+1 до n. При этом порядок элементов в каждой из частей должен быть сохранен и нельзя использовать дополнительные массивы.
Пример. n=9, m=5
Вход: 9 4 7 2 3 5 8 1 6 Выход: 5 8 1 6 9 4 7 2 3

[___ALex___]

Ivs: спираль, но код покомпактней малость

Код

program Spiral;
var
Mas: Array[1..n, 1..n] of Integer;
i, x, g, e, s: Integer;
 
begin

g := 0;
e := n + 1;
s := 0;
x := 0;

repeat
 Inc(s);
 Inc(g);
 Dec(e);
 for i := g to e do begin Inc(x); Mas[s, i] := x; end;
 for i := s + 1 to e do begin Inc(x); Mas[i, e] := x; end;
 for i := e - 1 downto g do begin Inc(x); Mas[e, i] := x; end;
 for i := e - 1 downto s + 1 do begin Inc(x); Mas[i, s] := x; end;
until x = Sqr(n);

WriteLn;
for i := 1 to n do begin
 for x := 1 to n do Write(Mas[i, x]:5, ' ');
 WriteLn;
end;

ReadLn
end.

Добавлено (13.01.03 20:58):

Ivs
а с обменом в массиве ты эмулировал сдвиг я понял. эта мысль мне в голову пришла первой, но никогда не задумывался об эффективности?! при таком подходе используется m * n перестановок! можно сделать за n! я сам ещё не доделал эту фишку (сессия фигова)
Удачи

Добавлено (14.01.03 22:42):

Ivs

Код

program Perestanovka;
const
n = 9;
m = 8;
k = n - m;
var
A: Array[1..n] of Byte;
t1, t2: Byte;
i, nInd, Ind, cob: Integer;

begin

for i := 1 to n do begin A[i] := i; Write(A[i], ' '); end;

cob := 0;
nInd := cob;
if (m > 0) and (m <> n) then
if n mod m = 0 then
for i := 1 to m do
 begin
  Ind := i;
  t2 := A[i];
  repeat
   t1 := t2;
   if Ind <= m then Inc(Ind, k) else Dec(Ind, m);
   t2 := A[Ind];
   A[Ind] := t1;
  until Ind = i;
 end else
 begin
  repeat
   Inc(nInd);
   t2 := A[nInd];
   Ind := nInd;
   repeat
    Inc(cob);
    t1 := t2;
    if Ind <= m then Inc(Ind, k) else Dec(Ind, m);
    t2 := A[Ind];
    A[Ind] := t1;
   until (Ind = nInd) or (cob = n);
  until cob = n;
 end;

WriteLn;
for i := 1 to n do Write(A[i], ' ');

ReadLn

end.

Вот этот алгоритм выполняет требуемые действия за n перестановок твой же за m * n! Я прогнал на время (по 30000000 циклов) каждый алгоритм!
Вот результаты:
Брал пограничные значения m (то есть 1 и n - 1) и n = 9
При m = 1 твой алгоритм опережал мой на 2 секунды!( это из-за большего числа разных условий и дополнительных операций в моей реализации, следовательно если юзаешь только одиночные сдвиги, то твой предпочтительней потому что он проще и быстрее, но мой надо использовать при сдвигах больших единицы (для этой цели он собственно и кодился!!!) )
При m = 8 мой алгоритм опережал твой на 16 секунд! Вот такие дела! Кстати ты не знаешь как узнать дату последнего выключения компа???Очень надо!