Discussion :

[Scorpi0]

ok du genre :

Code c++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
short i=0;
while (++i!=0) cout << "toto ";

va boucler jusqu'à faire le "tour" des entier et revenir à 0 et donc afficher environ 32768 (ou 65536 je me rappel plus combien de bits pour un short) fois toto alors que

Code c++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
short i=0;
while(i++!=0) cout << "toto ";

s'arrête dès le début et n'affiche rien.

C'est ça?

FYP, mais sinon oui, c'est ça.

[Hanz Peter Mariol]

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.

[lguignar]

FYP, mais sinon oui, c'est ça.

FYP?

[Scorpi0]

FYP?

Fixed Your Post (corrigé ton message). CF les == corrigé en !=.

[lguignar]

a yes carrément, merci j'edit dessuite

[Noxen]

H.S. : quelle est la différence entre i++ et ++i?

Il faut voir les opérateurs comme des fonctions.

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.

[lguignar]

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]

[nicroman]

Je pense que l'utilisation des pointeurs n'est pas nécessaire (ici on calcule sur une matrice 4x4, apparemment c'est juste pour faire un peu de C++ et manipuler les matrices).

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...

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 !

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 c++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
int n=0;
for (int j=0; j<numSubRow; ++j) {
    if (n==i) ++n;
    subrows[j]=rows[n]+1;
    ++n;
}

En fait... on construit la sous-matrice une seule fois...
Prenons l'exemple de la matrice 4x4...

On a initialement:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
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

On va faire le boulot ligne par ligne, en considérant la colonne 0...
donc on veut faire 00 * determinant(11-33) - 10 * determinant(...)...

La première sous-matrice sera:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
            [0]    [1]    [2] 
submat[0]   11     12    13
submat[1]   21     22    23
submat[2]   31     32    33

Hors... il s'avere, que
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:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
            [0]    [1]    [2] 
submat[0]   01     02    03
submat[1]   21     22    23
submat[2]   31     32    33

Hoho... c'est exactement la même sauf la ligne 0:
submat[0] = matrix[0]+1 !
1 affectation et on peut lancer un determinant dessus !

Passons à la ligne 2.... on veut la sous-matrice suivante:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
            [0]    [1]    [2] 
submat[0]   01     02    03
submat[1]   11     12    13
submat[2]   31     32    33

Hoho... c'est exactement la même que précédemment sauf la ligne 1:
submat[1] = matrix[1]+1 !
1 affectation... et determinant...

Passons à la ligne 3.... on veut la sous-matrice suivante:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
            [0]    [1]    [2] 
submat[0]   01     02    03
submat[1]   11     12    13
submat[2]   21     22    23

Hoho... c'est exactement la même que précédemment sauf la ligne 2
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 !

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...

Effectivement pow(-1,i) est pas terrible mais peut-être plus lisible (ou pas)

Ben je trouve pas personnellement... -1 exposant n... c'est quand même moins lisible que "négatif si c'est impair"...

[lguignar]

a oui, malin effectivement :p