Faire pivoter une matrice de 90 degrés

F

Problème : Étant donné une matrice ​\( N\times N \), faites-la pivoter de 90 degrés sur place. Sur place signifie une mémoire supplémentaire minimale à utiliser, c’est-à-dire ne pas créer de nouveau tableau à copier. Tourner dans le sens des aiguilles d’une montre signifie que la rangée du haut devient la colonne de droite, la colonne de droite devient la rangée du bas, etc.

Exemple :

\( M_{4,4} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 9 & 8 & 5 & 6 \\ 6 & 5 & 7 & 3 \\ 9 & 2 & 6 & 8 \end{pmatrix} \)\( \to \)\( M^{\prime}_{4,4} = \begin{pmatrix} 9 & 6 & 9 & 1 \\ 2 & 5 & 8 & 2 \\ 6 & 3 & 5 & 3 \\ 8 & 7 & 6 & 4 \end{pmatrix} \)

Solution : L’idée est de faire une variable d’échange “quadruple”, nous devons déplacer la valeur de haut\( \to \)​ droite, droite \( \to \)​ bas, bas \( \to \)​ gauche et gauche \( \to \)​ haut, pouvons-nous le faire en utilisant une seule variable supplémentaire ? Oui, c’est possible et nous le verrons plus bas.

A chaque couche, nous allons parcourir les éléments et les échanger comme suit :

  1. Enregistrez l’élément i-ième dans le tableau de boucles dans une variable temporaire (dans notre exemple le tableau supérieur ​\( \begin{bmatrix} 1 & 2 & 3 \end{bmatrix} \).
  2. Déplacez l’élément i-ième de la gauche vers le haut
  3. Déplacez l’élément i-ième du bas vers la gauche
  4. Déplace l’élément i-ième de la droite vers le bas
  5. Enregistrer la valeur de notre variable temporaire dans la position i-ième dans le tableau de droite

Implémentation :

void rotateMatrix(int a[][]){
	
	int n = a.lenght;
	if (n <= 1){
		return // Rien a faire 
	}
	
	// Layer
	for (int i = 0; i < n; i++){
		// Elements
		for (int j = 0; i < n-i-1; j++){
			int saved = a[i][j];
			a[i][j] = a[n-j-1][i];
			a[n-j-1][i] = a[n-1-i][n-1-j];
			a[n-1-i][n-1-j] = a[j][n-1-i];
			a[j][n-1-i] = saved
		}
	}
	
}

A propos de l'auteur

François KOBON

Trois mots pour me décrire : Code - Build - Hack. Je réponds au nom de François KOBON. Partisan passionné de technologies/innovations libre et ouverte, d'Algorithme, de Datas, des Mathématiques, tous types de sciences... et surtout d'apprentissage non conventionnel parce je suis auto-didacte. Je suis membre de la communauté Ayiyikoh que vous pouvez retrouver en ligne sur ayiyikoh.org

Ajouter un commentaire

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.

François KOBON

Trois mots pour me décrire : Code - Build - Hack. Je réponds au nom de François KOBON. Partisan passionné de technologies/innovations libre et ouverte, d'Algorithme, de Datas, des Mathématiques, tous types de sciences... et surtout d'apprentissage non conventionnel parce je suis auto-didacte. Je suis membre de la communauté Ayiyikoh que vous pouvez retrouver en ligne sur ayiyikoh.org

Suivez-moi

Insert math as
Block
Inline
Additional settings
Formula color
Text color
#333333
Type math using LaTeX
Preview
\({}\)
Nothing to preview
Insert