Rotation dans une matrice : problèmes !

Rotation dans une matrice : problèmes ! - C++ - Programmation

Marsh Posté le 12-11-2003 à 13:29:36    

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 :
  1. #include <iostream>
  2. using namespace std;
  3. int const MAX = 100;
  5. void ReadMat(int A[MAX][MAX], int n)
  6. {
  7. for(int i=0 ; i<n ; i++)
  8.  for(int j=0 ; j<n ; j++)
  9.   cin >> A[i][j];
  10. }
  12. void PrintMat(int A[MAX][MAX], int n)
  13. {
  14. for(int i=0 ; i<n ; i++)
  15. {
  16.  for(int j=0 ; j<n ; j++)
  17.   cout << A[i][j] << " ";
  18.  cout << endl;
  19. }
  20. }
  22. void LeftDiagRot(int A[MAX][MAX], int n, int k)
  23. {
  24. int i, j, cpt =0;
  25. int ligne=0;
  26. int colonne = n-1;
  27. while (cpt<n)
  28. {
  29.  int Save = A[ligne][colonne];
  30.  for (i=0 ; (i+k)%n != ligne ; i=(i+k)%n)
  31.   for (j=0 ; (j+k)%n != ligne ; j=(j+k)%n)
  32.   {
  33.    A[i][j]=A[(i+k)%n][(j+k)%n];
  34.    colonne--;
  35.    cpt++;
  36.   }
  37.  A[i][j] = Save;
  38.  colonne--;
  39.  cpt++;
  40.  ligne++;
  42. }
  43. }
  45. int main (void)
  46. {
  47. int n, k, A[MAX][MAX];
  49. cin >> n >> k;
  51. ReadMat(A,n);
  52. cout << endl;
  53. PrintMat(A,n);
  54. cout << endl;
  55. LeftDiagRot(A,n,k);
  56. PrintMat(A,n);
  58. return 0;
  59. }


 
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
Reply

Marsh Posté le 12-11-2003 à 13:29:36   

Reply

Marsh Posté le 12-11-2003 à 18:17:35    

UP :cry:

Reply

Marsh Posté le 12-11-2003 à 20:39:12    

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 ?

Reply

Marsh Posté le 12-11-2003 à 23:47:19    

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é

Reply

Marsh Posté le 13-11-2003 à 15:06:27    

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 ?

Reply

Marsh Posté le 18-12-2003 à 17:35:08    

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/
Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed