Форум программистов, компьютерный форум, киберфорум
Наши страницы
ПерС
Войти
Регистрация
Восстановить пароль
Оценить эту запись

Заполнение матрицы челыми числами по спирали :)

Запись от ПерС размещена 29.04.2018 в 08:02

На форуме есть несколько тем с этими спиралями, но вот такое заполнение кажется мне самым коротким по коду.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
 
int spiral(int m, int n, int j, int i) {
 return i ? m + spiral(n - 1, m, i - 1, m - j - 1) : j;
}
 
int main () {
 const int n = 5;
 const int m = 7;
 int a[n][m];
 for (int i = 0; i < n; i++) {
  for (int j = 0; j < m; j++) {
   a[i][j] = spiral(m, n, j, i);
   cout.width(4);
   cout << a[i][j] << " ";
  }
  cout << endl;
 }
 cin.get();
 return 0;
}
Нажмите на изображение для увеличения
Название: 1.png
Просмотров: 223
Размер:	3.9 Кб
ID:	4803

А если решать обратную задачу, то есть, не по индексам (i,j) элемента матрицы найти его место в спирали, а наоборот по порядковому номеру в спирали восстановить индексы элемента?
Тогда как в этой программке, которая сортирует целочисленные элементы матрицы, располагая их по спирали.
C++
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
using namespace std;
 
void next_indeх(int k, int n, int m, int &i, int &j, int dn, int dm) {
 //i,j - индексы k-го по порядку элемента в матрице n*m при обходе 
 //по спирали к центру по часовой стрелке начиная от верхнего левого угла матрицы
 //(нумерация k с единицы)
 if (n < 1 || m < 1 || k<1 || k>n*m) { //ошибка
  i = j = -1; return;
 }
 if (k <= m) { //первая строка
  i = 0 + dn; j = k - 1 + dm; return;
 }
 if (k <= m + n - 1) { //последний столбец
  i = k - m + dn; j = m - 1 + dm; return;
 }
 if (k <= (m + n - 1 + m - 1)) { //последняя строка
  i = n - 1 + dn; j = m - 1 - (k - (m + n - 1)) + dm; return;
 }
 if (k <= (m + n - 1 + m - 1 + n - 2)) { //первый столбец
  i = n - 1 - (k - (m + n - 1 + m - 1)) + dn; j = 0 + dm; return;
 }
 next_indeх(k - (2 * n + 2 * m - 4), n - 2, m - 2, i, j, dn + 1, dm + 1);
}
 
int main() {
 const int n = 4;
 const int m = 5;
 int a[n][m] = {
  { 1,2,3,4,7 },
  { 4,3,3,1,9 },
  { 5,1,3,2,-2 },
  { 6,7,3,6,15 }
 };
 
 int size = n*m;
 for (int i = 0; i < size - 1; i++) {
  for (int j = i + 1; j < size; j++) {
   int i1, j1, i2, j2;
   next_indeх(i + 1, n, m, i1, j1, 0, 0);
   next_indeх(j + 1, n, m, i2, j2, 0, 0);
   if (a[i1][j1] > a[i2][j2]) {
    int temp = a[i1][j1];
    a[i1][j1] = a[i2][j2];
    a[i2][j2] = temp;
   }
  }
 }
 for (int i = 0; i < n; i++) {
  for (int j = 0; j < m; j++) {
   cout.width (5);
   cout << a[i][j];
  }
  cout << endl;
 }
 cin.get();
 return 0;
}
Нажмите на изображение для увеличения
Название: 2.png
Просмотров: 181
Размер:	3.8 Кб
ID:	4804
Размещено в Без категории
Просмотров 571 Комментарии 5
Всего комментариев 5
Комментарии
  1. Старый комментарий
    Аватар для Storm23
    А вот хорошо бы было видеть код заполнения из центра к краям для матрицы произвольного размера из произвольной начальной точки.
    Такая задача иногда встречается на практике - когда нужно в двумерном пространстве найти соседей по клеткам, постепенно увеличивая радиус обхода.
    Запись от Storm23 размещена 29.04.2018 в 20:28 Storm23 вне форума
  2. Старый комментарий
    Аватар для ПерС
    Цитата:
    Сообщение от Storm23 Просмотреть комментарий
    код заполнения из центра к краям для матрицы произвольного размера из произвольной начальной точки.
    Ну, если не быть слишком требовательным к временной сложности алгоритма, можно вот так обойти

    C++
    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
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    
    //Visual Studio 2015
    #include <iostream>
    #include <cmath>
    #include <algorithm>
    using namespace std;
     
    void printItem (int a) {
     cout.width(3);
     cout << a << " ";
    }
     
    void spiral(int **arr, int X, int Y, int col_start, int row_start) {
     int x = col_start, y = row_start, dx = 1, dy = 0, step = 1;
     int filled = 0 , printable = X*Y;
     while (filled < printable) {
      for (int i =0 ; i < 2; i++) {
       for (int s = 0 ; s < step; s++) {
        if (x >= 0 && x < X && y >= 0 && y < Y) {
         //Здесь можно проверить, нет ли чего-то нужного в arr[y][x]
         printItem (arr[y][x]); 
         filled++;
        }
        x += dx; y += dy;
       }
       int t = dx; dx = -dy; dy = t;
      }
      step++;
     }
    }
     
    int main() {
     const int rows = 8;
     const int cols = 4;
     int **a = new int *[rows];
     int k = 1;
     for (int i = 0; i < rows; i++) {
      a[i] = new int[cols];
      cout << endl;
      for (int j = 0; j<cols; j++) {
       a[i][j] = k++;
       printItem (a[i][j]);
      }
     }
     
     cout << endl;
     int row_start = 2;
     int col_start = 3;
     spiral(a, cols, rows, col_start, row_start);
     
     cin.get(); return 0;
    }
    В принципе, такого кода много, мне кажется
    Запись от ПерС размещена 01.05.2018 в 13:58 ПерС вне форума
  3. Старый комментарий
    Аватар для Storm23
    Вот переписал на C# и в более удобоваримом виде:
    C#
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    
            static void Main()
            {
                var indexes = Spiral(5, 5).Take(15);
                foreach (var p in indexes)
                    Console.WriteLine(p);
            }
     
            static IEnumerable<Point> Spiral(int xStart, int yStart)
            {
                int x = xStart, y = yStart, dx = 1, dy = 0, step = 1;
                while (true)
                {
                    for (int i = 0; i < 2; i++)
                    {
                        for (int s = 0; s < step; s++)
                        {
                            yield return new Point(x, y);
                            x += dx; y += dy;
                        }
                        int t = dx; dx = -dy; dy = t;
                    }
                    step++;
                }
            }
    Цитата:
    В принципе, такого кода много, мне кажется
    Может и много, но вот недавно нужен был такой обход по спирали, в инете быстро не нашел, а ломать себе голову было лень, пришлось реализовывать по-другому.
    Теперь вот закину себе в библиотеку.
    Запись от Storm23 размещена 01.05.2018 в 19:18 Storm23 вне форума
  4. Старый комментарий
    Аватар для Avazart
    А для чего такое может понадобится?

    Наверное можно было бы проще создать массив bool как маску для проверки посещенности клетки, а направление рассматривать как шаг-вектор kx, kx и менять угол при упоре.
    Запись от Avazart размещена 05.05.2018 в 16:49 Avazart на форуме
    Обновил(-а) Avazart 05.05.2018 в 16:52
  5. Старый комментарий
    Аватар для Storm23
    Цитата:
    Сообщение от Avazart Просмотреть комментарий
    А для чего такое может понадобится?
    Так я же уже писал - для поиска соседей. Вот допустим у вас игра. Персонаж стоит в клетке с координатами (x,y), а вам нужно найти другого перса в соседней клетке (желательно ближайшего). Один из способов это сделать - вот такой вот поиск по спирали.

    Цитата:
    Сообщение от Avazart Просмотреть комментарий
    Наверное можно было бы проще создать массив bool как маску для проверки посещенности клетки, а направление рассматривать как шаг-вектор kx, kx и менять угол при упоре.
    По-вашему это проще?
    Запись от Storm23 размещена 05.05.2018 в 20:48 Storm23 вне форума
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru