Помогите со спиральной матрицей

Question

Мне нужно написать программу для Pascal, которая делает массив в виде спирали следующим образом:

(7) (8) (9) (10)
(6) (1) (2) (11)
(5) (4) (3) (12)
(16)(15)(14)(13)

Начните с 1 и продолжайте до 36, но это не так важно.

После 3 дней размышлений я понятия не имею, как это реализовать.

Проблема не в синтаксисе или массивах языка, а в алгоритме.

Можете ли вы помочь мне с любыми идеями, ссылками, псевдокодом или программным кодом на любом языке программирования?

Answer 1

Как насчет применения правила правой руки (например, решение лабиринта).

Считайте, что каждая клетка после того, как вы прошли, стала стеной.

Answer 2

Вот фрагмент из программы Java для выполнения спирального посещения матрицы.Он отслеживает изменения в направлениях, чтобы определить, сколько еще посещений нужно совершить, путешествуя в любом направлении.Модель, которая упрощает эту проблему, заключается в том, что при путешествии в любом заданном направлении при следующем посещении этого направления количество посещений уменьшается на единицу.Проще говоря, если при первом путешествии в горизонтальном направлении вы будете делать 6 посещений, то при следующем путешествии в горизонтальном направлении вы совершите 5 посещений.Следует также отметить, что горизонтальные и вертикальные посещения отслеживаются отдельно.Единственное уравнение, приведенное ниже, использовалось для расчета количества посещений для данного направления после необходимости изменения направления.Это уравнение выбирает вертикальное или горизонтальное, выводя его из общего числа изменений направления и используя mod в качестве селектора.Наконец, рассматривая посещения как змею, движущуюся по матрице, я представлял шаг как изменение строки / столбца как скорость (dy и dx).Как отметил другой человек, есть образец, который можно использовать и выраженный в формуле для dy и dx.

int[][] matrix = { {  1,  2,  3,  4,  5,  6,  7,  8 }, 
                   { 24, 25, 26, 27, 28, 29, 30,  9 },
                   { 23, 40, 41, 42, 43, 44, 31, 10 }, 
                   { 22, 39, 48, 47, 46, 45, 32, 11 },
                   { 21, 38, 37, 36, 35, 34, 33, 12 }, 
                   { 20, 19, 18, 17, 16, 15, 14, 13 } };

int n = matrix.length;
int m = matrix[0].length;
int row = 0;
int col = 0;
int dx = 1;
int dy = 0;
int dirChanges = 0;
int visits = m;

for (int i = 0; i < n * m; i++) {
  System.out.print(matrix[row][col] + " ");
  visits--;
  if (visits == 0) {
    visits = m * (dirChanges %2) + n * ((dirChanges + 1) %2) - (dirChanges/2 - 1);
    int temp = dx;
    dx = -dy;
    dy = temp;
    dirChanges++;
  }

  col += dx;
  row += dy;
}

Вывод этой программы:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 2829 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

Answer 3

Самая простая идея - начать с конца спирали и вернуться обратно.

Есть четыре переменные (left, top, right, bottom), которые сообщают вамсколько вы правильно заполнили с каждой стороны.

Создайте матрицу подходящего размера.

Инициализируйте left = top = 0 и right и bottom до последнего столбца и индекса строки.

• Заполните строку bottom из left -> right.Уменьшите bottom на единицу.

• Заполните right с bottom -> top.Уменьшите right на единицу.

• Заполните top с right -> left.Увеличьте top на единицу.

• Заполните left с top -> bottom.Увеличьте left на единицу.

• Повторяйте, пока не заполните всю матрицу.

Answer 4

Есть одна приятная идея, которую вы можете использовать, чтобы изменить направление во время итерации по матрице. Посмотрите на следующую таблицу. Вход (dX, dY) - это предыдущее направление в значениях приращения, а выход (cwdx, cwdy) - следующее направление по часовой стрелке, а выход (ccwdx, ccwdy) - следующее направление против часовой стрелки (координата (0,0) в левом верхнем углу):

dx dy | cwdx cwdy | ccwdx ccwdy
-------------------------------
 1  0 |   0    1  |    0    -1
 0  1 |  -1    0  |    1     0
-1  0 |   0   -1  |    0     1
 0 -1 |   1    0  |   -1     0

Таким образом, для направления (dx, dy) по часовой стрелке необходимо направление (-dy, dx), а для вращения против часовой стрелки - направление (dx, -dy). Это означает, что вам не нужен переключатель в вашем коде для изменения направления, вы просто делаете это тремя строками кода:

temp = dx; // this is for clockwise turn
dx = -dy;
dy = temp;

И еще одна маленькая хитрость. Чтобы заполнить матрицу, вы можете начать с конца и наибольшего числа, а затем перейти к центру и цифре 1. Если вы начинаете с края и идете к центру, то вы можете заполнять числа в строке до тех пор, пока достичь края матрицы или другого числа). Если вы больше не можете заполнить текущее направление, потому что (x + dx, y + dy) не «заполняется», измените направление.

Answer 5

Подумайте о разбиении матрицы nxn на концентрические подматрицы 2x2, 4x4, .. nxn.В вашем случае у нас будет внешняя подматрица (элементы с 5 по 16) и внутренняя (элементы с 1 по 4).

Теперь для каждого уровня вы должны выполнить итерацию по четырем ребрам и заполнить ихс необходимыми элементами.Вы можете выйти наизнанку или наружу.Я пойду на улицу.У нас есть счетчик, который изначально равен n*n (в нашем примере - 16).

Для i при переходе от 1 к n/2:

Сначала возьмем нижний край (элементы16-13 для внешнего уровня).Мы переходим от x[n-i+1][i] к x[n-i+1][n-i+1] и заполняем (это будет 16, 15, 14, 13 для первого уровня и 4,3 для второго уровня)

Затем мы берем правый край (элементы12-10 для внешнего уровня).Мы переходим от x[n-i][n-i+1] к x[i][n-i+1] (элементы 12, 11, 10 для внешнего уровня).

Затем берем верхний край (элементы 9-7 для внешнего уровня).Мы идем от x[i][n-i] до x[i][i] (элементы 9, 8, 7 для внешнего уровня)

Наконец, мы берем левый край (элементы 6-5 для внешнего уровня).Мы переходим от x[i+1][i] к x[n-i][i] и заполняем эту сторону (это будет 6, 5 для внешнего уровня).

И, наконец, у вас есть средний элемент, если n нечетно.Тогда все, что вам нужно сделать, это назначить x[n/2+1][n/2+1] = 1

Надеюсь, я прояснил идею;если есть что-то, чего вы не понимаете, спросите.

Также я не реализовал решение, потому что я полагаю, что ваша проблема - только идея, а не реализация

Answer 6

import java.util.Scanner; 
class CircularMatrixFromInnerClockwise
{
Scanner sc= new Scanner(System.in);
 void main()
 {
     System.out.println("Enter size.");
     int n=sc.nextInt();
     int a[][]= new int [n][n];
     int r1,c1,r2,c2;
     if(n%2==0)
     {
      r1=n/2-1;
      c1=n/2-1;
      r2=n/2-1;
      c2=n/2-1;
    }
    else
    {
      r1=(n+1)/2-1;
      c1=(n+1)/2-1;
      r2=(n+1)/2-1;
      c2=(n+1)/2-1;
    }
     int k=1;
     do
     {   
         if(c2<n-1&&r2<n-1)
        {
         r2++;
         c2++;
        }
        for(int i=c1;i<=c2;i++)
         a[r1][i]=k++;  
          if(k>=n*n)
         break;
        for(int i=r1+1;i<=r2;i++)
         a[i][c2]=k++; 
         if(k>=n*n)
         break;
        if(c1>0&&r1>0)
        {
             c1--;
             r1--;
        }
         for(int i=c2-1;i>=c1;i--)
         a[r2][i]=k++;
         if(k>=n*n)
         break;

         for(int i=r2-1;i>=r1+1;i--)
         a[i][c1]=k++;
         if(k>=n*n)
         break;
     }while(k<=n*n);
     System.out.println("Circular matrix");
     for(int i=0;i<n;i++)
     {
         for(int j=0;j<n;j++)
         {
             System.out.print( a[i][j]+"\t");
         }
         System.out.println();
     }
 }
}

Вы идете слева направо, затем вниз. влево, вверх и снова. Надеюсь, поможет. :)

Answer 7

Вы имеете в виду, что он должен распечатывать числа слева направо, сверху вниз?Полезно знать, что для создания квадратных чисел вы складываете последовательные нечетные числа - 1 + 3 + 5 + 7 + 9 + 11 = 36.

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

Answer 8

CurValue = n * n;

Конечная точка - самая нижняя левая точка.

Мы перейдем от конечной точки к первой точке (мы назначим значения при посещении)

Каждая ячейка имеет нулевое значение в начале.

x = n-1;

y = 0;

arr[x][y] = CurValue;


while ( CurValue greater than zero )
{


keep going right until you face a cell that has non-zero value or until you reach the most right cell

keep going top until you face a cell that has non-zero value or until you reach the most top cell

keep going left until you face a cell that has non-zero value or until you reach the most left cell

keep going down until you face a cell that has non-zero value or until you reach the most down cell

}

note: with each cell you visit then do the following :
    CurValue --;
    Assign CurValue to the current visited cell;

Я надеюсь, что приведенный выше алгоритм понятен.

Answer 9

К # 1

Я написал программу, но результат выглядит следующим образом:

00000
10000
11000
11100
.....

Не знаю, может быть, я не понял ваш алгоритм или возникла какая-либо другая проблема.Вот код:

  n:=16;
  x:=1;
  For i:=1 to (n div 2) do
  begin
    For p:=i to n-i+1 do
    begin
      a[n-i+1,p]:=x;
    end;

    For q:=n-i to i do
    begin
      a[q,n-i+1]:=x;
    end;

    For o:=n-i to i do
    begin
      a[i,o]:=x;
    end;

    For u:=i+1 to n-i do
    begin
      a[u,i]:=x;
    end;
  end;

Итак, я попытался написать программу # 2 из php в паскаль, и она работает.Теперь я исправлю это, чтобы записать числа по часовой стрелке и начать с центра массива.

Большое спасибо всем.

Answer 10

Вот рекурсивное решение, написанное на PHP.

<?php
header('Content-type: text/plain');

function fill($x, $y, $dir, $leftInDir, $index, $stepSize, $stop){
    global $out;

    // set the value for the current item //
    $out[$y][$x] = $index;

    // everything that comes after this point is computing for the parameters of the next call //

    // activate this for debugging //
    //echo $x, ',', $y, ',', $dir, ',', $leftInDir, ',', $index, ',', $stepSize, ',', $stop, "\n";

    // decrease the number of steps left to take in the current direction //
    $leftInDir--;

    // check if this is the last item //
    if($index == $stop)
        return;

    // we're going up for the next item //
    if($dir == 'U')
        $y--;

    // we're going right for the next item //
    if($dir == 'R')
        $x++;

    // we're going down for the next item //
    if($dir == 'D')
        $y++;

    // we're going left for the next item //
    if($dir == 'L')
        $x--;

    // if this was the last step in this direction we need to change the direction //
    if($leftInDir == 0){

        // after two direction changes we need to increase the numbers of steps to take //
        if($dir == 'D' || $dir == 'U'){
            $stepSize++;
        }

        // update the direction clockwise //
        if($dir == 'U')
            $dir = 'R';
        else if($dir == 'R')
            $dir = 'D';
        else if($dir == 'D')
            $dir = 'L';
        else if($dir == 'L')
            $dir = 'U';

        // set the number of steps left as the step size //
        $leftInDir = $stepSize;
    }

    // increase the number to put in the cell //
    $index++;

    // call for the next item //
    fill($x,$y,$dir,$leftInDir,$index,$stepSize,$stop);
}

// set the size //
$size = 100;

// start the process from the center of the matrix //
fill((int)$size/2, (int)$size/2, 'R', 1, 1, 1, $size*$size);

// just output //
ksort($out);
foreach($out as $row){
    ksort($row);
    foreach($row as $item){
        echo str_pad($item, 7);
    }
    echo "\n";
}
?>

Принцип довольно прямой (ну не прямой, а по спирали, вперед :)). Вы начинаете с того места, где должно быть * 1004, и начинаете идти. 1 ВПРАВО, 1 ВНИЗ, 2 ВЛЕВО, 2 ВВЕРХ, 3 ВПРАВО и т. Д., Пока вы не достигнете n*n.

Я написал ее как рекурсивную функцию, но ее можно легко преобразовать в цикл.