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

1 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.

  • Salut,

    attention à la petite erreur de la ligne 11 :
    for (int j = 0; i < n-i-1; j++){
    for (int j = 0; j < n-i-1; j++){

    Sinon on rentre dans un boucle infinie 🙂

    Merci pour le code (mais je souhaitais une rotation et non une transposition. dommage)

Par François KOBON

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