Заполнение квадратной матрицы по спирали

[serg_sk]

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

[Omnifarious]

Вот программа на C# - она печатает элементы по спирали. Писалась года полтора назад. Сейчас не имею возможности работоспособность проверить - скорее всего нужна будет доводка циклов( мы тогда крепко перемудрили ).

Код: Выделить всё

using System;


namespace Matrix
{

    class Class1
    {

  static void Main(string[] args)
  {
      int m = Convert.ToInt32(Console.ReadLine());
      int n = Convert.ToInt32(Console.ReadLine());

      int[,] matrix = new int[m,n];

//Заполняет рандомом
      Random randomizer = new Random();
      for (int i=0; i<m; i++)
      {
    for(int j=0; j<n; j++)
    {
        matrix[i,j] = randomizer.Next(9);
    }
      }
//Просто печатает
      for (int i=0; i<m; i++)
      {
    for(int j=0; j<n; j++)
    {
        Console.Write(matrix[i,j] + "\t");
    }
    Console.Write("\n");
      }

//Печатает по спирали
//Писалось для произвольных матриц - для квадратных, наверное можно //упростить...
      int k1 = 0;
      int k2 = 0;
      int a=0;
      int b=0;
      if(m>=n)
      {
[B]
//Собственно сами циклы - для квадратной, скорее всего, переменных(для индексов) вдвое меньше выйдет...
                                    do
    {
        for(b=k2; b<n; b++)
      Console.Write(matrix[a,b]);
        b--;
        for(a=k1+1; a<m; a++)
      Console.Write(matrix[a,b]);
        a--;
        for(b=b-1; b>=k2; b--)
      Console.Write(matrix[a,b]);
        b++;
        for(a=a-1; a>k1; a--)
      Console.Write(matrix[a,b]);
        a++;
        n--;
        m--;
        k1++;
        k2++;
    }while((m-k1>0)||(n-k2>0));
[/B]
      }
      else
      {
    do
    {
        for(a=k1; a<m; a++)
      Console.Write(matrix[a,b]);
        a--;
        for(b=k1+1; b<n; b++)
      Console.Write(matrix[a,b]);
        b--;
        for(a=a-1; a>=k2; a--)
      Console.Write(matrix[a,b]);
        a++;
        for(b=b-1; b>k1; b--)
      Console.Write(matrix[a,b]);
        b++;
        n--;
        m--;
        k1++;
        k2++;
    }while((m-k1>0)||(n-k2>0));
      }
      Console.ReadLine();
  }
    }
}

Как работает, и что для чего используется, извини, не помню.
Удачи.

[serg_sk]

Эм.. я забыл сказать, что нужно это все на паскале. От программирования я далек. От си тоже.

[Omnifarious]

Извини, с паскалем помочь ничем не могу.

[serg_sk]

Для Omnifarious:
Алгоритм опиши Я разберусь. А то сидеть разбираться в операторах си, желания нету

[KiWi]

примерно так:

Код: Выделить всё

Program teyufge;
Const
  { это типа комменты будут :-) }
  size = 5;
Var
  matr : Array[1..size, 1..size] of Real;
  i, h, x, y, dx, dy, t, d, k: Integer;
Begin
  { Количество "кругов" }
  if size mod 2 = 0 then h := size div 2 else h:= size div 2 + 1;
  for i:=h downto 1 do begin
    { Типа дельты относительно стартового квадрата }
    dx := 0;
    dy := 0;
    if size mod 2 = 0 then begin
      { Типа  стартовая позиция }
      y := size div 2 - i + 1;
      x := y;
      { Количество ячеек }
      t := 4*(2*i - 1);
      { 1ый поворот :-) }
      d := 2*i;
    end else begin
      y := size div 2 - i + 2;
      x := y;
      t := 8*(i - 1);
      d := 2*i - 1;
    end;
    if t = 0 then t:= 1;
    for k:=1 to t do begin
      { Считываем }
      read(matr[x+dx, y+dy]);
      { Меняем дельты по поворотам }
      if k < d then inc(dy)
       else if k < (2*d - 1) then inc(dx)
       else if k < (3*d - 2) then dec(dy)
       else dec(dx);
    end;
  end;
End.

вроде так, насколько я помню паскаль(fpc лень ставить (: )
и вроде правильно работает(снаружи внутрь спиралью, если я правильно понял что есть спираль :-) )
единственное, что не помню - как пишется elseif :-)


алгоритм:
1. считаем количество кругов
2. вычисляем координаты начала круга(заодно количество ячеек в круге, повороты)
3. обходим все круги по часовой стрелке

[Sparky]

Тут глянь

[serg_sk]

Для Sparky:
А чего там? У меня криво отображается Кстати гугл тоже меня туда отправил, но из-за того, что оно криво отображается, я смотреть не стал.
Для mani13:
Испытаем Только сначало, нужно уловить ход мысли

[Sparky]

А ты сорсы страницы посмотри...

[serg_sk]

Для Sparky:
Ну там есть похожее задание. Но ни нету ни алгоритма решения, ни самого решения Хоть бы линк был какой-то, но теорию нужную для решения

[Omnifarious]

Насколько могу сейчас разобраться, получается примерно следующее:

Интуитивно - пробежал по кругу от левого верхнего по часовой стрелке. А потом получаешь ту же задачку, только для матрицы на 1 меньних размеров - уменьшил размер(m и n) и побежал поновой, только уже со следующего элемента главной диагонали(k1 и k2 увеличил на 1). Так и бегаешь кругами, пока размер не станет 1 или 0.

В моей программе вроде вот так описать можно:
матрица - четыре стороны - для прохождения одного витка четыре цикла:
1 - с левого верхнего угла - направо до упора
2 - теперь сдвинулись на 1 элемент ниже и с него лдо упора вниз
3 - на 1 элемент налево и до упора влево
4 - на 1 элемент вверх и до предпоследнего элемента вверх(самый первый вывели в 1 цикле)
k1 хранит строчку, которую будем выводить при прохождении вправо
k2 - столбец, с которого начали идти вправо
Т.о. k1 k2 - положение элемента, с которого начинается обход.
a и b - просто индексы. В них получается текущее положение перед сменой направления.
После полного витка - уменьшаем размеры матрицы(m и n) и сдвигаем k1 и k2 на единицу. И так, пока размер не станет меньше 1.
Т.к. у тебя матрицы квадратные, то m=n и k1=k2.

[sash-kan]

примерно то же самое, что и у Omnifarious , только на ломаном (: паскале
(давно на нем ничего не писал).
написано только что, по воспоминаниям 18-летней давности.
возможны ошибки. в общем, смотри сам.

Код: Выделить всё

m(0..n-1,0..n-1)=... - матрица n x n
/* про координаты
левый верхний угол - координаты x=0, y=0
правый верхний угол - координаты x=n-1, y=0
левый нижний угол - координаты x=0, y=n-1
правый нижний угол - координаты

  function обход_матрицы (n, x, y)
  /*
  n - размер текущей вложенной матрицы
  x,y - координаты левого верхнего угла влож. матрицы
  */
    xi, yi - координаты текущего элемента
  begin
    if n > 0
    then begin
      вывод_элемента m(x, y);
      if n > 1
      then begin
        xi := x;
        yi := y;
        while (xi <> (x + 1) and yi <> (x + 1))
        do begin
          if xi = x /* верх. строка */
          then begin
            if yi < y + n - 1
            then yi := yi + 1;
            else xi := xi + 1
          end
          else if yi = y + n - 1 /* прав. столбец */
          then begin
            if xi < x + n - 1
            then xi := xi + 1;
            else yi := yi - 1;
          end
          else if xi = x + n - 1 /* ниж. строка */
          then begin
            if yi > y
            then yi := yi - 1;
            else xi := xi - 1;
          end
          else if yi = y /* лев. столбец */
          then begin
            if xi > x + 1
            then xi := xi - 1;
            else /* прошли полный круг */
            begin
              yi := yi + 1;
              обход_матрицы (n - 2, xi, yi)
            end;
          end;
          /* начало корректировки */
          if not ((xi = x + 1) and (yi = y + 1)) then
          /* смысл корректировки - чтобы не выводились
              задним числом элементы (0,0), (1,1) и т.д. */
          /* конец корректировки */
          вывод_элемента m(xi, yi);
        end;
      end;
    end;
  end;
begin
  обход_матрицы (n, 0, 0)
end;

внес корректировки. а то была логическая ошибка.

[harms]

Алгоритм обхода с применением маркеров "я здесь уже был"
Типа мышь бежит вдоль стены и сворачивает вправо, если упрется в стенку или в собственный след
"Похоже" (в алгор. смысле) на сделанное Sash Kan, только короче
НЕ ПРОВЕРЯЛ + МОГУТ БЫТЬ ОПЕЧАТКИ

Код: Выделить всё

dest_matrix:array [1..SIZE, 1..SIZE] of int;
mark:array [1..SIZE, 1..SIZE] of bool; //i was here?

for i:=1 to SIZE do
  for i:=1 to SIZE do
    mark[i,j]:=false;

dx:=1;  //идем влево
dy:=0;

x:=1; y:=1;
xp:=0; yp:=0; //предыдущ коорд
counter:=1;

while(x<>xp and y<>yp) do begin
  mark[x,y]:=true;
  dest_matrix[x,y]:=counter;
  inc(counter);
  xp:=x;
  yp:=y;

  if( x+dx > SIZE or
      x+dx < 1 or
      y+dy > SIZE or
      y+dy < 1 or
      mark[x+dx, y+dy]=true) then //если долбим "стенку" следующим ходом
  begin
    if(dx=1) then begin dx:=0; dy:=1; end
    else if(dy=1) then begin dy:=0; dx:=-1; end
    else if(dx=-1) then begin dx:=0; dy:=-1; end
    else begin dy:=0; dx:=1; end;
  end;

  if( x+dx <= SIZE and
      x+dx >= 1 and
      y+dy <= SIZE and
      y+dy >= 1 and
      mark[x+dx, y+dy]=false) then //если НЕ уперлись в "стенку"
                                   //упремся только в центре, а там и выход
  begin
    x:=x+dx;
    y:=y+dy;
  end;

end;

[t.t]

Эх.. Двоешники-алгоритмизаторы.. Всё проще гораздо. "Спираль" можно разбить на последовательность сходящихся "колец", каждое следующее внутри предыдущего, примерно таких:

Код: Выделить всё

------------->\
.             |
^             |
|             |
|             |
|             |
|             |
|             v
\<------------/

Исходя из этого, вот такой цикл (в уме; не проверял, может где-то надо интдексы подкорректировать, но идея такая):

Код: Выделить всё

for i:=1 to n-int(n/2) do begin
  for j:=i to n-i do begin
    fa-fa(a[i,j]);
  end
  for j:=i to n-i do begin
    fa-fa(a[j,n-i]);
  end
  for j:=i to n-i do begin
    fa-fa(a[i,n-j]);
  end
  for j:=i to n-i do begin
    fa-fa(a[n-j,n-i]);
  end
end

[serg_sk]

Для t.t:
оооо!!! Эта идея мне нравится Код использовать твой не буду. Попробую сам написать. Ну чтобы понять принцип

[KiWi]

Эх.. Двоешники-алгоритмизаторы.. Всё проще гораздо. "Спираль" можно разбить на последовательность сходящихся "колец", каждое следующее внутри предыдущего, примерно таких:

↑

но-но!
я про то же писал, только кольцо === круг :-)
+ проход по всем сторонам в 1 цикле... (:

[t.t]

но-но!
я про то же писал, только кольцо === круг :-)
+ проход по всем сторонам в 1 цикле... (:

↑

Да, но согласитесь, что ваш алгоритм всё-таки заметно сложнее моего.

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

↑

Вот это правильно. Вообще, учиться программированию надо начинать с алгоритмов. Т.к. обычно криво реализованный хороший алгоритм работает лучше (и/или быстрее), чем хорошо реализованный кривой.

[KiWi]

Да, но согласитесь, что ваш алгоритм всё-таки заметно сложнее моего.

↑

а это спортивный интерес... :-)

Сказал только, что можно сделать с использованием двух циклов или четырех.

хм... а четырёх... интересно как :-)

[serg_sk]

Для mani13:

хм... а четырёх... интересно как :-)

ХЗ Сказал придумать самому

[Dummy!]

Гы а нам такую задачку ф школе задавали - но я её не решил так как дома компа тогда еще не было да и не влом было НО в голову тогда мне пришла идея - может кто то помнит принцип перевода полярных координат в декартовы? так вот надо вспомнить формулу отображения спирали в полярных координатах перевести в декартовы максимально увеличить прирошение аргумента - дабы спираль стала квадратной и округлить координаты до целых - и тогда координаты каждой точки будут координатами элементов в массиве :devil_2: от такая вот задумочка планкосрывательная! если кто таким способом решит с меня ПИВО и Нобелевку до кучи!

[xorader]

я бы так сделал (образно пишу)

Код: Выделить всё

change = ((1,0), (0,1), (-1,0), (0,-1));
x:=y:=0;
radius:=0;

while not (radius < maxradius  -- пока мы не в центре матрицы)
{
  for (i:=0; i<4; i++)
  {
    while (1)
    {
      (x,y) += change[i];
      if ((x,y) вышел за границы текущего кольца: (x > max_X - radius   ||   y > max_Y - radius))
      { break; } else { заполняем матрицу в координате (x,y) }
    }
  }
   radius++;
}

смысл - просто идём по стенке и сужаем стенку после каждой 4-ой стены

[t.t]

смысл - просто идём по стенке и сужаем стенку после каждой 4-ой стены

↑

Так это примерно то же самое, что у меня; только реализовано немного по-другому.

[Nevod]

Знакомое задание. Жаль, раньше не зашел. Вообще, подобные задачки имхо в уме решать уметь надо. Порядок в голове некоторый появляется. Могу автору предложитm еще обход матрицы по зигзагу, это уже посложнее. Или допустим задачка из другой области - вычислтиь факториал 1000. Препод на соседнем факультете такии штучками балуется.

[Lotos]

помогите заполнить матрицы n<8 вот так
1 3 4
2 5 8
6 7 9