simple et sans pointeurs, transposer une matrice

Le
bpascal123
Bonjour-soir,

Le code ci-dessous pour transposer une matrice ne fonctionne pas bien
que la compilation a lieu voir le message d'erreur après le code ci-
dessous qui se produit lors de l'exécution. Je voudrais comprendre, ça
fait pas mal de temps que je cherche pourquoi mais je n'ai pas assez
de temps pour aller en profondeur.


#include <stdio.h>

int main(void)
{
int Mat[3][2] = {1, 4, 2, 5, 3, 6 } ;
int i, j ;
int lig = 3 ;
int col = 2 ;
int aide ;


printf("AFFICHAGE MATRICE AVANT TRANSPOSITION: ") ;
for ( i = 0 ; i < lig ; i++ )
{
for ( j = 0 ; j < col ; j++ )
printf("%d", Mat[i][j]) ;
printf("") ;
}

/*Permutation : */

for ( i = 0 ; i <= lig ; i++ )
for ( j = 0 ; j <= i ; j++ )
{
aide = Mat[i][j] ;
Mat[i][j] = Mat[j][i] ;
Mat[j][i] = aide ;
}
/*Fin permutation */

printf("AFFICHAGE MATRICE TRANSPOSEE: ") ;
for ( i = 0 ; i < col ; i++ )
{
for ( j = 0 ; j < lig ; j++ )
{
printf("%d", Mat[i][j]) ;
}
printf("") ;
}

printf("") ;
return 0 ;
}

c:>gcc monprog.c -o monprog.exe
fonctionne
c:>monprog
ne fonctionne pas!

Exiting due to signal SIGSEGV
Stack Fault at eip=00088c47
eax=00000063 ebx=00000001 ecx=00000256 edx=00000000 esi=00000054 =
edi=0
000ff3e
ebp=0008ff30 esp=000002da program=C:CODE_CMONPROG~3.EXE
cs: sel=01a7 base=029d0000 limit=0009ffff
ds: sel=01af base=029d0000 limit=0009ffff
es: sel=01af base=029d0000 limit=0009ffff
fs: sel=017f base=0000f9c0 limit=0000ffff
gs: sel=01bf base=00000000 limit=0010ffff
ss: sel=01af base=029d0000 limit=0009ffff
App stack: [0008ff3c..0000ff3c] Exceptn stack: [0000fe9c..0000df5c]

Call frame traceback EIPs:
0x00088c47
0x00001ac6

Merci
Pascal
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses Page 1 / 2
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Etienne Rousee
Le #21523702
for ( i = 0 ; i <= lig ; i++ )
for ( j = 0 ; j <= i ; j++ )



Tu débordes.

En plus, la transposée d'une 3x2 est une 2x3.

--

Etienne
Samuel DEVULDER
Le #21523922
a écrit :

for ( i = 0 ; i <= lig ; i++ )


^^^^^^^^

heu "<=" ???

for ( j = 0 ; j <= i ; j++ )
{
aide = Mat[i][j] ;



Tu n'as pas l'impression que tu va taper dans Mat[3][machin] à un
moment, donc taper à l'exterieur?? Et boom segmentation violation!

Du reste je me demande comment tu peux représenter la transposée d'une
matrice 3x2 dans une matrice 3x2 aussi. Il te faut un autre tableau 2x3
si tu veux t'y retrouver.

sam.
Antoine Leca
Le #21524212
écrivit :
int Mat[3][2] = {1, 4, 2, 5, 3, 6 } ;



Prend l'habitude d'écrire cela sous la forme
int Mat[3][2] = { {1, 4}, {2, 5}, {3, 6} } ;

D'abord c'est plus lisible (à mon sens) ; ensuite cela t'évitera des
avertissements inutiles; il viendra peut-être même un jour où ta version
ne sera plus acceptée. Mais surtout, si tu as besoin ultérieurement de
modifier la taille des lignes (passer de 2 à 4, par exemple), avec ta
méthode c'est une galère pas possible.


Antoine
bpascal123
Le #21525481
J'ai oublié de dire que j'ai essayé le code ci-dessous qui reprend ce
que vous pensez être l'erreur mais ça ne convient pas mais alors pas
du tout:

printf("nAFFICHAGE MATRICE TRANSPOSEE: n") ;
for ( i = 0 ; i < col ; i++ )
{
for ( j = 0 ; j < lig ; j++ )
{
printf("%d", Mat[i][j]) ;
}
printf("n") ;
}

Voilà le résultat :

AFFICHAGE MATRICE AVANT TRANSPOSITION:
14
25
36

AFFICHAGE MATRICE TRANSPOSEE:
123
356


Ca ne devrait pas être :
AFFICHAGE MATRICE TRANSPOSEE:
123
456

ou bien j'ai oublié les cours sur les matrices, ça doit faire 4-5 ans
et pourtant je m'en sortais bien...j'avoue que ce n'était qu'une
introduction.

Merci,

Pascal
Manuel Pégourié-Gonnard
Le #21525771
scripsit :

printf("nAFFICHAGE MATRICE TRANSPOSEE: n") ;
for ( i = 0 ; i < col ; i++ )
{
for ( j = 0 ; j < lig ; j++ )
{
printf("%d", Mat[i][j]) ;


Ici : Mat[j][i].

--
Manuel Pégourié-Gonnard Institut de mathématiques de Jussieu
http://weblog.elzevir.fr/ http://people.math.jussieu.fr/~mpg/
Benoit Izac
Le #21525941
Bonjour,

le 09/04/2010 à 15:41, bpascal a écrit dans le message




J'ai oublié de dire que j'ai essayé le code ci-dessous qui reprend ce
que vous pensez être l'erreur mais ça ne convient pas mais alors pas
du tout:

printf("nAFFICHAGE MATRICE TRANSPOSEE: n") ;
for ( i = 0 ; i < col ; i++ )
{
for ( j = 0 ; j < lig ; j++ )
{
printf("%d", Mat[i][j]) ;
}
printf("n") ;
}

Voilà le résultat :

AFFICHAGE MATRICE AVANT TRANSPOSITION:
14
25
36

AFFICHAGE MATRICE TRANSPOSEE:
123
356


Ca ne devrait pas être :
AFFICHAGE MATRICE TRANSPOSEE:
123
456

ou bien j'ai oublié les cours sur les matrices, ça doit faire 4-5 ans
et pourtant je m'en sortais bien...j'avoue que ce n'était qu'une
introduction.



Une chose est sûr, si tu veux garder la même matrice, il va falloir
qu'elle soit carré, sinon tu n'écris pas où tu penses.


#include
#define LINE 3
#define COL 2

int main(void)
{
int m1[LINE][COL] = {
{1, 4},
{2, 5},
{3, 6},
};
int m2[COL][LINE];
int i, j;


printf("AFFICHAGE MATRICE AVANT TRANSPOSITION:n");
for (i = 0; i < LINE; i++) {
for (j = 0; j < COL; j++)
printf("%d", m1[i][j]);
printf("n");
}

for (i = 0; i < LINE; i++)
for (j = 0; j < COL; j++)
m2[j][i] = m1[i][j];

printf("AFFICHAGE MATRICE TRANSPOSEE:n");
for (i = 0; i < COL; i++) {
for (j = 0; j < LINE; j++)
printf("%d", m2[i][j]);
printf("n");
}

return 0;
}

% gcc -W -Wall -Wextra -O2 matrice.c
% ./a.out
AFFICHAGE MATRICE AVANT TRANSPOSITION:
14
25
36
AFFICHAGE MATRICE TRANSPOSEE:
123
456


--
Benoit Izac
Samuel DEVULDER
Le #21526071
a écrit :
J'ai oublié de dire que j'ai essayé le code ci-dessous qui reprend ce
que vous pensez être l'erreur mais ça ne convient pas mais alors pas
du tout:

printf("nAFFICHAGE MATRICE TRANSPOSEE: n") ;
for ( i = 0 ; i < col ; i++ )
{
for ( j = 0 ; j < lig ; j++ )
{
printf("%d", Mat[i][j]) ;
}
printf("n") ;
}



Heu c'est du "n'importe quoi" ton code (du vrai, hein pas comme celui de
Marc ;-) ).

Quand tu écris Mat[i][j], tu accèdes à l'élément i*2+j en mémoire (int
Mat[3][2]). Dans la boucle for, à un moment tu accèdes à Mat[0][2],
c'est à dire à la case 0*2+2=2. Or si tu regardes Mat[1][0] c'est aussi
à cette case que tu accèdes. Au final tu te retrouves à avoir plusieurs
fois le même élément affiché. Voici ce que donne ton affichage
symboliquement


Mat[0][0], Mat[0][1], Mat[0][2] <== tu débordes et tombe sur Mat[1][0]
Mat[1][0], Mat[1][1], Mat[1][2] <== Ca deborde sur Mat[3][0].

ou bien j'ai oublié les cours sur les matrices, ça doit faire 4-5 ans
et pourtant je m'en sortais bien...j'avoue que ce n'était qu'une
introduction.



Ton pb de vient pas de cours sur les matrices, mais d'un mélange
ligne/colonne et du débordement de tableaux qui en résulte.

Par ailleurs, matrice transposée ou pas, si tu prends la convention de
faire que la boucle la plus interne soit sur les colonnes, tu l'utilise
partout, et surtout tu n'inverse pas lignes et colonnes quand tu
affiches le résultat de la transposition. Enfin vu que tu travailles
avec la même matrice source et résultat, la transposition ne sera valide
que si la matrice est carrée.

sam.
zwim
Le #21526851
Le Fri, 09 Apr 2010 17:54:29 +0200
Samuel DEVULDER a écrit
Enfin vu que tu travailles
avec la même matrice source et résultat, la transposition ne sera valide
que si la matrice est carrée.



Pourtant la matrice et sa transposée ayant le même nombre d'éléments
on peut théoriquement faire la transposition sur place à un cast prêt
vu que la réprésentation interne du tableau bidimensionnel est un
tableau unidimensionnel de taille LIGNE * COL équivalent à un tableau
COL * LIGNE.

Donc si on a

int M[L][C];
/* ... algo de transposition ... */

alors maintenant après permutation, on a (symboliquement) le cast (
int[C][L] ) M qui est la transposée de M.

Bien entendu les échanges d'éléments dans l'algo de transposition
deviennent en peut plus compliqués à exprimer sous forme M[i][j].

Cela dit sous forme unidimensionnelle c'est juste
swap( M[i*C+j], M[j*L+i] )

Soit en bidimensionnel
swap ( M[i][j], M[(j*L+i)/C][(j*L+i)%C] )


--
zwim.
Rien n'est impossible que la mesure de la volonté humaine...
Samuel DEVULDER
Le #21527261
zwim a écrit :
Le Fri, 09 Apr 2010 17:54:29 +0200
Samuel DEVULDER a écrit
Enfin vu que tu travailles
avec la même matrice source et résultat, la transposition ne sera valide
que si la matrice est carrée.



Pourtant la matrice et sa transposée ayant le même nombre d'éléments
on peut théoriquement faire la transposition sur place à un cast prêt
vu que la réprésentation interne du tableau bidimensionnel est un
tableau unidimensionnel de taille LIGNE * COL équivalent à un tableau
COL * LIGNE.



C'est équivalent en occupation mémoire, mais pas au niveau de l'accès
aux éléments. Tu ne peux pas acceder à un tableau 3x2, comme s'il
sagissait d'un 2x3: pour un 3x2, l'accès à l'élément i,j est i*2+j et
pour 2x3 c'est i*3+j. C'est pas pareil. L'algo doit en tenir compte.

Pour légitimer le truc, il faut considérer la structure linéairement.
Laisse tomber les int[3][2] et considère un int[6].

La matrice de départ est:
123
456
Et se stocke en mémoire comme: 123456

Celle qu'on veut avoir est:
14
25
36
Et se stocke comme: 142536

Seuls 1 et 6 restent à leur place. Tout le reste bouge suivant une
permutation: 2 va en 3, 3 en 5, 4 en 2 et 5 en 4. Elle est circulaire

Si on raisonne en indice de tableaux on veut que:
i->j
----
0->0
1->3
2->1
3->4
4->2
5->5

En fait ca correspond presque à j = (3*i) % 5, sauf pour la dernière
ligne. On démontre que la formule est générale. Pour permuter "en place"
un tableau linéaire vu comme une matrice de M ligne x N colonnes il faut
executer le code suivant

#define M 3
#define N 2
int tab[N*M] = {1, 2, 3, 4, 5, 6 };

/* calcule avec qui permuter i */
int f(int i) {
if(i==N*M-1) return i;
else return (M*i) % (N*M-1);
}

et dans le main:
for(i = 0; i<N*M; ++i) {
int j = f(j);
int tmp = tab[j];
tab[j] = tab[i];
tab[i] = tmp;
}

Tu constate que c'est nettement moins efficace que pour une matrice
carrée (on fait deux fois plus d'échanges), mais ca marche.

sam.
bpascal123
Le #21527511
Merci pour toutes ces informations, astuces, conseils sur les
matrices.

Je me concentre fortement sur ce sujet en C car après je pense ça sera
plus évident de m'orienter vers la programmation objet vba pour ms
xcel ou python sur calc d'open office voire en clouds computing avec
google docs... je suppose que comprendre les matrices ne sera pas
inutile pour manipuler des données dans un tableur...

Dans le cas présent, la solution de Benoit Izac montre que mon erreur
venait de la déclaration de la matrice. Il sembe que pour un tableau
2d de type matrice, les bracelets délimitent aussi bien les lignes que
la dimension de la matrice.

Pour un simple tableau sur lequel on fait des calculs ou des
permutations, les bracelets ne sont présents que pour la dimension du
tableau. Sur Excel et Calc, je crois que c'est obligatoire de signaler
la présence d'une matrice en cas de calcul matriciel avec une
combinaison de touches spécialement pour ça, ALT F4 je crois ou
quelque chose comme ça. C'est pour obliger le tableur a insérer les
bracelets à chaque fin de ligne?...
Publicité
Poster une réponse
Anonyme