Operations sur Tableau à 2 dimention

Operations sur Tableau à 2 dimention - C - Programmation

Marsh Posté le 03-03-2007 à 14:25:38    

Salut,
je galère un peut dans la création d'une fonction de calcule du déterminant d'une matrice:
pour l'algo c'est facile:
 

Code :
  1. Fonction determinant (Matrice M)
  2. debut
  3.    det = 0
  4.    pour i de 1 à M.taille
  5.       det += (-1)^(i + 1) * M[1][i] * determinant(sous_matrice(M, 1, i))
  6.    fin pour
  7.    renvoyer det
  8. fin
  9. // sous_matrice(M, i, j) renvoie la sous-matrice de M dont on a retiré la i-ème ligne et la j-ième colonne


 
alors voilà la fonction que j'ai fait pour l'instant, mais elle ne marche pas correctement :

Code :
  1. int determinant( int **mat, int N )  // N étant la dimension de la matrice (carrée)
  2. {
  3.     int c, det = 0;
  5.     if( N == 1 )
  6.         return mat[0][0];
  7.     if( N == 2 )
  8.         return ( mat[0][0] * mat[1][1] - mat[1][0] * mat[0][1] );
  10.     for(c=0; c<N; c++)
  11.     {
  12.         det += pow(-1,c) * mat[0][c] * determinant(sousMatrice(mat,N,c), N);
  13.     }
  15.     return det;
  16. }


 
Le problème est dans la fonction récursive, mais je ne trouve trop où !
 
merci


Message édité par bad___day le 05-03-2007 à 15:43:23
Reply

Marsh Posté le 03-03-2007 à 14:25:38   

Reply

Marsh Posté le 03-03-2007 à 17:29:19    

la sous matrice a pour dim N-1 et pas N comme marque ligne 12
donc la recursion ne se fait pas.

Message cité 1 fois
Reply

Marsh Posté le 04-03-2007 à 15:36:34    

Dag elg a écrit :

la sous matrice a pour dim N-1 et pas N comme marque ligne 12
donc la recursion ne se fait pas.


Ah oui, merci  :)  
et dire que je cherchais plus profond lol
 

Reply

Marsh Posté le 05-03-2007 à 15:47:24    

Sinon, j'ai essayer de faire un trie par sélection pour une matrice, voici le code:

Code :
  1. /* ordre Decroissant (par selection) */
  2. void TrierMatrice( int **mat, int N, int M )
  3. {
  4.     int i, j, L, C, posColonMax, posLignMax, temp;
  6.     for (i=0; i<N; i++)
  7.         for (j=0; j<N; j++)
  8.         {
  9.             /* Recherche du maximum après A[i][j] */
  10.             posLignMax = i;
  11.             posColonMax = j;
  13.             for (L=i; L<N; L++)
  14.                 for (C=i+1; C<M; C++)
  15.                     if ( mat[L][C] > mat[posLignMax][posColonMax] )
  16.                     {
  17.                         posLignMax = L;
  18.                         posColonMax = C;
  19.                     }
  21.             /* échange de A[I] avec le maximum */
  22.             temp = mat[i][j];
  23.             mat[i][j] = mat[posLignMax][posColonMax];
  24.             mat[posLignMax][posColonMax] = temp;
  25.         }
  26. }
 

Mais ça ne ma pas donnee un bon résultat, ça me parais pourtant juste .
encore merci.

 
Spoiler :

j'aurais due poster dans la catégorie algo ?  :p  

 


Message édité par bad___day le 07-03-2007 à 16:38:31
Reply

Marsh Posté le 05-03-2007 à 15:49:38    

pow(-1,c)
 
Cherche un peu, il y a beaucoup plus simple que ça, et sans calcul flottant.

Message cité 1 fois
Reply

Marsh Posté le 05-03-2007 à 15:51:00    

> determinant(sousMatrice(mat,N,c), N);
 
et gaffe à ce que retourne sousMatrice. Fuite de mémoire ?

Reply

Marsh Posté le 05-03-2007 à 17:04:18    

Taz a écrit :

pow(-1,c)
Cherche un peu, il y a beaucoup plus simple que ça, et sans calcul flottant.


Tu veut dire quoi ?
tu parle de mon 1er ou 2eme poste ?
 

Reply

Marsh Posté le 05-03-2007 à 22:07:55    

je parle de coder (-1)^(i + 1)

Message cité 1 fois
Reply

Marsh Posté le 07-03-2007 à 11:45:29    

Taz a écrit :

je parle de coder (-1)^(i + 1)


ok,
et pour le Trier de la Matrice http://forum.hardware.fr/forum2.ph [...] 0#t1523846

Reply

Marsh Posté le 07-03-2007 à 12:51:37    

bah j'ai pas compris. C'est quoi pour toi une matrice ordonnée ?

Message cité 1 fois
Reply

Marsh Posté le 07-03-2007 à 12:51:37   

Reply

Marsh Posté le 07-03-2007 à 15:47:38    

Taz a écrit :

bah j'ai pas compris. C'est quoi pour toi une matrice ordonnée ?


O_o
Bah une matrice trier, quoi ...
 

Reply

Marsh Posté le 07-03-2007 à 15:48:18    

Si t'es pas capable de l'expliquer, c'est que ça doit être drôlement clair pour toi.

Reply

Marsh Posté le 07-03-2007 à 15:53:11    

Peut être que je devrai mettre les élément de la matrice dans un vecteur, le trier, et les remettre dans la matrice...
mais je veut le faire directement....
 
Sinon pour la fonction de déterminant, je ne vois pas où est le problème à faire pow(-1,c)
 

Reply

Marsh Posté le 07-03-2007 à 15:55:30    

1) tu parles de bricolage alors que tu ne sais pas clairement ce que tu veux faire. Qu'est-ce qu'une matrice ordonnée ?
2) cette expression implique un calcul flottant inutile et couteux. On peut la simplifier trivialement du fait des propriétés de (-1)^(2n) and (-1)^(2n+1)

Message cité 1 fois
Reply

Marsh Posté le 07-03-2007 à 16:06:59    

Taz a écrit :

1) tu parles de bricolage alors que tu ne sais pas clairement ce que tu veux faire. Qu'est-ce qu'une matrice ordonnée ?


Tu veut que j'explique l'algorithme ?

 


Taz a écrit :

2) cette expression implique un calcul flottant inutile et couteux. On peut la simplifier trivialement du fait des propriétés de (-1)^(2n) and (-1)^(2n+1)


Faire par exemple :

Code :
  1. int signe = 1;
  2. for(c=0; c<N; c++)
  3. {
  4.        det += signe * mat[0][c] * determinant(sousMatrice(mat,N,c), N);
  5.        signe = signe * (-1);
  6. }


?

 


Message édité par bad___day le 07-03-2007 à 16:07:11
Reply

Marsh Posté le 07-03-2007 à 16:25:32    

1) non, je veux savoir ce qu'est une matrice ordonnée.
2) par exemple !

Reply

Marsh Posté le 07-03-2007 à 22:06:04    

Très inefficace, comme manière de calculer un déterminant. Cette définition n'a pas d'intérêt pratique. Il vaut mieux trigonaliser la matrice avec une élimination de Gauss et faire le produit des éléments diagonaux.


Message édité par el muchacho le 07-03-2007 à 22:20:47
Reply

Marsh Posté le 07-03-2007 à 22:25:20    

bah quoi, n! c'est bien non ?

Reply

Marsh Posté le 07-03-2007 à 22:30:29    

Ah non au contraire c'est catastrophique. En tout cas, c'est bcp moins bien que O(n^3) (Gauss).

 

Essaye de calculer le déterminant d'une matrice 30x30 avec n! Tu te retrouves avec du 10^32 calculs, t'as intérêt à être patient !
Alors que 30^3 = 27 000


Message édité par el muchacho le 07-03-2007 à 22:32:19
Reply

Marsh Posté le 08-03-2007 à 00:25:15    

humour ...

Reply

Marsh Posté le 08-03-2007 à 00:40:39    

Arf, j'ai eu un doute, mais à force, on n'a plus l'habitude de deviner sans le smiley qui signale "attention ironie"...


Message édité par el muchacho le 08-03-2007 à 00:41:52
Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

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