Skip to content

C – Points-cols dans une matrice

10 mars 2016

Les séries de TD et TP ont un exercice sur la recherche des points-cols dans une matrice :

Écrire un programme permettant de rechercher dans une matrice donnée A les éléments qui sont à la fois un maximum sur leur ligne et un minimum sur leur colonne. Ces éléments sont appelés des points-cols. Afficher les positions et les valeurs de tous les points-cols trouvés.

Reprenons l’exemple donné :

3 2 1
6 5 4
9 8 1

L’élément à la 1re ligne et 1re colonne, de valeur 3, est un point-col car c’est à la fois un maximum sur sa ligne et un minimum sur sa colonne.

Prenons un exemple avec plusieurs points-cols :

 1  3  2  3
 9  6  5  4
11 13  8  7
 0  3  1  3
10  9  3  2

Pour trouver les points-cols, on examine la matrice ligne par ligne. Pour chaque ligne i, on cherche la valeur du maximum Max. Ensuite pour chaque position (i,j) contenant Max, on examine la colonne j pour voir s’il n’y a pas une valeur plus petite. Si l’on n’en trouve pas, c’est que c’est un point-col.

Dans cet exemple :

  • la 1re ligne a la valeur 3 comme maximum,
  • la valeur 3 se trouve à la 2e colonne et la 4e :
    • on commence par la 2e colonne : elle ne contient pas de valeur plus petite que 3, c’est donc un minimum sur cette colonne et donc l’élément de la 1re ligne et 2e colonne est un point-col de valeur 3,
    • on continue sur la 1re ligne avec la 4e colonne (puisqu’elle contient aussi la valeur maximum 3) : la 4e colonne  n’a pas de valeur plus petite, donc on a un deuxième point-col à la 1re ligne, 4e colonne, de valeur 3,
  • la 2e ligne a la valeur 9 comme maximum,
  • la valeur 9 ne se trouve qu’à la 1re colonne :
    • la 1re colonne contient des valeurs plus petites que 9, ce n’est donc pas un minimum sur cette colonne, donc pas de point-col ici,
  • la 3e ligne a 13 comme maximum,
  • le seul 13 est à la 2e colonne :
    • la 2e colonne contient des valeurs plus petites que 13, donc pas de point-col ici,
  • on passe à la 4e ligne : elle a 3 comme maximum,
  • il y a deux 3 sur cette ligne, un à la 2e colonne et un à la 4e :
    • dans la 2e colonne pas de valeur plus petite que 3, donc l’élément de la 4e ligne et 2e colonne est un point-col de valeur 3,
    • dans la 4e colonne, 3 est aussi le minimum, donc le 4e point-col, de valeur 3, est à la 4e ligne, 4e colonne.
  • 5e ligne : le maximum est 10
  • il n’y a un 10 qu’à la 1re colonne :
    • la 1re colonne contient des valeurs plus petites que 10, donc ce n’est pas un point-col.

Une indication sur la méthode à suivre pour écrire le programme est donnée, qui suggère de construire deux « matrices d’aide » MAX et MIN, de mêmes dimensions que A. MAX contiendra des 1 aux positions correspondant dans A à un maximum sur une ligne, le reste étant des zéros. De même MIN contiendra des 1 aux positions correspondant dans A à un minimum sur une colonne, le reste étant des zéros. Il suffira alors de comparer ces matrices : les positions contenant un 1 dans les deux matrices à la fois seront celles des points-cols dans A.

Dans l’exemple précédent les matrices MAX et MIN seront :

        0  1  0  1            0  1  0  1
        1  0  0  0            0  0  0  0
MAX  =  0  1  0  0    MIN  =  0  0  0  0
        0  1  0  1            1  1  1  1
        1  0  0  0            0  0  0  0

Les positions où il y a un 1 à la fois dans MAX et dans MIN sont celles des 4 points-cols de A.

Commençons par écrire une solution en utilisant la méthode donnée dans l’énoncé :

#include <stdio.h>

void lire_matrice(int li, int co, double m[li][co])
{
    for (int i=0 ; i<li ; ++i)
        for (int j=0 ; j<co ; ++j)
            scanf("%lf", &m[i][j]);
}

void ecrire_matrice(int li, int co, double m[li][co])
{
    printf(" /  %*s", co*7, "\\\n");
    for (int i=0 ; i<li ; ++i) {
        printf("|  ");
        for (int j=0 ; j<co ; ++j)
            printf("%-6g ", m[i][j]);
        puts("|");
    }
    printf(" \\  %*s", co*7, "/\n");
}
    

/* prend en entrée une matrice a et le numéro d'une ligne de a
 * et renvoie la valeur maximum dans cette ligne
 */ 
double max_li(int li, int co, double a[li][co], int ligne)
{
    double max = a[ligne][0];
    for (int j=1 ; j<co ; ++j)
        if (max < a[ligne][j])
            max = a[ligne][j];
    return max;
}

/* prend en entrée une matrice a et le numéro d'une colonne de a
 * et renvoie la valeur minimum dans cette colonne
 */ 
double min_co(int li, int co, double a[li][co], int colonne)
{
    double min = a[0][colonne];
    for (int i=1 ; i<li ; ++i)
        if (min > a[i][colonne])
            min = a[i][colonne];
    return min;
}

/* cherche et affiche les points cols de la matrice
 * passée en paramètre
 */
void affich_pts_cols(int li, int co, double a[li][co])
{
    double max[li][co];
    for (int i=0 ; i<li ; ++i) {
        double maxl = max_li(li, co, a, i);
        for (int j=0 ; j<co ; ++j)
            max[i][j] = (a[i][j] == maxl);
    }
    printf("Matrice d'aide MAX(%d,%d) :\n", li, co);
    ecrire_matrice(li, co, max);  // pas demandé dans l'énoncé
    double min[li][co];
    for (int j=0 ; j<co ; ++j) {
        double minc = min_co(li, co, a, j);
        for (int i=0 ; i<li ; ++i)
            min[i][j] = (a[i][j] == minc);
    }
    printf("Matrice d'aide MIN(%d,%d) :\n", li, co);
    ecrire_matrice(li, co, min);  // pas demandé dans l'énoncé
    puts("Points-cols trouvés :");
    int nb_pts_cols = 0;
    for (int i=0 ; i<li ; ++i)
        for (int j=0 ; j<co ; ++j)
            if (max[i][j] && min[i][j]) {
                printf("\ta[%d][%d] = %g\n", i, j, a[i][j]);
                ++nb_pts_cols;
            }
    if (!nb_pts_cols)
        puts(" -- Aucun --");
}

int main(void)
{
    int li, co;
    puts("Matrice A :");
    printf("Nombre de lignes ? ");
    scanf("%d", &li);
    printf("Nombre de colonnes ? ");
    scanf("%d", &co);
    double a[li][co];
    puts("Tapez les éléments de la matrice séparés par des espaces :");
    lire_matrice(li, co, a);
    printf("\nMatrice A(%d,%d) :\n",li,co);
    ecrire_matrice(li, co, a);
    puts("\nRecherche des points-cols de A :");
    affich_pts_cols(li, co, a);
    return 0;
}

Encore une fois, dans cet exercice j’ai profité de la disponibilité des tableaux à longueur variable (VLA) dans la grande majorité des compilateurs actuels. Ne pas oublier seulement dans les paramètres des fonctions de mettre les dimensions des tableaux avant les tableaux (et bien sûr dans main() de déclarer les tableaux après avoir lu leurs dimensions).

L’algorithme est assez simple. La construction de la matrice d’aide MAX se fait avec la boucle for en ligne 53 : pour chaque ligne i, le maximum est cherché et mis dans la variable maxl. Comme il peut se trouver en plusieurs exemplaires dans la ligne, on doit reparcourir celle-ci avec la boucle de la ligne 55. On met alors dans la case correspondante de MAX la valeur 1 quand on le trouve et 0 quand on ne le trouve pas. Ce qui revient à la valeur de l’expression logique a[i][j] == maxl.

J’ai déclaré max et min comme des tableaux de double (réels) alors qu’ils ne contiennent que des 0 et des 1. C’est juste pour pouvoir afficher leur contenu avec la fonction ecrire_matrice(). Leur affichage n’étant pas demandé, on peut très bien mettre int.

J’ai écrit les fonctions max_li() et min_co() pour simplifier un peu l’algorithme. Sans max_li() par exemple, la boucle for de la ligne 53 serait ainsi :

    for (int i=0 ; i<li ; ++i) {
        double maxl = a[i][0];
        for (int j=1 ; j<co ; ++j)
            if (maxl < a[i][j])
                maxl = a[i][j];
        for (int j=0 ; j<co ; ++j)
            max[i][j] = (a[i][j] == maxl);
    }

(Cela revient donc juste à déplacer une boucle for)

Après avoir procédé de la même manière pour la construction de la matrice d’aide MIN, il ne reste plus qu’à comparer MIN et MAX en les parcourant avec deux boucles for imbriquées (lignes 70-75) dans lesquelles on affiche la position et la valeur de Aij à chaque fois que MINij = MAXij = 1, c’est à dire à chaque fois que la valeur de l’expression logique (max[i][j] && min[i][j]) est 1 (vrai). (C’est plus court que (max[i][j] == 1 && min[i][j] == 1))

Autres solutions

D’abord, il est possible de simplifier la solution précédente en ne créant que la matrice d’aide MIN (qui nécessite de parcourir les colonnes), puis parcourir les lignes non pas pour créer une matrice MAX, mais pour voir directement si les positions où se trouvent la valeur maximum correspondent à un 1 dans MIN. Si c’est le cas, c’est qu’on a trouvé un point-col et on peut donc l’afficher !

void affich_pts_cols(int li, int co, double a[li][co])
{
    int min[li][co];
    for (int j=0 ; j<co ; ++j) {
        double minc = min_co(li, co, a, j);
        for (int i=0 ; i<li ; ++i)
            min[i][j] = (a[i][j] == minc);
    }
    puts("Points-cols trouvés :");
    int nb_pts_cols = 0;
    for (int i=0 ; i<li ; ++i) {
        double maxl = max_li(li, co, a, i);
        for (int j=0 ; j<co ; ++j)
            if (a[i][j] == maxl && min[i][j]) {
                printf("\ta[%d][%d] = %g\n", i, j, a[i][j]);
                ++nb_pts_cols;
            }
    }
    if (!nb_pts_cols)
        puts(" -- Aucun --");
}

Une étudiante de 1re année MI nous a proposé en TD une solution très simple (bravo à elle !) qui emploie également des tableaux d’aide MIN et MAX mais à une dimension. MIN est rempli avec les valeurs minimums des colonnes de A (sa taille est donc le nombre de colonnes de A). MAX prend les valeurs maximums des lignes de A (sa taille est donc le nombre de lignes de A). Elle compare ensuite les valeurs de MIN et MAX et à chaque fois que MAXi = MINj, Aij est un point-col !

void affich_pts_cols(int li, int co, double a[li][co])
{
    double max[li];
    for (int i=0 ; i<li ; ++i)
        max[i] = max_li(li, co, a, i);
    double min[co];
    for (int j=0 ; j<co ; ++j)
        min[j] = min_co(li, co, a, j);
    puts("Points-cols trouvés :");
    int nb_pts_cols = 0;
    for (int i=0 ; i<li ; ++i)
        for (int j=0 ; j<co ; ++j)
            if (max[i] == min[j]) {
                printf("\ta[%d][%d] = %g\n", i, j, a[i][j]);
                ++nb_pts_cols;
            }
    if (!nb_pts_cols)
        puts(" -- Aucun --");
}

De la même manière que précédemment, on peut simplifier cette méthode en se passant du tableau max :

void affich_pts_cols(int li, int co, double a[li][co])
{
    double min[co];
    for (int j=0 ; j<co ; ++j)
        min[j] = min_co(li, co, a, j);
    puts("Points-cols trouvés :");
    int nb_pts_cols = 0;
    for (int i=0 ; i<li ; ++i){
        double max = max_li(li, co, a, i);
        for (int j=0 ; j<co ; ++j)
            if (max == min[j]) {
                printf("\ta[%d][%d] = %g\n", i, j, a[i][j]);
                ++nb_pts_cols;
            }
    }
    if (!nb_pts_cols)
        puts(" -- Aucun --");
}

Enfin, si l’on ne m’avait pas donné la méthode qui emploie les matrices d’aide dans l’énoncé, l’algorithme le plus intuitif aurait peut-être été celui que j’ai décrit au début de cet article (en bleu) et que j’ai appliqué (en vert) dans l’exemple. Il se traduit en C par les instructions suivantes :

void affich_pts_cols(int li, int co, double a[li][co])
{
    puts("Points-cols trouvés :");
    int nb_pts_cols = 0;
    for (int i=0 ; i<li ; ++i){
        double max = max_li(li, co, a, i);
        for (int j=0 ; j<co ; ++j)
            if (a[i][j] == max) {
                int est_min = a[i][j] <= a[0][j];
                for (int ii=1 ; est_min && ii<li ; ++ii)
                    est_min = a[i][j] <= a[ii][j];
                if (est_min) {
                    printf("\ta[%d][%d] = %g\n", i, j, a[i][j]);
                    ++nb_pts_cols;
                }
            }
    }
    if (!nb_pts_cols)
        puts(" -- Aucun --");
}

Voilà ! Vous voyez quand je vous disais qu’il y a souvent plusieurs solutions à un même problème ! Pourriez-vous dire quelle est la meilleure des solutions vues dans cet exercice ? En avez-vous une autre ? Vos commentaires sont les bienvenus comme d’habitude :-)

Publicités
One Comment
  1. zerga hadi permalink

    voici une autre méthode
    une fonction qui cherche et affiche les points cole.

    void point_cole(int lmax,int cmax,int t[lmax][cmax])
    {
    int i,j,b=0,e,l,r,m;
    for(i=0;i<lmax;i++){b=0;
    for(j=0;j<cmax;j++){e=1;
    for(l=0;l<cmax;l++ ){ if(t[i][b]<t[i][l]){ b=l; }}
    for(l=0;lt[l][b]){ e=0;}}
    if(e&&(r!=b||m!=i)) {printf( » t[%d][%d]=%d est un point cole \n »,i,b,t[i][b]); r=b;m=i;}
    b++;}
    }
    }

    J'aime

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s

%d blogueurs aiment cette page :