Livre_silo 30 août 2013 16:32 Page 100
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
100
Informatique pour tous
Partant de l’état initial
. .
5 .
p
, on obtient successivement les états suivants :
1
. .
0 .
c
. .
5 .
p
2
. .
1 .
c
. .
3 .
p
3
. .
0 .
c
. .
4 .
p
4
. .
1 .
c
. .
2 .
p
5
. .
0 .
c
. .
3 .
p
6
. .
1 .
c
. .
1 .
p
7
. .
0 .
c
. .
2 .
p
8
. .
1 .
c
. .
0 .
p
On note p i et c i les valeurs des variables p et c après l’itération i.
On considère alors l’expression 2p i +3c i . Comme p i et c i sont toujours des entiers naturels,
cette expression est bien un entier naturel. On étudie l’effet de la i + 1-ème itération sur
l’état.
• Si c i = 0 alors p i+1 = p i − 2 et c i+1 = 1, d’où
2p i+1 + 3c i+1 = 2p i − 4 + 3 = 2p i − 1 < 2p i = 2p i + 3c i
• Sinon, on a c i = 1, p i+1 = p i + 1 et c i+1 = 0. Ici encore, on a
2p i+1 + 3c i+1 = 2p i + 2 < 2p i + 3 = 2p i + 3c i
Dans tous les cas, la quantité 2p i + 3c i diminue strictement à chaque itération et ainsi la
boucle se termine.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
100
Informatique pour tous
Partant de l’état initial
. .
5 .
p
, on obtient successivement les états suivants :
1
. .
0 .
c
. .
5 .
p
2
. .
1 .
c
. .
3 .
p
3
. .
0 .
c
. .
4 .
p
4
. .
1 .
c
. .
2 .
p
5
. .
0 .
c
. .
3 .
p
6
. .
1 .
c
. .
1 .
p
7
. .
0 .
c
. .
2 .
p
8
. .
1 .
c
. .
0 .
p
On note p i et c i les valeurs des variables p et c après l’itération i.
On considère alors l’expression 2p i +3c i . Comme p i et c i sont toujours des entiers naturels,
cette expression est bien un entier naturel. On étudie l’effet de la i + 1-ème itération sur
l’état.
• Si c i = 0 alors p i+1 = p i − 2 et c i+1 = 1, d’où
2p i+1 + 3c i+1 = 2p i − 4 + 3 = 2p i − 1 < 2p i = 2p i + 3c i
• Sinon, on a c i = 1, p i+1 = p i + 1 et c i+1 = 0. Ici encore, on a
2p i+1 + 3c i+1 = 2p i + 2 < 2p i + 3 = 2p i + 3c i
Dans tous les cas, la quantité 2p i + 3c i diminue strictement à chaque itération et ainsi la
boucle se termine.