Blog de Laurent Bloch
Blog de Laurent Bloch

ISSN 2271-3980
Cliquez ici si vous voulez visiter mon autre site, orienté vers des sujets informatiques et mes enseignements.

Pour recevoir (au plus une fois par semaine) les nouveautés de ce site, indiquez ici votre adresse électronique :

Algorithme itératif : une méthode empirique

Programmer un algorithme calqué sur le modèle du calcul « à la main ».

Article mis en ligne le 15 novembre 2004
dernière modification le 23 octobre 2006

par Laurent Bloch

L’article Construire un algorithme itératif expose les principes de réalisation d’un tel algorithme. Nous allons aborder ici le problème sous un autre angle, plus empirique mais de ce fait peut-être plus facile à comprendre. En fait, nous allons décrire la procédure suivie pour effectuer le calcul « à la main », et traduire cette procédure en langage Scheme.

Plutôt que de partir de la définition de la fonction factorielle, nous pourrions écrire notre programme en nous inspirant du calcul manuel et en décrivant en Scheme nos actions successives. C’est-à-dire que pour calculer n! il faut multiplier le premier entier naturel par son successeur, puis le résultat par le successeur du successeur, ainsi de suite, et s’arrêter lorsque le dernier nombre multiplié atteint la valeur de n. Il faut pour cela garder à la mémoire la valeur de n. Il nous faut aussi savoir combien de fois nous avons effectué l’opération, et tenir ce compte dans une variable compteur, qui sera aussi le nombre dont on veut calculer la factorielle à l’étape courante. Les résultats des multiplications successives sont consignés dans la variable produit.

À chaque étape, on multiplie compteur par produit, et on écrit le résultat dans la colonne produit à la ligne du dessous. Lorsque la valeur de compteur dépasse celle de n, le calcul est terminé et le résultat est dans la colonne produit.

Représentons-nous le processus de calcul pas à pas, en
prenant une colonne par variable, et en plaçant dans chaque colonne les valeurs successives de ladite variable. Voici le tableau du calcul :

n compteur par produit résultat
6 1 × 1
6 2 × 1
6 3 × 2
6 4 × 6
6 5 × 24
6 6 × 120
6 7 720 n ! = 720

Traduisons cela en Scheme. Ces opérations de mécanique calculatoire seront réalisées par une procédure auxiliaire fact-aux, appelée par la procédure principale fact.

(define (fact-aux n compteur produit)
   (if (> compteur n)
       produit
       (fact-aux n
                 (+ compteur 1)
                 (* compteur produit))))

(define (fact n)
   (fact-aux n 1 1))

Dans la même rubrique