Tableaux | Exercices 6-10

Enoncé exercice 6

Ecrire un programme C qui lit un tableau de taille nxm, et cherche tous les points-col qui s’y trouvent.

Un point-col est un élément qui est max sa ligne et min sur sa colonne.

Correction exercice 6

On demande à l’utilisateur d’entrer la taille (n,m) du tableau t. On lit ensuite ses éléments. Et en parallèle on initialise les deux tableaux min et max qui ont la même taille que t par des zéros.

La démarche pour trouver tous les points-col est très simple, on cherche tous les éléments qui sont des maximums sur leurs lignes, on les marque ensuite en affectant la valeur 1 à la position qui leur correspond dans le tableau max (lignes 18-27). De la même façon on marque tous les éléments qui sont des minimums sur leurs colonnes dans le tableau min (lignes 28-35).

La deuxième et dernière étape de cette démarche consiste à chercher dans les deux tableaux min et max une position qui a la valeur 1 sur les deux tableaux, cette valeur de 1 dans les deux tableaux reflète le fait que l’élément dans cette position est max sur sa ligne et min sur sa colonne, cette position représente donc un point-col.

Solution exercice 6
#include<stdio.h>
#include<stdlib.h>
int main()
{
   int t[100][100],min[100][100],max[100][100];
   int i,j,k,n,m;
   int MAX,MIN;
   printf("Donnez le nombre de lignes et de colonnes:\n");
   scanf("%d%d",&n,&m);
   printf("Entrez les element du tableau:\n");
   for(i=0;i<n;i++)
      for(j=0;j<m;j++)
      {
         scanf("%d",&t[i][j]);
         min[i][j]=0;
         max[i][j]=0;
      }
   for(i=0;i<n;i++)
   {
      MAX=t[i][0];
      for(j=1;j<m;j++)
      {
         if(MAX<t[i][j]) MAX=t[i][j];
      }
      for(k=0;k<m;k++)
         if(t[i][k]==MAX) max[i][k]=1;
   }
   for(j=0;j<m;j++)
   {
      MIN=t[0][j];
      for(i=1;i<n;i++)
         if(MIN>t[i][j]) MIN=t[i][j];
      for(k=0;k<n;k++)
         if(t[k][j]==MIN) min[k][j]=1;
   }
   for(i=0;i<n;i++)
      for(j=0;j<m;j++)
      {
         if(min[i][j]==1 && max[i][j]==1)
            printf("La position (%d,%d) est un point-col.\n",i,j);
      }
   system("pause");
   return 0;
}
Enoncé exercice 7

Ecrire un programme C qui lit une position (i,j) d’un tableau 8×8, rempli par des zéros. Et marque toutes les cases des deux diagonales qui passent par cette position en y mettant des uns.

Correction exercice 7

On déclare un tableau t de dimension 8×8, et deux variables entières a et b pour abriter la position que va entrer l’utilisateur. On initialise ensuite le tableau t avec des zéros (lignes 8-10). On demande après à l’utilisateur d’entrer des valeurs pour a et b (lignes 11-12).

Le but donc et de mettre à 1 toutes les cases qui appartiennent aux deux diagonales qui passent par la position (a,b). Pour ce faire, on va diviser la tâche en quatre morceaux:

1-La demie diagonale qui part de (a,b) à gauche en haut (lignes 13-20): pour pouvoir mettre à 1 les cases qui se trouvent sur cette demi diagonale, il faudra savoir trois choses: par quelle case on va commencer, comment on va se déplacer d’une case à l’autre et quand est ce qu’on va s’arrêter.

La case de départ sera la case (a,b) (lignes 13-14).

Pour se déplacer d’une case à l’autre on peut remarquer qu’il suffit de décrémenter par un l’indice des lignes (ligne 18) et aussi par un celui des colonnes (ligne 19).

La condition d’arrêt est soit toucher le bord gauche (i==0) ou celui d’en haut (j==0). Donc la boucle while doit itérer tant que les deux indices sont supérieurs ou égaux à zéro (ligne 15).

2-La demi diagonale qui part de (a,b) à droite en bas (lignes 21-28): La case de départ est toujours (a,b), le déplacement sera en incrémentant les deux indices, et on continue jusqu’à ce qu’un des bords de droite ou d’en bas soit atteint.

3-La demi diagonale qui part de (a,b) à droite en haut (lignes 29-36): La case de départ est toujours (a,b), le déplacement se fera en incrémentant l’indice j et en décrémentant i, et on continue jusqu’à ce qu’un des bords de droite ou d’en haut soit atteint.

4-La demi diagonale qui part de (a,b) à gauche en bas (lignes 37-44): La case de départ est toujours (a,b), le déplacement sera en incrémentant l’indice i et en décrémentant j, et on continue jusqu’à ce qu’un des bords de gauche ou d’en bas soit atteint.

A chaque itération des quatre boucles on mit la case actuelle à 1. On affiche ensuite le tableau obtenu (lignes 45-50).

Solution exercice 7
#include<stdio.h>
#include<stdlib.h>
int main()
{
    int t[8][8];
    int i,j;
    int a,b;
    for(i=0;i<8;i++)
       for(j=0;j<8;j++)
          t[i][j]=0;
    printf("Entrez une position:\n");
    scanf("%d%d",&a,&b);
    i=a;
    j=b;
    while(i>=0 && j>=0)
    {
       t[i][j]=1;
       i--;
       j--;
    }
    i=a;
    j=b;
    while(i<8 && j<8)
    {
       t[i][j]=1;
       i++;
       j++;
    }
    i=a;
    j=b;
    while(i>=0 && j<8)
    {
       t[i][j]=1;
       i--;
       j++;
    }
    i=a;
    j=b;
    while(i<8 && j>=0)
    {
       t[i][j]=1;
       i++;
       j--;
    }
    for(i=0;i<8;i++)
    {
       for(j=0;j<8;j++)
       printf("%d ",t[i][j]);
       printf("\n");
    }
    system("pause");
    return 0;
}
Enoncé exercice 8

Ecrire un programme C qui lit un tableau nxn, et vérifie s’il est magique ou non. Un tableau est dit magique, si la somme des éléments de chaque ligne, de chaque colonne et de chaque une des deux diagonales est la même. En plus il doit contenir tous les entiers entre 1 et n2.
L’exemple suivant montre un carré magique de dimension 3×3 :

Correction exercice 8

Dans cet exercice on va écrire un programme C qui détermine si un tableau à deux dimensions de taille nxn est un carré magique ou non. Ceci revient à vérifier deux conditions. La première est que les sommes des éléments de chaque ligne, de chaque colonne et des deux diagonales doivent être égales. La deuxième est que ce tableau doit contenir tous les entiers entre 1 et n2.

La solution présentée dans cet exercice introduit deux techniques pour vérifier ces deux conditions avec un minimum de code.

Après la lecture du tableau t, on enchaînera par la vérification de la première condition. Comme première étape, on va calculer la somme des éléments de la diagonale principale et on va la mettre dans la variable som_mag (ligne 15). Donc, pour que t soit un tableau magique le reste des sommes à calculer doivent nécessairement être égales à som_mag.

La première des techniques mentionnées en haut consiste à parcourir les lignes et les colonnes en parallèle. En effet, à l’intérieur d’une boucle for de compteur i, allant de zéro jusqu’à n-1 on va utiliser deux boucles for de même compteur j. Où la première va servir au parcours de la ligne d’indice i, en accédant à ses éléments par t[i][j]. Et la deuxième sera réservée au parcour

s de la colonne i en indiquant i comme indice de colonne et j comme indice de ligne (lignes 16-24).

Le parcours de ces lignes et ces colonnes a pour objectif le calcul de leur somme. Et une fois la somme d’une ligne ou d’une colonne est calculée, on la compare alors avec la valeur de som_mag. Si elles sont différentes le tableau ne peut plus être magique. On l’indique en affectant zéro à la variable entière mag qui a été initialisée au départ par 1. On sort à ce moment de la boucle for de compteur i en utilisant l’instruction break (lignes 20 et 23).

Il ne faut pas oublier de mettre à zéro la variable s, utilisée pour le calcul des sommes, avant l’entrée dans chaque une des deux boucles de compteur j (lignes 18 et 21).

Après le calcul des sommes des éléments des lignes, des colonnes et de la diagonale principale on passera ensuite à la deuxième diagonale. Pour cet effet, on va utiliser une seule boucle for de compteur i allant de 0 à n-1 à l’intérieur de laquelle on peut accéder aux éléments de la diagonale en utilisant i comme indice de ligne et n-1-i comme indice de colonne.

La variable mag est initialisée à sa déclaration par 1 pour supposer que le tableau t est un carré magique. Et si sa valeur change vers zéro, au cours de la vérification de la première condition, ça veut dire que cette supposition est fausse et qu’il n’est pas nécessaire de vérifier la deuxième condition. Dans l’autre cas où mag est toujours égale à 1 le tableau a toujours toutes les chances d’être un carré magique et on passera pour voir si tous les entiers entre 1 et n2 sont présents dans ce dernier.

Cette condition ne sera pas vraie si un entier n’appartenant pas à l’intervalle précité est rencontré dans t, ou si un entier y apparaisse plus qu’une fois. La première tranche de la condition est simple à vérifier et pour la deuxième on va utiliser un tableau v à une dimension, initialisé par des zéros (ligne 30). Et lors du parcours du tableau t, on affecte une valeur de 1 à la case de v correspondante à l’indice égale à la valeur t[i][j] pour dire que cet entier existe dans le tableau. Mais avant de faire cette affectation on doit voir si la case à cet indice n’est pas déjà égale à 1. Chose qui indiquera que cet élément apparaisse deux fois au moins dans t (lignes 34-35). Dans ce cas t ne peut pas être magique, et on mit à zéro la variable mag, puis on quitte les deux boucles avec deux instructions break (lignes 34 et 36).

A la fin du programme on fait un test sur la valeur de la variable mag et on affiche le message adéquat.

Solution exercice 8
#include<stdio.h>
#include<stdlib.h>
int main()
{
    int t[15][15],v[300];
    int i,j,n,som_mag,s;
    int mag=1;
    printf("Donnez la dimension du carre:\n");
    scanf("%d",&n);
    printf("Entrez les elements du carre:\n");
    for(i=0;i<n;i++)
       for(j=0;j<n;j++)
          scanf("%d",&t[i][j]);
    som_mag=0;
    for(i=0;i<n;i++) som_mag+=t[i][i];
    for(i=0;i<n;i++)
    {
       s=0;
       for(j=0;j<n;j++) s+=t[i][j];
       if(s!=som_mag){ mag=0; break;}
       s=0;
       for(j=0;j<n;j++) s+=t[j][i];
       if(s!=som_mag){ mag=0; break;}
    }
    s=0;
    for(i=0;i<n;i++) s+=t[i][n-i-1];
    if(s!=som_mag) mag=0;
    if(mag==1)
    {
        for(i=1;i<=n*n;i++) v[i]=0;
        for(i=0;i<n;i++)
        {
           for(j=0;j<n;j++)
              if(v[t[i][j]]==1 || t[i][j]>n*n || t[i][j]<1){ mag=0; break; }
              else v[t[i][j]]=1;
           if(mag==0) break;
        }
    }
    if(mag==1) printf("Le tableau est un carre magique.\n");
    else printf("Le tableau n'est pas un carre magique.\n");
    system("pause");
    return 0;
}
Enoncé exercice 9

Ecrire un programme C qui lit les dimensions n et m d’un tableau à deux dimensions, le remplit d’une manière spirale en utilisant les entiers de l’intervalle 1 à n*m comme indiqué sur le tableau ci-dessous:

Correction exercice 9

Dans cet exercice il est demandé de remplir un tableau à deux dimensions d’une manière spirale. La première différence avec le remplissage courant, ligne par ligne, est que ici on doit commencer par varier le compteur des colonnes et garder celui des ligne fixe puis varier celui des lignes et fixer celui des colonne et ce, d’une manière alternative. Et la deuxième différence, se situe au niveau des bornes de variations de ces deux compteurs qui ne sont pas fixes.

Il est évident qu’on ne peut pas consacrer à chaque ligne ou à chaque colonne sa propre boucle, vu leur nombre important d’une part, et les dimensions du tableau qui ne sont pas connues d’une autre. Pour ces raisons, il faudra dans un premier temps trouver un motif répétitif qui constitue la spirale. Puis déterminer la façon adéquate pour le parcourir, ainsi que la méthode de transition entre les différentes parties de la spirale obtenues en subdivisant le tableau selon le motif choisi.

Dans cette solution on a considéré que la spirale est constituée selon un motif sous forme d’un circuit rectangulaire. L’image suivante montre la subdivision d’un tableau de taille 10×10 en cinq circuits d’après le motif adopté:

Ce motif peut être parcouru en utilisant quatre boucles for dont on doit déterminer les bornes des compteurs. Pour ceci on va isoler un circuit rectangulaire ayant son point de départ situé dans une ligne d’indice a (cette ligne de départ est différente d’un circuit à l’autre). Si n et m sont respectivement le nombre de lignes et celui des colonnes, le circuit sera alors défini comme montré sur l’image ci-dessous:

Après la détermination des indices des deux lignes et des deux colonnes qui constituent un circuit donné. Son parcourt suivra alors les quatre étapes suivantes:

Etape 1: On va utiliser une boucle for pour la partie de la ligne d’indice a allant de la colonne d’indice a jusqu’à celle d’indice m-a-1 (indice de lignes fixe et celui de colonnes croissant) (ligne 15).

Etape 2: On va utiliser une deuxième boucle for pour la partie de la colonne d’indice m-a-1 située entre les deux lignes d’indice a et d’indice n-a-1 (indice de lignes croissant et celui de colonnes constant) (ligne 18).

Etape 3: On va utiliser une troisième boucle for pour la partie de la ligne d’indice n-a-1 située entre les deux colonnes d’indice a et d’indice m-a-1 (indice de lignes fixe et celui de colonnes décroissant) (ligne 21).

Etape 4: On va utiliser une quatrième boucle for pour la partie de la colonne d’indice a située entre les deux lignes d’indice a et d’indice n-a-1 (indice de lignes décroissant et celui de colonnes fixe) (ligne 24).

Pour parcourir tous les circuits constituants le tableau, on va utiliser une boucle while qui va englober les quatre boucles for précédentes, et qui va permettre à chaque itération l’incrémentation de la valeur de a, pour assurer le passage d’un circuit à l’autre.

Pour le remplissage des cases du tableau, on va utiliser une variable entière k qui va être incrémentée après chaque case remplie, en utilisant l’instruction t[i][j]=k++. On va donc atteindre la dernière case à remplir lorsque k atteint la valeur n*m. Ceci doit être vérifié seulement après la première et la troisième boucle for (simple à vérifier). Si cette condition est vérifiée on sort alors de la boucle while en utilisant l’instruction break. Il est même indispensable de vérifier cette condition directement après ces deux boucles pour éviter le remplissage d’une même ligne ou de la même colonne deux fois, chose qui peut se manifester dans le cas où l’une des deux dimensions du tableau est impaire et inférieure à l’autre dimension au moins par deux. Pour observer ce phénomène il faut supprimer les deux lignes qui contiennent l’instruction break et mettre la condition d’arrêt entre les deux parenthèses de la boucle while, puis essayer les valeurs 3×6 ou 8×5 comme dimensions du tableau). Puisque cette boucle while sera toujours quittée par le biais de l’une des deux instructions break, on n’aura donc pas besoin de définir une condition d’arrêt précise pour cette boucle. Et on peut tout simplement l’utiliser comme une boucle infinie, en lui donnant comme condition d’arrêt une expression qui est toujours vraie par “exemple 2 est supérieur à 0” (ligne 12).

A la fin on affiche le tableau en utilisant la méthode usuelle.

Solution exercice 9
#include<stdio.h>
#include<stdlib.h>
int main()
{
    int t[15][15];
    int i,j,k,n,m;
    int a;
    printf("Entrez les dimensions du tableau:\n");
    scanf("%d%d",&n,&m);
    k=1;
    a=0;
    while(2>0)
    {
       i=a;
       for(j=a;j<=m-a-1;j++) t[i][j]=k++;
       if(k>n*m) break;
       j=m-a-1;
       for(i=a+1;i<=n-a-2;i++) t[i][j]=k++;
       i=n-a-1;
       for(j=m-a-1;j>=a;j--) t[i][j]=k++;
       if(k>n*m) break;
       j=a;
       for(i=n-a-2;i>=a+1;i--) t[i][j]=k++;
       a++;
    }
    for(i=0;i<n;i++)
    {
       for(j=0;j<m;j++)
          printf("%4d",t[i][j]);
       printf("\n");
    }
    system("pause");
    return 0;
}
Enoncé exercice 10

Ecrire un programme C qui lit un tableau d’entiers à une dimension puis affiche les trous et les bosses qu’il contient.

Un trou est la position d’un entier situé entre deux nombres qui lui sont strictement supérieurs. Et s’ils lui sont strictement inférieurs, on appelle cette position bosse.

Correction exercice 10

Après la lecture du nombre des éléments du tableau vers la variable n, et la lecture de ces n éléments vers le tableau t à l’aide d’une boucle for, on passera directement à la recherche des trous et des bosses du tableau.

D’après les deux définitions, on peut tirer que la première et la dernière case du tableau ne peuvent pas contenir un trou ou une bosse. C’est pourquoi on va parcourir le tableau t seulement à partir de la case d’indice 1, et on s’arrêtant avant la case d’indice n-1 (ligne 12).

Pour chaque élément t[i], on va dans un premier temps utiliser un test simple pour voir s’il est inférieur aux deux éléments qui le côtoient. A savoir le t[i-1] et le t[i+1]. Dans l’affirmative, on affiche qu’on a un trou dans cette position (lignes 14-15).

D’une manière similaire, on va vérifier si cet élément est supérieur à ses deux voisins pour pouvoir indiquer sa position comme étant une bosse (lignes 16-17).

Solution exercice 10
#include<stdio.h>
#include<stdlib.h>
int main()
{
    int t[100];
    int i,n;
    printf("Entrez le nombre d'elements: ");
    scanf("%d",&n);
    printf("Entrez les elements du tableau;\n");
    for(i=0;i<n;i++)
       scanf("%d",&t[i]);
    for(i=1;i<n-1;i++)
    {
       if(t[i]<t[i-1] && t[i]<t[i+1])
          printf("La position %d est un trou.\n",i);
       if(t[i]>t[i-1] && t[i]>t[i+1])
          printf("La position %d est une bosse.\n",i);
    }
    system("pause");
    return 0;
}