Calculer la déterminante d'une matrice aléatoire de grandeur définie

Soyez le premier à donner votre avis sur cette source.

Vue 9 799 fois - Téléchargée 444 fois

Description

flashback

Driiiing, le cours de math est terminé et nous venons d'apprendre comment calculer la déterminante d'une matrice de n'importe quelle grandeur.
Avec des potes, j'ai eu la brillante idée de faire le pari que j'arriverai à écrire un programme calculant une déterminante encore le jour même.

Driiiing, fin des cours, je rentre à la maison, je mange qqch et je m'y mets. J'utilise comme d'hab mes fonctions MyMalloc, MyFree etc. pour ne pas m'emmerder avec ces trucs. Et voila le défi: pour calculer une déterminante im faut calculer le mineur et pour calculer un mineur il faut calculer une déterminante. c'était bien fun :P

Bon venons en au programme, que fait-il ?
Simple: il lit la grandeur de la matrice dans le fichier conf.txt et la remplit avec des valeurs aléatoires pour ensuite calculer sa déterminante et me dire combien de déterminantes/mineurs il a du calculer et combien il aurait du calculer au maximum.

CE PROGRAMME NE SERT STRICTEMENT A RIEN juste a m'occuper un apres midi :p

En plus, il choisit chaque fois la ligne avec le plus de 0 pour etre le plus rapide possible.

Ah oui, le programme original était uniquement allemand, alors si j'ai oublié de traduire certains messages d'erreur, dsl ^^

Source / Exemple :


/* Juste la partie principale du code source. */

int choose_line( MATRIX *pMatrix )
{
        int curr = 0;
        int max  = 0;
        int line = 0;
        int i, j;

        for( i = 0 ; i < pMatrix->iSize ; i++ ) {
                for( j = 0 ; j < pMatrix->iSize ; j++ ) {
                        if( pMatrix->pData[XY( j, i, pMatrix->iSize)] == 0 )
                                curr++;
                }
                if( curr > max ) {
                        max = curr;
                        line = i;
                }
                curr = 0;
        }

        return line + 1;
}

int calc_minor( MATRIX *pMatrix, int Line, int Column )
{
        MATRIX *pTemp = NULL;
        int i = 0,
            j = 0;

        g_nbr_minors++;

        /* (-1) ^ (i+j) */
        i     = pow( -1, (long)(Line + Column) );
        /* La determinante de la matrice kon a si on supprimme la ligne et

  • la colonne de l'element dont on doit calculer le mineur.
  • /
pTemp = matrix_delete_line_column( pMatrix, Line, Column ); j = calc_determinante( pTemp ); SAFE_FREE( pTemp->pData ); SAFE_FREE( pTemp ); return i * j; } int iLastPercent = -1; int iLastPerthousand = 0; int calc_determinante( MATRIX *pMatrix ) { int iChoosenLine = 1, iChoosenLineIsLine = 1, iResult = 0, a = 0, b = 0, i = 0, k = 0; float fPercent = 0.0f; g_real_nbr_determs++, g_virt_nbr_determs++; fPercent = (((float)g_virt_nbr_determs / (float)g_needed_determinants) * 100.0f); /* Actualiser la barre des % a chak fois kon est 1 % plus loin. */ if( iLastPercent < (int)fPercent ) { iLastPercent = (int)fPercent; for( a = 0 ; a < 100 ; a++ ) printf( "\b" ); printf( "Prog: |" ); for( i = 0 ; i < (int)(fPercent / 2.0f) ; i++ ) printf( "=" ); for( i = (int)(fPercent / 2.0f) ; i < 50 ; i++ ) printf( " " ); if( fPercent < 10.0f ) printf( "| ", fPercent ); else printf( "| ", fPercent ); fflush( stdout ); } /* Actualiser l'affiche des % et du temps restant a chak fois kon est 0.1 % plus loin. */ if( iLastPerthousand < (int)(fPercent * 10.0f) ) { iLastPerthousand = (int)(fPercent * 10.0f); /* Et afficher sa :p */ if( fPercent < 10.0f ) printf( "\b\b\b\b\b%3.1f %%", fPercent ); else printf( "\b\b\b\b\b\b%3.1f %%", fPercent ); fflush( stdout ); } /* Si la matrice n'est plus ke de 2x2, alors c gagner ^^ */ if( pMatrix->iSize == 2 ) return pMatrix->pData[0] * pMatrix->pData[3] - pMatrix->pData[2] * pMatrix->pData[1]; /* Autment bin tampi :p */ /* On le fait comme jviens de lapprendre en maths :p */ /* c "la somme des produits des elements d'une rangee et leur mineur" */ /* demerdez vous :D:D */ /* On choisit la ligne/colonne qui contient le plus de 0. */ iChoosenLine = choose_line( pMatrix ); /* Sa c pour faire sa sur une ligne. */ if( iChoosenLineIsLine ) { for( i = 1 ; i <= pMatrix->iSize ; i++ ) { k = XY( i-1, iChoosenLine-1, pMatrix->iSize ); /* La valeur de l'element de la rangee choisie. */ a = pMatrix->pData[k]; /* Le mineur de l'element de la rangee choisie.
  • Si a est dja 0, plus bsoin de calculer le mineur, puiske 0*x = 0
  • /
if( a != 0 ) { b = calc_minor( pMatrix, iChoosenLine, i ); } else { g_virt_nbr_determs += calc_nbr_determinants( pMatrix->iSize - 1 ); } iResult += a * b; } /* Et sa c pour faire sa sur une colonne. */ } else { for( i = 1 ; i <= pMatrix->iSize ; i++ ) { k = XY( iChoosenLine-1, i-1, pMatrix->iSize ); /* La valeur de l'element de la rangee choisie. */ a = pMatrix->pData[k]; /* Le mineur de l'element de la rangee choisie.
  • Si a est dja 0, plus bsoin de calculer le mineur, puiske 0*x = 0
  • /
if( a != 0 ) b = calc_minor( pMatrix, i, iChoosenLine ); iResult += a * b; } } return iResult; }

Conclusion :


J'ai deja fait tourner le programme avec une matrice de 15x15, je suis allé voir un film et en revenant, le prog avait crashé, je pense que c'est du à la limite de fonctions récursives pouvant être appelées. (Donc une limite windows ... sous linux je n'ai encore jamais rencontré un problème pareil)

PS: renommez le fichier "matrix.ex_" en "matrix.exe" ...
il y a aussi un executable linux: "matrix"

PPS: .wpj = Watcom ProJect pour l'IDE Open Watcom

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

munstef676
Messages postés
4
Date d'inscription
dimanche 1 juin 2014
Statut
Membre
Dernière intervention
31 mai 2019
-
A mon avis tu utilises une version longue pour calculer le déterminant d'une matrice. La complexité de cette algo est de l'ordre O(n!)
fener3475
Messages postés
1
Date d'inscription
vendredi 28 mars 2008
Statut
Membre
Dernière intervention
28 mars 2008
-
jai un devoir a faire c dire ke D n+1 > 0 avec le calcul des mineurs c une demonstration pleaseeee aider moi
dPompei2
Messages postés
56
Date d'inscription
samedi 27 mars 2004
Statut
Membre
Dernière intervention
1 septembre 2006
-
wai mais moi je venais d'apprendre celui que j'ai fait le jours meme :p l'autre, je connais tjrs pas, mais c'est pas grave, jai pas envie de l'apprendre mnt :)
cs_JCDjcd
Messages postés
1138
Date d'inscription
mardi 10 juin 2003
Statut
Membre
Dernière intervention
25 janvier 2009
2 -
Le faire en un jour ... j'ai fait les DEUX algorithmes en un meme jour, c'est pas la fin du monde non plus !!
dPompei2
Messages postés
56
Date d'inscription
samedi 27 mars 2004
Statut
Membre
Dernière intervention
1 septembre 2006
-
comme tu dis: c'est plus chiant à programmer ... et moi je voulais le faire en un jour :p

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.