Forum Programmation.java Programme Déterminant matrice carrée

Posté par  .
Étiquettes : aucune
-2
31
déc.
2011

Bonjour a tous,

Actuellement étudiant en informatique, je dois pour un projet d'algorithmique réaliser un programme permettant de calculer le déterminant d'une matrice.
Je n'ai pas le droit d'utiliser de langage objet, hormis pour la création d'une nouvelle structure a utiliser comme variable. Mes fonctions et procédure doivent toujours être de la forme 'public static'.
Et pour être honnête, ce projet j'en bave... Je viens vers vous dans l'espoir de recevoir vos lumières, si quelqu'un sait pourquoi ce que je vais poster ne marche pas...

J'utilise donc une structure matrice définie dans une classe mat :

public class mat {
    int col;
    int row;
    int [][] T ;
}

Et j'ai crée le code suivant pour calculer le déterminant d'une matrice carrée ( le fameux qui ne marche pas ), que j'ai essayé de commenter a maximum. J'utilise la méthode des cofacteurs (http://fr.wikipedia.org/wiki/Comatrice). Je vous invite a le copier dans votre IDE et si vous arrivez a le faire tourner, je serai vraiment fort reconnaissant ! Voici le code :

import java.util.Scanner;

public class testdet3 {
    private static Scanner scanner = new Scanner(System.in);
    
    
    
    public static void main(String[] args) {
     
     mat matricetest;
     matricetest = new mat ();
     remplirmatrice(matricetest);
     int det;
     det = determinant(matricetest);
     
     System.out.println("Le determinant est : "+det);
     
     
     afficherMatrice(matricetest);



     }
    
    public static int determinant(mat matrice)
    {
        
    int determ = 0, row, col;
    
    // On crée un tableau dans lesquel on stockera les déterminants des cofacteurs de la premiere ligne
    int detcofact[] = new int [matrice.col-1];

    
    
    
    /*calcule le cofacteur (sans le signe) pour chaque cases de la premiere ligne du tableau et
     * le reporte dans le tableau des cofacteurs de la premiere ligne */


            for ( col = 0; col < matrice.col; col++) 

            {
            detcofact[col] = detcofacteur(matrice,col,matrice.col);
            }
            
   // multiplie chaque case de la premiere ligne de la matrice en entrée par son cofacteur calculé dans le tableau cofacteur
            
                   for ( col = 0; col < matrice.col; col++) 

                    {
                    detcofact[col]=matrice.T[0][col]*detcofact[col];
                    determ += detcofact[col]*(-1^col);
                    }
       return determ;
    }
    
    
    
    
    public static int detcofacteur(mat matricofact,int rang, int dim)
            
    {
    int detcofact = 0;
    
    // si la dimension de la matrice entrée est 1*1, on retourne alors le seul nombre concerné

    
    if (dim == 1)
        
    {
    detcofact=matricofact.T[0][0];
    }
    
    // Sinon on définit la sous matrice par apport a matricofact dont on devra calculer le déterminant, qu'on appelle cofact
    else 
            {
            mat cofact;
            cofact = new mat();
            // Cofact aura donc une ligne et une colonne de moins que matricofact
            
            cofact.T = new int [dim-2][dim-2];
            
            
            // Dans le cas ou le cofacteur calculé n'est pas celui en [0][0]
            if (rang != 0)
                
            {
            
            // On remplit Cofact par les éléments de matricofact AVANT la colonne du cofacteur en cours de calcul
            for (int colonne=0 ; colonne < rang ; colonne++)
            {
                for (int ligne=1 ; ligne < dim ; ligne ++)
                {
                // Ligne -1 car dans cofact, la premiere ligne ne doit pas être vide
                cofact.T[ligne-1][colonne]=matricofact.T[ligne][colonne];
                }
            }
            
             // On remplit Cofact par les éléments de matricofact APRES la colonne du cofacteur en cours de calcul
                        for (int colonne=dim-1 ; colonne > rang ; colonne--)
                    {
                        for (int ligne = 1 ; ligne < dim ; ligne ++)
                        {
                        // Colonne -1 car une colonne a été enlevée dans matricofact : celle du cofacteur en cours de calcul
                        cofact.T[ligne-1][colonne-1]=matricofact.T[ligne][colonne];
                        }
                    }
                                
                                
             detcofact=determinant(cofact);
            }
            
            // Dans le cas ou le cofacteur calculé est celui en [0][0]
            
            else 
            {
                        for (int colonne=dim-1 ; colonne > rang ; colonne--)
                    {
                        for (int ligne = 1 ; ligne < dim ; ligne ++)
                        {
                        // Colonne -1 car une colonne a été enlevée dans matricofact : celle du cofacteur en cours de calcul
                        cofact.T[ligne-1][colonne-1]=matricofact.T[ligne][colonne];
                        }
                    }
            }
            }
    return detcofact;
    }
    
    public static void remplirmatrice(mat matrice)
        {
            int row,col;
        System.out.println("Saisie d'une matrice :");
        
        System.out.println("Merci de rentrer un nombre de lignes (entier positif < 10) :");
        matrice.row = scanner.nextInt();
        
        System.out.println("Merci de rentrer un nombre de colonnes (entier positif < 10) :");
        matrice.col = scanner.nextInt();
        
        matrice.T = new int [11][11];
        
        System.out.println("Veuillez maintenant rentrer les valeurs de chaque case de la"
                + " matrice, comprises dans ]-100,100[ et entieres");
        
            for ( row = 0; row < matrice.row; row++)
            {
            for ( col = 0; col < matrice.col; col++) 
                
            {
                System.out.print(" mat[" + (row + 1) + "," + (col + 1) + "]=");
                matrice.T[row][col] = scanner.nextInt();
            }
            }
        }
    
    
public static void afficherMatrice(mat add) {
            
            for (int row = 0; row < add.row; row++) {
            
            for (int col = 0; col < add.col; col++) {
                
            /* Pour un affichage plus propre, si le nombre est négatif et comporte donc
               un "-", on mettra un espace de moins que si le nombre est positif
               De même si le nombre a 2 chiffres, on lui enlevera un espace ( donc un nombre a 2 chiffres max)*/
                
                if (add.T[row][col]<0)
                {
                    if (add.T[row][col] <= -10)
                    {
                System.out.print(" " +add.T[row][col] );
                    }
                    else
                    {
                       System.out.print("  " +add.T[row][col] ); 
                    }
                }
                else
                {
                    if (add.T[row][col] > 10)
                    {
                System.out.print("  " +add.T[row][col] );
                    }
                    else
                    {
                    System.out.print("   " +add.T[row][col] );
                    }
                }
            }
            // Retour à la ligne
            System.out.println();
        }
    }
}

  • # Coloration syntaxique

    Posté par  . Évalué à 4.

    J'ai modifié ton message pour inclure la coloration syntaxique, c'est beaucoup plus lisible.

    « Rappelez-vous toujours que si la Gestapo avait les moyens de vous faire parler, les politiciens ont, eux, les moyens de vous faire taire. » Coluche

    • [^] # Re: Coloration syntaxique

      Posté par  . Évalué à 2.

      T'aurais pu aussi corriger le lien wikipédia au passage ;)

      • [^] # Re: Coloration syntaxique

        Posté par  . Évalué à 4.

        Voilà, c'est fait.

        « Rappelez-vous toujours que si la Gestapo avait les moyens de vous faire parler, les politiciens ont, eux, les moyens de vous faire taire. » Coluche

  • # peut-etre commencer par le commencement

    Posté par  . Évalué à 4.

    Actuellement étudiant en informatique, je dois pour un projet d'algorithmique

    si on te demande les "matrice carré" et le calcul du determinant, c'est surement aussi que tu fais des maths, donc tu dois savoir deja le faire sur papier avant de le faire par l'informatique.

    on appelle ca la pluri-disciplinarité.

    comme c'est un projet d'algorithmique, alors ecris ton algorithme en francais,
    - decompose tes actions, celles qui peuvent etre repetées, celles qui sont uniques
    - decompose tes vairables et leurs valeurs.

    ensuite seulement tu devras te poser la question de l'ecriture dans un langage.

  • # Taille d'un tableau

    Posté par  . Évalué à 4.

    En faisant le test avec une matrice toute bête : la matrice unité de taille 1, on s'aperçoit que lors du calcul du déterminant, tu crées un tableau de 0 éléments (le nombre entre crochets est le nombre d'éléments) :

    int detcofact[] = new int [matrice.col-1];
    
    

    Ensuite tu essaies de mettre un élément dedans à l'indice 0.
    detcofact[col] = detcofacteur(matrice,col,matrice.col);
    
    

    Autre remarque : le calcul du déterminant s'applique uniquement aux matrices carrées donc il est inutile de demander le nombre de colonnes.

    • [^] # Re: Taille d'un tableau

      Posté par  . Évalué à 2.

      j'ajouterais qu'avec de tels indices :
      nombre de ligne de 1 à 9 (<10)
      nombre de colonne de 1 à 9 (<10)

      puis creation d'une matrice de 11 colonnes,
      ca va poser souci

      System.out.println("Merci de rentrer un nombre de lignes (entier positif < 10) :");
              matrice.row = scanner.nextInt();
              
              System.out.println("Merci de rentrer un nombre de colonnes (entier positif < 10) :");
              matrice.col = scanner.nextInt();
              
              matrice.T = new int [11][11];
      
      
  • # méthode récursive

    Posté par  (site Web personnel) . Évalué à 2.

    À l'aube, au lendemain de la saint sylvestre, la java on en a souvent son compte. Du coup, je n'ai pas trop de commentaire sur votre code ou visiblement quelques coquilles trainaient.

    En revanche, si vous en bavez avec la méthode des cofacteurs et que l'algorithme n'est pas imposé, pourquoi ne pas essayer une autre approche ? Il me semble — je parle d'expérience — que la programmation d'un calcul récursif de déterminants est très simple. Peut-être qu'essayer dans cette direction vaudrait le coup ?

    En gros, le déterminant d'une matrice nxn est la somme des déterminants des sous-matrice (n-1)x(n-1) — obtenues par élimination d'une ligne et d'une colonne — multipliées par (-1) à la puissance (décalage de colonne + décalage de ligne). Et on recommence jusqu'aux déterminants 2x2. Ce calcul est inefficace au possible. Mais il a l'avantage d'être programmable en deux coups d'emacs^w^w^w de vim.

    « IRAFURORBREVISESTANIMUMREGEQUINISIPARETIMPERAT » — Odes — Horace

    • [^] # Re: méthode récursive

      Posté par  . Évalué à 2.

      Ce calcul est inefficace au possible.

      Plus précisément, la complexité est factorielle, il y aura par exemple 3628800 appels récursifs pour une matrice 10×10. Pour avoir une complexité polynômiale en temps, on peut utiliser un pivot de Gauss.

    • [^] # Re: méthode récursive

      Posté par  . Évalué à 1.

      Les cofacteurs, c'est pareil en terme de complexité que la méthode récursive : d'ailleurs si je ne m'abuse il y a un appel récursif dans le code.
      Par contre la méthode récursive est plus simple à programmer, les histoires de comatrices ça sert surtout pour des questions mathématiques théoriques.

    • [^] # Re: méthode récursive

      Posté par  . Évalué à 3.

      En gros, le déterminant d'une matrice nxn est la somme des déterminants des sous-matrice (n-1)x(n-1) — obtenues par élimination d'une ligne et d'une colonne — multipliées par (-1) à la puissance (décalage de colonne + décalage de ligne).

      Ces déterminants sont (au signe près) les fameux cofacteurs. Donc la méthode quetu décris est bel et bien celle que veut utiliser l'OP.

      Ce calcul est inefficace au possible.

      Effectivement, c'est difficile de faire pire, et même quand on calcule à la main ce n'est jamais la méthode qu'on utilise! (Sauf pour les matrices 2x2 ou quand le calcul semble particulièrement facile.) En pratique on fait un pivot de Gauss pour se ramener à une matrice diagonale de même déterminant. Cela se fait en espace constant (si la représentation des nombres est en espace constant) et en temps O(n^3) où n est la taille de la matrice. Des variantes permettent de passer de 3 à un nombre un peu plus petit, dans les 2,73.

      Ceci dit, pour le type de projet, je pense que la méthode des cofacteurs est un bon choix, simple à mettre proprement en œuvre. Bon courage!

  • # Réponse

    Posté par  . Évalué à -1.

    En principe, il faut trouver par soi-même mais bon :

    public class TestDet3 {
    
    	public static void main(String[] args) {
    		Mat matricetest = remplirmatrice();
    		afficherMatrice(matricetest);
    		
    		System.out.println("Le determinant est : "+determinant(matricetest));
    
    		afficherMatrice(matricetest);
    	}
    
    	public static int determinant(Mat matrice)
    	{
    		int determinant=0;
    		
    		if(matrice.col==1)
    			return matrice.T[0][0];
    		
    		for (int col = 0; col < matrice.col; col++) 
    		{
    			Mat sousMat=getSousMatrice(matrice,col,0);
    			int detSousMatrice=determinant(sousMat);
    			if(col%2==0)
    				determinant+=matrice.T[col][0]*detSousMatrice;
    			else
    				determinant-=matrice.T[col][0]*detSousMatrice;
    		}
    
    		return determinant;
    	}
    
    	private static Mat getSousMatrice(Mat matrice,int colToSupp,int rowToSupp)
    	{
    		Mat retour = new Mat();
    		retour.col=matrice.col-1;
    		retour.row=matrice.row-1;
    		retour.T=new int[retour.row][retour.col];
    		
    		for(int i=0;i<matrice.col;i++)
    			for(int j=0;j<matrice.row;j++)
    			{
    				if(j<rowToSupp && i<colToSupp)
    					retour.T[i][j]=matrice.T[i][j];
    				else if(j<rowToSupp && i>colToSupp)
    					retour.T[i-1][j]=matrice.T[i][j];
    				else if(j>rowToSupp && i>colToSupp)
    					retour.T[i-1][j-1]=matrice.T[i][j];
    				else if(j>rowToSupp && i<colToSupp)
    					retour.T[i][j-1]=matrice.T[i][j];
    			}
    		return retour;
    	}
    	
    	public static Mat remplirmatrice()
    	{
    		Mat retour=new Mat();
    		int [][] T={{-2,2,-3},{-1,1,3},{2,0,-1}};
    		//int [][] T={{-2,2,-3},{0,1,3},{0,0,-1}};
    		retour.T=T;
    		retour.col=3;
    		retour.row=3;
    		
    		return retour;
    	}
    
    	public static void afficherMatrice(Mat add) {
    
    		for (int row = 0; row < add.row; row++)
    		{
    			for (int col = 0; col < add.col; col++) 
    				System.out.print(" " +add.T[row][col]);
    			System.out.println();
    		}
    		System.out.println();
    	}
    }
    
    

    Ça ne doit fonctionner que pour les matrices carrées. Je te laisse faire les autres. Attention à la syntaxe, nom d'une classe commençant par une majuscule...

    En contrepartie, tu participeras au libre. Je suggère une dépêche linuxfr ou une page wikipedia de ton choix.

    • [^] # Re: Réponse

      Posté par  . Évalué à -1.

      J'ai dit une connerie, le déterminant, c'est seulement pour les matrices carrées. Du coup, dans la classe Mat, pas la peine d'avoir col et row, la dimension suffit. Voir, cette classe ne sert à rien du tout. Un tableau suffit.

  • # Tes commentaires et ton code

    Posté par  . Évalué à 3.

    Tes commentaires ne sont pas bons:
    - bavards;
    - imprécis;
    - pas pertinents.

    Ne le prends pas mal, c'est pour t'aider à t'améliorer.

    int determ = 0, row, col;
        
        // On crée un tableau dans lesquel on stockera les déterminants des cofacteurs de la premiere ligne
        int detcofact[] = new int [matrice.col-1];
    
    

    Cela s'écrit plutôt

    int determ = 0, // accumulateur: calcul du déterminant
     row, // curseur des lignes
     col; // curseur des colonnes
     int detcofact[] = new int [matrice.col-1]; // déterminants des cofacteurs de la première ligne  de matrice.T     
    
    

    (Avec des alignements que je ne peux pas faire ici.)

    Dans la deuxième version toutes les lignes sont documentées, la mention on crée un tableau pour y stocker disparaît: une variable sert à stocker une valeur, pas la peine de l'écrire, dit plutôt ce qui est dedans!

     public static int detcofacteur(mat matricofact,int rang, int dim)
    
    // Retour à la ligne
    System.out.println();
    
    

    Tu trouves ça plus pertinent d'indiquer un retour à la ligne que d'expliquer ce que fait ta fonction auxiliaire et de décrire ses paramètres? Gros problème de hiérarchisation des informations, de plus la paraphrase du code est inutile ou nuisible. Si tu te donnais la peine de faire cette description, tu te donnerais une chance d'écrire une fonction qui fait ce que tu veux en éclaircissant cette histoire dans ta tête.

    // si la dimension de la matrice entrée est 1*1, on retourne alors le seul nombre concerné
        if (dim == 1)
        {
        detcofact=matricofact.T[0][0];
        }
        // Sinon on définit la sous matrice par apport a matricofact dont on devra calculer le déterminant, qu'on appelle cofact
        else 
    
    

    deviens
    // Si la taille de la matrice entrée est 1x1, alors son déterminant detcofact est son unique coefficient
    // sinon on construit le cofacteur cofact dont on calcule le déterminant detcofact.
     if (dim == 1)
        {
        detcofact=matricofact.T[0][0];
        }
     else
    
    

    Ceci dit, dans ce fragment la logique me paraît suspecte. Tes commentaires doivent: 1. expliquer ce que font les fonctions et 2. expliquer pourquoi ce qu'elles font donne le bon résultat.
     /* Pour un affichage plus propre, si le nombre est négatif et comporte donc
          un "-", on mettra un espace de moins que si le nombre est positif
          De même si le nombre a 2 chiffres, on lui enlevera un espace ( donc un nombre a 2 chiffres max). */
    
    

    C'est bavard, tu n'a pas décrit le travail que fait ta procédure et enfin, ne programmant pas en java j'hésite tout de même à croire qu'il n'y a pas de fonction de type printf qui t'aidera à afficher proprement un tableau de nombres.

    Voilà un canvas pour ton programme:

    // determinant(MATRICE)
    //  Renvoie le déterminant de la matrice carrée MATRICE. 
    //  Calcul par la méthode des cofacteurs.
    public static int determinant(mat matrice)
        {
    int determ = 0, // accumulateur: calcul du déterminant
     j; // curseur des colonnes
     
    // Le déterminant d'une matrice 1x1 est son unique coefficeint, on développe le déterminant des matrices de taille plus grande selon la première ligne, grâce à la fonction `comatrice`. 
    if (matrice.col == 1) {
      determ = matrice.T[0][0];
    } else {
      for (j = 0; j < matrice.col; j++) 
      {
       determ += (-1^j)*matrice.T[0][j]*determinant(comatrice(matrice,0,j));
      }
      return determ;
    }
    
    // comatrice(MATRICE, I0, J0)
    //  Renvoie la comatrice de MATRICE relative à la position I0, J0.
    public static mat comatrice(mat matrice, int i0, int j0)
    {
    int i, // curseur des lignes
    int j; // curseur des colonnes
    mat c = new mat();
    c.row = matrice.row - 1;
    c.col = matrice.col - 1;
    c.T = new int[c.row][c.col];
    
    for (i = 0; i < c.col; i++) {
     for(j = 0; j < c.row; j++) {
      c.T[i][j] = 
    }
    }
    }
    
    

    Cette structure est meilleure parcequ'elle met en évidence le caractère récursif de determinantet l'opération élémentaire produire la comatrice qui apparaît dans ton algorithme mais pas dans ton code. Avec ce point de départ plus sein, tu devrais t'en sortir.

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n’en sommes pas responsables.