Le C en 20 heures

Le but de ce chapitre est de vous montrer quelques problèmes accompagnés de leur solution.

On apprend beaucoup de choses en lisant des programmes finis  ;-)

Voici un programme qui produit une petite table de conversion francs/euros.

Sélectionnez

#include <stdio.h> 
#define TAUX 6.55957
int main () {
   float francs;
   francs=0;
   while (francs<=10) {
      printf("%4.1f francs = %.2f euros\n",francs,francs/TAUX);
      francs=francs+0.5;
   }
   return 0;
}

L'exécution donnera :

Sélectionnez

0.0 francs = 0.00 euros
 0.5 francs = 0.08 euros
 1.0 francs = 0.15 euros
 1.5 francs = 0.23 euros
 2.0 francs = 0.30 euros
 2.5 francs = 0.38 euros
 3.0 francs = 0.46 euros
 3.5 francs = 0.53 euros
 4.0 francs = 0.61 euros
 4.5 francs = 0.69 euros
 5.0 francs = 0.76 euros
 5.5 francs = 0.84 euros
 6.0 francs = 0.91 euros
 6.5 francs = 0.99 euros
 7.0 francs = 1.07 euros
 7.5 francs = 1.14 euros
 8.0 francs = 1.22 euros
 8.5 francs = 1.30 euros
 9.0 francs = 1.37 euros
 9.5 francs = 1.45 euros
10.0 francs = 1.52 euros

Notez l'utilisation du format dans le printf :

%4.1f signifie : écrire en utilisant 4 caractères, dont 1 après la virgule exactement (si l'écriture du nombre nécessite moins de 4 caractères, l'affichage sera calé à droite).
%.2f signifie : écrire le nombre en affichant 2 chiffres après la virgule exactement.

Voici un programme dont le but est de générer 1000 nombres pseudo‐aléatoires et de compter combien sont pairs. En générant suffisamment de nombres, nous devrions nous rapprocher de 50%

Sélectionnez

#include <stdio.h> 
#include <stdlib.h>  /* pour le générateur pseudo-aléatoire */
#include <time.h> 
int main () {
   int nb_hasard=0;
   int i;
   
   int nb_pairs=0;   /*compte le nombre de nombres pairs */
   int nb_impairs=0; /*compte le nombre de nombre impairs */
   
   srand (time (NULL)); /*initialisation du générateur
         de nombres aléatoires à une valeur
         différente à chaque exécution */
   i=0;
   do {
      nb_hasard = rand ();
      if (nb_hasard % 2==0)  /* c'est un nombre pair */
         nb_pairs=nb_pairs+1;
      else
         nb_impairs=nb_impairs+1;
      i++;
   }
   while (i<1000);
   
   printf("Proportion de nombres pairs=%f\n",(float)nb_pairs/i);
   printf("Proportion de nombres impairs=%f\n",(float)nb_impairs/i);
   return 0;
}

Notez l'utilisation du cast dans les dernières lignes. Les deux variablesnb_pairset iétant entières, la division aurait été arrondie (toujours à 0 en l'occurrence). La conversion de type (float) est donc ici très importante.

Nous souhaitons obtenir la table de multiplication suivante :

Sélectionnez

 1   2   3   4   5   6   7   8   9  10
 2   4   6   8  10  12  14  16  18  20
 3   6   9  12  15  18  21  24  27  30
 4   8  12  16  20  24  28  32  36  40
 5  10  15  20  25  30  35  40  45  50
 6  12  18  24  30  36  42  48  54  60
 7  14  21  28  35  42  49  56  63  70
 8  16  24  32  40  48  56  64  72  80
 9  18  27  36  45  54  63  72  81  90
10  20  30  40  50  60  70  80  90 100

Voici le programme qui réalise cette tâche :

Sélectionnez

#include <stdio.h> 
int main () {
   int ligne, colonne;
   for (ligne=1;ligne<=10;ligne++) {
      for (colonne=1;colonne<=10;colonne++) {
         printf("%4d",ligne*colonne); /* affichage sur 4 caractères */
      }
      printf("\n");
   }
   return 0;
}

Voici un exemple de fonction qui renvoie le maximum d'un tableau qui lui est passé en paramètre. Voir le commentaire en dessous.

Sélectionnez

#include <stdio.h> 
int max_Tableau (int tab[], int taille);
int main() {
   int t1[] = {1,10,4,5,-7}, t2[] = {2,1,14,3};
   printf("Maximum de t1 : %d\n", max_Tableau(t1,5) );
   printf("Maximum de t2 : %d\n", max_Tableau(t2,4) );
   return 0;
}
int max_Tableau (int tab [], int taille) {
   int i,  max;
   for (i=1, max=tab[0]; i< taille; i++) {
      if (max<tab[i]) max=tab[i];
   }
   return max;
}

En fait, seule l'adresse de la 1re case du tableau est passée en paramètre à la fonction max_Tableau

La ligne qui suit le #include est la déclaration de la fonction max_Tableau. En effet, l'appel à la fonction (dans main) figure avant la définition de la fonction. Dans une telle situation, il est nécessaire d'annoncer au compilateur l'existence de la fonction en précisant le type de variables en paramètres, et le type de variable renvoyé.

Remarque préliminaire : Les deux programmes suivants ont des effets rigoureusement équivalents :

Sélectionnez

#include <stdio.h> 
#define TAILLE 10
int main () {
   int i,j;
   for (i=0, j=TAILLE-1 ; i<j ; i++,j--)
      printf("i=%d j=%d\n",i,j);
   return 0;
}

Sélectionnez

#include <stdio.h> 
#define TAILLE 10
int main () {
   int i,j;
   i=0;
   j=TAILLE-1;
   while (i<j) {
      printf("i=%d j=%d\n",i,j);
      i++, j--;
   }
   return 0;
}

Voici à présent un programme qui remplit un tableau de 10 cases par des valeurs saisies au clavier. Dans un second temps, le programme inverse l'ordre des éléments du tableau. Ainsi, si au départ nous avions les dix valeurs suivantes dans le tableau : 1, 2, 3, 4,5, 6, 7, 8, 9, 10 ; à l'arrivée, nous aurons le tableau suivant : 10, 9, 8, 7, 6, 5, 4, 3, 2, 1.

L'idée est d'échanger les éléments du tableau à l'aide de deux indices qui parcourent le tableau en commençant respectivement au début et à la fin du tableau et qui se rencontrent en son milieu. Tandis que l'indice i va démarrer au début du tableau, l'indice j va démarrer à la fin. Lorsque les indices se croisent, on arrête.

Dès que les programmes sont un peu longs, il est préférable de décomposer le problème sous forme de fonctions.

Sélectionnez

#include <stdio.h> 
#define TAILLE 10
/* Procédure permettant la saisie d'un tableau de taille n */
void saisie(int t[], int n){
   int i;
   for (i=0; i<n; i++) {
      printf("Elément %d: ", i+1);
      scanf("%d", &t[i]);
   }
}
/*Procédure affichant un tableau de taille n */
void affiche (int t[],int n) {
   int i;
   for (i=0; i<n; i++) {
      printf ("%d ", t[i]);
   }
   printf("\n");
}
/* Procédure inversant le tableau */
void miroir (int t[], int n) {
   int i,j; /* indices courants */
   int aide; /* pour l'échange */
   for (i=0, j=n-1 ; i<j ; i++, j--) {
      /* Echange de t[i] et t[j] */
      aide = t[i];
      t[i] = t[j];
      t[j] = aide;
   }
}
int main() {
   /* Déclarations */
   int tab[TAILLE]; /* tableau donné */
   saisie (tab,TAILLE);
   printf("Tableau donné : \n");
   affiche(tab,TAILLE);
   miroir(tab,TAILLE);
   printf("Tableau résultat:\n");
   affiche(tab,TAILLE);
   return 0;
}

Supposons que l'on dispose d'un tableau tab qui contient 10 valeurs. Nous souhaitons trier ce tableau. Une solution toute simple consiste à faire un passage sur le tableau et à comparer la case d'indice n avec celle d'indice n+1.

Si la case se trouvant à l'indice n contient une valeur plus grande que celle de l'indice n+1, alors on inverse les deux valeurs, et ainsi de suite. Voici un exemple sur un tableau de 10 cases :

Tableau initial :

Table 13.1 - Tri d'un tableau (1)
Indice de la case :	0	1	2	3	4	5	6	7	8	9
Valeur stockée :	12	10	4	5	6	7	8	9	10	1

On teste la case d'indice 0 et la case d'indice 1, si besoin est, on permute :

Table 13.2 - Tri d'un tableau (2)
0	1	2	3	4	5	6	7	8	9
10	12	4	5	6	7	8	9	10	1

On teste la case d'indice 1 et la case d'indice 2, si besoin est, on permute :

Table 13.3 - Tri d'un tableau (3)
0	1	2	3	4	5	6	7	8	9
10	4	12	5	6	7	8	9	10	1

…

Au bout d'un parcours complet du tableau, on obtient :

Table 13.4 - Tri d'un tableau (4)
0	1	2	3	4	5	6	7	8	9
10	4	5	6	7	8	9	10	1	12

Nous constatons que le tableau est « mieux » trié, mais ça n'est pas encore parfait. Dans le pire des cas (tableau trié dans l'ordre décroissant) n-1 passages seront nécessaires et suffisants pour trier un tableau de taille n.

Cette méthode de tri porte un nom, il s'agit du tri à bulles.

Voici l'ensemble des fonctions qui réalisent ce travail :

Sélectionnez

#include <stdio.h>
#define TAILLE 10
/******************************************/
void saisie(int t[], int n);
void affiche(int t[],int n);
void tri_tableau (int tab[], int taille);
/******************************************/
int main () {
   int tab[TAILLE];
   saisie(tab,TAILLE);
   tri_tableau(tab,TAILLE);
   printf("Voici votre tableau trié :\n");
   affiche(tab,TAILLE);
   return 0;
}
/* Procédure permettant la saisie d'un tableau de taille n */
void saisie(int t[], int n){
   int i;
   for (i=0; i<n; i++) {
      printf("Elément %d : ", i+1);
      scanf("%d",& t[i]);
   }
}
/* Procédure de tri */
void tri_tableau (int tab[], int taille) {
   int i,j;
   int temp;
   /* tri du tableau */
   for (i=0; i<taille-1; i++)
      for (j=0; j<taille-1; j++)
         if (tab[j]>tab[j+1]) { /* échange de valeurs */
            temp=tab[j];
            tab[j]=tab[j+1];
            tab[j+1]=temp;
         }
}
/* Procédure affichant un tableau de taille n */
void affiche(int t[],int n){
   int i;
   for (i=0; i<n; i++) {
      printf("%d ", t[i]);
   }
   printf("\n");
}

Il est important d'avoir bien tout compris dans ce programme…

Notez que dans ce programme, nous avons repris des fonctions qui avaient été écrites pour un autre problème (saisie et affiche écrites pour le programme qui affiche un tableau à l'envers). Un programmeur aime beaucoup réutiliser le travail qu'il a déjà fait. Les fonctions servent en partie à cela : à être réutilisables. Rares sont les programmeurs qui n'ont pas leur boîte à outils de fonctions avec eux !
Par ailleurs, le programme de tri peut être amélioré. En effet, dans notre programme, nous effectuons toujours n‐1 passages, qui sont nécessaires pour trier dans le pire des cas. Parfois, le tableau peut être néanmoins trié en moins de passes. La boucle for extérieure pourra être avantageusement remplacée par une boucle while qui s'arrête si le tableau est effectivement trié (parce qu'il n'y a eu aucun échange de valeurs lors du dernier passage par exemple). Si ce dernier point vous paraît un peu compliqué, vous pourrez y revenir plus tard et y réfléchir à nouveau.

XIV-H-1. Historique▲

John Horton Conway est un mathématicien qui a exercé à l'Université de Cambridge puis a Princeton. Très prolifique en matière de jeux mathématiques, il décrivit en 1970 le jeu de la vie, visant à modéliser d'une façon simplifiée l'évolution d'organismes vivants.

XIV-H-2. Règles du jeu▲

Le jeu de la vie se joue normalement sur un damier infini. Chaque case est occupée par une cellule qui peut être vivante ou morte. À chaque génération, chaque cellule peut naître, mourir, ou rester dans son état. Les règles qui permettent de passer d'une génération à l'autre sont précises et ont été choisies avec soin pour que l'évolution des organismes soit intéressante et semble imprévisible. En premier lieu, notons que sur un damier infini, chaque case a exactement huit voisins (si on considère aussi les voisins par une diagonale(24)). Les règles du jeu de la vie sont les suivantes :

une cellule vivante ayant exactement 2 ou 3 voisins vivants survit à la génération suivante.
une cellule vivante ayant de 4 à 8 cellules voisines vivantes meurt d'étouffement à la génération suivante.
une cellule vivante ayant zéro ou une cellule voisine vivante meurt d'isolement à la génération suivante.
sur une case vide ayant exactement 3 voisins vivants, une cellule naîtra à la génération suivante.

Notons que c'est l'ensemble de la génération actuelle qui doit être pris en compte pour l'établissement de l'état des cellules à la génération suivante.

Voici un exemple de figure sur un petit damier. Les cellules qui devront mourir à la génération suivante sont grisées (cette figure porte un nom, il s'agit d'un planeur) :

Image non disponible — Figure 13.1 - Générations (le jeu de la vie)

XIV-H-3. Images obtenues▲

Si nous faisions une version graphique, voici ce que nous pourrions obtenir (figures 13.2 à 13.3) :

Certaines configurations réapparaissent spontanément sur un damier initialement aléatoire, comme les planeurs mentionnés ci‐dessus. Des centaines de figures sont ainsi recensées pour leur « comportement » plus ou moins remarquable (le lecteur intéressé pourra faire des recherches très fructueuses sur Internet).

XIV-H-4. Proposition de programme▲

Nous allons considérer que toutes les cellules sont stockées dans une matrice (notre damier ne sera donc pas infini). Pour une case m[i][j], les huit voisins sont :

Sélectionnez

m[i-1][j], m[i+1][j], m[i][j-1], m[i][j+1]
m[i-1][j-1], m[i+1][j+1], m[i+1][j-1], m[i-1][j+1]

Pour éviter les problèmes qui se posent au bord de la matrice(25) nous ne considérerons comme faisant partie du jeu que les cellules qui ne sont pas sur la couronne extérieure de la matrice (voir figure suivante) :

Nous considérerons que la couronne extérieure (grisée sur l'image) est constituée de cellules mortes qui ne sont pas mises à jour.

On se propose de découper le programme de la façon suivante (lisez ce programme, qui n'est pas encore complet, ainsi que les explications ci‐dessous) :

Sélectionnez

/**************************************
            JEU DE LA VIE
****************************************/
#include <stdio.h> 
#include <stdlib.h> 
#define TAILLE_SOUS_MATRICE 7
#define TAILLE_SUR_MATRICE  9
/* Taille de la matrice contenant */
/* les cellules + 2 pour la bordure */
/****************************************/
/*******   P R O T O T Y P E S   ********/
/****************************************/
/* Initialisation de la matrice de départ */
void init(int matrice [][TAILLE_SUR_MATRICE ]);
/* Indique pour la cellule de coordonnées (ligne,colonne) */
/* le nombre de cellules voisines vivantes */
int nombre_voisins (int matrice [][TAILLE_SUR_MATRICE], int ligne, int colonne);
/* Réalise une étape de plus dans la mise à jour de la matrice: */
/* autrement dit, on réalise un cycle de vie */
void mise_a_jour(int matrice[][TAILLE_SUR_MATRICE]);
/* Affichage de la matrice en cours */
void affiche_matrice(int matrice [][TAILLE_SUR_MATRICE]);
/****************************************/
/*******   F O N C T I O N S   **********/
/****************************************/
int main() {
   int i;
   int nbr_cycles;
   int matrice[TAILLE_SUR_MATRICE] [TAILLE_SUR_MATRICE ];
}
void init(int matrice [][TAILLE_SUR_MATRICE]) { ... }
void mise_a_jour(int matrice[][TAILLE_SUR_MATRICE]) {
   int matrice_densite[TAILLE_SOUS_MATRICE][ TAILLE_SOUS_MATRICE];
...
}

Lisons le prototype de la fonction init :

Sélectionnez

void init(int matrice[] [TAILLE_SUR_MATRICE]);

Il aurait été possible d'écrire :

Sélectionnez

void init(int matrice[TAILLE_SUR_MATRICE] [TAILLE_SUR_MATRICE]);

Nous pourrions penser à tort que la fonction reçoit la matrice TAILLE_SUR_MATRICE*TAILLE_SUR_MATRICE en entrée et qu'à la sortie elle ne sera pas modifiée (passage des paramètres par valeur). Dès lors, la fonction init ne servirait à rien.
En fait, c'est l'adresse mémoire de la matrice (&matrice[0][0]) qui est passée à la fonction init. C'est donc un passage par adresse qui est effectué.
La fonction ne pourra effectivement pas modifier l'adresse de matrice[0][0] mais, en revanche, pourra modifier les contenus de matrice[0][0], matrice[1][0]…

Avant de voir la correction complète de cet exercice, on notera que lors d'un cycle de vie, on ne doit pas modifier la matrice de vie courante au fur et à mesure, elle doit être modifiée d'un coup. Il est donc nécessaire de passer par 2 étapes :

construire une matrice intermédiaire qui contient par exemple le nombre de voisins pour chaque cellule.
parcourir cette matrice en une passe et modifier la matrice contenant les cellules vivantes.

Voici donc le programme complet :

Sélectionnez

/***************************************
            JEU DE LA VIE
***************************************/
#include <stdio.h> 
#include <stdlib.h> 
#define TAILLE_SOUS_MATRICE 7
/* On peut avoir 7 * 7 cellules vivantes */
#define TAILLE_SUR_MATRICE  9
/* On place une bordure autour qui facilite la vie du programmeur... */
/***************** PROTOTYPES ***********************/
void init(int matrice [][TAILLE_SUR_MATRICE ]);
int nombre_voisins (int matrice [][TAILLE_SUR_MATRICE ],
                    int ligne, int colonne);
void mise_a_jour(int matrice[][TAILLE_SUR_MATRICE ]);
void affiche_matrice(int matrice [][TAILLE_SUR_MATRICE ]);
void ligne(int largeur);
/*****************************************************/
int main( ) {
   int i;
   int nbr_cycles;
   int matrice[TAILLE_SUR_MATRICE] [TAILLE_SUR_MATRICE ];
   char s[2];
   printf("Nombre de cycles : ");
   scanf("%i",&nbr_cycles);
   init(matrice);
   printf("La population au départ : \n");
   affiche_matrice(matrice);
   printf("Pressez sur ENTER pour continuer...\n");
   gets(s);
   for(i=0; i<nbr_cycles; i++) {
      mise_a_jour (matrice);
      printf("La population après %d cycles: \n", i+1);
      affiche_matrice (matrice);
      printf("Pressez sur ENTER pour continuer...\n");
      gets(s);
   }
   return 0;
}

Sélectionnez

/****************************************/
/* Initialisation de la matrice */
void init(int matrice [][TAILLE_SUR_MATRICE ]) {
/****************************************/
   int i,j;
   for(i=0; i<TAILLE_SUR_MATRICE ; i++) {
      for(j=0; j<TAILLE_SUR_MATRICE ; j++) {
         if (i<=j && i>0 && j<=7)
            matrice[i][j]=1;
         else
            matrice[i][j]=0; 
      }
   }
   /* On pourrait aussi faire une initialisation aléatoire */
}
/****************************************/
/* Calcul du nombre de voisins vivants */
int nombre_voisins (int matrice[][TAILLE_SUR_MATRICE ],
                    int ligne, int colonne) {
/****************************************/
   int compte=0; /* compteur de cellules */
   int i,j;
/* On additionne les 9 cellules centrées en ligne,colonne */
   for (i=ligne-1;i<=ligne+1;i++)
      for(j=colonne-1;j<=colonne+1;j++)
         compte=compte+matrice[i][j];
 
         /* Puis on retire celle du milieu... */
         compte -= matrice[ligne][colonne];
         return compte;
}
/****************************************/
/* Correspond à l'étape n+1 */
void mise_a_jour(int matrice[ ][TAILLE_SUR_MATRICE ]) {
/****************************************/
   int i,j;
   int nbr_voisins;
   int matrice_densite[TAILLE_SOUS_MATRICE][TAILLE_SOUS_MATRICE];
   /* matrice qui comptabilise le nombre de voisins */
   /* et cela, case par case */
   for(i=0; i< TAILLE_SOUS_MATRICE; i++)
         for(j=0; j< TAILLE_SOUS_MATRICE; j++)
            matrice_densite[i][j]=nombre_voisins(matrice,i+1,j+1);
      /* i+1 et j+1 car on passe de la SOUS_MATRICE à la MATRICE   */
   
   for(i=0; i< TAILLE_SOUS_MATRICE; i++)
      for(j=0; j< TAILLE_SOUS_MATRICE; j++) {
            nbr_voisins=matrice_densite[i][j];
            if(nbr_voisins==2)
                  matrice[i+1][j+1]=1;
            else if (nbr_voisins==0 || nbr_voisins==4)
                  matrice[i+1][j+1]=0;
   }
}

Sélectionnez

/****************************************/
/* Affichage à l'écran des cellules vivantes */
void affiche_matrice(int matrice[ ][TAILLE_SUR_MATRICE ]) {
/****************************************/
   int i,j;
   for(i=1; i<=TAILLE_SOUS_MATRICE; i++) {
      ligne(7);
      for(j=1; j<= TAILLE_SOUS_MATRICE; j++)
         if (matrice[i][j]==1)
            printf("|%c",'*');
         else
            printf("|%c",'|');
      printf("|\n");
   }
   ligne(TAILLE_SOUS_MATRICE);
}
/****************************************/
/* Tracé d'une ligne */
void ligne(int largeur) {
/****************************************/
   int i;
   for(i=0; i<largeur; i++)
      printf("+-");
   printf("+\n");
}

L'exécution de ce programme en mode non‐graphique est un peu frustrante. L'adaptation nécessaire pour dessiner réellement les cellules à l'écran est cependant assez simple (fondamentalement, il faut uniquement modifier la procédure affiche_matrice pour obtenir un affichage différent).

Le C en 20 heures

XIV. Quelques exemples de programmes▲

XIV-A. Objectifs▲

XIV-B. Convertisseur francs/euros▲

XIV-C. Proportion de nombres pairs et impairs▲

XIV-D. Affichage d'une table de multiplication▲

XIV-E. Maximum d'un tableau▲

XIV-F. Inverser les éléments d'un tableau▲

XIV-G. Tri d'un tableau▲

XIV-H. Jeu de la vie▲

XIV-H-1. Historique▲

XIV-H-2. Règles du jeu▲

XIV-H-3. Images obtenues▲

XIV-H-4. Proposition de programme▲