TD-2, division par deux, types enregistrements

Ce document est disponible à l'URL http://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/TC/X.97/TD-2/enonce.html

Vos programmes à déposer sous la forme Prenom.Nom par ftp sur poly en /users/profs/maranget/TD-2.

1  Division par deux

Afin de laisser le plus de place possible à la programmation, voici quelques indications sur l'exercice 2 du cours.

Cet exercice demande un calcul efficace de x puissance n, à partir de la décomposition binaire de n, en itérant l'élévation à la puissance deux (c'est à dire le carré).

Il y a plusieurs façons d'aborder cet exercice classique. En voici d'abord une qui conduit à une boucle. Soit la décomposition de n en base deux : n = n0 + n1 * 2 + ··· + nt * 2t. Alors, on a xn = xn0 * x(n1 * 2) * ··· * x(nt * 2t). Soit maintenant la suite w0 = x, wk+1 = wk * wk --- autrement dit wk est x à la puissance 2k. Le résultat xn est un produit de wj. Dans ce produit, il y a un facteur wj pour chacun des j tel que 2j entre dans la décomposition en base 2 de n (i.e. nj = 1). Le programme est donc une boucle sur n0, n1, ..., nt, la décomposition binaire de n. À la j-ème itération, on accumulera ou non un facteur, selon que nj vaut 1 ou 0, et on calculera le wj+1 de l'itération suivante. Avec cette technique, x7 est calculé comme le produit w0 * w1 * w2 = x * x2 * x4 (puisque 7 = 111 en base deux).

Une autre technique (plus simple à mon avis) est de considérer les deux relations de récurrence x2k = (xk)2 et x2k+1 = x * (xk)2, puis d'écrire une fonction récursive. Avec cette technique x7, est calculé directement comme x * (x * x2)2.

Dans tous les cas, on a besoin de l'opération modulo, reste de la division euclidienne, qui s'écrit % en C. Par exemple la fonction suivante teste la parité d'un entier : 
int pair(int i)
{
  return (i % 2) == 0;
}

2  Puissances des entiers

Écrire le programme d'élévation à la puissance n, selon l'une ou l'autre des techniques présentées ci-dessus. On se place dans le cas où x est un entier long (type long).

Pour lire un entier au clavier et le ranger dans une variable n du type int, on écrit : 
  scanf("%d",&n); /* attention au & devant la variable !!! */
Dans le cas d'un entier long, à ranger dans x de type long, c'est un peu différent : 
  scanf("%ld",&x);
Pour afficher, on utilise printf et les mêmes formats que pour scanf. 
  printf("%d",n);
  printf("%ld",x);
Faites particulièrement attention aux types, x est de type long, tandis que n est de type int.

3  Nombres complexes

On se place dans le cas particulier des nombres complexes de la forme n1 + n2 i, où n1 et n2 sont des entiers. En C, un tel complexe et une valeur du type suivant : 
typedef struct {
  int re;  /* partie réelle */
  int im;  /* partie imaginaire */
} Complexe;
On demande d'écrire les fonctions qui réalisent les opérations suivantes :
  1. Lire un complexe, sous la forme de deux entiers tapés au clavier.
  2. Afficher un complexe à l'écran.
  3. Multiplier deux complexes.
  4. Calculer le carré d'un complexe.
En outre, la variable globale neutre devra être déclarée de type Complexe et initialisée à l'élement neutre de la multiplication.

Ensuite, écrire un programme qui lit un complexe c et un entier n au clavier, puis calcule et affiche le complexe c à la puissance n. Ce programme devra utiliser l'élévation à la puissance efficace. Il sera facile à écrire à partir du programme de l'exercice précédent, surtout si vous avez utilisé les types rigoureusement et écrit votre premier programme de façon générique.

4  Il vous reste du temps

Faites le dernier exercice du TP précédent : ``démonstration graphique des tris''.

Ce document a été traduit de LATEX par HEVEA.