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 claudex . É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 Marotte ⛧ . Évalué à 2.
T'aurais pu aussi corriger le lien wikipédia au passage ;)
[^] # Re: Coloration syntaxique
Posté par claudex . É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 NeoX . Évalué à 4.
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 leolio . É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) :
Ensuite tu essaies de mettre un élément dedans à l'indice 0.
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 NeoX . É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
# méthode récursive
Posté par ǝpɐןƃu∀ nǝıɥʇʇɐW-ǝɹɹǝıԀ (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 FreeB5D . Évalué à 2.
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 Deuterium . É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 Michaël (site web personnel) . Évalué à 3.
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.
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 PierreLM . Évalué à -1.
En principe, il faut trouver par soi-même mais bon :
Ç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 PierreLM . É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 Michaël (site web personnel) . É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.
Cela s'écrit plutô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!
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.
deviens
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.
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:
Cette structure est meilleure parcequ'elle met en évidence le caractère récursif de
determinantet l'opération élémentaireproduire la comatricequi 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 à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.