C++

Rotation dans une matrice : problèmes !

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : Rotation dans une matrice : problèmes !

drvins

Salut, j'ai un problème dans un exo sur les matrices, il s'agit de faire une rotation vers la gauche de k éléments dans une matrice n sur n...

exemple avec k = 2 :

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

devient

12 13 14 3 4
17 18 19 2 9
22 23 24 1 8
15 10 5 0 7
20 21 16 11 6

Je doit donc faire un déplacement de k positions sur la gauche sur chaque diagonale de la matrice.
Si je prend la diagonale centrale :
0
6
12
18
24
avec k = 2, ça devient :
12
18
24
0
6

et je dois faire ça pour chaques diagonales.

Voilà mon code :

Code :

#include <iostream>
using namespace std;
int const MAX = 100;
void ReadMat(int A[MAX][MAX], int n)
{
for(int i=0 ; i<n ; i++)
for(int j=0 ; j<n ; j++)
cin >> A[i][j];
}
void PrintMat(int A[MAX][MAX], int n)
{
for(int i=0 ; i<n ; i++)
{
for(int j=0 ; j<n ; j++)
cout << A[i][j] << " ";
cout << endl;
}
}
void LeftDiagRot(int A[MAX][MAX], int n, int k)
{
int i, j, cpt =0;
int ligne=0;
int colonne = n-1;
while (cpt<n)
{
int Save = A[ligne][colonne];
for (i=0 ; (i+k)%n != ligne ; i=(i+k)%n)
for (j=0 ; (j+k)%n != ligne ; j=(j+k)%n)
{
A[i][j]=A[(i+k)%n][(j+k)%n];
colonne--;
cpt++;
}
A[i][j] = Save;
colonne--;
cpt++;
ligne++;
}
}
int main (void)
{
int n, k, A[MAX][MAX];
cin >> n >> k;
ReadMat(A,n);
cout << endl;
PrintMat(A,n);
cout << endl;
LeftDiagRot(A,n,k);
PrintMat(A,n);
return 0;
}

et j'obtiens :

12 13 14 3 11
17 18 19 6 16
22 23 24 13 21
15 16 17 4 19
7 8 9 23 6

En gros, le code que j'ai fait est censé effectuer la rotation dans la moitié de la matrice, ça je le comprendrais, mais là, je pige pas bien et donc je ne peux pas continuer pour la seconde moitié...

Message édité par drvins le 12-11-2003 à 18:09:19

Publicité

drvins

UP :cry:

Carbon_14

Pour mieux comprendre le pb : dans l'exemple donné, seules bougent les diagonales contenant le "bloc" désigné

00 01 02 XX XX
05 06 07 08 XX
10 11 12 13 14
XX 16 17 18 19
XX XX 22 23 24

donc les XX sont figés ?

Happy Life

dans ce cas précis ca me parait logique ques les X soient figés, car k = 2, et card(deuxieme diagonale) = 2 donc transition invisible,
card(premiere diagonale) = 1, meme chose...

je pense pas que ca soit figé, c'est juste dans cet exemple particulier que ca reste figé

Carbon_14

C'était pour faire avancer le schmilibilick, et me replonger dans les matrices (ça fait 25 ans que j'y touche plus).
Personne n'a trouvé son bug ?

ACut

DrVins a écrit :

void LeftDiagRot(int A[MAX][MAX], int n, int k)
{
int i, j, cpt =0;
int ligne=0;
int colonne = n-1;
while (cpt<n)
{
int Save = A[ligne][colonne];
for (i=0 ; (i+k)%n != ligne ; i=(i+k)%n)
for (j=0 ; (j+k)%n != ligne ; j=(j+k)%n)
{
A[i][j]=A[(i+k)%n][(j+k)%n];
colonne--;
cpt++;
}
A[i][j] = Save;
colonne--;
cpt++;
ligne++;

}
}

Ce code est une aberration:
- pourquoi (j+k)%n est-il comparé à ligne dans la boucle de j?
- pourquoi "colonne--" alors que colonne est inutilisé dans la boucle?

Ca risque pas de fonctionner!
Il serait plus simple de:

1) indexer les diagonales à rotater. Elles sont au nombre de 2N-1 (en fait 2N-3 car les points (0,N-1) et (N-1,0) ne bougent pas dans la matrice qqsoit k). Il suffit donc de considérer 2N-3 fois un pointeur "diag" (de dimension 1 et de largeur comprise entre 2 et N)

2) à chaque passe, on fournit "diag" à une fonction qui opère proprement la rotation de k élems vers la gauche.

Une fois que cette logique est bien posée, y a plus qu'à bosser directement sur int** A avec les offsets appropriés.

Message édité par ACut le 18-12-2003 à 20:06:04

---------------
NOUVEAU! Le guide de l'édition en version ebook : http://marcautret.free.fr/autret/150q-ebook/

FORUM HardWare.fr

Programmation

C++

Rotation dans une matrice : problèmes !

Sujets relatifs
Problèmes de chargement d'extension Easyphp1.7	matrice, fonction
[C++]Réduction zone de travail dans une matrice	Les problèmes de qualité reliés au code
Code pour un pop-up marche pas sur IE et a des problèmes sur Mozilla	Coloration syntaxique de C++ vers du HTML, problèmes ....
Problemes avec pointeurs/tableaux adresses	[C++] Problèmes à la compilation avec des fonctions amies
Rotation d'images pour page d'acceuil	[jbuilder] problemes de double buffering
Plus de sujets relatifs à : Rotation dans une matrice : problèmes !

Page générée en 0.068 secondes