Testing can show the presense of bugs, but not their absence.[0]
-- Edger W. Dijkstra

• 0. Introduction
• 1. Blocs d'Instructions
• 2. La Conditionnelle if-else
• 3. Choix Multiple switch
• 4. Itérations while, for, do-while
  • 4.1. Boucle while
  • 4.2. Boucle for
  • 4.3. Boucle do...while
• 5. Les Ruptures de Contrôle
  • 5.1. Break
  • 5.2. Continue
  • 5.3. Return
  • 5.4. Goto goto <label>
• 6. Exemples d'Algorithmes Programmés en C
  

0. Introduction

Les structures de contrôle permettent de spécifier l'ordre d'exécution d'un calcul. C offre les structures de contrôle traditionnelles des langages, à savoir:

• le bloc ou la composition d'instructions,
• la conditionnelle qui est if-else,
• le choix entres cas multiples qui est switch-case,
• les itérations qui sont for, while et do-while,
• les ruptures de séquence break, continue et return,
• et le branchement goto (ne polémiquons pas).

1. Blocs d'Instructions

x = 0;        /* Instruction d'affectation  */
i++;          /* Incrémentation */
f(x, y);      /* Appel de fonction */

{
     w = a; 
     a = b; 
     b = w; 
}

Il n'y a donc pas le ; après }. On peut rajouter éventuellement des déclarations locales au bloc comme

où w n'a qu'une portée locale au bloc. Mais, ces déclarations locales doivent se trouver en début de bloc.

L'intérêt de l'instruction composée est évident : corps de fonctions, bloc if, while, for ..., car il n'y a pas de endif, endwhile, endfor ...

Dans tout ce qui suit, <instruction> sera l'une des formes suivantes:

• <expressions> ;
• /* bloc */
{
     <liste_déclarations_éventuelles>
     <liste_instructions>
}
• if ...
• switch ...
• while ...
• for ...
• do... while
• break ;
• continue ;
• goto label ;
• return ;
• return ( <expression> );

2. La Conditionnelle if-else

En C, on retrouve l'instruction conditionnelle avec la signification classique. Attention Il n'y a pas le mot then.

La partie else est bien sûr optionnelle. Remarquer la présence obligatoire des parenthèses de l'expression de test.

L'expression est évaluée et si elle est différente de zéro (c'est la condition vraie) la partie <instruction_1> est exécutée. Sinon, l'expression donne zéro (condition fausse), la partie <instruction_2> est exécutée si elle est présente.

Exemples:

• if ( n != 0)
     moyenne = somme / n;

• if ( n )
    moyenne = somme / n;
else
     printf("Je refuse de diviser par zero\n");

• if ( delta >= 0 ) {
    x1 = (-b - sqrt(delta))/(2*a) ;
    x2 = (-b + sqrt(delta))/(2*a) ;
}
else
     printf(" Autres racines \n ");

Remarquer l'usage d'un bloc {} dans la partie vraie de if qui contient plusieurs instructions.

Attention à l'ambiguïté du else (source d'erreur!)

Ici, le else se rapporte au deuxième if, le plus interne, comme l'illustre l'indentation. Pour le rapporter au premier if, il faut utiliser les accolades {} qui mettent le deuxième if dans un bloc.

Une autre bonne habitude consisterait à mettre systématiquement un else, suivi de «;», même s'il est sans instructions.

if (n > 0)
      if (a > b)
            z = a;
      else ;
else
      z = b;

Par ailleurs, pour séparer la partie else qui contient plusieurs instructions de la suite du programme, on utilisera aussi un bloc.

if (...)
    ...
else {
    ...
}
...


if en cascade

C'est une série de tests. Il est commode de les écrire comme

if (...)
   ...
else if (...)
   ...
else if (...)
   ...
else if (...)
.
.
.
else
   ...

3. Choix Multiple switch

Le switch, correspondant de CASE de PASCAL, permet d'évaluer une expression entière (ou caractère convertie en entier) et selon la valeur du résultat exécuter une partie donnée du programme.

switch ( <expresionEntière> ) {
       case <constanteEntière_1> : <choix_1>
       case <constanteEntière_2> : <choix_2>
       ...
       case <constanteEntière_n> : <choix_n>
     [ default : <choix_autre> ]
}

Chaque choix est vide, ou est de la forme <instruction> suivie éventuellement de break; pour arrêter l'exécution des autres cas. Les <constanteEntière_i> peuvent être constante ou expression constante entière ou caractère. En tout cas elles doivent être différentes.

L'expression est évaluée et est comparée à toutes les constantes. Dès que sa valeur est égale à une de ces constantes, l'exécution reprend au choix correspondant, et se poursuit sur les choix suivants s'il y' en a. Sinon c'est le choix autre , default, qui est sélectionné quand il est présent.

switch (i) {
       case 1  : printf("i = 1\n");    break;
       case 3  : printf("i = 3\n");    break;
       case 0  : printf("i = 0\n");    break;
       case 23 : printf("i = 23\n");   break;
       default : printf("i autre \n"); break;
}

La figure III-1 est un exemple général de l'usage de switch qui, pour chaque valeur de i dans {0, 1, 3, 23}, fait un traitement, e.g. printf("...") ici, et quitte switch avec break. Si i n'est pas dans l'ensemble énuméré la partie default est exécutée.

Attention, les choix case sont comme des labels (étiquettes) qui montrent le début d'exécution. Le break n'est pas toujours nécessaire mais il permet de terminer le choix en cours. La figure III-2 montre un exemple où un choix case est considéré comme une étiquette. Si le choix sélectionné est vide c'est le premier choix non vide rencontré qui est exécuté. Ici par exemple, c'est le cas de printf("mention Bien\n") qui est exécuté si note est égale à 17; de même pour 16 ou 15. Les case ne sont donc pas tout à fait comme en PASCAL.

switch (note) {
       case 20 :
       case 19 :
       case 18 : printf("Mention Très Bien\n"); break;
       case 17 :
       case 16 :
       case 15 : printf("Mention Bien\n"); break;
       case 14 :
       case 13 :
       case 12 : printf("Mention Assez Bien\n");
                 break;
       default : printf(" Mention Passable\n");
                 break;
}

4. Itérations while, for, do-while

4.1. Boucle while

C'est l'instruction d'itération while classique.

Tant que l'expression <expression> est évaluée à vrai, l'exécution de <instruction> est répétée. La figure III-3 est un exemple de recherche dichotomique dans un tableau trié, entre les bornes bas et haut. La variable rang est le résultat de la recherche: indice de l'élément sinon -1. Remarquer l'usage du break pour quitter prématurément la boucle quand on a trouvé l'élément.

/* trouver x dans t[bas .. haut] trii*/
rang = -1;
while (bas <= haut) {
      milieu = (bas + haut) / 2;
      if (x < t[milieu]) haut = milieu - 1;
      else if (x > t[milieu]) bas = milieu + 1;
      else { /* trouvi */ rang = milieu;
            break;
      }
}

4.2. Boucle for

L'instruction for de C ne ressemble pas aux habitudes des autres langages. Elle s'écrit

et signifie (exprimé en while)

Généralement, <expr_1> est l'initialisation d'une variable de contrôle, <expr_2> une expression logique qui est la condition d'arrêt de la boucle (en devenant fausse) et <expr_3> une incrémentation de la variable de contrôle ("finalisation"). C'est assez fort (sic) comme moyen d'expression d'itération.

Exemple:

Pour les mordu(e)s des programmes C condensés, c'est équivalent à:

où la dernière expression groupe l'incrémentation de i avec l'instruction printf..., corps de la boucle.

Remarquer la présence de ; en fin de for ici. C'est pour dire qu'il n'y a pas de corps de boucle car sinon, c'est la mauvaise instruction (la prochaine du programme) qui sera répétée !!! Encore une source d'erreur pour les amateur(e)s de programmes condensés.

Une des expressions <expr_1> ou <expr_3> peut manquer. La même itération peut s'écrire sans <expr_3>:

Si <expr_1> et <expr_3> manquent, c'est une boucle sans variable de contrôle qui ressemble à while. Sa condition d'arrêt est <expr_2> (fausse) .

Si <expr_2> manque, elle est considérée toujours vrai. Ainsi

est une boucle sans fin, qu'on ne peut quitter qu'avec break, return, goto ou ... une bogue fatale.

4.3. Boucle do...while

Ce type d'itération se distingue du while normal par le fait que le test d'arrêt se fait après un passage dans le corps de la boucle.

veut dire répéter l'instruction tant-que l'expression est vrai (ou jusqu'à ce que l'expression devienne fausse). C'est le même comportement, mais plus commode à écrire, que

où <instruction> est la même dans les deux lignes.

Remarque: do ... while en C est comme REPEAT ... UNTIL en Pascal avec la condition inversée.

Exemple: Faire la somme des N premiers entiers naturels,

Noter le ; après while.

Quoique cela ne soit pas nécessaire on peut utiliser les {} comme ici, pour la lisibilité et afin de ne pas prendre while pour un début de boucle tant-que.

A propos de l'usage des accolades pour la lisibilité, une bonne habitude veut qu'elles soient alignées verticalement pour délimiter leur bloc.

Mais dans les cas des structures de contrôles, il est peut être préférable [1] d'aligner l'accolade fermante } sur le mot clé qui débute la structure de contrôle nécessitant un bloc { }. L'accolade ouvrante { venant sur la même ligne que ce mot clé. Ecrire:

if() {               while () {               switch () {
...                      ...                      ...
}                    }                        }

if()                while ()              switch ()
{                   {                     {
...                      ...                      ...
}                   }                     }

L'accolade } jouant alors le rôle d'un endif, endwhile etc., et on gagne une ligne.

Exercice: Ecrire des blocs d'instructions syntaxiquement correctes (comprenant des if, while, for, switch ...) et leur faire une indentation par l'utilitaire UNIX cb ou indent (ou tout autre utilitaire dans son éditeur préféré).

5. Les Ruptures de Contrôle

5.1. L'instruction break

while (...){
       ...
       while (...) {
              ...
              break;
       }
       /* suite premier while */
}

Après break le contrôle se poursuit à la ligne marquée /* suite premier while */.

Exemple:

/* ajouter les n premiers entiers jusqu'à atteindre ou dépasser 1000 */ 
s = 0; 
for (i = 1; ; i++) { 
       s += i; 
       if (s >= 1000) break; 
}

Ici, le test d'arrêt de la boucle est programmé. L'instruction break intervient donc, après un test.

Exercice: Vérifier, pour les fanatiques encore du code condensé, que les trois instructions suivantes font la même chose que ce dernier exemple.

for (s = i = 0; ; i++) 
       if ((s += i) >= 1000) break ; 

for (s = i = 0; s < 1000; ) s += i++ ; 

for (s = i = 0; s < 1000; s += i++) ;

Quelle est la valeur de s et de i dans chaque cas? [2]

5.2. L'Instruction continue

Comme break, l'instruction continue est utilisée dans une boucle. Elle sert quand à elle, à arrêter l'itération courante pour continuer la même boucle à la prochaine itération.

Exemple:

/* Compter les entiers positifs d'un tableau 
 * (sauter les négatifs) */ 
positif = 0; 
for (i = 0; i < max; i++) { 
       if ( t[i] < 0 ) continue; 
       positif++; 
}

Si t[i] est inférieur à 0, on passe à l'itération suivante, sinon on incrémente positif de 1. L'instruction continue est surtout utile pour la lisibilité et la présentation de texte de programmes. Elle fait économiser des indentations dans les niveaux d'imbrications. En inversant le test ci-dessus, la partie positif++ aurait été indentée d'un pas.

5.3. L'instruction return

return;

ou

return ( <expression> );

est l'instruction qui arrête l'exécution d'une fonction et renvoie à la fonction appelante. Le cas échéant, la valeur de l'expression <expression> est la résultat de la fonction. Exemple:

float fahr2celc (int f){
      float c;
      c = (5.0/9.0)*(f-32);
      return c;
}

5.4. L'instruction goto

L'instruction goto n'est en fait jamais nécessaire. Elle a été jugée mauvaise (harmfull) par Edger W. DIJKSTRA, un des fondateurs des concepts de la programmation structurée. Mais, et comme l'a souligné Donald E. KNUTH, on peut faire de la programmation structurée avec goto qui est utile dans certains algorithmes pour des cas, e.g. cas d'exception, où on aimerait arrêter le processus en cours. Surtout dans les boucles. break ne peut être utilisé puisqu'il ne quitte que la boucle la plus interne. D'où l'usage de goto qui s'utilise comme

où <label> est un identificateur. Le contrôle est transféré vers l'instruction étiquetée par le label <label>

Cette dernière écriture joue aussi le rôle de déclarateur du label.

Exemple:

/* Recherche x dans une matrice t[m][n] */
for ( i = 0; i < m; i++)
       for ( j = 0; j < n; j++)
       if (t[i][j] == x)
              goto trouve;
 /* partie non trouvé */
 trouve:
 /* c'est t[i][j] */

Voici l'équivalent sans goto mais avec une variable logique trouve. On arrête la recherche après avoir trouvé.

trouve = 0;
for ( i = 0; i < m && !trouve; i++)
       for ( j = 0; j < n && !trouve; j++)
              if (t[i][j] == x)
                     trouve = 1;
if (trouve)
       /* c'est t[i-1][j-1] ! */
else
       /* cas non trouvé */

On peut débattre longtemps sur la meilleure écriture. D'ailleurs le débat «GOTO or GOTOless», commencé en 1968, se poursuit toujours et encore. L'instruction goto figure dans la plupart des langages et souvent pour des raisons de complétude que pour autre chose.

Exercice: Que fait le premier programme ci-dessus (celui avec goto) si on a utilisé break au lieu de goto?

6. Exemples d'Algorithmes Programmés en C

Pour terminer ce chapitre, on propose un assortiment de programmes C, assez classiques du reste, pour se familiariser avec la syntaxe C. Il est très utile de refaire ces programmes sur machine, et d'essayer de les varier, les augmenter etc... Les algorithmes sont de plus en plus... élaborés.

Un premier programme très simple, (dans Kenighan & Ritchie), convertit des températures Fahrenait en degré Celsius.

Un second, est un programme "de gestion" (adapté de Richard Moore), qui calcule les amortissements d'un prêt bancaire avec taux d'intérêt. Il calcule et imprime le montant des mensualités et l'échéancier des sommes restant à rembourser: Principal et Intérêt.

Un troisième programme est le triangle de Pascal, avec une variante pour visualiser les emplacements des nombres pairs et impairs du triangle (structure "scalante" ou fractale)

Deux autres programmes font le tri d'un tableau selon les méthodes: tri par insertion, tri par sélection. Algorithmes en O(n²). Il y a de meilleurs algorithmes de tri, plus efficaces (en O(n.log(n)) ), mais là n'est pas notre souci.

Les deux programmes qui viennent ensuite, parcours de tableau aussi, représentent des algorithmes très intéressants. Le premier d'entre eux est une solution du problème du Drapeau Hollandais de E. W. Dijkstra: un tableau contient n éléments ayant chacun une couleur, valeur de l'élément. Il y a en tout trois couleurs: Rouge (ou 1), Bleu (ou 2), Blanc (ou 3). D'où le nom de drapeau hollandais. Il s'agit, en balayant une seule fois le tableau, de mettre les couleurs dans l'ordre: Rouge d'abord, Bleu ensuite et Blanc enfin. Le problème peut se réduire à trier un tableau ne contenant que trois valeurs différentes. L'autre problème, dit problème du plateau (dû à Michael Griffith), consiste à chercher dans un tableau d'entiers rangés en ordre croissant, l'élément le plus souvent répété. Le tableau est considéré comme une montée en côte (valeurs croissantes), entrecoupée par des espaces plats (valeurs répétées). D'où le nom. Une variante un peu compliquée de ce problème (due à Jacques Arsac [3]) consiste à chercher dans un tableau d'entiers quelconques, les indices i et j tels que la sommes des éléments entre i et j soit maximum, quelque soit i et j. Balayer une seule fois le tableau évidemment.

Enfin un dernier programme «last but not least», un peu insolite, est un programme qui a pour résultat lui-même (qui imprime son texte source).

Pour terminer (promis), avec un programme intéressant (donné tel que trouvé dans une revue) qui calcule le nombre pi a 2400 décimales. Je vous propose un exercice (sur C) à son propos.

Programme 1:

Conversion de températures en degrés Fahrenait vers degrés Celcius.

# include <stdio.h>
float celcius(float);
main(){
 /* Programme qui imprime la conversion des degres
  * Fahrenait (de 0 a 300 par pas de 20) en Celcius
  */ 
        int bas, haut, pas;
        float fahr,c;
        bas = 0;
        haut = 300;
        pas = 20;

        fahr = bas;
        printf("Fahrenait   Celcius\n\n");
        while(fahr <= haut)     {
                c = celcius (fahr);
                printf("%8.0f %8.1f \n",fahr,c);
                fahr += pas;
        }
}

float celcius(float x) {
        return (5.0/9.0)*(x-32.0);
}

Fahrenait   Celcius

   0    -17.8 
      20     -6.7 
      40      4.4 
      60     15.6 
      80     26.7 
     100     37.8 
     120     48.9 
     140     60.0 
     160     71.1 
     180     82.2 
     200     93.3 
     220    104.4 
     240    115.6 
     260    126.7 
     280    137.8 
     300    148.9

Programme 2:

Calcul des amortissements d'un prêt bancaire. La banque vous prête un montant M , au taux t_x% annuel (≠ 0) et pour une durée d en mois. Vous rembourser mensuellement une certaine somme fixe v, calculée comme étant composée d'un principal: la partie affectée au montant M, et d'un intérêt: partie couvrant les intérêts.

La formule (un banquier vous la fournira --s'il la connaît) de calcul du montant d'une mensualité est:

v = t_m . M / (1 - (1 + t_m) ^-d )

où t_m est le taux d'intérêt mensuel calculé comme t_x /12.

#include <math.h>
#include <stdio.h>

main() {
      /*
       * programme qui calcule les amortissements d'un pret. Entrees:
       * Montant du Pret, Taux Interet annuel et Duree du pret (en mois).
       * Sortie: Montant Versements mensuels, Tableau des amortissements:
       * Mois, Solde(Debit), Cumul Verse(Credit), Cumul Interet et Cumul
       * Principal ( CI + CP = CV)
       */

int i, duree;
      double    mtPret, tauxMensuel, tauxAnnuel;
      double    solde, credit, cumulInteret, cumulPrincipal;
      double    mensualite, principal, interet;

      printf("montant du pret? \n");
      scanf("%lf", &mtPret);
      printf("taux interet annuel en pourcentage? \n");
      scanf("%lf", &tauxAnnuel);
      printf("nombre de mois? \n");
      scanf("%d", &duree);

      tauxMensuel = (tauxAnnuel / 100.) / 12.;
      mensualite = tauxMensuel * mtPret / (1. - pow(1. + tauxMensuel, (double) -duree));

      printf("\nMontant du pret = %12.2f DH\n", mtPret);
      printf(" taux annuel = %4.2f pour cent (%0.3f mensuel)\n", tauxAnnuel, tauxMensuel);
      printf("\n Soit: %d MENSUALITE DE %12.2f DH\n", duree, mensualite);

      cumulPrincipal = cumulInteret = interet = 0.0;
      solde = mtPret;
      credit = cumulPrincipal + cumulInteret;
      printf("\n");
      printf("| ECHEANCE | SOLDE       | CREDIT      | INTERET     | PRINCIPAL   |\n");
      printf("|==========|=============|=============|=============|=============|\n");

      for (i = 0; i <= duree; i++) {
             printf("| [%2d]     |", i);
             printf("%12.2f |", solde);
             printf("%12.2f |", credit);
             printf("%12.2f |", cumulInteret);
             printf("%12.2f |\n", cumulPrincipal);
             interet = tauxMensuel * solde;
             principal = mensualite - interet;
             cumulInteret += interet;
             cumulPrincipal += principal;

             credit = cumulPrincipal + cumulInteret;
             solde += interet;
             solde -= mensualite;
      }
}

Résultat:

% a.out 
montant du pret? 
12000 
taux interet annuel en pourcentage? 
10 
nombre de mois? 
12

Montant du pret =     12000.00 DH 
 taux annuel = 10.00 pour cent (0.008 mensuel)

 Soit: 12 MENSUALITE DE      1054.99 DH

  | ECHEANCE | SOLDE       | CREDIT      | INTERET     | PRINCIPAL   |
  |==========|=============|=============|=============|=============|
  | [ 0]     |    12000.00 |        0.00 |        0.00 |        0.00 |
  | [ 1]     |    11045.01 |     1054.99 |      100.00 |      954.99 |
  | [ 2]     |    10082.06 |     2109.98 |      192.04 |     1917.94 |
  | [ 3]     |     9111.09 |     3164.97 |      276.06 |     2888.91 |
  | [ 4]     |     8132.02 |     4219.96 |      351.98 |     3867.98 |
  | [ 5]     |     7144.80 |     5274.95 |      419.75 |     4855.20 |
  | [ 6]     |     6149.35 |     6329.94 |      479.29 |     5850.65 |
  | [ 7]     |     5145.60 |     7384.93 |      530.54 |     6854.40 |
  | [ 8]     |     4133.49 |     8439.93 |      573.42 |     7866.51 |
  | [ 9]     |     3112.95 |     9494.92 |      607.86 |     8887.05 |
  | [10]     |     2083.90 |    10549.91 |      633.80 |     9916.10 |
  | [11]     |     1046.27 |    11604.90 |      651.17 |    10953.73 |
  | [12]     |       -0.00 |    12659.89 |      659.89 |    12000.00 |

Constater que le montant des intérêts (100, 92.04, ...) diminue au fur et à mesure, et que celui du principal (954.99, 962.95, ...) augmente de façon à ce que leur somme soit constante (c'est la mensualité à verser).

Exercice: Variante du programme. Le client dispose d'un délai de 3 mois (ou n mois) avant de commencer à effectuer les remboursements. On compte donc les intérêts afférents à ce délai. Adapter le programme précédent pour cela (Il n'y a pas d'amortissements durant cette période).

Programme 3: Le triangle de Pascal.

La ligne i est obtenue à partir de la ligne i-1 par:

La méthode consiste à utiliser 2 tableaux t et s de taille MAXC impair: un qui représente la dernière ligne calculée (et imprimée), et l'autre, la nouvelle ligne à calculer et imprimer. Chaque tableau contient les nombres de Pascal (Coefficients d'un polynôme de NEWTON) centrés, séparés et complétés par des 0, qui deviendront des espaces à l'impression (c'est notre astuce pour avoir une triangle isocèle).

Exemple:

Le calcul de la prochaine ligne est facile:

Soit:

A l'impression d'une ligne, on n'imprime pas les 0. La boucle du programme consiste donc à répéter:

- Imprimer t
- Calculer s
- Imprimer s
- Calculer t

MAXL/2 fois (2 impressions par boucle), où MAXL est le nombre de lignes à sortir. Les deux premières lignes sont calculées et imprimées, en dehors de la boucle. Soit le programme:

#define MAXL 10     /* 10 lignes a imprimer */
#define MAXC  31    /* taille des tableaux  */ 

int t[MAXC], s[MAXC];
void newtab( int [], int []);
void impr( int []);

main() { 
 /* On initialise les deux premieres lignes 
  * (une valeur toutes les deux cases)
  * et on les imprime 
  */
        int i,j;
        j = MAXC / 2;
        t[j] = 1;
        impr(t);
        t[j-1] = 1; 
        t[j] = 0; 
        t[j+1] = 1;
        impr(t);

        /* On commence le calcul */
        for(i=0; i<(MAXL/2); i++){
                newtab(t,s);
                impr (s);
                newtab(s,t);
                impr(t);
        }
}

void newtab( int x[],int y[]) {
  /* Copy x sur y en effectuant les additions qu'il faut */
        int i;
        for (i=0; i<MAXC; i++)
                if (x[i]==0) y[i] = x[i-1] + x[i+1];
                else y[i]=0;
}

void impr(int x[]) {
      /* imprime tableau x (3 espaces pour les 0)*/
        int i;
        for (i=0; i<MAXC; i++)
                (x[i]==0)? printf("   ") : printf("%3d",x[i]) ;
        printf("\n\n");
}

Remarque: Voici le même triangle, en faisant apparaître la répartitions des nombres pairs (*) et impairs (espace) (d'après Ian STEWART, revue Pour la Science Mars 1993). On obtient ce beau dessin, dit triangle de Sierpiński, bien structuré comme une fractale: le tout ressemble à la partie.

Exercice : Re-imprimer ce dernier triangle en y rajoutant un autre "étage".

Programme 3 et 4: Algorithmes de tri simples

Les programmes qui suivent illustrent, entre autre, la notion d'invariant de boucle. Une boucle fait passer un programme d'un état initial I à un état final F, par répétition d'un traitement, qui le fait passer par différents états intermédiaires E_i. Chaque itération fait passer d'un état intermédiaire à un autre, en partant de l'état initial I jusqu'à l'état final F. Dans un programme itératif, la règle d'or est :

Une propriété comme P ci-dessus, s'appelle un invariant de boucle. C'est une propriété invariante durant la boucle. Ainsi, cette propriété P est vérifié:

Une fois trouvé l'invariant (pas toujours facile), il suffit de trouver l'initialisation de i et la condition d'arrêt de la boucle.

Tri par Selection d'un tableau:

#include <stdio.h>
#define N 10

int t[N] = { 2, -44, 1, 0, -5, 9, 12, 4, 1, 3};

main() {
 /* Algorithme Tri Par Selection. 
  * Invariant de boucle:
  * t [ <-- trie --> | <-- Vrac --> ]  
  *                   i      k    
  *  t[k] = min(Vrac); Permute t[i] et t[k] 
  *  i dans [0..N-1], k dans [i+1.. N-1]
  */
        int i, j, k;
        int min, w;
        for (i=0; i<N; i++){
                k = i;
                /* On suppose que t[k] est t[i] 
                 * et on cherche plus petit
                 */
                for(j=i+1; j<N; j++)
                        if ( t[j]<t[k])
                                k = j;

                /* On permute t[k] et t[i] */
                w=t[k];
                t[k]=t[i];
                t[i]=w;
        }
        for (i=0; i<N; i++)
                printf("%2d\n", t[i]);
}

Résultat: (Sans les sauts à la ligne)

Tri par insertion d'un tableau:

Ici, les éléments de la partie trièe ne sont pas forcément définitifs (inférieurs au reste). On place le i^ème élément à la bonne place dans la partie triée.

#include <stdio.h>
#define N 10

int t[N] = { 2, -4, 1, 0, -5, 9, 12, 4, 1, 3};

main() {

 /* Algorithme Tri Par Insertion
  * Invariant de boucle:
  * t [ <-- trie --> | <-- Vrac --> ]   
  *         k         i    
  *
  *  On insere t[i] a la bonne place k dans t[<trie>]
  *  i dans [1..N-1], k dans [0..i-1]
  */
        int i, k;
        int w, aCaser;
        for (i=1; i<N; i++){
                aCaser = t[i];
                k = i-1;
                /* On permute t[k] et t[k+1] (aCaser)
                 * jusqu'a k<0 ou t[k] <= aCaser
                 */
                while (t[k]>aCaser && k>=0){
                        w=t[k];
                        t[k]=t[k+1];
                        t[k-- +1]=w;
                }
        }
        for (i=0; i<N; i++)
                printf("%2d\n", t[i]);
}

Résultat: (Sans les sauts à la ligne)

Programme 5: Le problème du drapeau Hollandais.

#define T 12
int t[T] = {2, 2, 2, 3, 3, 2, 2, 1, 3, 3, 1, 1};

main(){

/* Programme Drapeau Hollandais 
 * Dans t, mettre d'abord les 1, ensuite les 2 enfin les 3
 * Invariant de boucle:
 * t[ 111112222???????333333 ]
 *        i    j      k
 * Jusqu'a i c'est les 1. Ensuite les 2 (jusqu'a j-1).
 * Elements t[j..k-1] non encore examines. 
 * De k a la fin c'est les 3. Arret j=k (CQFD).
 */
        int i, j, k;
        int w;

   /* Initialisations */
        i = -1;   /* i avant t */
        j = 0;    /* j 1er element */
        k = T;    /* k au dela de t */

        /* On examine t[j] */
        /* j = k  Il ne reste plus de ?  donc fini */

        while ( j<k ) {
                switch (t[j]){
                case 1: /* on le met avec les 1 
                          i.e. on permute avec t[i+1] */
                        w=t[i+1];
                        t[i+1]=t[j];
                        t[j]=w;
                        i++; 
                        j++;
                        break;
                case 2: /* t[j] a la bonne place */
                        j++;
                        break;
                case 3: /* on le met avec les 3 
                         * i.e. on permute avec t[k-1] 
                         * Mais on n'incremente pas j ! 
                         */
                        w=t[k-1];
                        t[k-1]=t[j];
                        t[j]=w;
                        k--;
                        break;
                }
        }
        for (w=0; w<T; w++)
                printf("%d ",t[w]);
        printf("\n");
}

Résultat:

Programme 6 et 7: Le problème du plateau.

C'est un problème assez classique qui illustre bien la notion d'invariant de boucle et de manière générale comment écrire un programme de façon raisonnée.

Programme 6

Pour trouver l'algorithme, imaginons que le travail est fait à moitié: en l'occurrence, on a parcouru une partie du tableau jusqu'à i non compris. Dans cette partie, c'est x l'élément répété nb fois et c'est un maximum de fois. Si i devient supérieur à taille du tableau, le travail est fait et on arrête. Si i = 0, alors nb est nul et cela répond à la question (Il n'y a pas d'éléments dans cette partie vide). Maintenant, sinon, examinons si l'élément t[i] est de nature à changer la situation. C'est le cas s'il est répété nb+1 fois, c'est a dire si t[i] = t[i-nb]. Auquel cas x devient t[i], nb est augmenté de 1 et on passe à l'itération suivante. D'où le programme:

#define N 15
int t[N]={1,1,3,3,3,4,4,4,5,5,6,6,6,6,7};

main(){
/*
 *  Probleme du Plateau:
 *  Chercher l'element le plus souvent repete
 *  dans un tableau 
 */
        int i;
        int nb, x; /* nb est le nombre d'occurrence de 
                      l'element x le plus souvent repete */
        nb = 0;
        for (i=0; i<N; i++) {

        /* On est a l'etape i,
         * on examine si le plateau courant est 
         * plus long que celui deja calcule 
         * i.e. t[i] est egale a t[i-nb], auquel cas
         * t[i] est un nouveau x avec nb augmente de 1
         */
                if (t[i] == t[i-nb]) {
                        x = t[i];
                        nb++;
                }
        }
        printf("%d est repete un maximum de fois = %d\n", x,nb);
      }

Résultat (le tableau étant {1,1,3,3,3,4,4,4,5,5,6,6,6,6,7}) :

Programme 7:

Une variante du programme ci-dessus (Jacques ARSAC, revue Pour la Science No 85, Nov. 84) est de chercher dans le tableau t, quelconque cette fois-ci, les indices d et f tels que la somme des éléments entre d et f soit maximale. Par exemple, dans le tableau {2, -5, 3, -1, 8, -2} on a :

2  -5  3  -1  8  -2 
       d      f

la plus grande somme (10) est entre le 3e et le 5e élément, i.e. indices d = 2 et f = 4.

Comme pour les programmes précédents, on va supposer qu'on a fait la moitié du travail, c'est à dire:

• qu'on possède déjà les indices d et f (d <= f) de la plus grande somme som calculée jusqu'à maintenant
• qu'on est à l'indice i (i >= f) et en train de chercher une meilleure somme m, laquelle commence à un nouvel indice k (k >= d), autrement dit, m est la somme des éléments de k à i-1.

On examine t[i] donc, qui, rajouté à m , peut contribuer à améliorer la somme som déjà connue. Auquel cas som deviendra m, d et f devenant k et i respectivement. Mais on ne rajoute t[i] à m que si m est positif (m <0 ==> t[i] > t[i]+m ), sinon m se réduit à t[i] et k devient i. D'où le programme:

#define N 6

int t[N] = {2, -5, 3, -1, 8, -2} ;  
/*           somme maximale 10 entre 2 et 4 */
/* int t[N] = {2, -5, 3, -4, 8, -2}; 
           somme maxiamle 8 entre 4 et 4*/
/*int t[N] = {-10, -12, -2, -3, -4, -1}; 
           somme maximale -1 entre 5 et 5*/

main(){
 /*  Variante du probleme du plateau.
 *  Il s'agit de trouver deux indice d et f
 * tel que la somme des elements de t entre d et f soit
 * maximale
 */

        int d,f, i,k;
        int som, m;

        d = k = f = 1;
        som = m = t[0];

 /* On a parcouru t jusqu'a i (exclu)
  * som est la meilleure somme rencontree 
  * jusqu'a present et elle est entre d et f. 
  * On est en train d'examiner si une somme actuelle (m)
  * entre k et i n'est pas meilleure que som,
  * auquel cas d devient k et f devient i.
  */
        for (i=1; i<N; i++){
                /* On regarde une nouvelle somme m + t[i] 
          (ou t[i], si m negatif) */
                if (m < 0) {
                        m = t[i] ; 
                        k = i;
                }
                else m += t[i] ;

                /* On compare avec som */
                if ( m > som) {
                        d = k; 
                        f = i; 
                        som = m;
                }
                else ;
        }

        printf(" Meilleur somme %d entre %d et %d \n",som,d,f);
}

Les commentaires en début de programmes indiquent les trois jeux d'essai testés avec leur résultats. Par exemple, pour le premier:

Exercice: Dans le même ordre d'idées, dans un tableau t quelconque, chercher la plus longue sous suite croissante. Dans la suite :

on aura :

qui est la plus longue sous suite croissante.

Programme 8:

Un dernier programme (last but not least), un peu insolite, est un programme qui a pour résultat lui-même. C'est à dire un programme qui imprime son texte source. Il va de soi que le programme n'a pas de données, sinon, un programme qui imprime un fichier texte fait l'affaire: on lui donne en entrée son fichier source à lire et à imprimer.

Un tel programme n'est pas facile, car il y a un phénomène d'auto référence, source de paradoxe, comme un serpent qui se mord la queue. On pourrait imaginer un programme qui contient pour seule instruction

avec la chaîne égale au texte du programme. Mais alors si N est la longueur de cette chaîne, N est aussi la longueur du programme, puisque cette chaîne est le texte du programme lui-même. Or ce programme contient au moins 11 autres caractères qui sont: p r i n t f ( " " ) ; Sa longueur est au moins N+11. D'où la contradiction N >= N+11.

Une solution imaginée par Kenneth THOMPSON [4], l'inventeur de UNIX, est donnée juste ci-dessous (c'est en réalité un programme qui a pour résultat un programme qui a pour résultat lui-même).

Ce programme a l'allure suivante (lignes numérotées):

La chaîne s est initialisée et sa valeur est une partie seulement du texte total du programme (partie allant de (n) à la fin). En l'occurrence, la partie code qui doit reproduire le texte total justement, imprimé en deux fois. L'instruction (n+2) reproduit les lignes (1) à (n-1), et l'instruction (n+3) reproduit le texte allant de (n) à la fin. Il ne reste plus qu'à reproduire la ligne (0) et déclarer i.

char s[]={
'0',
'\n',
'}',
    etc  ...   
 '}',
'\n'
};
/* meme les commentaires s'y trouvent */ 
main(){
int i; 
printf("char  s[] = {\n"); 
for (i=0;s[i];i++)
printf("%d,\n",s[i],s[i],i);  
printf("%s",s);
}

Le programme complet.

D'autres solutions, imaginées par les programmeurs chevronnés (hackers) sont données en ANNEXE C. Elles sont beaucoup plus courtes, mais pas plus simples, que celle donnée ici.

Programme 9:

Le programme suivant calcule π (pi) avec 2400 decimales. Il est illisible!

int a=10000,b,c=8400,
d,e,f[8401],g;
main(){
       for(;b-c;)
            f[b++]=a/5;
       for(;d=0,g=c*2;c -= 14,printf("%.4d",e+d/a),e=d%a)
            for(b=c;d += f[b]*a,f[b]=d% --g,d /=g--, --b; d *=b);
}

Voici son résultat:

31415926535897932384626433832795028841971693993751058209749445923078164062862089
98628034825342117067982148086513282306647093844609550582231725359408128481117450
28410270193852110555964462294895493038196442881097566593344612847564823378678316
52712019091456485669234603486104543266482133936072602491412737245870066063155881
74881520920962829254091715364367892590360011330530548820466521384146951941511609
43305727036575959195309218611738193261179310511854807446237996274956735188575272
48912279381830119491298336733624406566430860213949463952247371907021798609437027
70539217176293176752384674818467669405132000568127145263560827785771342757789609
17363717872146844090122495343014654958537105079227968925892354201995611212902196
08640344181598136297747713099605187072113499999983729780499510597317328160963185
95024459455346908302642522308253344685035261931188171010003137838752886587533208
38142061717766914730359825349042875546873115956286388235378759375195778185778053
21712268066130019278766111959092164201989380952572010654858632788659361533818279
68230301952035301852968995773622599413891249721775283479131515574857242454150695
95082953311686172785588907509838175463746493931925506040092770167113900984882401
28583616035637076601047101819429555961989467678374494482553797747268471040475346
46208046684259069491293313677028989152104752162056966024058038150193511253382430
03558764024749647326391419927260426992279678235478163600934172164121992458631503
02861829745557067498385054945885869269956909272107975093029553211653449872027559
60236480665499119881834797753566369807426542527862551818417574672890977772793800
08164706001614524919217321721477235014144197356854816136115735255213347574184946
84385233239073941433345477624168625189835694855620992192221842725502542568876717
90494601653466804988627232791786085784383827967976681454100953883786360950680064
22512520511739298489608412848862694560424196528502221066118630674427862203919494
50471237137869609563643719172874677646575739624138908658326459958133904780275900
99465764078951269468398352595709825822620522489407726719478268482601476990902640
13639443745530506820349625245174939965143142980919065925093722169646151570985838
74105978859597729754989301617539284681382686838689427741559918559252459539594310
49972524680845987273644695848653836736222626099124608051243884390451244136549762
78079771569143599770012961608944169486855584840635342207222582848864815845602850

Je vous propose de structurer ce programme (e.g. faire des boucles while plus simples) pour une meilleure lisibilité -- mais pas forcément une meilleure compréhensibilité. Voici ma solution:

int a=10000, b, c=8400, d, e, f[8401], g;
main(){
        while (b-c)
                f[b++] = a/5;
        d=0;
        while (g = c*2){
                b = c;
                d += f[b]*a; 
                f[b] = d % --g; 
                d /= g--;
                while (--b){
                        d *= b;
                        d += f[b]*a; 
                        f[b] = d % --g; 
                        d /= g--;
                }
                c -= 14; 
                printf("%.4d",e+d/a); 
                e = d%a;
                d = 0;
        }
}

[0] Tester un programme peut montrer qu'il contient des erreurs, mais jamais qu'il est correct.

[1] Oui c'est subjectif

[2] Réponse: s = 1035 dans les 4 cas, i = 45 dans les deux premiers cas et 46 (pourquoi?) dans les deux derniers cas. (1035 = (45*46) / 2)

[3] Pour la Science , n° Spécial Génie Logiciel, Novembre 84

[4] Ken Thompson, "Reflections on Trusting Trust", ACM Turing Award Lecture, Aout 1984.