Возможный дубликат:
Алгоритм для поворота изображения на 90 градусов? (Нет дополнительной памяти)
Говоря 90 градусов, я хочу сказать, если:
A = {1,2,3,
4,5,6,
7,8,9}
то после 90 градусов вращение A становится:
A = {7,4,1,
8,5,2,
9,6,3}
let a быть индексированием на основе nxn 0 на основе
f = floor(n/2)
c = ceil(n/2)
for x = 0 to f - 1
for y = 0 to c - 1
temp = a[x,y]
a[x,y] = a[y,n-1-x]
a[y,n-1-x] = a[n-1-x,n-1-y]
a[n-1-x,n-1-y] = a[n-1-y,x]
a[n-1-y,x] = temp
Изменить. Если вы хотите избежать использования temp, это работает (оно также вращается в правильном направлении) на этот раз в python.
def rot2(a):
n = len(a)
c = (n+1) / 2
f = n / 2
for x in range(c):
for y in range(f):
a[x][y] = a[x][y] ^ a[n-1-y][x]
a[n-1-y][x] = a[x][y] ^ a[n-1-y][x]
a[x][y] = a[x][y] ^ a[n-1-y][x]
a[n-1-y][x] = a[n-1-y][x] ^ a[n-1-x][n-1-y]
a[n-1-x][n-1-y] = a[n-1-y][x] ^ a[n-1-x][n-1-y]
a[n-1-y][x] = a[n-1-y][x] ^ a[n-1-x][n-1-y]
a[n-1-x][n-1-y] = a[n-1-x][n-1-y]^a[y][n-1-x]
a[y][n-1-x] = a[n-1-x][n-1-y]^a[y][n-1-x]
a[n-1-x][n-1-y] = a[n-1-x][n-1-y]^a[y][n-1-x]
Примечание. Это работает только для матриц целых чисел.
Транспонирование и обмен строк или столбцов (зависит от того, хотите ли вы поворачивать влево или вправо).
е. г.
1) original matrix
1 2 3
4 5 6
7 8 9
2) transpose
1 4 7
2 5 8
3 6 9
3-a) change rows to rotate left
3 6 9
2 5 8
1 4 7
3-b) or change columns to rotate right
7 4 1
8 5 2
9 6 3
Все эти операции могут выполняться без выделения памяти.
Алгоритм состоит в том, чтобы повернуть каждое "кольцо", работая от внешнего к самому внутреннему.
AAAAA
ABBBA
ABCBA
ABBBA
AAAAA
Алгоритм будет вращать все A сначала, а затем B, а затем C. Для поворота кольца необходимо сразу перемещать 4 значения.
Индекс я варьируется от 0..ring-width-1, например. для A ширина равна 5.
(i,0) -> temp
(0, N-i-1) -> (i, 0)
(N-i-1, N-1) -> (0, N-i-1)
(N-1, i) -> (N-i-1, N-1)
temp -> (N-1, i)
Затем это повторяется для каждого последующего внутреннего кольца, компенсируя координаты, уменьшая ширину кольца на 2.
[Еще один ответ появился с кодом, поэтому я не повторю этого.]
См. эту статью для транспонирования на месте; также google для "транспонирования на месте матрицы". Его можно легко адаптировать для вращения на 90 градусов. Чтобы транспонировать квадратные матрицы, вы просто меняете b[i][j] на b[j][i], где b[k][l] есть a[n*k+l]. На несырчатых матрицах это значительно сложнее. "Без лишнего пространства" - довольно сильное требование, может быть, вы имели в виду O (1) пространство? (предполагая, что целые числа являются фиксированным размером) Реализация на С++: здесь.
Полная реализация в C с использованием метода, описанного @Narek выше
#include <stdio.h>
int n;
unsigned int arr[100][100];
void rotate() {
int i,j,temp;
for(i=0; i<n; i++) {
for(j=i; j<n; j++) {
if(i!=j) {
arr[i][j]^=arr[j][i];
arr[j][i]^=arr[i][j];
arr[i][j]^=arr[j][i];
}
}
}
for(i=0; i<n/2; i++) {
for(j=0; j<n; j++) {
arr[j][i]^=arr[j][n-1-i];
arr[j][n-1-i]^=arr[j][i];
arr[j][i]^=arr[j][n-1-i];
}
}
}
void display(){
int i,j;
for(i=0;i<n;i++) {
for(j=0;j<n;j++) {
printf("%d",arr[i][j]);}
printf("%s","\n");
}
}
int main(int argc, char *argv[]){
int i,j;
printf("%s","Enter size of matrix:");
scanf("%d",&n);
printf("%s","Enter matrix elements\n");
for(i=0;i<n;i++) {
for(j=0;j<n;j++) {
scanf("%d",&arr[i][j]);
}
}
rotate();
display();
return 0;
}
Вам нужна одна временная переменная, тогда просто нужно перемещать элементы вокруг.
temp = A[0];
A[0] = A[6];
A[6] = A[8];
A[8] = A[2];
A[2] = temp;
temp = A[1];
A[1] = A[3];
A[3] = A[7];
A[7] = A[5];
A[5] = temp;
Я столкнулся с следующей реализацией:
Для квадратных матриц:
for n = 0 to N - 2
for m = n + 1 to N - 1
swap A(n,m) with A(m,n)
Для прямоугольных матриц:
for each length>1 cycle C of the permutation
pick a starting address s in C
let D = data at s
let x = predecessor of s in the cycle
while x ≠ s
move data from x to successor of x
let x = predecessor of x
move data from D to successor of s
Для получения дополнительной информации можно обратиться сюда: http://en.wikipedia.org/wiki/In-place_matrix_transposition