Come si fa a ruotare un array a due dimensioni?
https://stackoverflow.com/questions/42519
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Ispirato Raymond Chen post, dici di avere un 4x4 array a due dimensioni, scrivere una funzione che consente di ruotare di 90 gradi.Raymond link ad una soluzione in pseudo codice, ma mi piacerebbe vedere il mondo reale alcune cose.
[1][2][3][4]
[5][6][7][8]
[9][0][1][2]
[3][4][5][6]
Diventa:
[3][9][5][1]
[4][0][6][2]
[5][1][7][3]
[6][2][8][4]
Aggiornamento:Nick risposta è la più semplice, ma c'è un modo per fare meglio di n^2?Che cosa succede se la matrice è stata 10000x10000?
Soluzione
Qui è in C#
int[,] array = new int[4,4] {
{ 1,2,3,4 },
{ 5,6,7,8 },
{ 9,0,1,2 },
{ 3,4,5,6 }
};
int[,] rotated = RotateMatrix(array, 4);
static int[,] RotateMatrix(int[,] matrix, int n) {
int[,] ret = new int[n, n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
ret[i, j] = matrix[n - j - 1, i];
}
}
return ret;
}
Altri suggerimenti
O(n^2) e O(1) spazio algoritmo ( senza soluzioni alternative e hanky-panky roba!)
Ruotare da +90:
- Recepire
- Inversione di ogni riga
Rotazione: -90:
Metodo 1 :
- Recepire
- Inversione di ogni colonna
Metodo 2 :
- Inversione di ogni riga
- Recepire
Ruotare di +180:
Metodo 1:Ruotare da +90 volte
Metodo 2:Inversione di ogni riga e quindi annullare ogni colonna (Transpose)
Ruotare da -180:
Metodo 1:Rotazione: -90 due volte
Metodo 2:Inversione di ogni colonna e quindi annullare ogni riga
Metodo 3:Ruotare di +180 come sono lo stesso
Vorrei aggiungere qualche dettaglio in più.In questa risposta, concetti chiave vengono ripetute, il ritmo è lento e volutamente ripetitivo.La soluzione fornita qui non è più sintatticamente compatto, tuttavia, è destinato a coloro che desiderano imparare ciò che la matrice di rotazione e la conseguente attuazione.
In primo luogo, che cosa è una matrice?Ai fini di questa risposta, una matrice è solo una griglia in cui la larghezza e l'altezza sono uguali.Nota, la larghezza e l'altezza di una matrice possono essere diversi, ma per semplicità, in questo tutorial considera solo matrici con larghezza e altezza uguali (matrici quadrate).E sì, matrici è il plurale di matrice.
Esempio matrici sono:2×2, 3×3 o 5×5.O, più in generale, di N×N.Un 2×2 matrice avrà 4 piazze, perché 2×2=4.Un 5×5 matrix avrà 25 piazze, perché in 5×5=25.Ogni quadrato è chiamato un elemento o di una voce.Staremo a rappresentare ogni elemento con un periodo (.) negli schemi di seguito:
2×2 a matrice
. .
. .
3×3 matrice
. . .
. . .
. . .
Matrice 4×4
. . . .
. . . .
. . . .
. . . .
Così, che cosa significa per ruotare una matrice?Facciamo un 2×2 matrice e mettere alcuni numeri in ogni elemento, in modo che la rotazione può essere osservato:
0 1
2 3
Ruotando di 90 gradi ci dà:
2 0
3 1
Ci hanno letteralmente trasformato l'intera matrice, una volta a destra, proprio come gira il volante di un'auto.Essa può aiutare a pensare di “ribaltamento” matrice sul suo lato destro.Vogliamo scrivere una funzione in Python, che prende una matrice e ruota una volta a destra.La funzione di firma:
def rotate(matrix):
# Algorithm goes here.
La matrice sarà definito mediante una matrice bidimensionale:
matrix = [
[0,1],
[2,3]
]
Quindi la prima posizione di indice accede alla riga.La seconda posizione di indice accede alla colonna:
matrix[row][column]
Definiamo una funzione di utilità per la stampa di una matrice.
def print_matrix(matrix):
for row in matrix:
print row
Un metodo di rotazione di una matrice è quello di fare uno strato alla volta.Ma che cosa è un livello?Pensare a una cipolla.Proprio come gli strati di una cipolla, come ogni strato viene rimosso, ci si sposta verso il centro.Altre analogie è un Matryoshka bambola o un gioco di passare-il-pacco.
La larghezza e l'altezza di una matrice di dettare il numero di livelli di quella matrice.Proviamo ad usare simboli diversi per ogni livello:
Un 2×2 matrice di 1 livello
. .
. .
Un 3×3 matrix ha 2 strati
. . .
. x .
. . .
Una matrice 4×4 ha 2 strati
. . . .
. x x .
. x x .
. . . .
Un 5×5 matrice ha 3 strati
. . . . .
. x x x .
. x O x .
. x x x .
. . . . .
Un 6×6 matrice ha 3 strati
. . . . . .
. x x x x .
. x O O x .
. x O O x .
. x x x x .
. . . . . .
7×7 matrice di 4 strati
. . . . . . .
. x x x x x .
. x O O O x .
. x O - O x .
. x O O O x .
. x x x x x .
. . . . . . .
Si può notare che incrementare la larghezza e l'altezza di una matrice per uno, non sempre aumentare il numero di strati.L'assunzione di cui sopra matrici e tabulando i livelli e le dimensioni, possiamo vedere il numero di strati aumenta una volta ogni due incrementi di larghezza e altezza:
+-----+--------+
| N×N | Layers |
+-----+--------+
| 1×1 | 1 |
| 2×2 | 1 |
| 3×3 | 2 |
| 4×4 | 2 |
| 5×5 | 3 |
| 6×6 | 3 |
| 7×7 | 4 |
+-----+--------+
Tuttavia, non tutti i livelli di rotazione.1×1 matrice è la stessa prima e dopo la rotazione.Centrale 1×1 livello è sempre lo stesso prima e dopo la rotazione non importa quanto sia grande la matrice complessiva:
+-----+--------+------------------+
| N×N | Layers | Rotatable Layers |
+-----+--------+------------------+
| 1×1 | 1 | 0 |
| 2×2 | 1 | 1 |
| 3×3 | 2 | 1 |
| 4×4 | 2 | 2 |
| 5×5 | 3 | 2 |
| 6×6 | 3 | 3 |
| 7×7 | 4 | 3 |
+-----+--------+------------------+
Data la matrice N×N, come possiamo determinare a livello di programmazione il numero di strati di cui abbiamo bisogno per ruotare?Se dividiamo la larghezza o l'altezza da due e ignorare il resto si ottengono i seguenti risultati.
+-----+--------+------------------+---------+
| N×N | Layers | Rotatable Layers | N/2 |
+-----+--------+------------------+---------+
| 1×1 | 1 | 0 | 1/2 = 0 |
| 2×2 | 1 | 1 | 2/2 = 1 |
| 3×3 | 2 | 1 | 3/2 = 1 |
| 4×4 | 2 | 2 | 4/2 = 2 |
| 5×5 | 3 | 2 | 5/2 = 2 |
| 6×6 | 3 | 3 | 6/2 = 3 |
| 7×7 | 4 | 3 | 7/2 = 3 |
+-----+--------+------------------+---------+
Si noti come N/2 corrisponde al numero di livelli che devono essere ruotata?A volte il numero di ruotabile strati, uno in meno del numero totale di livelli nella matrice.Questo si verifica quando lo strato più interno è costituito di un solo elemento (es.1×1 matrix) e pertanto non ha bisogno di essere ruotato.Viene semplicemente ignorato.
Ci sarà senza dubbio bisogno di queste informazioni la nostra funzione per ruotare una matrice, quindi cerchiamo di aggiungere:
def rotate(matrix):
size = len(matrix)
# Rotatable layers only.
layer_count = size / 2
Ora sappiamo che i livelli sono e come determinare il numero di strati che effettivamente hanno bisogno di rotazione, come facciamo a isolare un singolo strato in modo che possiamo ruotare?In primo luogo, l'ispezione di una matrice da strato più esterno verso l'interno, verso lo strato più interno.Un 5×5 matrix è dotato di tre livelli di un totale di due strati che necessitano di rotazione:
. . . . .
. x x x .
. x O x .
. x x x .
. . . . .
Vediamo prima le colonne.La posizione delle colonne che definiscono lo strato più esterno, ipotizzando di contare da 0, sono 0 e 4:
+--------+-----------+
| Column | 0 1 2 3 4 |
+--------+-----------+
| | . . . . . |
| | . x x x . |
| | . x O x . |
| | . x x x . |
| | . . . . . |
+--------+-----------+
0 e 4 sono anche le posizioni delle righe per lo strato più esterno.
+-----+-----------+
| Row | |
+-----+-----------+
| 0 | . . . . . |
| 1 | . x x x . |
| 2 | . x O x . |
| 3 | . x x x . |
| 4 | . . . . . |
+-----+-----------+
Questo sarà sempre il caso, in quanto la larghezza e l'altezza sono uguali.Quindi possiamo definire la colonna e la riga posizioni di un livello con solo due valori (anziché quattro).
Muovendo per il secondo strato, la posizione delle colonne 1 e 3.E, sì, avete indovinato, è la stessa per le righe.È importante capire che abbiamo dovuto sia di incremento e decremento della riga e della colonna posizioni quando si sposta verso l'interno per il livello successivo.
+-----------+---------+---------+---------+
| Layer | Rows | Columns | Rotate? |
+-----------+---------+---------+---------+
| Outermost | 0 and 4 | 0 and 4 | Yes |
| Inner | 1 and 3 | 1 and 3 | Yes |
| Innermost | 2 | 2 | No |
+-----------+---------+---------+---------+
Così, per ispezionare ogni livello, ci vuole un loop con crescente e decrescente i contatori che rappresentano lo spostamento verso l'interno, a partire dal lo strato più esterno.Chiameremo il nostro strato di loop’.
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
print 'Layer %d: first: %d, last: %d' % (layer, first, last)
# 5x5 matrix
matrix = [
[ 0, 1, 2, 3, 4],
[ 5, 6, 6, 8, 9],
[10,11,12,13,14],
[15,16,17,18,19],
[20,21,22,23,24]
]
rotate(matrix)
Il codice di cui sopra scorre l' (riga e colonna) le posizioni di tutti i livelli che necessitano di rotazione.
Layer 0: first: 0, last: 4
Layer 1: first: 1, last: 3
Ora abbiamo un ciclo fornendo le posizioni delle righe e delle colonne di ogni livello.Le variabili first e last identificare la posizione di indice il primo e l'ultimo righe e colonne.Ritornando al nostro riga e di colonna tabelle:
+--------+-----------+
| Column | 0 1 2 3 4 |
+--------+-----------+
| | . . . . . |
| | . x x x . |
| | . x O x . |
| | . x x x . |
| | . . . . . |
+--------+-----------+
+-----+-----------+
| Row | |
+-----+-----------+
| 0 | . . . . . |
| 1 | . x x x . |
| 2 | . x O x . |
| 3 | . x x x . |
| 4 | . . . . . |
+-----+-----------+
Così siamo in grado di passare attraverso gli strati di una matrice.Ora abbiamo bisogno di un modo di navigare all'interno di un layer, in modo siamo in grado di spostare gli elementi intorno a quel livello.Nota, gli elementi di non "saltare" da un livello a un altro, ma lo fanno muovere, nell'ambito dei rispettivi livelli.
Rotazione di ogni elemento in un livello ruota l'intero livello.Ruotare tutti i livelli in una matrice ruota l'intera matrice.Questa frase è molto importante, quindi, per favore cercate di capire prima di passare.
Ora, abbiamo bisogno di un modo di spostare effettivamente elementi, vale a direruotare ogni elemento, e, successivamente, il livello, e, infine, la matrice.Per semplicità, noi provvederemo a ripristinare una matrice 3x3 — che ha una rotabile livello.
0 1 2
3 4 5
6 7 8
Il nostro livello di loop fornisce gli indici del primo e dell'ultimo colonne, così come la prima e l'ultima riga:
+-----+-------+
| Col | 0 1 2 |
+-----+-------+
| | 0 1 2 |
| | 3 4 5 |
| | 6 7 8 |
+-----+-------+
+-----+-------+
| Row | |
+-----+-------+
| 0 | 0 1 2 |
| 1 | 3 4 5 |
| 2 | 6 7 8 |
+-----+-------+
Perché il nostro matrici sono sempre a piazza, abbiamo bisogno solo di due variabili, first e last, poiché le posizioni dell'indice stesso per righe e colonne.
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
# Our layer loop i=0, i=1, i=2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
# We want to move within a layer here.
Le variabili prima e l'ultima può essere facilmente utilizzato per fare riferimento ai quattro angoli di una matrice.Questo perché gli stessi angoli, possono essere definiti utilizzando varie combinazioni di first e last (senza la sottrazione, l'addizione o la compensazione di tali variabili):
+---------------+-------------------+-------------+
| Corner | Position | 3x3 Values |
+---------------+-------------------+-------------+
| top left | (first, first) | (0,0) |
| top right | (first, last) | (0,2) |
| bottom right | (last, last) | (2,2) |
| bottom left | (last, first) | (2,0) |
+---------------+-------------------+-------------+
Per questo motivo, iniziamo la nostra rotazione esterna e quattro gli angoli, saremo in grado di ruotare di quelli di prima.Evidenziamo con *.
* 1 *
3 4 5
* 7 *
Vogliamo scambiare ogni * con il * a destra di esso.Quindi cerchiamo di andare avanti e stampare i nostri angoli definiti utilizzando solo le varie permutazioni di first e last:
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
top_left = (first, first)
top_right = (first, last)
bottom_right = (last, last)
bottom_left = (last, first)
print 'top_left: %s' % (top_left)
print 'top_right: %s' % (top_right)
print 'bottom_right: %s' % (bottom_right)
print 'bottom_left: %s' % (bottom_left)
matrix = [
[0, 1, 2],
[3, 4, 5],
[6, 7, 8]
]
rotate(matrix)
L'uscita dovrebbe essere:
top_left: (0, 0)
top_right: (0, 2)
bottom_right: (2, 2)
bottom_left: (2, 0)
Ora si potrebbe facilmente scambiare ogni angolo interno dell'strato loop:
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
top_left = matrix[first][first]
top_right = matrix[first][last]
bottom_right = matrix[last][last]
bottom_left = matrix[last][first]
# bottom_left -> top_left
matrix[first][first] = bottom_left
# top_left -> top_right
matrix[first][last] = top_left
# top_right -> bottom_right
matrix[last][last] = top_right
# bottom_right -> bottom_left
matrix[last][first] = bottom_right
print_matrix(matrix)
print '---------'
rotate(matrix)
print_matrix(matrix)
Matrice prima di ruotare gli angoli:
[0, 1, 2]
[3, 4, 5]
[6, 7, 8]
Matrix dopo la rotazione angoli:
[6, 1, 0]
[3, 4, 5]
[8, 7, 2]
Grande!Abbiamo con successo ruotato ogni angolo della matrice.Ma, non abbiamo ruotato gli elementi al centro di ogni strato.Chiaramente abbiamo bisogno di un modo di agire all'interno di un livello.
Il problema è che l'unico anello nella nostra funzione finora (il nostro livello di ciclo), si sposta al livello successivo ad ogni iterazione.Dal momento che la nostra matrice è solo una rotabile strato, lo strato ciclo chiuso dopo la rotazione solo gli angoli.Vediamo cosa succede con una più grande, 5×5 matrix (dove due livelli bisogno di rotazione).Il codice della funzione è stato omesso, ma rimane lo stesso come sopra:
matrix = [
[0, 1, 2, 3, 4],
[5, 6, 7, 8, 9],
[10, 11, 12, 13, 14],
[15, 16, 17, 18, 19],
[20, 21, 22, 23, 24]
]
print_matrix(matrix)
print '--------------------'
rotate(matrix)
print_matrix(matrix)
L'output è:
[20, 1, 2, 3, 0]
[ 5, 16, 7, 6, 9]
[10, 11, 12, 13, 14]
[15, 18, 17, 8, 19]
[24, 21, 22, 23, 4]
Non dovrebbe essere una sorpresa che gli angoli dello strato più esterno, ruotato, ma, si può anche notare gli angoli del livello successivo (verso l'interno) sono stati girati.Il senso è questo.Abbiamo scritto un codice per navigare attraverso i livelli e anche per ruotare gli angoli di ogni livello.Questo si sente come un progresso, ma purtroppo dobbiamo fare un passo indietro.Non bene di passare al livello successivo finché il precedente (esterno) strato è stato completamente ruotato.Che è, fino a che ogni elemento che il livello è stato ruotato.Rotazione con angoli non fare!
Prendere un respiro profondo.Abbiamo bisogno di un altro ciclo.Un ciclo nidificato niente di meno.Il nuovo ciclo nidificato, i first e last variabili, con un offset di navigare all'interno di un livello.Chiameremo questo nuovo ciclo nostra ‘elemento loop’.L'elemento ciclo di visitare ogni elemento lungo la riga superiore, ogni elemento in basso a destra, lato, ogni elemento lungo la riga in basso e ogni elemento sinistra.
- Lo spostamento in avanti lungo la riga superiore richiede la colonna indice viene incrementato.
- Lo spostamento verso il lato destro richiede l'indice di riga per essere incrementato.
- Lo spostamento all'indietro lungo la parte inferiore richiede la colonna indice per decrementato.
- Si muove la sinistra richiede l'indice di riga per essere decrementato.
Questo complesso dei suoni, ma è facile, perché il numero di volte che abbiamo di incremento e decremento per raggiungere tale obiettivo rimane lo stesso lungo tutti e quattro i lati della matrice.Per esempio:
- Spostare 1 elemento nella riga superiore.
- Spostare 1 elemento giù per il lato destro.
- Spostare 1 elemento a ritroso lungo la riga in basso.
- Spostare 1 elemento sinistra.
Questo significa che si può usare una sola variabile, in combinazione con il first e last variabili per muoversi all'interno di un livello.Può essere utile notare che si muove attraverso la riga superiore e giù per il lato destro entrambi richiedono incremento.Mentre si sposta all'indietro lungo il fondo e il lato sinistro entrambi richiedono di diminuire.
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
# Move through layers (i.e. layer loop).
for layer in range(0, layer_count):
first = layer
last = size - first - 1
# Move within a single layer (i.e. element loop).
for element in range(first, last):
offset = element - first
# 'element' increments column (across right)
top_element = (first, element)
# 'element' increments row (move down)
right_side = (element, last)
# 'last-offset' decrements column (across left)
bottom = (last, last-offset)
# 'last-offset' decrements row (move up)
left_side = (last-offset, first)
print 'top: %s' % (top)
print 'right_side: %s' % (right_side)
print 'bottom: %s' % (bottom)
print 'left_side: %s' % (left_side)
Ora abbiamo solo bisogno di assegnare la parte superiore del lato destro, lato destro verso il basso, in basso a sinistra, e da sinistra verso l'alto.Mettendo tutto insieme si ottiene:
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
for element in range(first, last):
offset = element - first
top = matrix[first][element]
right_side = matrix[element][last]
bottom = matrix[last][last-offset]
left_side = matrix[last-offset][first]
matrix[first][element] = left_side
matrix[element][last] = top
matrix[last][last-offset] = right_side
matrix[last-offset][first] = bottom
Data la matrice:
0, 1, 2
3, 4, 5
6, 7, 8
Il nostro rotate funzione si traduce in:
6, 3, 0
7, 4, 1
8, 5, 2
Python:
rotated = zip(*original[::-1]) # On Python 3, list(zip(*original[::-1]))
A buon mercato, lo so.
E in senso antiorario:
rotated_ccw = zip(*original)[::-1] # On Python 3, list(zip(*original))[::-1]
Come funziona: (Richiesto nei commenti)
zip(*original) swap assi di 2d array impilando le corrispondenti voci dagli elenchi di nuove liste.(Il * operatore dice la funzione di distribuire i contenuti in elenchi di argomenti)
>>> zip(*[[1,2,3],[4,5,6],[7,8,9]])
[[1,4,7],[2,5,8],[3,6,9]]
Il [::-1] dichiarazione inverte gli elementi dell'array (vedere Estesa Fette).
>>> [[1,2,3],[4,5,6],[7,8,9]][::-1]
[[7,8,9],[4,5,6],[1,2,3]]
Infine, la combinazione delle due avrà come risultato la trasformazione di rotazione.
Il cambiamento nel posizionamento di un [::-1] inversione delle liste in diversi livelli della matrice.
Qui è uno che si fa la rotazione in luogo invece di utilizzare un completamente nuovo array per contenere il risultato.Io ho lasciato l'inizializzazione di array e di stamparlo.Questo funziona solo per piazza matrici, ma essi possono essere di qualsiasi dimensione.Overhead di memoria è pari alla dimensione di un elemento della matrice, in modo che si può fare la rotazione di grandi array, come si desidera.
int a[4][4];
int n = 4;
int tmp;
for (int i = 0; i < n / 2; i++)
{
for (int j = i; j < n - i - 1; j++)
{
tmp = a[i][j];
a[i][j] = a[j][n-i-1];
a[j][n-i-1] = a[n-i-1][n-j-1];
a[n-i-1][n-j-1] = a[n-j-1][i];
a[n-j-1][i] = tmp;
}
}
Ci sono tonnellate di buoni di codice qui, ma voglio solo mostrare ciò che sta succedendo geometricamente in modo che si può capire la logica del codice un po ' meglio.Ecco come vorrei approccio.
prima di tutto, non confondere questo con il recepimento che è molto facile..
il basica idea è di trattarlo come livelli e noi ruotare uno strato alla volta..
supponiamo di avere un 4x4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
dopo che abbiamo ruotare in senso orario di 90 otteniamo
13 9 5 1
14 10 6 2
15 11 7 3
16 12 8 4
così proviamo a scomporre questo, in primo luogo abbiamo ruotare i 4 angoli essenzialmente
1 4
13 16
poi ci ruotare il seguente diamante che è una sorta di traverso
2
8
9
15
e poi il 2 ° inclinata diamante
3
5
12
14
in modo che si prende cura del bordo esterno, quindi in sostanza noi che un guscio alla volta fino a quando
infine la piazza centrale (o, se è dispari solo l'ultimo elemento che non si muove)
6 7
10 11
così ora vediamo di capire gli indici di ogni livello, supponiamo di lavorare sempre con lo strato più esterno, che stiamo facendo
[0,0] -> [0,n-1], [0,n-1] -> [n-1,n-1], [n-1,n-1] -> [n-1,0], and [n-1,0] -> [0,0]
[0,1] -> [1,n-1], [1,n-2] -> [n-1,n-2], [n-1,n-2] -> [n-2,0], and [n-2,0] -> [0,1]
[0,2] -> [2,n-2], [2,n-2] -> [n-1,n-3], [n-1,n-3] -> [n-3,0], and [n-3,0] -> [0,2]
così via e così via fino a che siamo a metà strada attraverso il bordo
così, in generale, il modello è
[0,i] -> [i,n-i], [i,n-i] -> [n-1,n-(i+1)], [n-1,n-(i+1)] -> [n-(i+1),0], and [n-(i+1),0] to [0,i]
Come ho detto nel mio post precedente, ecco un po ' di codice in C# che implementa una O(1) la matrice di rotazione per qualsiasi dimensione della matrice.Per brevità e la leggibilità non c'è nessun errore di verifica o di controllo della portata.Codice:
static void Main (string [] args)
{
int [,]
// create an arbitrary matrix
m = {{0, 1}, {2, 3}, {4, 5}};
Matrix
// create wrappers for the data
m1 = new Matrix (m),
m2 = new Matrix (m),
m3 = new Matrix (m);
// rotate the matricies in various ways - all are O(1)
m1.RotateClockwise90 ();
m2.Rotate180 ();
m3.RotateAnitclockwise90 ();
// output the result of transforms
System.Diagnostics.Trace.WriteLine (m1.ToString ());
System.Diagnostics.Trace.WriteLine (m2.ToString ());
System.Diagnostics.Trace.WriteLine (m3.ToString ());
}
class Matrix
{
enum Rotation
{
None,
Clockwise90,
Clockwise180,
Clockwise270
}
public Matrix (int [,] matrix)
{
m_matrix = matrix;
m_rotation = Rotation.None;
}
// the transformation routines
public void RotateClockwise90 ()
{
m_rotation = (Rotation) (((int) m_rotation + 1) & 3);
}
public void Rotate180 ()
{
m_rotation = (Rotation) (((int) m_rotation + 2) & 3);
}
public void RotateAnitclockwise90 ()
{
m_rotation = (Rotation) (((int) m_rotation + 3) & 3);
}
// accessor property to make class look like a two dimensional array
public int this [int row, int column]
{
get
{
int
value = 0;
switch (m_rotation)
{
case Rotation.None:
value = m_matrix [row, column];
break;
case Rotation.Clockwise90:
value = m_matrix [m_matrix.GetUpperBound (0) - column, row];
break;
case Rotation.Clockwise180:
value = m_matrix [m_matrix.GetUpperBound (0) - row, m_matrix.GetUpperBound (1) - column];
break;
case Rotation.Clockwise270:
value = m_matrix [column, m_matrix.GetUpperBound (1) - row];
break;
}
return value;
}
set
{
switch (m_rotation)
{
case Rotation.None:
m_matrix [row, column] = value;
break;
case Rotation.Clockwise90:
m_matrix [m_matrix.GetUpperBound (0) - column, row] = value;
break;
case Rotation.Clockwise180:
m_matrix [m_matrix.GetUpperBound (0) - row, m_matrix.GetUpperBound (1) - column] = value;
break;
case Rotation.Clockwise270:
m_matrix [column, m_matrix.GetUpperBound (1) - row] = value;
break;
}
}
}
// creates a string with the matrix values
public override string ToString ()
{
int
num_rows = 0,
num_columns = 0;
switch (m_rotation)
{
case Rotation.None:
case Rotation.Clockwise180:
num_rows = m_matrix.GetUpperBound (0);
num_columns = m_matrix.GetUpperBound (1);
break;
case Rotation.Clockwise90:
case Rotation.Clockwise270:
num_rows = m_matrix.GetUpperBound (1);
num_columns = m_matrix.GetUpperBound (0);
break;
}
StringBuilder
output = new StringBuilder ();
output.Append ("{");
for (int row = 0 ; row <= num_rows ; ++row)
{
if (row != 0)
{
output.Append (", ");
}
output.Append ("{");
for (int column = 0 ; column <= num_columns ; ++column)
{
if (column != 0)
{
output.Append (", ");
}
output.Append (this [row, column].ToString ());
}
output.Append ("}");
}
output.Append ("}");
return output.ToString ();
}
int [,]
// the original matrix
m_matrix;
Rotation
// the current view of the matrix
m_rotation;
}
OK, cercherò di mettere la mia mano, in realtà, non fare modifiche alla matrice originale durante la rotazione.Ma, in un sistema OO che non importa come lungo come l'oggetto appare come è stata ruotata per i clienti di classe.Al momento, la classe Matrix utilizza i riferimenti all'originale matrice di dati in modo da cambiare ogni valore di m1, cambia anche il m2 e m3.Una piccola modifica al costruttore per creare un nuovo array e copiare i valori a ordinare che fuori.
Mentre la rotazione di dati potrebbe essere necessario (forse per aggiornare la memorizzati fisicamente rappresentazione), diventa più semplice e forse più performante, per aggiungere un livello di riferimento indiretto sulla matrice di accesso, forse un'interfaccia:
interface IReadableMatrix
{
int GetValue(int x, int y);
}
Se il vostro Matrix già implementa questa interfaccia, quindi può essere ruotata tramite un decoratore di classe come questo:
class RotatedMatrix : IReadableMatrix
{
private readonly IReadableMatrix _baseMatrix;
public RotatedMatrix(IReadableMatrix baseMatrix)
{
_baseMatrix = baseMatrix;
}
int GetValue(int x, int y)
{
// transpose x and y dimensions
return _baseMatrix(y, x);
}
}
Rotazione +90/-90/180 gradi, capovolgere orizzontalmente/verticalmente e fattore di scala può essere ottenuto in questo modo, come bene.
E le prestazioni, è necessario misurare il vostro scenario specifico.Tuttavia la O(n^2) operazione è stato sostituito con un O(1) chiamata.Si tratta di un metodo virtuale chiamata che è più lento di diretto accesso ad un array, in modo che dipende dalla frequenza di rotazione matrice viene utilizzata dopo la rotazione.Se ha usato una volta, quindi questo approccio sarebbe sicuramente vincere.Se è ruotato poi utilizzato in un lungo sistema per giorni, poi posto la rotazione potrebbe fare di meglio.Dipende anche se si può accettare il costo iniziale.
Come con tutti i problemi di prestazioni, misurare, misurare, misurare!
Questa una versione migliore in Java:Io l'ho fatta per una matrice con una diversa larghezza e altezza
- h è qui l'altezza della matrice dopo la rotazione
- w è la larghezza della matrice dopo la rotazione
public int[][] rotateMatrixRight(int[][] matrix)
{
/* W and H are already swapped */
int w = matrix.length;
int h = matrix[0].length;
int[][] ret = new int[h][w];
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
ret[i][j] = matrix[w - j - 1][i];
}
}
return ret;
}
public int[][] rotateMatrixLeft(int[][] matrix)
{
/* W and H are already swapped */
int w = matrix.length;
int h = matrix[0].length;
int[][] ret = new int[h][w];
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
ret[i][j] = matrix[j][h - i - 1];
}
}
return ret;
}
Questo codice è basato sul Nick di Berardi post.
Ruby-modo: .transpose.map &:reverse
Ci sono un sacco di risposte già, e ho trovato due rivendicazione O(1) tempo di complessità.Il reale Algoritmo O(1) è quello di lasciare l'archiviazione di matrice intatta, e cambiare il modo di indice i suoi elementi.L'obiettivo qui è che non consuma memoria aggiuntiva, né richiede ulteriore tempo a scorrere i dati.
Rotazioni di 90-90 e 180 gradi sono semplici trasformazioni che può essere eseguita come lungo come lei sa quante righe e colonne sono in 2D array;Per ruotare qualsiasi vettore di 90 gradi, scambiare gli assi e negare l'asse Y.Per -90 gradi, scambiare gli assi e negare l'asse X.Per 180 gradi, negare entrambi gli assi, senza scambio.
Ulteriori trasformazioni sono possibili, come per esempio il mirroring orizzontalmente e/o verticalmente, negando gli assi in modo indipendente.
Questo può essere fatto attraverso, per esempio,un metodo di accesso.Gli esempi riportati di seguito sono funzioni JavaScript, ma i concetti sono applicabili a tutte le lingue.
// Get an array element in column/row order
var getArray2d = function(a, x, y) {
return a[y][x];
};
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));
for (var i = 0; i < newarr.length; i++) {
for (var j = 0; j < newarr[0].length; j++) {
newarr[i][j] = getArray2d(arr, i, j);
}
}
console.log(newarr);// Get an array element rotated 90 degrees clockwise
function getArray2dCW(a, x, y) {
var t = x;
x = y;
y = a.length - t - 1;
return a[y][x];
}
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));
for (var i = 0; i < newarr[0].length; i++) {
for (var j = 0; j < newarr.length; j++) {
newarr[j][i] = getArray2dCW(arr, i, j);
}
}
console.log(newarr);// Get an array element rotated 90 degrees counter-clockwise
function getArray2dCCW(a, x, y) {
var t = x;
x = a[0].length - y - 1;
y = t;
return a[y][x];
}
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));
for (var i = 0; i < newarr[0].length; i++) {
for (var j = 0; j < newarr.length; j++) {
newarr[j][i] = getArray2dCCW(arr, i, j);
}
}
console.log(newarr);// Get an array element rotated 180 degrees
function getArray2d180(a, x, y) {
x = a[0].length - x - 1;
y = a.length - y - 1;
return a[y][x];
}
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr.forEach(() => newarr.push(new Array(arr[0].length)));
for (var i = 0; i < newarr[0].length; i++) {
for (var j = 0; j < newarr.length; j++) {
newarr[j][i] = getArray2d180(arr, i, j);
}
}
console.log(newarr);Questo codice si presuppone un array di array nidificati, dove ciascuno interno dell'array è una riga.
Il metodo consente di leggere (o scrivere) di elementi (anche in ordine casuale) come se la matrice è stata ruotata o trasformato.Ora basta scegliere la funzione da chiamare, probabilmente per riferimento, e si va via!
Il concetto può essere esteso ad applicare le trasformazioni additivamente (e in modo non distruttivo) attraverso i metodi supplementari.Incluso qualsiasi angolo di rotazione e scalatura.
Un paio di persone hanno già messo gli esempi che richiedono la realizzazione di un nuovo array.
Alcune altre cose da considerare:
(a) Invece di spostamento dei dati, è sufficiente attraversare la "ruotato" di matrice in modo diverso.
(b) Fare la rotazione sul posto può essere un po ' più complicato.Avrete bisogno di un po ' di scratch luogo (probabilmente circa uguale a una riga o una colonna di dimensione).C'è un antico ACM carta facendo posto recepisce (http://doi.acm.org/10.1145/355719.355729), ma il loro codice di esempio è brutto goto-laden FORTRAN.
Addendum:
http://doi.acm.org/10.1145/355611.355612 è un altro, presumibilmente superiore, posto recepire algoritmo.
Nick la risposta sarebbe al lavoro per una matrice NxM anche solo con una piccola modifica (in contrapposizione a un NxN).
string[,] orig = new string[n, m];
string[,] rot = new string[m, n];
...
for ( int i=0; i < n; i++ )
for ( int j=0; j < m; j++ )
rot[j, n - i - 1] = orig[i, j];
Un modo per pensare a questo è che hai spostato il centro dell'asse (0,0) dall'angolo superiore sinistro all'angolo superiore destro.Sei semplicemente recepimento da uno all'altro.
Tempo O(N), Di Spazio O(1)
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n / 2; i++) {
int last = n - 1 - i;
for (int j = i; j < last; j++) {
int top = matrix[i][j];
matrix[i][j] = matrix[last - j][i];
matrix[last - j][i] = matrix[last][last - j];
matrix[last][last - j] = matrix[j][last];
matrix[j][last] = top;
}
}
}
Ecco la mia versione di Ruby (nota: i valori non vengono visualizzati lo stesso, ma gira ancora come descritto).
def rotate(matrix)
result = []
4.times { |x|
result[x] = []
4.times { |y|
result[x][y] = matrix[y][3 - x]
}
}
result
end
matrix = []
matrix[0] = [1,2,3,4]
matrix[1] = [5,6,7,8]
matrix[2] = [9,0,1,2]
matrix[3] = [3,4,5,6]
def print_matrix(matrix)
4.times { |y|
4.times { |x|
print "#{matrix[x][y]} "
}
puts ""
}
end
print_matrix(matrix)
puts ""
print_matrix(rotate(matrix))
L'output:
1 5 9 3
2 6 0 4
3 7 1 5
4 8 2 6
4 3 2 1
8 7 6 5
2 1 0 9
6 5 4 3
ecco una spazio-metodo di rotazione, da java, solo per la piazza.per i non-piazza matrice 2d, è necessario creare un nuovo array comunque.
private void rotateInSpace(int[][] arr) {
int z = arr.length;
for (int i = 0; i < z / 2; i++) {
for (int j = 0; j < (z / 2 + z % 2); j++) {
int x = i, y = j;
int temp = arr[x][y];
for (int k = 0; k < 4; k++) {
int temptemp = arr[y][z - x - 1];
arr[y][z - x - 1] = temp;
temp = temptemp;
int tempX = y;
y = z - x - 1;
x = tempX;
}
}
}
}
codice di ruotare qualsiasi dimensione matrice 2d con la creazione di nuovi array:
private int[][] rotate(int[][] arr) {
int width = arr[0].length;
int depth = arr.length;
int[][] re = new int[width][depth];
for (int i = 0; i < depth; i++) {
for (int j = 0; j < width; j++) {
re[j][depth - i - 1] = arr[i][j];
}
}
return re;
}
Attuazione della fossetta del +90 pseudocodice (ad es.recepimento poi invertire ogni riga) in JavaScript:
function rotate90(a){
// transpose from http://www.codesuck.com/2012/02/transpose-javascript-array-in-one-line.html
a = Object.keys(a[0]).map(function (c) { return a.map(function (r) { return r[c]; }); });
// row reverse
for (i in a){
a[i] = a[i].reverse();
}
return a;
}
Si può fare questo in 3 semplici passi:
1)Supponiamo di avere una matrice
1 2 3
4 5 6
7 8 9
2)Prendere la trasposta della matrice
1 4 7
2 5 8
3 6 9
3)L'interscambio righe di rotazione della matrice
3 6 9
2 5 8
1 4 7
Java il codice sorgente per questo:
public class MyClass {
public static void main(String args[]) {
Demo obj = new Demo();
/*initial matrix to rotate*/
int[][] matrix = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
int[][] transpose = new int[3][3]; // matrix to store transpose
obj.display(matrix); // initial matrix
obj.rotate(matrix, transpose); // call rotate method
System.out.println();
obj.display(transpose); // display the rotated matix
}
}
class Demo {
public void rotate(int[][] mat, int[][] tran) {
/* First take the transpose of the matrix */
for (int i = 0; i < mat.length; i++) {
for (int j = 0; j < mat.length; j++) {
tran[i][j] = mat[j][i];
}
}
/*
* Interchange the rows of the transpose matrix to get rotated
* matrix
*/
for (int i = 0, j = tran.length - 1; i != j; i++, j--) {
for (int k = 0; k < tran.length; k++) {
swap(i, k, j, k, tran);
}
}
}
public void swap(int a, int b, int c, int d, int[][] arr) {
int temp = arr[a][b];
arr[a][b] = arr[c][d];
arr[c][d] = temp;
}
/* Method to display the matrix */
public void display(int[][] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
}
}
Output:
1 2 3
4 5 6
7 8 9
3 6 9
2 5 8
1 4 7
PHP:
<?php
$a = array(array(1,2,3,4),array(5,6,7,8),array(9,0,1,2),array(3,4,5,6));
$b = array(); //result
while(count($a)>0)
{
$b[count($a[0])-1][] = array_shift($a[0]);
if (count($a[0])==0)
{
array_shift($a);
}
}
?>
Questo è il mio attuazione, in C, O(1) memoria complessità, in luogo di rotazione di 90 gradi in senso orario:
#include <stdio.h>
#define M_SIZE 5
static void initMatrix();
static void printMatrix();
static void rotateMatrix();
static int m[M_SIZE][M_SIZE];
int main(void){
initMatrix();
printMatrix();
rotateMatrix();
printMatrix();
return 0;
}
static void initMatrix(){
int i, j;
for(i = 0; i < M_SIZE; i++){
for(j = 0; j < M_SIZE; j++){
m[i][j] = M_SIZE*i + j + 1;
}
}
}
static void printMatrix(){
int i, j;
printf("Matrix\n");
for(i = 0; i < M_SIZE; i++){
for(j = 0; j < M_SIZE; j++){
printf("%02d ", m[i][j]);
}
printf("\n");
}
printf("\n");
}
static void rotateMatrix(){
int r, c;
for(r = 0; r < M_SIZE/2; r++){
for(c = r; c < M_SIZE - r - 1; c++){
int tmp = m[r][c];
m[r][c] = m[M_SIZE - c - 1][r];
m[M_SIZE - c - 1][r] = m[M_SIZE - r - 1][M_SIZE - c - 1];
m[M_SIZE - r - 1][M_SIZE - c - 1] = m[c][M_SIZE - r - 1];
m[c][M_SIZE - r - 1] = tmp;
}
}
}
Ecco la versione di Java:
public static void rightRotate(int[][] matrix, int n) {
for (int layer = 0; layer < n / 2; layer++) {
int first = layer;
int last = n - 1 - first;
for (int i = first; i < last; i++) {
int offset = i - first;
int temp = matrix[first][i];
matrix[first][i] = matrix[last-offset][first];
matrix[last-offset][first] = matrix[last][last-offset];
matrix[last][last-offset] = matrix[i][last];
matrix[i][last] = temp;
}
}
}
il primo metodo ruotare il mostouter strato, quindi spostare lo strato interno squentially.
Da un lineare, punto di vista, considerare le matrici:
1 2 3 0 0 1
A = 4 5 6 B = 0 1 0
7 8 9 1 0 0
Ora prendete Una trasposizione
1 4 7
A' = 2 5 8
3 6 9
E si consideri l'azione di Un' a B o B'.
Rispettivamente:
7 4 1 3 6 9
A'B = 8 5 2 BA' = 2 5 8
9 6 3 1 4 7
Questo è espandibile per ogni n x n matrice.E l'applicazione di questo concetto rapidamente nel codice:
void swapInSpace(int** mat, int r1, int c1, int r2, int c2)
{
mat[r1][c1] ^= mat[r2][c2];
mat[r2][c2] ^= mat[r1][c1];
mat[r1][c1] ^= mat[r2][c2];
}
void transpose(int** mat, int size)
{
for (int i = 0; i < size; i++)
{
for (int j = (i + 1); j < size; j++)
{
swapInSpace(mat, i, j, j, i);
}
}
}
void rotate(int** mat, int size)
{
//Get transpose
transpose(mat, size);
//Swap columns
for (int i = 0; i < size / 2; i++)
{
for (int j = 0; j < size; j++)
{
swapInSpace(mat, i, j, size - (i + 1), j);
}
}
}
Codice C# per ruotare [n,m] 2D array di 90 gradi a destra
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace MatrixProject
{
// mattrix class
class Matrix{
private int rows;
private int cols;
private int[,] matrix;
public Matrix(int n){
this.rows = n;
this.cols = n;
this.matrix = new int[this.rows,this.cols];
}
public Matrix(int n,int m){
this.rows = n;
this.cols = m;
this.matrix = new int[this.rows,this.cols];
}
public void Show()
{
for (var i = 0; i < this.rows; i++)
{
for (var j = 0; j < this.cols; j++) {
Console.Write("{0,3}", this.matrix[i, j]);
}
Console.WriteLine();
}
}
public void ReadElements()
{
for (var i = 0; i < this.rows; i++)
for (var j = 0; j < this.cols; j++)
{
Console.Write("element[{0},{1}]=",i,j);
this.matrix[i, j] = Convert.ToInt32(Console.ReadLine());
}
}
// rotate [n,m] 2D array by 90 deg right
public void Rotate90DegRight()
{
// create a mirror of current matrix
int[,] mirror = this.matrix;
// create a new matrix
this.matrix = new int[this.cols, this.rows];
for (int i = 0; i < this.rows; i++)
{
for (int j = 0; j < this.cols; j++)
{
this.matrix[j, this.rows - i - 1] = mirror[i, j];
}
}
// replace cols count with rows count
int tmp = this.rows;
this.rows = this.cols;
this.cols = tmp;
}
}
class Program
{
static void Main(string[] args)
{
Matrix myMatrix = new Matrix(3,4);
Console.WriteLine("Enter matrix elements:");
myMatrix.ReadElements();
Console.WriteLine("Matrix elements are:");
myMatrix.Show();
myMatrix.Rotate90DegRight();
Console.WriteLine("Matrix rotated at 90 deg are:");
myMatrix.Show();
Console.ReadLine();
}
}
}
Risultato:
Enter matrix elements:
element[0,0]=1
element[0,1]=2
element[0,2]=3
element[0,3]=4
element[1,0]=5
element[1,1]=6
element[1,2]=7
element[1,3]=8
element[2,0]=9
element[2,1]=10
element[2,2]=11
element[2,3]=12
Matrix elements are:
1 2 3 4
5 6 7 8
9 10 11 12
Matrix rotated at 90 deg are:
9 5 1
10 6 2
11 7 3
12 8 4
For i:= 0 to X do
For j := 0 to X do
graphic[j][i] := graphic2[X-i][j]
X è la dimensione della matrice, la grafica è in.
#recepire è un metodo standard di Ruby classe Array, quindi:
% irb
irb(main):001:0> m = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]]
=> [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]]
irb(main):002:0> m.reverse.transpose
=> [[3, 9, 5, 1], [4, 0, 6, 2], [5, 1, 7, 3], [6, 2, 8, 4]]
L'implementazione è un n^2 funzione di trasposizione scritto in C.Si può vedere qui:http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-transpose scegliendo l'opzione "fare clic per attivare source" accanto a "recepire".
Ricordo meglio di O(n^2) soluzioni, ma solo per appositamente costruito matrici (come matrici sparse)
Codice C per la matrice di rotazione di 90 gradi in senso orario per ogni M*N matrice
void rotateInPlace(int * arr[size][size], int row, int column){
int i, j;
int temp = row>column?row:column;
int flipTill = row < column ? row : column;
for(i=0;i<flipTill;i++){
for(j=0;j<i;j++){
swapArrayElements(arr, i, j);
}
}
temp = j+1;
for(i = row>column?i:0; i<row; i++){
for(j=row<column?temp:0; j<column; j++){
swapArrayElements(arr, i, j);
}
}
for(i=0;i<column;i++){
for(j=0;j<row/2;j++){
temp = arr[i][j];
arr[i][j] = arr[i][row-j-1];
arr[i][row-j-1] = temp;
}
}
}
qui è il mio Posto implementazione in C
void rotateRight(int matrix[][SIZE], int length) {
int layer = 0;
for (int layer = 0; layer < length / 2; ++layer) {
int first = layer;
int last = length - 1 - layer;
for (int i = first; i < last; ++i) {
int topline = matrix[first][i];
int rightcol = matrix[i][last];
int bottomline = matrix[last][length - layer - 1 - i];
int leftcol = matrix[length - layer - 1 - i][first];
matrix[first][i] = leftcol;
matrix[i][last] = topline;
matrix[last][length - layer - 1 - i] = rightcol;
matrix[length - layer - 1 - i][first] = bottomline;
}
}
}
Qui è il mio tentativo per la matrice di 90 gradi di rotazione che è un 2 passo la soluzione in C.Prima trasporre la matrice a posto e quindi di scambiare i cols.
#define ROWS 5
#define COLS 5
void print_matrix_b(int B[][COLS], int rows, int cols)
{
for (int i = 0; i <= rows; i++) {
for (int j = 0; j <=cols; j++) {
printf("%d ", B[i][j]);
}
printf("\n");
}
}
void swap_columns(int B[][COLS], int l, int r, int rows)
{
int tmp;
for (int i = 0; i <= rows; i++) {
tmp = B[i][l];
B[i][l] = B[i][r];
B[i][r] = tmp;
}
}
void matrix_2d_rotation(int B[][COLS], int rows, int cols)
{
int tmp;
// Transpose the matrix first
for (int i = 0; i <= rows; i++) {
for (int j = i; j <=cols; j++) {
tmp = B[i][j];
B[i][j] = B[j][i];
B[j][i] = tmp;
}
}
// Swap the first and last col and continue until
// the middle.
for (int i = 0; i < (cols / 2); i++)
swap_columns(B, i, cols - i, rows);
}
int _tmain(int argc, _TCHAR* argv[])
{
int B[ROWS][COLS] = {
{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}
};
matrix_2d_rotation(B, ROWS - 1, COLS - 1);
print_matrix_b(B, ROWS - 1, COLS -1);
return 0;
}
@dagorym:Aw, uomo.Mi era stato appeso su un buon "mi annoio, cosa posso meditare" puzzle.Mi si avvicinò con il mio posto di recepimento del codice, ma sono qui per trovare il vostro praticamente identico al mio...ah, bene.Qui è in Ruby.
require 'pp'
n = 10
a = []
n.times { a << (1..n).to_a }
pp a
0.upto(n/2-1) do |i|
i.upto(n-i-2) do |j|
tmp = 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] = tmp
end
end
pp a
short normal[4][4] = {{8,4,7,5},{3,4,5,7},{9,5,5,6},{3,3,3,3}};
short rotated[4][4];
for (int r = 0; r < 4; ++r)
{
for (int c = 0; c < 4; ++c)
{
rotated[r][c] = normal[c][3-r];
}
}
Semplice metodo di C++, tho ci sarebbe un grande sovraccarico di memoria in una grande matrice.
