FYP, mais sinon oui, c'est ça.Citation:
Envoyé par lguignar
Version imprimable
FYP, mais sinon oui, c'est ça.Citation:
Envoyé par lguignar
Moi j'aurais bien vu une classe matrice avec pour attribut la dimension.
Ensuite ne serai-ce qu'une méthode SM(int i,int j), relativement simple, qui quand on l'applique à A : B = A.SM(i,j) nous fourni B, une matrice de dimension (n-1), égale à A à qui on aurait ôtée la ligne i et la colonne j.
Ensuite en suivant un principe de récursivité dans ta méthode "det" tu développais itérativement:
B = A.SM(i,j)
rezultat(i,j) = A(i,j)*(((-1)^(i+j))*det(B))
en prenant soin de décrire les premiers élément de ta récursivité, mais tu as dit que tu savais faire.
tu return rezultat.
Bon je n'ai pas écrit en langage C++, je dois filer, je pense que l'algo est complet (si mes restes de maths sont encore convenables, le doute plane).
Bonne journée.
FYP?Citation:
Envoyé par Scorpi0
Fixed Your Post (corrigé ton message). CF les == corrigé en !=.Citation:
Envoyé par lguignar
a yes carrément, merci j'edit dessuite
Il faut voir les opérateurs comme des fonctions.Citation:
Envoyé par lguignar
i++ :
- crée une copie de i;
- incrémente i;
- renvoie la copie.
++i :
- incrémente i;
- renvoie i.
Donc si l'utilisation de i++ ou ++i n'est pas dictée par un comportement requis, il vaut mieux utiliser ++i :
- ++i est plus rapide que i++, même si ce n'est pas un grosse optimisation, ça ne prend pas plus de temps de l'écrire comme ça, et ça ne diminue pas la lisibilité, alors pour quoi s'en priver (cf. Standards de programmation en C++, Herb Sutter et Andrei Alexandrescu : art. Ne pas être prématurément pessimiste) ;
- ++i me parait également plus fiable, dans la mesure où tu es sûr que i a été incrémenté au moment où tu l'emploi dans une autre opération.
Intéressant tout ça, moi qui ne faisait que des i++...
Je m'éloigne un peu du sujet par contre désolé
Mode Hors Sujet on [off]
Oui... sauf que c'est un algorithme récursif... Le problême des algos récursifs c'est la mémoire... quand il sagit de calculer n! pas de problême mais sur les matrices.... c'est autre chose...Citation:
Envoyé par lguignar
Prenons un exemple... une (petite?) matrice de 100x100... Elle utilise 100x100x4 = 40Ko
A chaque récursion, tu vas créer des sous matrices 99x99 (39Ko) puis 98x98 (38Ko) puis 97x97 (38Ko)...
Pour un total de 2*n(n + 1)(2n + 1)/3 (avec n=100) => 1.3Mo !!!
Une matrice de 200x200 couterai 10Mo
Et une matrice de 1000x1000... 1 bon Go !
Et si ta construction se fait dans la pile (retour de fonction, déclaration dans la fonction...), la taille de pile faisant par défaut 1Mo (sans toucher aux options de compilation), même la matrice 100x100 ne passera pas !!
De plus ton code à l'air d'allouer un tableau de MAX*MAX à chaque fois... donc hop... ca sera 4*MAX*MAX*n octets ... si MAX=n=100 => 4Mo !
En fait... on construit la sous-matrice une seule fois...Citation:
j'arrive pas à comprendre comment tu construis ta sous matrice quand i est différent de 0. Tu n'attribues qu'une ligne? subrows est bien "vide" au départ?
J'aurais fait un truc du genre :
Code:
2
3
4
5
6
Prenons l'exemple de la matrice 4x4...
On a initialement:
On va faire le boulot ligne par ligne, en considérant la colonne 0...Code:
2
3
4
5
6[0] [1] [2] [3] matrix[0] 00 01 02 03 matrix[1] 10 11 12 13 matrix[2] 20 21 22 23 matrix[3] 30 31 32 33
donc on veut faire 00 * determinant(11-33) - 10 * determinant(...)...
La première sous-matrice sera:
Hors... il s'avere, queCode:
2
3
4
5[0] [1] [2] submat[0] 11 12 13 submat[1] 21 22 23 submat[2] 31 32 33
submat[0] = matrix[1]+1 !
submat[1] = matrix[2]+1
submat[2] = matrix[3]+1
Du coups... 3 affectations pour remplir la sous-matrice pour la ligne 0, et on peut lancer le determinant dessus.
Passons à la ligne 1.... on veut la sous-matrice suivante:
Hoho... c'est exactement la même sauf la ligne 0:Code:
2
3
4
5[0] [1] [2] submat[0] 01 02 03 submat[1] 21 22 23 submat[2] 31 32 33
submat[0] = matrix[0]+1 !
1 affectation et on peut lancer un determinant dessus !
Passons à la ligne 2.... on veut la sous-matrice suivante:
Hoho... c'est exactement la même que précédemment sauf la ligne 1:Code:
2
3
4
5[0] [1] [2] submat[0] 01 02 03 submat[1] 11 12 13 submat[2] 31 32 33
submat[1] = matrix[1]+1 !
1 affectation... et determinant...
Passons à la ligne 3.... on veut la sous-matrice suivante:
Hoho... c'est exactement la même que précédemment sauf la ligne 2Code:
2
3
4
5[0] [1] [2] submat[0] 01 02 03 submat[1] 11 12 13 submat[2] 21 22 23
submat[2] = matrix[2]+1 !
1 affectation... et determinant....
Et voilà pour la construction des sous-matrices... Aucune mémoire allouée sauf pour les pointeurs de ligne.... 2*n - 1 affectations pour l'ensemble des sous matrices... (un retour naïf d'appel de fonction nécessiterait n*n*n affectations).
Résultat des courses... pour faire le déterminant, ce n'est plus 2*n(n + 1)(2n + 1)/3 octets qu'il faut... mais 2*n*(n+1) ! Ce qui change nettement la donne... (200Ko pour une matrice 1000x1000 !). Le cache CPU sera ravi du changement ! :D
Sans compter le nombre d'affectations, qui a bien l'air d'être en n exposant 4 avec un algorithme naïf, alors qu'il peut être en n² .
Malheureusement (ou heureusement?), le nombre d'opération (* + / -) lui, est identique...
Ben je trouve pas personnellement... -1 exposant n... c'est quand même moins lisible que "négatif si c'est impair"...Citation:
Effectivement pow(-1,i) est pas terrible mais peut-être plus lisible (ou pas)
a oui, malin effectivement :p