C++

[C] Calcul du déterminant d'une matrice [résolu] :sol

Recherche :

Mot : Pseudo : Filtrer
Page : 1 2 Page Suivante Page Précédente Bas de page
Auteur	Sujet : [C] Calcul du déterminant d'une matrice [résolu] :sol

Giz

Voilà je galère un peu, alors j'ai l'algo (c t un ex a faire):

On considère une matrice carrée M de dimension n, n >= 1, dont les éléments sont notés m(i,j), avec 1<=i<=n, 1<=j<=n. Le déterminant de M noté D est égal à:

D= m(1,1) si n=1,
Somme de k=1 à n de : (-1)^(k+1)*m(k,1)D(k) si n>1.

D(k) est le déterminant d'une sous matrice de M obtenue en lui supprimant la ligne k et la colonne 1.

--> Ecrire une fonction C qui permet de calculer le déterminant d'une matrice carrée de dimension n.

----------------------------------------------------------------
Voilà ci dessus TEL QUEL l'énoncé.

Voici ci dessous ma fonction C (décomposé en 2 fonctions) dont je sais qu'elle est fausse car:
1- Le résultat est faux (mon determine est tjs nul)
2- Je ne sais pas comment libérer la mémoire allouer par malloc()

Code :

/***************************************************************************************/
//Calcul du determinant de la matrice M
int determinant(int **M, int dim)
{
int somme = 0, **m;
int i, k, taille = dim;
static int compteur = 0;
compteur++;
printf("entree n %d dans la fonction determinant()\n", compteur);
afficher(M, dim);
if (taille > 1)
{
for(k=0;k<taille;k++)
{
//Calcul du "sous" determinant
m = (int**)malloc(sizeof(int*)*taille-1);
for(i=0;i<taille-1;i++)
m[i] = (int*)malloc(sizeof(int)*taille-1);
initialisation_sous_matrice(m, M, k, taille);
//Cas k pair
if((k+1)%2)
somme += -1*M[k][1]*determinant(m, taille-1);
//Cas k impair
else
somme += M[k][1]*determinant(m, taille-1);
}
//Ce qui suit est en commentaire car je ne vois pas comment déssallouer la mémoire ds un 1er tps !
/*for(i=0;i<taille-1;i++)
free(m[i]);
free (m);*/
}
else
return M[0][0];
return somme;
}
/***************************************************************************************/
//Calcul du sous determinant de la matrice M
void initialisation_sous_matrice(int **m, int **M, int k, int taille)
{
int i, j, l;
l = -1;
for(i=0;i<taille;i++)
{
if (i==k)
{
l = i-1;
continue;
}
l++;
for(j=1;j<taille;j++)
m[l][j-1] = M[i][j];
}
return;
}

----------------------------------------------------------------

Comme d'hab, si vous a v des questions ou besoin de précision pour m'éclaicir sur ce code, dite le moi ... parce que jsuis un peu bloqué (jmi suis penché 1H !)

Message édité par Giz le 27-12-2002 à 16:24:01

Publicité

Giz

pkoi somme = 0 deja ?? :??:

Giz

personne a trouvé ? :??:

Taz@PPC

saloperie de i=`expr $i + 1`;

c'est koi ce taille -1 ?

---------------
du bon usage de rand [C] / [C++]

Giz

parce que la "sous matrice" est de taille-1 (une ligne de moins et une colonne de moins)

Taz@PPC

saloperie de i=`expr $i + 1`;

si c'est un problème d'algo, j'ai pas trop envie de regarder

---------------
du bon usage de rand [C] / [C++]

farib

le fait est que pour calculer le déterminant, c'est bcp plus intéressant de diagonaliser la matrice plutot que de tout de suite calculer a la bourrin

paske la , la matrice 10*10, je la sens déja pas....

---------------
Bitcoin, Magical Thinking, and Political Ideology

Giz

:non:
l'algo est ds l'énoncé !!
c un problème de le coder en C pur !

Giz

farib a écrit :

Cai pas moi qui a fait l'énoncé desolai ... c l'algo qu'on m'impose c un devoir d'exam !

Profil supprimé

ptain j'ai essayé de m'y mettre hier a 2h du mat, mais ca faisait trop mal a la tete... :wahoo:
et today au taff, j'avais pas l'ennoncé, je vais voir ce soir mais je promet rien !
sur ce que j'ai vu, la fontc void initialisation_sous_matrice a l'air correcte

Publicité

Giz

zedine a écrit :

ptain j'ai essayé de m'y mettre hier a 2h du mat, mais ca faisait trop mal a la tete... :wahoo:
et today au taff, j'avais pas l'ennoncé, je vais voir ce soir mais je promet rien !
sur ce que j'ai vu, la fontc void initialisation_sous_matrice a l'air correcte

Vi tout a fait, jfais un printf de la matrice m et ca fé bien ce que je veu

Profil supprimé

Giz a écrit :

[cpp]/ //Cas k pair
if((k+1)%2)
somme += -1*M[k][1]*determinant(m, taille-1);
//Cas k impair
else
somme += M[k][1]*determinant(m, taille-1);

juste un truc, prquoi k pair donne *-1 ??
tu pars de la 1ere ligne donc k=0, donc pair, donc c + non ?

Giz a écrit :

//Ce qui suit est en commentaire car je ne vois pas comment déssallouer la mémoire ds un 1er tps !
/*for(i=0;i<taille-1;i++)
free(m[i]);
free (m);*/

perso, je pensais plus a un
for(0<i<n-1)
{
for(0<j<n-1)
{
free(m[i][j]);
}
}

pro du c needed...

Profil supprimé

Giz a écrit :

pkoi somme = 0 deja ?? :??:

si somme egale 0, c que toutes les colones (ou lignes) ne sont pas independantes, donc un vecteur peut etre exprimé a partir de tous les autres.
info si c bien ca la question ?

dis moi si je me trompe plus haut, surtout a propos du *(-1) et *(+1)

Profil supprimé

bon apres, mais c juste un detail, histoire de faire encore mieux (tu me diras, il faut deja que ca marche... :pt1cable: )
un petit plus aurai ete de faire un code pr des matrices de tout et n'importe quoi, donc prendre des void** et les caster en int au moment voulu, pour faire un code plus generique :sol: (ptain les cours de java sur la genericité ca marque !!)

Giz

zedine a écrit :

juste un truc, prquoi k pair donne *-1 ??
tu pars de la 1ere ligne donc k=0, donc pair, donc c + non ?

perso, je pensais plus a un
for(0<i<n-1)
{
for(0<j<n-1)
{
free(m[i][j]);
}
}

pro du c needed...

k pair donne -1 car :
si k=2 par ex :
k+1 = 3, (k+1)%2 = 1 dc on rentre ds le if (-1) tout simplement parce que la puissance est dc impaire

Pour le free ! :non:
c beaucoup plus compliké (mais jpense avoir trouvé)

Message édité par Giz le 26-12-2002 à 16:55:30

Giz

zedine a écrit :

t'inquiete ma matrice de départ est la matrice d'identité ! (det = 1 ca j'en suis sur )...et dc somme de vré =lé 1 !

Message édité par Giz le 26-12-2002 à 16:59:41

Taz@PPC

saloperie de i=`expr $i + 1`;

Code :

for(0<i<n-1)
{
for(0<j<n-1)
{
free(m[i][j]);
}
}

n'importe quoi.... tes désallocations doivent etre complement symétrique

Code :

m=malloc(n * sizeof *m)
for(i=0; i<n, ++i)
{
m[i]=malloc(n * sizeof *m[i])
}
/* ... */
for(i=0; i<n, ++i)
{
free(m[i]);
}
free(m);

sinon penser aussi à l'option

Code :

<Type>* m=malloc(n * n * sizeof <Type> ) // limite la fragmentation externe de la mémoire
//fonction d'acces l'acces
<Type> acces(<Type>*m, unsigned i, unsigned j)
{
// verification
return m[i*n+j]; // effectivement ça coute un petit calcul
}

Message édité par Taz@PPC le 26-12-2002 à 17:01:30

---------------
du bon usage de rand [C] / [C++]

Giz

zedine a écrit :

ben si jve traiter ma matrice m fo bien convertir en int pour faire les calcul du det :whistle: ...jte suis po la ... :??:

Giz

pour faire le free jsuis obligé de passé par un tableau de pointeurs dt chaque case du tablo pointeur sur une zone alloué !...et ce né SEULEMENT au changement deligne de la matrice de départ (M) lorsque k=1 par ex que je pe dessalouer toute la mémoire alouer par les sous matrices ...

Taz@PPC

saloperie de i=`expr $i + 1`;

:heink: je comprends rien à ce que tu racontes: mon exemple est pourtant simple

---------------
du bon usage de rand [C] / [C++]

Giz

Taz@PPC a écrit :

:heink: je comprends rien à ce que tu racontes: mon exemple est pourtant simple

ben ton exemple est celui que ja v en commentaire, ca differe en koi ?

Taz@PPC

saloperie de i=`expr $i + 1`;

ben allocation et désallocation doivent etre symetrique: si tu n'alloues pas case par case, ne désalloues pas case par case

---------------
du bon usage de rand [C] / [C++]

Giz

tu vois bien que je ne pe pas dessallouer la meme après mon malloc car la sous sous matrice depend de la sous matrice. Je ne pourré desalloué la sous matrice qu'au moment ou j'ai eu la fin de la récursivité (lorsque la sous matrice = a 1 seul chiffre) equivalent a changement de ligne par rapport a la matrice du tout départ (filé par l'utilisateur)

Taz@PPC

saloperie de i=`expr $i + 1`;

Citation :

tu vois bien que je ne pe pas dessallouer la meme après mon malloc car la sous sous matrice depend de la sous matrice.

alors revois ta conception

---------------
du bon usage de rand [C] / [C++]

Giz

Taz@PPC a écrit :

Citation :

tu vois bien que je ne pe pas dessallouer la meme après mon malloc car la sous sous matrice depend de la sous matrice.

alors revois ta conception

:non:
moi c pa le free qui m'inquiète ! c ke somme = 0 ...

farib

je comprend pas que t'ai besoin de malloc a souhait....

ta matrice, tu la recopie pas quand même ?

---------------
Bitcoin, Magical Thinking, and Political Ideology

Giz

farib a écrit :

je comprend pas que t'ai besoin de malloc a souhait....

ta matrice, tu la recopie pas quand même ?

ben écoute si on pars d'une matrice 4*4, la prochaine sera un "tablo" a 2 dimensions (passé en argument a la fonction determinant()) de 3*3 puis 2*2 puis 1*1 ... au final, je ne pe passé de tablo de taille fixe !! car la taille change en permanence...d'ou passage par les pointeurs (allocation memoire dynamique de tablo a 2 dimension via malloc())

Taz@PPC

saloperie de i=`expr $i + 1`;

:pfff:

---------------
du bon usage de rand [C] / [C++]

Giz

Taz@PPC a écrit :

:pfff:

[:spamafote]

farib

Giz a écrit :

tu fais bcp plus simple

ta fonction déterminant, tu lui passes comme argument un pointeur vers la matrice originale, et les numéros de ligne et de colonne que tu supprimes !

tu évites de recopier, ca ca ne sert à rien !

---------------
Bitcoin, Magical Thinking, and Political Ideology

Taz@PPC

saloperie de i=`expr $i + 1`;

ton problème d'allocation est un problème: le mieux c'est de libérer des que tu n'en as plus besoin pour soulager ton système.

ca peut etre joliment réalisé par une approche objet.

sinon, tu peux mémoriser toutes les allocations que tu as faites (soit en copiant des pointeurs dans des variables de sauvegarde, soit plus élégant dans un tableau/ liste et tout nettoyer proprement.)

mais préoccupes toid e ce problème. si tu n'arrives pas à le résoudre, c'est significatif d'une autre complexité dans ton programme. reprends simplement ton problème du début, deroules un peu à la main et c adevrait passer non d'un chien

---------------
du bon usage de rand [C] / [C++]

farib

a la limite fais deux tableau de dimension 1, de taile n pour les lignes/colonnes a supprimer

---------------
Bitcoin, Magical Thinking, and Political Ideology

farib

Taz@PPC a écrit :

il a pas besoin de tant allouer !

---------------
Bitcoin, Magical Thinking, and Political Ideology

Taz@PPC

saloperie de i=`expr $i + 1`;

le problème c'est que ta fonction boucle en permanence et allou à gogo

petit exemple: le det d'une 3x3, c'est 3 det de 2*2. pas la peine de créer toutes les 2x2 nécessaire. fais tes 3 appels recursifs sur une portion de la matrice initiale en jouant sur la taille de la sous matrice, en bougeant des pointeurs, etc.

si tu n'y arrives pas, reviens au solutions déjà donnée.

etant donné que tu ne fais pas de programmation concurrente, tu peux aussi tres bien envisager de créer un matric ede "de travail": tu ne modifies jamais ta matrice passer en paramètre et tu te sers de cette matrice temporaire et tu la désalloue

det(m, n)
{
matrice_temporaire bien allouée

// autant de fois
remplissage de matrice_temporaire

appel_recursif de det(matrice_temporaire, n-1)
ou
procéder iteratif

liberer matrice_temporaire
}

afin que seul la fonction appelante en premier libére la matrice_temporaire (dans une approche recursive), tu peux :rajouter un paramètre à det ou utiliser une vraiable statique (commune a toutes les fonctions (static int suis_je_la_premiere)

---------------
du bon usage de rand [C] / [C++]

farib

Taz@PPC a écrit :

c'est marrant, c'est ce que je dis depuis quelques posts :pfff: :pfff:

---------------
Bitcoin, Magical Thinking, and Political Ideology

Taz@PPC

saloperie de i=`expr $i + 1`;

ben vi je reprends ton idée: mais comme il semble pas comprendre.... :bounce:

---------------
du bon usage de rand [C] / [C++]

farib

de toute facon, même le prof d'info est con, car il impose un des algos les plus betes....

---------------
Bitcoin, Magical Thinking, and Political Ideology

Taz@PPC

saloperie de i=`expr $i + 1`;

:cry:

---------------
du bon usage de rand [C] / [C++]

Giz

farib a écrit :

mais au 1er appel j'ai rien a supprimer, juste a passer la matrice de départ

Giz

farib a écrit :

il a pas besoin de tant allouer !

Rien a foutre de l'optimisation c un sujet d'examen !! ... le but c ke ca marche ! :fou:

Publicité

Page : 1 2

Page Suivante

Page Précédente

Haut de page

FORUM HardWare.fr

Programmation

C++

[C] Calcul du déterminant d'une matrice [résolu] :sol

Sujets relatifs
[Java] Convertir un String en un Object Color [Résolu]	[Java] Rechercher un String dans un autre String [Résolu]
[Java] Occuper plusieurs cases dans un GridLayout? [Résolu]	[Java] Conversion int,double <-> object est ce possible? [Résolu]
probleme de <SELECT> et présélection d'une value [RESOLU]	ident failed for user machin?? d'où ça vient (Postgres inside)[résolu]
[C] Liste chainée que j'arrive pas à parcourir [resolu]	Calcul volume d'une page php envoyée
[résolu - C & Linux] Compilation du C sous Mandrake	[Java / Swing] Boite de dialogue avec JDialog ? [Résolu]
Plus de sujets relatifs à : [C] Calcul du déterminant d'une matrice [résolu] :sol

Page générée en 0.129 secondes