Année universitaire 2003-2004

DEUG MIAS
Module Info 2
Travaux dirigés

Séance 4 Complément:

  • Instructions Conditionnelles.
    		•

    TD 4 Complément : Invariant de boucle
    On considère le programme suivant (exponentiation indienne):
    #include <stdio.h>
    void   main(void){
     int  a;   /* base de l'exposant */
     int b;   /* exposant */
     int  x, y, z; /* var. auxiliaires */
     scanf("%d%d", &a, &b);  /* lecture des entrees */
     x = a; /* initialisation */
     y = b;
     z = 1;
     while (y != 0){
      if (y % 2 == 1){
       z = z * x;
       y = y - 1;
      }
      else {
       x = x * x;
       y = y / 2;
      }
     }
     printf("%d a la puissance %d vaut: %d ", a, b, z);
    }
    1. Montrer que la propriété :

       x >0 et y³ 0 et z xy =ab
    est un invariant de la boucle while (préciser à quel endroit).
    2. En déduire que le programme est correct.
    3. Quel est l'intérêt de cet algorithme par rapport au calcul classique?
    4. Réécrire le programme en utilisant les opérateurs *=, /=, - -, et sans utiliser == dans le test du if.

    Commentaires pascal.lafourcade@lsv.ens-cachan.fr