Livre_silo 30 août 2013 16:32 Page 99
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
99
4 – Instructions : langage minimal de l’algorithmique
Pour illustrer cela, on considère maintenant un programme réalisant l’algorithme usuel de
division euclidienne pour des entiers naturels. Ici, l’état initial contient deux variables n et d
et, à l’issue de l’exécution, on souhaite que les deux variables q et r contiennent le quotient
et le reste dans la division euclidienne de la valeur de n par la valeur de d.
q = 0
r = n
while r >= d:
q = q + 1
r = r - d
On va détailler l’exécution de ce programme à partir de l’état
. .
17 .
n
. .
4 .
d
. On omet ces
deux variables, qui ne sont pas modifiées.
• Avant la première itération :
. .
0 .
q
. .
17 .
r
• Après la première itération :
. .
1 .
q
. .
13 .
r
• Après la deuxième itération :
. .
2 .
q
. .
9 .
r
• Après la troisième itération :
. .
3 .
q
. .
5 .
r
• Après la quatrième itération :
. .
4 .
q
. .
1 .
r
Ici, si la valeur de d est un entier strictement positif, la variable r reste positive tout au long
de l’algorithme et, après chaque itération, elle diminue de la valeur de d, donc elle décroît
strictement. Ainsi ce programme se termine-t-il.
Cas où l’expression qui décroît n’est pas une variable
On considère le programme suivant :
c = 0
while p > 0:
if c == 0:
p = p - 2
c = 1
else:
p = p + 1
c = 0