Discussion :

[mouchT8]

Bonjour,

Me revoilà avec des problèmes de Matrice.
C'est la première fois que j'utilise les Matrice, et ça se voit !!

J'ai plusieurs problèmes à résoudre mais tout d'abord commençons par ce qui me pose le plus gros problème!

J'ai une matrice carré 4X4 a initialiser jusque là pas trop de problème mais là ou ça "choc" c'est lorsque je doit calculer le déterminant !
Je ne trouve pas la formule correcte !!!
Pour une 2X2 facil, POur une 3X3 idem, mais la 4X4 ...

J'ai bien une "formule" donné par mon énoncé mais alors impossible de la rentré correctement avec VS !!

La voici:

Det(A)= detA = somme[1<=i<=n] (-1)i+1 ai1 |Aij|;

avec
A: une matrice carrée
(a): l'élément unique de la matrice
(aij): les éléments de la matrice (je sais pas pourquoi mais les indices ne s'affiche pas dsl)
det(A): le déterminant
A(ij) une sous matrice de A

J'avoue que je ne comprend rien !!!
N'y aurait t il pas une formule plus "soft" ???

Merci de votre aide !!

[nicroman]

Ben non... c'est la formule de base du déterminant.... Et c'est la même quelque soit la taille de matrice...

On prend une colonne (ou un ligne), et pour chaque element on ajoute (pour les index pairs) ou on retire (pour les index impairs) sa valeur multiplié par le determinant de la matrice qui reste une fois qu'on a enleve la colonne et la ligne de cet élément.

Pour
00 01
10 11
on a donc: 00 * det(11) - 10 * det(01) = 00 * 11 - 10 * 01

Pour:
00 01 02
10 11 12
20 21 22
on a donc: 00 * det (11,12,21,22) - 10 * det(01,02,21,22) + 20 * det(01,02,11,12)
soit: 00*11*22 - 00*12*21 - 10*01*22 + 10*21*02 + 20*01*12 - 20*02*11


Pour:
00 01 02 03
10 11 12 13
20 21 22 23
30 31 32 33

Le determinant est:

Code :

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

1
2
3
4
 
         11 12 13             01 02 03             01 02 03             01 02 03
00 * det(21 22 23) - 10 * det(21 22 23) + 20 * det(11 12 13) - 30 * det(11 12 13)
         31 32 33             31 32 33             31 32 33             21 22 23

Maintenant, je ne sais pas ce que tu fais sur ces matrices, peut-être ont elles des particularités ?
Parceque pour une matrice 'quelconque', ca fait quand même (n! - 1) additions et (n-1)*n! multiplications

[mouchT8]

non je ne fait rien de particulier,
c'est une simple matrice, juste pour apprendre à les manipuler quoi.

Mais le probleme c'est que de la manière dont la formule est écrite, j'ai plein d'erreur sur cette ligne avec VS.
Deja les indices ne s'écrivent pas en indices
et on dirait qu'il manque des opérateurs non ??
Mon dieu que le temps du lycée est loin

[Flow_75]

Code :

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

Det(A)= detA = somme[1<=i<=n] (-1)i+1 ai1 |Aij|

Tu le code comment sous VC ?

sinon, la méthode de nicroman est correcte pour un déterminant d'une matrice 4x4 et assez simple à coder si tu as fait le calcul de déterminant pour 3x3

[nicroman]

Faudrait voir un bout de code...
C++ (forum C++)


Voici un 'exemple' de code (j'ai pas compilé, mais l'idée y est):

Code C :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
/// on passe n ligne de n valeurs....
template<type T> T det(int numRows, const T** rows)
{
     int numSubRows = numRows - 1;
     if (numSubRows == 0)
         return rows[0][0];
 
     T acc = 0;
 
     const T** subrows = new (const T*)[numRows-1];
     for (int i = 0; (i < numRows); ++i) {
         // filling subrows
         if (i == 0) {
             // initial setup
             for (int j = 0; (j < numSubRows ); ++j) 
                subrows[j] = rows[j+1] + 1;
         } else {
             // we just have to replace row i-1  !!!
             subrows[i-1] = rows[i-1] + 1;
         }
         T subdet = det<T>(numSubRows,subrows);
         if (i % 2)
            acc -= rows[i][0] * subdet;
         else
            acc += rows[i][0] * subdet;
     }
     delete [] subrows;
     return acc;
}

[nicroman]

Et un exemple à base de template (déroulés)

Code C++ :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
 
///
/// Initial setup of sub-elements, starting with last row...
///
template<type T, int row> void det_subelts_setup(const T** elts, const T** subelts)
{
    det_subelts_setup<T,row-1>(elts,subelts);
    subelts[row] = elts[row]+1;
}
///
/// Specialisation when row index is 0 (no call to previous row)
///
template<type T, 0> void det_subelts_setup(const T** elts, const T** subelts)
{
    subelts[0] = elts[0] +1;
}
 
///
/// Code factorisation to retrieve a sub-matrix * element value
///
template<type T, int n, int row> T det_part(const T** elts, const T** subelts)
{
    return (row%2) ? 
        -elts[row][0] * det<T,n-1>(subelts) :
        +elts[row][0] * det<T,n-1>(subelts);
}
 
///
/// Determinant accumlation for any row (subelts must be already setup 
/// for that row).
///
template<type T, int n, int row> T det_acc(const T** elts, const T** subelts)
{
    // subelts is already setup to handle row !
    T ret = det_part<T,n,row>(elts,subelts);
    // replacing previous row
    subelts[row-1] = elts[row]+1;
    // accumulating (loop)
    ret += det_acc<T,n,row-1>(elts,subelts);
    return ret;
}
///
/// Specialisation for row 0 (no call to previous row)
///
template<type T, int n, 0> T det_acc(const T** elts, const T** subelts)
{
     return det_part<T,n,row>(elts,subelts);
}
 
///
/// Determinant function:
/// - Prepare sub-rows
/// - Start accumulation
template<type T, int n> det(const T** elts)
{
     const T* subelts[n-1];
     det_subelts_setup<T,n-2>(elts,subelts);
     // making the loop
     return det_acc<T,n,n-1>(elts,subelts);
}
 
/// specialization for n==1
template<type T,1> T det(const T** elts)
{ 
    return elts[0][0];
}
 
/// specialization for n==2 (optionel)
template<type T,2> T det(const T** elts)
{ 
    return elts[0][0]*elts[1][1] - elts[0][1]*elts[1][0];
}

Là encore, j'ai pas compilé... mais le coeur y est !

[mouchT8]

Je ne comprend rien a tes codes
Je n'pense pas que ce soit ce qu'il faut que je face.
Ou alors je suis pas dans la m****

...

C'est juste ma formule qui me pose problème.
Enfin je n'arrive pas non plus a déclarer ma matrice mais c'est autre chose

Je met tel quel: Det(A)= somme[1<=i<=n] (-1)i+1 ai1 |Aij|;

et apparement c'est pas du tout son truc a VS...

[nicroman]

Heu....
On parle bien de C++ non ?

Si dans un éditeur de fichier source C++ tu rentres tel quel:

Code :

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

1
2
 
Det(A)= somme[1<=i<=n] (-1)i+1 ai1 |Aij|;

Alors oui, tu es dans le caca... et je te conseille vivement d'ouvrir un livre d'initiation à la programmation, puis un livre d'initiation au C/C++
Ensuite il ne te restera plus qu'à "modéliser" l'écriture "mathématique" Det(A)= somme[1<=i<=n] (-1)i+1 ai1 |Aij|; (parceque ce n'est rien d'autre, et un non mathématicien ne comprendrait rien à ce qui est écrit),
en un algorithme (un truc à base de 'pseudo-code'), compréhensible par un informaticien,
puis en language (C, C++, Java, Visual Basic, ou tout autre language qui te plaira) compréhensible par un "compilateur"/"interpreteur"
qui sera capable de fournir un programme (compréhensible par un *ordinateur*).

[mouchT8]

euh d'accord.

Je ne savais pas qu'il fallait transformer cela !

Sinon, je sais ce qu'est un algorithme merci...
idem pour le reste d'ailleurs..

C'est justement ce que je voulais savoir, si cette formule était a écrire tel quelle ou non.

Je n'suis pas complètement atardée non plus.
Enfin..

Merci pour votre aide!

[mouchT8]

rebonjour !

Voilà ce que donne ma formule désormé:

Code :

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

1
2
3
4
5
6
7
8
detA = 0;

	for(i=1; i<n; i++) {	
	detA+=(-1)^(i+1)* m[1][i] * determinant(m[1][i]);
	}

return detA;
}

Je ne vois pas d'autre solution.

Mon seul probleme est que

error C2664: 'Matrice::determinant' : impossible de convertir le paramètre 1 de 'int' en 'Matrice'

à l'endroit indiqué en rouge...

Pourtant c'est bien la sous matrice que j'ai mit là.. NOn?

[Flow_75]

Normal, tu mets en paramètre le contenu d'une case (le contenu de la case m[1][i]), et non une matrice.

[Scorpi0]

Un conseil :

Développe une fonction qui à partir d'une matrice et d'un ensemble de ligne et de colonne te retourne une sous matrice, et c'est cette fonction que tu doit passer ici :

Code :

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

detA+=(-1)^(i+1)* m[1][i] * determinant(m[1][i]);

à la place de determinant(m[1][i]) (qui ne ressemble pas du tout à ce que ta formule te donne, c'est à dire : A(ij) une sous matrice de A)

[mouchT8]

Voila mon code::::

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<iostream>
#include <conio.h>
#include <string.h> 
#include <stdio.h> 
 
using namespace std;
 
int n;
int i,j;
int m[4][4];
 
//DECLARATION DE LA CLASSE MATRICE
//********************************
 
class Matrice {
 
 
public:
 
	void initialise();
	int sous_matrice(m,i,j);
	int determinant(Matrice);
	void affiche();
};
 
 
//****************************************
// FONCTION D'INITIALISATION DE LA MATRICE
 
void Matrice::initialise() 
{ 
m[0][0]=0;m[1][0]=1;m[2][0]=1;m[3][0]=2; 
m[0][0]=3;m[1][1]=2;m[2][1]=0;m[3][1]=1; 
m[0][0]=0;m[1][2]=1;m[2][2]=2;m[3][2]=4; 
m[0][0]=2;m[1][3]=3;m[2][3]=2;m[3][3]=0; 
}
 
 
//*****************************************************
//FONCTION QUI RENVOIS LA SOUS_MATRICE
 
int Matrice::sous_matrice(m,i,j) {
 
 
 
}
 
 
//**********************************
// FONCTION DE CALCUL DU DETERMINANT
 
int Matrice::determinant(Matrice) {
 
int detA;		// déterminant
 
//Au cas où la matrice n'est pas carrée:
if (i!=j){	
return 0;
}
 
//Calcul du déterminant de la matrice:
 
detA = 0;
 
	for(i=1; i<n; i++) {	
	detA+=(-1)^(i+1)* m[1][i] * determinant(sous_matrice(m,1,i));
	}
 
return detA;
}
 
 
//****************
//FONCTION AFFICHE
 
void Matrice::affiche () 		
{
cout<<"Voici notre Matrice A:"<<endl;
cout<<"--------------------"<<endl;
 
cout<<m[0][0]<<" | "<<m[1][0]<<" | "<<m[2][0]<<" | "<<m[3][0]<<endl;
cout<<m[0][0]<<" | "<<m[1][1]<<" | "<<m[2][1]<<" | "<<m[3][1]<<endl; 
cout<<m[0][0]<<" | "<<m[1][2]<<" | "<<m[2][2]<<" | "<<m[3][2]<<endl;
cout<<m[0][0]<<" | "<<m[1][3]<<" | "<<m[2][3]<<" | "<<m[3][3]<<endl;
 
cout<<endl;
}
 
 
 
/////////////////////
//FONCTION PRINCIPALE
/////////////////////
 
void main() {
 
Matrice A; 
 
cout<<"Bienvenue dans notre programme d'exemple de manipulation de Matrice!! "<<endl;
cout<<"----------------------------------------------------------------------"<<endl;
 
cout<<"Initialisation d'une Matrice A ......"<<endl;
cout<<endl;
 
cout<<"Entrée de l'indice pour notre Matrice: indice 1,2,3 ou 4..."<<endl;
cout<<"Ici nous allons prendre par exemple un indice 4. Entrez donc '4'."<<endl;
cin>>n;
 
A.initialise(); 
 
cout<<"Voici un exemple d'initialisation pour la Matrice A 4X4: "<<endl; 
A.affiche(); 
cout<<endl;
 
cout<<"Le Determinant de A vaut: \n "<<A.determinant(A)<<endl; 
 
getchar();
}

ET en réponse à Scorpi0:

Merci pour le tuyau !!!!
[...]

[lguignar]

j'imagine que tu t'en doute mais il faut faire de la récursivité ici (enfin je pense...)

en exalgo quelquechose comme ça:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
int det(Matrice m) {
     if (m.size()==1)
         return m.getValue(0,0);
     else {
         int result=0;
         for (int i=0; i<m.size(); i++) {
              result+=pow(-1,i)*m.getValue(i,0)*m.sousMatrice(i);
         }
         return result;
     }
}

et pour les grandes lignes de la classe matrice :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Matrice {
     private :
     int _m[MAX][MAX];
     int _size;
 
     public :     
     /* constructeurs et destructeurs */
     Matrice();
     ~Matrice();
 
     /* opérateurs */
     void setValue(int i, int j, int value);
     int size() const;
     int getValue(int i, int j) const;
     Matrice sousMatrice(int i) const;
};

et pour l'implémentation de la fonction sousMatrice (le reste est trivial je pense)

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Matrice
Matrice::sousMatrice(int i) const {
     Matrice m;
     int x=0; int y=0;
     for (int j=0; j<_size; i++) {
         for (int k=0; k<_size; k++) {
             if (j!=i && k!=i) {
                 m.setValue(x, y, _m[j][k]);
                 y++;
             }
         x++;
         }
     }
}

Bon le code pour sousMatrice n'est à mon avis pas le meilleur possible :p
l'entier en paramètre c'est l'entier qui determine la ligne et la colonne à "enlever"

Bien sur tout ceci est à vérifier (je le tape à la volé, pas compilé) et donc à prendre avec des pincettes, j'espère pouvoir t'aider

[EDIT] mouarf t'as déjà trouvé tout seul les trois quarts :p, j'ai codé la fonction sousMatrice mais on a pas les mêmes arguments, je regarde avec les tiens... [/EDIT]

[lguignar]

hmm il y a quelques erreurs de conception j'ai l'impression (ou alors on a pas du tout la même manière de coder et j'ai du mal à appréhender ta manière, ce qui est plus qu'envisageable :p )

enfin je dis quand même : ta fonction sousMatrice retourne un int pourquoi? elle devrait plutôt renvoyer un tableau d'int ou même mieux une entité Matrice (mais dans ce cas il faut que ta classe matrice contienne un tableau d'int...)

D'ailleurs le fait que ta classe ne contienne que des fonctions m'étonne un peu... A mon avis ce serait plus "propre" que tu mettes

Code :

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

int m[4][4];

comme attribut privé de la classe Matrice avec des accesseurs

Parce que de mon point de vu ta classe ne sert à rien, tu pourrais très bien déclarer tes fonctions hors de la classe ça ne changerais strictement rien.

De plus tu n'initialise jamais ton n (qui représente la taille de la matrice j'imagine), je pense qu'il pourrait aussi être en attribut de ta classe Matrice.

enfin bref tout ça ne te fait pas trop avancer pour la fonction mais dès que t'aura revu ta structure de données j'essayerai de t'aider (je m'ennuie pas mal au taf en ce moment )

[mouchT8]

merci beaucoup pour ces quelques bons conseils 'lguignar' !!

Dès que j'ai le temps je m'y remet et je post mes changements!!

Pas aujourd'hui car je finit un autre programme
Demain probablement !

Je vais donc réfléchir la dessus

merki

[nicroman]

Je reposte mon exemple de code...

Sans template (remplacé par des float), et avec commentaires en Français (habitudes quand vous nous tenez...)

Code c++ :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
/// on passe n ligne de n valeurs....
float  determinant (int numRows, const float** rows)
{
     // on vérifie le cas trivial 1 seul ligne/colonne....
     int numSubRows = numRows - 1;
     if (numSubRows == 0)
         return rows[0][0];
 
     // on prépare l'accumulateur de retour
     float acc = 0;
     // et la sous-matrice utilisée... A noter qu'on a juste besoin de conserver
     // des pointeurs de lignes vu qu'on va prendre les sous matrices par colonne croissante...
     // on utilise une allocation dynamique, parceque l'algorithme est récursif
     // 1000 lignes ferait un total de 4Mo (ce qui risque d'exploser la pile).
     const float** subrows = new (const float*)[numSubRows]; 
 
     // pour chaque ligne
     for (int i = 0; (i < numRows); ++i) {
         // si on est sur la première ligne, il faut initialiser la 'sous-matrice'
         if (i == 0) {
             // dans celle-ci chaque ligne pointe sur l'élément 1 de la ligne suivante
             for (int j = 0; (j < numSubRows ); ++j) 
                subrows[j] = rows[j+1] + 1;
         } else {
             // on a juste à changer la ligne i-1, les autres sont bonnes
             subrows[i-1] = rows[i-1] + 1;
         }
 
         float subdet = determinant(numSubRows,subrows);
         // pow(-1,i) est un peu hard à mon gout ! :D
         if (i & 1)
            acc -= rows[i][0] * subdet;   // ligne impaire... c'est -1
         else
            acc += rows[i][0] * subdet;  // ligne paire... c'est 1
     }
     // et voilà...
     return acc;
}

A noter toutefois que la version templatisée (que j'avais posté) est un poil plus rapide....
Surtout sur de petites matrices (10x10)

[lguignar]

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

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 plus ça évite de différencier le cas i==0.
Mais bon s'il n'y a pas besoin de boucle quand i!=0 alors mieux vaut différencier effectivement.

Si tu peux m'expliquer stp?

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

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

[Flow_75]

Code :

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

i++ et ++i

dans le premier cas, tu fais l'opération qui est associée à la variable, puis tu incrémente.
dans le deuxième cas, tu incrémente, puis tu fais l'opération associée

[lguignar]

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?