Bonjour,

A titre d'entrainement j'ai essaye de mettre au point un programme qui calcule le determinant d'une matrice
voici mon code:

# include <stdio.h>
# include <stdlib.h>
# define LEN 3
# define POWER(n) ((1)-(2)*(n%2))

void input(int matrix[][LEN]);
void afficher(int matrix[][LEN]);
int** minor(int matrix[][LEN], int len, int i, int j);
double deter(int matrix[][LEN], int len);

int main (void) {

    int matrix[LEN][LEN] = {{0}};

    input(matrix);

    printf("%d", deter(matrix, LEN));

return 0;
}

void afficher(int matrix[][LEN])
{
    int i, j;

    putchar('\n');

    for (i=0 ; i < LEN ; i++) {
        for (j=0 ; j < LEN ; j++)
            printf("%3d ", matrix[i][j]);

        putchar('\n');
    }
}

void input(int matrix[][LEN])
{
    int i, j;

    for (i=0 ; i < LEN ; i++)
        for (j=0 ; j < LEN ; j++)
            scanf("%d", &matrix[i][j]);

}

int** minor(int matrix[][LEN], int len, int i, int j)
{
    int k, l, m, n;
    int **minor = NULL;

    minor = (int**)malloc((len-1)*sizeof(int*));

    if (!minor)
        exit(0);

    for (k=0 ; k < len-1 ; k++) {
        minor[k] = (int*)malloc((len-1)*sizeof(int));

        if (!minor[k])
            exit(0);
    }

    for (k=0, l=0, m=0, n=0 ; k != len || l != 0 
    {

        if (k != i && l != j)
            minor[m][n++] = matrix[k][l++];

        if (k == i || l == j)
            l++;

        if (l == len) {
            k++;
            l=0;
        }

        if (n == len-1) {
            m++;
            n=0;
        }
    }

return minor;
}


double deter(int matrix[][LEN], int len)
{

    int j, k, l, **min = NULL;
    double det=0;

    if (len == 1)
        return matrix[0][0];

    if (!len)
        return 0;

    for (j=0 ; j < len ; j++) 
    {
        min = minor(matrix, len, 0, j);

        det += POWER(j)*matrix[0][j]*deter(min, len-1);

        for (k=0 ; k < len-1 ; k++)
            free(min[k]);

        free(min);
    }

return det;
}

Seulement voila le programme ne marche pas : mon compilo donne un warning ligne 97 "passing arg 1 of `deter' from incompatible pointer type" et mon programme affiche des valeurs completement aberrantes

Il me semble que le probleme vient du fait que dans la fonction "deter" je fais un appel recursif mais en lui donnant en parametre une matrice de taille differente de celle donnee precedemment.

Pourriez-vous m'aider?

Merci!

Bonjour,
1.-- La fonction power n'intervient que pour number = (-1). Ce que tas as fait est donc bien trop compliqué.
En fait (-1)^n vaut 1 si n est pair et (-1) sinon, donc inutile de faire une fonction récursive :
(-1)^n = 1-2*(n%2)

2.-- Cette méthode (récursive) du calcul d'un déterminant est valable pour un déterminant d'ordre 3 (mais la règle de Sarrus donne un calcul très rapide) ou à la rigueur 4. Pour un ordre plus élevé, la récursivité est trop gourmande en temps et en mémoire. La méthode du pivot de Gauss me semble plus adaptée : avec ta méthode, un déterminant d'ordre 10 demande le calcul de 10 déterminants d'ordre 9; Chacun des déterminants d'ordre 9 demande le calcul de 9 déterminants d'ordre 8 etc...

1- C'est vrai t'as raison j'ai fait la modif

2- C'est vrai que cette methode est assez gourmande mais dans un premier temps j'aimerais quand meme savoir comment la realiser (en plus cette methode recursive m'as l'air beaucoup plus simple a coder)

Merci d'avance pour vos conseils!

Je pense que ta fonction deter(*,*,*,*)est correcte à condition de remplacer power(j) par
1-2*(j%2)
Tu peux diminuer le nombre de calculs en donnant directement la valeur pour un déterminant d'ordre 1,2 ou 3 (règle de Sarrus) et pour l'ordre > 3 faire comme tu as fait en arrêtant la récursion quand l'ordre parvient à 3 : 2 ou 3 instructions de plus dans la déf. de deter, mais beaucoup de calculs en moins.

Quant au (1-2*(j%2)) j'ai fait un define POWER(j) pour que ce soit plus propre

C'est vrai tu as raison ca me permettrait d'economiser pas mal d'operations.
Je vais faire ces modifications

Maintenant le probleme c'est que mon compilo me donne un warning ligne 97 "passing arg 1 of `deter' from incompatible pointer type" et que mon programme affiche des valeurs completement aberrantes

Je pense que cela est du au fait que dans l'appel recursif de la fonction deter je lui envoie en parametre la matrice "minor(matrix, len, 0, j)" qui est une matrice de taille "len - 1" or la fonction deter est concue pour recevoir une matrice de taille "LEN (defini par un define)".

Seulement je sais pas comment remedier a ca et si le probleme vient vraiment de la ou s'il y en a un autre

Si tu fais un déterminant d'ordre quelconque, la fonction deter calcul des deter de minor, puis de minor de minor , puis de minor de minor de minor, puis...C'est là que la récursivité utilise énormément de mémoire.
Donc si tu utilises ne cste prédéfinie LEN (>3 car pour 3, Sarrus donne le résultat immédiatement), il faut introduire la variable entière interne à la fonction deter, len fixée à LEN au départ, mais qui va décroître à chaque passage à un minor, ce qui va donner un grand nombre de variables len interne à chaque copie de la fonction deter.
De même dans la définition de minor, il faut remplacer partout LEN.
D'autre part, à la ligne précédant return det, tu devrais libérer la mémoire occupée par la matrice courante, sinon il y aurait une énorme quantité de matrices mineures inutiles lorsque l'on a calculé leur déterminant.
Bon travail et surtout bien avoir en tête tout ce qui est récursif.

Voila j'ai modifie le fonction "deter" pour eviter les fuites de memoire.

J'ai pas compris pourquoi je devrais mettre des "LEN" dans la fonction "minor"

D'autre part, j'ai toujours le meme probleme et j'ai pas tres bien compris comment y remedier...

Je n'ai pas calculer la complexité de ton algorithme mais une piste à creuser pour un algorithme plus simple et surement plus performant serait de triangulariser ta matrice via une bête méthode LU et de simplement faire le produit des termes diagonaux.
Et c'est d'autant plus léger en mémoire que tu n'as pas besoin de conteneur supplémentaire comme avec les mineurs / cofacteurs.

C'est vrai ce serait une solution mais je vois pas comment je pourrait facilement trouver un algorithme pour triangulariser ma matrice tout en gardant un code relativement simple

"Dans un premier temps" je prefere privilegier la simplicite du code a la complexite de l'algo.

En plus j'aimerais vraiment savoir pourquoi ce code ne marche pas et comment le reparer parce-que la je vois vraiment pas quelles modifs apporter pour qu'il fonctionne

A algorithme simple pour triangulariser ?

Voici une piste, un peu brutale (beaucoup de calculs pour rien) à explorer :

int det (double A[DIM][DIM], int N)
{
    double c, r=1;
    for(int i = 0; i < N; i++) {
        for(int k = i+1; k < N; k++) {
            c = A[k][i] / A[i][i];
            for(int j = i; j < N; j++)
                A[k][j]= A[k][j] - c*A[i][j];

        }
    }

    for (int i = 0; i < N; i++)
        r*=A[i][i];

    return r;
}

Je n'ai pas dit de mettre des LEN mais de remplacer par la variable len en paramètre qui pourra avoir différentes valeurs suivant le niveau de minor de minor de minor... où l'on se trouve, alors que LEN est une constante donc n'utilise que le 1er niveau.
Il est tard, demain, si j'ai le temps, je programmerai, mais en C++ (ce qui sera probablement du C).

Voici le code complet pour triangulariser. J'ai défini une matrice ligne par ligne : voir la méthode dans le main().
L'avantage cette méthode est de simplifier l'échange de 2 lignes : on échange les pointeurs sur les 2 lignes plutôt que de 'échanger 1 à 1 chaque terme des 2 lignes :

//
//  main.cpp
//  Determinant
//
//  Created by WROBEL Claude on 01/03/12.
//  Copyright (c) 2012 Domicile. All rights reserved.
//

#include <iostream>
#include <math.h>

// **************** FONCTION DETERMINANT **************** 
double determinant(const unsigned ordre,double ** tableau)
{
    double max, multiplicateur;
    unsigned i,j,k,ii;
    double *echange;
    double deter = 1.0;

    
    double **matrice = new double*[ordre]; // Matrice est un tableau de pointeurs sur des tableaux de doubles
    for (unsigned i = 0; i < ordre; i++)
    {
        matrice[i] = new double[ordre];
        
        for (unsigned j = 0; j < ordre; j++) // On copie tableau dans matrice pour ne pas modifier tableau
        {
            matrice[i][j] = tableau[i][j];

        }            
    }
            
            
    for(i = 0; i < ordre-1; i++) // Recherche du plus grand terme de la colonne i en valeur absolue.
    {
        max = 0.0;
        
        k = i;
        for (j = i; j < ordre; j++)
        {
            if (fabs(matrice[j][i]) > max)
            {
                 max = fabs(matrice[j][i]);
                 k = j;
            }
           
        }

        if (max == 0.0) return 0.0; //Toute la colonne sous la diagonale est nulle, le déterminant est donc nul
        if (k != i) // On échange les lignes pour que l'élément le plus grand (le pivot) soit sur la diagonale
        {
            echange = matrice[i];
            matrice[i] = matrice[k];
            matrice[k] = echange;
            deter *= -1; // Échange de lignes : le déterminant est changé en son opposé 

        }
        
        /* 
         on ajoute à chaque ligne un multiple de la ligne pivot pour annuller les termes sous le pivot,
         ce qui ne modifie pas le déterminant :
         */
        for (j = i+1; j < ordre; j++) // 
        {
            multiplicateur = -matrice[j][i]/matrice[i][i];
            for (ii = i; ii < ordre; ii++) 
            {
                
                matrice[j][ii] += matrice[i][ii]*multiplicateur;
            }

        }
       
        /*
        La matrice est triangulaire. Son déterminant est le produit des termes de la diagonale:
        */
        deter *= matrice[i][i];  
        

    }
    
    
    
    for ( i = 0; i < ordre; i++) delete matrice[i];
    delete matrice;
    
    return deter * matrice[ordre-1][ordre-1];
}


// **************** PROGRAMME MAIN() : EXEMPLE ****************
 
int main (int argc, const char * argv[])
{

    unsigned i,j;
    double **tableau = new double*[3];
    for (i = 0; i < 3; i++) tableau[i]= new double[3];

    /*
     tableau est une matrice de rotation d'angle 2Pi/3 autour de l'axe Oz, son déterminant vaut donc 1.
     Ce qui suit n'est pas la meilleure manière de calculer le déterminant,
     Mais cela permet de tester le cacul du pivot de Gauss sur un déterminant connu.
     */
     
    tableau[0][0] = -0.5; tableau[0][1] = -sqrt(3)/2; tableau[0][2] = 0.0;
    tableau[1][0] = sqrt(3)/2; tableau[1][1] = -0.5; tableau[1][2] = 0.0;
    tableau[2][0] = 0.0; tableau[2][1] = 0.0; tableau[2][2] = 1.0;
    

    
    std::cout << "Tableau : \n";
    for(i = 0; i < 3 ; i++)
    {
        for (j = 0; j < 3 ; j++) std::cout << tableau [i][j] << "\t";
        std::cout << "\n\n";
    }
        
    
    std::cout << "\n\nDéterminant = " << determinant(3,tableau) << "\n";
    
    
    for( i = 0; i < 3; i++) delete tableau[i];
    delete tableau;
    tableau = 0;
        
    return 0;
}

Si on enlève les commentaires et les lignes vides pour éclaircir le code, ce programme avec son application est court et vaut pour toute matrice carrée.
Je fais une copie de la matrice dans la fonction pour ne pas modifier la matrice du main().
La structure de la fonction est simple :
Ligne 21 : Construction de matrice et copie de tableau dans matrice.
Ligne 34 : Recherche du pivot.
Ligne 50 : Échange des lignes pour que le pivot soit sur la diagonale.
Ligne 58 : Mettre des 0 sous le pivot.
Ligne 84 : Rendre la mémoire et retourner la valeur du déterminant.
Ligne 93 : main()
Ligne 106: Matrice de rotation et calcul de son déterminant normalement égal à 1.

Pour revenir au problème initial, tu mélanges tableaux statiques et dynamiques. Ça marche bien à une dimension, après ça casse.
Ton compilateur t'en avertit d'ailleurs, d'où le warning que tu reçois.
Si tu définis int matrix[LEN][LEN], matrix n'est pas équivalent à un pointeur de type **int mais est plus proche du pointeur de type *int : c'est en quelque sorte équivalent à &matrix[0][0] (même si mon compilateur n'est pas d'accord, il semble lui accorder un statut particulier).

Etant donné que la fonction minor() ne peut pas se passer de tableau dynamique, je te conseille d'utiliser uniquement ce type de tableau...

Autre problème :

if (k != i && l != j)
    minor[m][n++] = matrix[k][l++];

Je crois me souvenir qu'une instruction modifiant la valeur de plusieurs variables en même temps est classée comme "comportement indéterminé". Je n'en suis pas sûr à 100%, mais dans tous les cas, mieux vaut éviter !


@Claude_le_Lorrain : Nous sommes ici dans la rubrique langage C...

Je me suis rendu compte que je répondais en C++ à un problème C. Mais j'ai très peu de fonctionalité C++, il suffit de remplacer les new par malloc(sizeof(double*) * ordre)) (pour le tableau des pointeurs de ligne) et malloc(sizeof(double) * ordre) pour les tableaux des termes de chaque ligne de la matrice), les cout par des printf et delete par free.

Merci pour votre aide!!

J'ai entre temps resolu le probleme par un simple remplacement des tableux statiques par des tableux dynamiques
Voici donc le code corrige de la solution recursive:

# include <stdio.h>
# include <stdlib.h>
# define LEN 3
# define POWER(n) ((1)-(2)*(n%2))

void input(int** matrix, int len);
void afficher(int** matrix, int len);
int** minor(int** matrix, int len, int i, int j);
double deter(int** matrix, int len);
void destroyMatrix(int** matrix, int len);

int main (void) {

    int **matrix = (int**)malloc(sizeof(*matrix)*LEN);

    for (int i=0 ; i < LEN ; i++)
        matrix[i] = (int*)malloc(sizeof(*matrix[i])*LEN);

    input(matrix, LEN);

    system("cls");
    afficher(matrix, LEN);
    printf("\nDeterminant: %lf", deter(matrix, LEN));

    destroyMatrix(matrix, LEN);

    return 0;
}

void destroyMatrix(int** matrix, int len) {
    for (int i=0 ; i < len ; i++)
        free(matrix[i]);

    free(matrix);
}

void afficher(int** matrix, int len) {
    int i, j;

    putchar('\n');

    for (i=0 ; i < len ; i++) {
        for (j=0 ; j < len ; j++)
            printf("%3d ", matrix[i][j]);

        putchar('\n');
    }
}

void input(int** matrix, int len) {
    int i, j;

    for (i=0 ; i < len ; i++)
        for (j=0 ; j < len ; j++)
            scanf("%d", &matrix[i][j]);
}

int** minor(int** matrix, int len, int i, int j) {
    int k, l, m, n;
    int **minor = NULL;

    minor = (int**)malloc((len-1)*sizeof(int*));

    if (!minor)
        exit(0);

    for (k=0 ; k < len-1 ; k++) {
        minor[k] = (int*)malloc((len-1)*sizeof(int));

        if (!minor[k])
            exit(0);
    }

    for (k=0, l=0, m=0, n=0 ; k != len || l != 0  {

        if (k != i && l != j)
            minor[m][n++] = matrix[k][l++];

        if (k == i || l == j)
            l++;

        if (l == len) {
            k++;
            l=0;
        }

        if (n == len-1) {
            m++;
            n=0;
        }
    }

    return minor;
}

double deter(int** matrix, int len) {

    int j, k, **min = NULL;
    double det=0;

    if (len == 1)
        return (double)matrix[0][0];

    if (!len)
        return 0;

    for (j=0 ; j < len ; j++) {
        min = minor(matrix, len, 0, j);
        det += POWER(j)*matrix[0][j]*deter(min, len-1);

        for (k=0 ; k < len-1 ; k++)
            free(min[k]);

        free(min);
    }

return det;
}

Ton code (fonction determinant et toutes les fonctions utilisées par determinant) contient plus de lignes que le mien (en supprimant les lignes de commentaires, les lignes vides et celles ne contenant que les accolades). En plus, tes lignes de code font appel à des fonctions complexes qui appellent elles même des fonctions, qui appellent ... (récursivité) ce qui augmente considérablement le temps d'exécution. J'essaierai de comparer les durées respectives des inversions de la même matrice 30x30 par chacune des 2 méthodes.
Ta fonction pour une matrice d'ordre 30 va construire 30 mineurs et fait une opération en boucle assez compliquée.
Chaque mineur va construire 29 mineurs qui...
Soit la construction de 30! mineurs d'ordre 2 et 30!/2 mineurs d'ordre 3, 30!/3! mineurs d'ordre 4, 30!/4! mineurs d'ordre 5 .... cela fait énormément de mineurs construits et détruits. et à la fin il faudra remonter le calcul des 30! déterminants dordre 2 qui permettent de caluler les 30!/2! determinants d'ordre 3 qui ......
Je te propose déjà de faire ce calcul sur une matrice 30x30 avec des coefficients aléatoires compris entre 0 et 1, je ferai de même de mon côté.

Je réédite 1 heure après. J'ai essayé un déterminant d'ordre 30 (30 lignes, 30 colonnes) à coeff aléatoire : 1,25 milliseconde.
Pour vérifier que le calcul est bon, j'ai pris une matrice dont je connais le résultat : 0,5 sur la diagonale, aléatoire sous la diagonale, 0 au dessus. Le résultat est bien 0,5 à la puissance 30 (produit des termes de la diagonale). Une autre avec 0 sur la diagonale, et 1 partout ailleurs. Le résultat est -29 comme le prévoit la théorie : une valeur propre simple 29 et une valeur propre (-1) multiple d'ordre 29 et le déterminant vaut le produit des valeurs propres.
Moins de 2 millisecondes. Je ne pense pas que la méthode récursive soit plus rapide.

J'ai testé ta méthode :
Déterminant d'ordre 10 : un peu moins de 4 secondes.
Déterminant d'ordre 11 : 40 secondes.
Déterminant d'ordre 12 : 8 minutes soit 40x12 secondes
Je n'ai pas fait l'ordre 13 mais comme il faut calculer 13 mineurs, le temps doit être de 8x13 = 104 minutes.
Pour un déterminant d'ordre 20, la durée de traitement devrait être de plus de 700 siècles : (104*14*15*...*20 minutes). Je n'ai pas eu la patience d'essayer.
Par contre, avec la méthode que je t'ai proposée, la durée de calcul d'un déterminant d'ordre 30 est inférieure à 1 milliseconde, de même pour un déterminant d'ordre 65. Mon ordi compile pour un déterminant d'ordre 66, mais l'exécution stoppe avec le message "Gdb", probablement un problème de mémoire.

Bonsoir à tous!!!
Je me suis inspiré de ce forum pour faire un programme qui calcule le déterminant d'une matrice fournie en argument. Il marche sans problème quand j'intègre la matrice dans le code source mais me renvoie toujours zéro quand j'utilise une procédure pour la saisie des éléments de la matrice par l'utilisateur.
Merci d'avance pour votre aide!!!

Ton post n'est pas très explicite; Peut-être un peu de code ?

Mais l exercice est posée comme ça

Bonjour,

Déterrage

Citation des règles générales du forum :

Avant de poster un message, vérifiez la date du sujet dans lequel vous comptiez intervenir.

Si le dernier message sur le sujet date de plus de deux mois, mieux vaut ne pas répondre.
En effet, le déterrage d'un sujet nuit au bon fonctionnement du forum, et l'informatique pouvant grandement changer en quelques mois il n'est donc que rarement pertinent de déterrer un vieux sujet.

Au lieu de déterrer un sujet il est préférable :

• soit de contacter directement le membre voulu par messagerie privée en cliquant sur son pseudonyme pour accéder à sa page profil, puis sur le lien "Ecrire un message"
• soit de créer un nouveau sujet décrivant votre propre contexte
• ne pas répondre à un déterrage et le signaler à la modération

Je ferme ce sujet.