Livre_silo 30 août 2013 16:32 Page 104
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
104
Informatique pour tous
Exercice 4.25 ** Pour accélérer le calcul de k n , on se propose d’exploiter les identités suivantes, qui
montrent comment calculer une puissance de k en remplaçant k par son carré et l’exposant par sa moitié :
{
k 2n = (k 2 ) n
k 2n+1 = k(k 2 ) n
L’algorithme est le suivant :
r = 1
while n > 0:
if n % 2 == 1:
r = r * k
k = k**2
n = n // 2
1 Quel est le rôle de la variable r dans cet algorithme ?
2 Établir la terminaison de cet algorithme.
3 Démontrer que cet algorithme est correct.
4 Cet algorithme est dit d’exponentiation rapide. Pour comprendre pourquoi, évaluer combien de multiplications il effectue et comparer avec la version naïve présentée plus haut dans ce chapitre.
4.4 Boucles inconditionnelles
On a pu voir dans la partie précédente que les boucles conditionnelles étaient nécessaires
pour effectuer des calculs lorsqu’il n’est pas possible de borner le nombre d’étapes nécessaires. En pratique, dans de nombreux cas, on connaît à l’avance le nombre d’itérations
qu’il faudra effectuer, ce qui rend inutile d’utiliser une boucle conditionnelle.
4.4.1 Boucle for
À l’aide de la construction for c in range(n), on effectue un nombre d’itérations n donné.
Ainsi, si on reprend le programme de calcul de 2
n , on aura juste à écrire :
p = 1
for c in range(n):
p = 2 * p
Le compteur de boucle est ici entièrement géré par la boucle for. Il n’est pas besoin de
l’incrémenter, ni de tester qu’il ne dépasse pas une certaine limite.
Il reste possible d’utiliser ce compteur au sein du corps de la boucle. Dans la boucle
for c in range(n), la variable c parcourt les entiers de 0 à n − 1. On remarque que le paramètre passé à range est donc la valeur avant laquelle on s’arrête. Comme souvent en
informatique, on numérote à partir de 0.
Ainsi, si l’on souhaite calculer la factorielle d’un entier n, définie par les relations :
0! = 1
(n + 1)! = (n + 1) × n!
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
104
Informatique pour tous
Exercice 4.25 ** Pour accélérer le calcul de k n , on se propose d’exploiter les identités suivantes, qui
montrent comment calculer une puissance de k en remplaçant k par son carré et l’exposant par sa moitié :
{
k 2n = (k 2 ) n
k 2n+1 = k(k 2 ) n
L’algorithme est le suivant :
r = 1
while n > 0:
if n % 2 == 1:
r = r * k
k = k**2
n = n // 2
1 Quel est le rôle de la variable r dans cet algorithme ?
2 Établir la terminaison de cet algorithme.
3 Démontrer que cet algorithme est correct.
4 Cet algorithme est dit d’exponentiation rapide. Pour comprendre pourquoi, évaluer combien de multiplications il effectue et comparer avec la version naïve présentée plus haut dans ce chapitre.
4.4 Boucles inconditionnelles
On a pu voir dans la partie précédente que les boucles conditionnelles étaient nécessaires
pour effectuer des calculs lorsqu’il n’est pas possible de borner le nombre d’étapes nécessaires. En pratique, dans de nombreux cas, on connaît à l’avance le nombre d’itérations
qu’il faudra effectuer, ce qui rend inutile d’utiliser une boucle conditionnelle.
4.4.1 Boucle for
À l’aide de la construction for c in range(n), on effectue un nombre d’itérations n donné.
Ainsi, si on reprend le programme de calcul de 2
n , on aura juste à écrire :
p = 1
for c in range(n):
p = 2 * p
Le compteur de boucle est ici entièrement géré par la boucle for. Il n’est pas besoin de
l’incrémenter, ni de tester qu’il ne dépasse pas une certaine limite.
Il reste possible d’utiliser ce compteur au sein du corps de la boucle. Dans la boucle
for c in range(n), la variable c parcourt les entiers de 0 à n − 1. On remarque que le paramètre passé à range est donc la valeur avant laquelle on s’arrête. Comme souvent en
informatique, on numérote à partir de 0.
Ainsi, si l’on souhaite calculer la factorielle d’un entier n, définie par les relations :
0! = 1
(n + 1)! = (n + 1) × n!