Livre_silo 30 août 2013 16:32 Page 105
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
105
4 – Instructions : langage minimal de l’algorithmique
on écrit le programme suivant :
p = 1
for c in range(n):
p = (c+1) * p
Exercice 4.26 Démontrer au moyen d’un invariant de boucle que le programme ci-dessus calcule bien n!
dans la variable p.
SAVOIR-FAIRE Écrire un programme utilisant une boucle for
1 On détermine combien de fois la boucle devra s’exécuter, ce nombre étant en général exprimé en fonction d’une ou plusieurs variable(s) du programme.
2 On choisit une variable pour le compteur et on identifie si elle doit jouer un rôle
dans le corps de la boucle.
3 On écrit le corps de la boucle.
4 Comme pour la boucle while, il peut être nécessaire de prévoir une initialisation
des variables en amont de la boucle et un post-traitement en aval.
Exercice 4.27 Écrire un programme qui calcule la n-ième puissance itérée de k, autrement dit le nombre
k k
. . . k
formé de n exemplaires de k.
Les exposants les plus hauts doivent être calculés en premier, sinon cette expression serait équivalente à
k k
n−1 . Par exemple, la quatrième puissance itérée de 2 est 2 2
2 2
= 2 2
4 = 2 16 = 65536 et non pas
( (
2 2
) 2
) 2
= 2 2 × 2 × 2 = 2 8 = 256.
1 Puisque l’expression est formée de n exemplaires de k, il y a n−1 exponentiations successives à calculer,
ce qu’on réalisera en autant d’itérations.
2 Ici, le compteur de boucle ne jouera aucun rôle dans le calcul, il peut prendre un nom générique
comme i. La boucle commencera donc par :
for i in range(n-1):
3 Le corps de la boucle consiste à calculer une des exponentiations. Puisque les exposants sont à calculer
« de haut en bas », on prévoit ici une variable r qui contient l’exposant déjà calculé au rang précédent,
autrement dit la i-ème puissance itérée de k. Le corps de la boucle est donc simplement :
r = k ** r
4 Il faut évidemment initialiser r avant d’entrer dans la boucle. Comme à la première itération, on veut
calculer k k , la valeur initiale correcte pour r est donc k. Le compteur i est entièrement géré par la
boucle for, il est inutile de l’initialiser.
r = k
En sortie de boucle, r contient le résultat recherché, il n’y a donc aucun traitement supplémentaire.
On donne ci-après le programme complet obtenu.
r = k
for i in range(n-1):
r = k ** r
En initialisant r à 1 et en effectuant n itérations, on a un programme équivalent et même correct
pour n = 0. On ne pourra tester ce programme que pour de petites valeurs de n et k, car les nombres
calculés croissent très rapidement. On obtient un résultat intéressant en prenant k ≃
√
2.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
105
4 – Instructions : langage minimal de l’algorithmique
on écrit le programme suivant :
p = 1
for c in range(n):
p = (c+1) * p
Exercice 4.26 Démontrer au moyen d’un invariant de boucle que le programme ci-dessus calcule bien n!
dans la variable p.
SAVOIR-FAIRE Écrire un programme utilisant une boucle for
1 On détermine combien de fois la boucle devra s’exécuter, ce nombre étant en général exprimé en fonction d’une ou plusieurs variable(s) du programme.
2 On choisit une variable pour le compteur et on identifie si elle doit jouer un rôle
dans le corps de la boucle.
3 On écrit le corps de la boucle.
4 Comme pour la boucle while, il peut être nécessaire de prévoir une initialisation
des variables en amont de la boucle et un post-traitement en aval.
Exercice 4.27 Écrire un programme qui calcule la n-ième puissance itérée de k, autrement dit le nombre
k k
. . . k
formé de n exemplaires de k.
Les exposants les plus hauts doivent être calculés en premier, sinon cette expression serait équivalente à
k k
n−1 . Par exemple, la quatrième puissance itérée de 2 est 2 2
2 2
= 2 2
4 = 2 16 = 65536 et non pas
( (
2 2
) 2
) 2
= 2 2 × 2 × 2 = 2 8 = 256.
1 Puisque l’expression est formée de n exemplaires de k, il y a n−1 exponentiations successives à calculer,
ce qu’on réalisera en autant d’itérations.
2 Ici, le compteur de boucle ne jouera aucun rôle dans le calcul, il peut prendre un nom générique
comme i. La boucle commencera donc par :
for i in range(n-1):
3 Le corps de la boucle consiste à calculer une des exponentiations. Puisque les exposants sont à calculer
« de haut en bas », on prévoit ici une variable r qui contient l’exposant déjà calculé au rang précédent,
autrement dit la i-ème puissance itérée de k. Le corps de la boucle est donc simplement :
r = k ** r
4 Il faut évidemment initialiser r avant d’entrer dans la boucle. Comme à la première itération, on veut
calculer k k , la valeur initiale correcte pour r est donc k. Le compteur i est entièrement géré par la
boucle for, il est inutile de l’initialiser.
r = k
En sortie de boucle, r contient le résultat recherché, il n’y a donc aucun traitement supplémentaire.
On donne ci-après le programme complet obtenu.
r = k
for i in range(n-1):
r = k ** r
En initialisant r à 1 et en effectuant n itérations, on a un programme équivalent et même correct
pour n = 0. On ne pourra tester ce programme que pour de petites valeurs de n et k, car les nombres
calculés croissent très rapidement. On obtient un résultat intéressant en prenant k ≃
√
2.