БлогNot. С++: поворот матрицы

С++: поворот матрицы

Любопытная задача - не транспонировать, а именно повернуть на 90, 180 или 270 градусов матрицу.

Если результаты перестановки писать в новую матрицу, задач тривиальна. Достаточно иметь функцию вращения матрицы на 90 градусов (например, по часовой стрелке), вызываемую нужное число раз. В примере квадратная матрица "вращается" четырежды, возвращаясь, в итоге, "на место". Для неквадратной матрицы изменятся лишь границы циклов и выделение памяти.

#include <stdio.h>
 
int ** turn90 (int n, int **a) {
 int i,j;
 int **b;
 b = new int * [n];
 for (i=0; i<n; i++) b[i]= new int [n];
 for (i=0; i<n; i++)
 for (j=0; j<n; j++) {
  b[j][n-i-1]=a[i][j];
 }
 return b;
}
 
void out (char *s, int n, int **a) {
 int i,j;
 printf ("\n%s",s);
 for (i=0; i<n; i++) {
  printf ("\n");
  for (j=0; j<n; j++) printf ("%d ",a[i][j]);
 }
}
 
int main () {
 const int n=5;
 int **a;
 int i,j,k=1;
 a = new int * [n];
 for (i=0; i<n; i++) a[i]= new int [n];
 for (i=0; i<n; i++)
 for (j=0; j<n; j++) a[i][j]=k++;
 out ("Before",n,a);
 int **b=turn90 (n,a);
 out ("After 1",n,b);
 int **c=turn90 (n,b);
 out ("After 2",n,c);
 int **d=turn90 (n,c);
 out ("After 3",n,d);
 int **e=turn90 (n,d);
 out ("After 4",n,e);
 getchar();
 return 0;
}

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

Before
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
After 1
21 16 11 6 1
22 17 12 7 2
23 18 13 8 3
24 19 14 9 4
25 20 15 10 5
After 2
25 24 23 22 21
20 19 18 17 16
15 14 13 12 11
10 9 8 7 6
5 4 3 2 1
After 3
5 10 15 20 25
4 9 14 19 24
3 8 13 18 23
2 7 12 17 22
1 6 11 16 21
After 4
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

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

Напишем пару функций для вращения матрицы по и против часовой стрелки на 90 градусов:

#include <stdio.h>

int **turn90_clockwise (int n, int **a) {
 int i,j,b;
 for (i=0;i<n/2;i++)
 for (j=i;j<n-1-i;j++) {
  b=a[i][j];
  a[i][j]=a[n-j-1][i];
  a[n-j-1][i]=a[n-i-1][n-j-1];
  a[n-i-1][n-j-1]=a[j][n-i-1];
  a[j][n-i-1]=b;
 }
 return a;
}

int **turn90_counterclockwise (int n, int **a) {
 int i,j,b;
 for (i=0;i<n/2;i++)
 for (j=i;j<n-1-i;j++) {
  b=a[i][j];
  a[i][j]=a[j][n-1-i];
  a[j][n-1-i]=a[n-1-i][n-1-j];
  a[n-1-i][n-1-j]=a[n-1-j][i];
  a[n-1-j][i]=b;
 }
 return a;
}

void out (char *s, int n, int **a) {
 int i,j;
 printf ("\n%s",s);
 for (i=0; i<n; i++) {
  printf ("\n");
  for (j=0; j<n; j++) printf ("%d ",a[i][j]);
 }
}

int main () {
 const int n=5;
 int **a;
 int i,j,k=1;
 a = new int * [n];
 for (i=0; i<n; i++) a[i]= new int [n];
 for (i=0; i<n; i++)
 for (j=0; j<n; j++) a[i][j]=k++;
 out ("Before",n,a);
 a=turn90_clockwise (n,a);
 out ("After turn90_clockwise",n,a);
 a=turn90_counterclockwise (n,a);
 out ("After turn90_counterclockwise",n,a);
 getchar();
 return 0;
}

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

Before
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
After turn90_clockwise
21 16 11 6 1
22 17 12 7 2
23 18 13 8 3
24 19 14 9 4
25 20 15 10 5
After turn90_counterclockwise
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

19.11.2013, 23:01 [27764 просмотра]


теги: c++ алгоритм

К этой статье пока нет комментариев, Ваш будет первым