Livre_silo 30 août 2013 16:32 Page 98
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
98
Informatique pour tous
Exercice 4.19 Déterminer le rang du dernier terme strictement positif de la suite récurrente définie par
u n+1 =
1
2
un − 3n, la valeur de u 0 étant donnée dans la variable u_0.
On utilisera dans ce programme les variables n pour le rang courant et u pour la valeur de un.
1 Le calcul des termes un devra s’arrêter dès que un ⩽ 0 ; en prenant la négation de cette expression et
en la traduisant avec les variables du programme, on trouve la condition u > 0.
2 Le corps de la boucle consiste simplement à calculer la valeur de u n+1 à partir de celle de un et à
mettre à jour le rang. Les deux lignes ci-après ne doivent pas être interchangées sinon la formule de
récurrence n’est pas correctement traduite.
u = 0.5*u - 3*n
n = n + 1
La variable u étant modifiée, la valeur de la condition u > 0 pourra changer au cours de l’exécution de
la boucle.
3 En amont de la boucle, il faut initialiser les variables u et n.
u = u_0
n = 0
4 Enfin, à la sortie de la boucle, on a atteint le premier terme un négatif ou nul, mais il était demandé le
rang du dernier terme strictement positif. Il faut donc « revenir en arrière » d’un rang.
n = n - 1
Voici le programme complet :
u = u_0
n = 0
while u > 0:
u = 0.5*u - 3*n
n = n + 1
n = n - 1
4.3.3 Terminaison de boucle
Compteur
Dans le programme précédent, on remarque que la variable c joue le rôle d’un compteur.
Au départ, c contient le nombre d’itérations à effectuer. Après chaque itération, on enlève
un à ce nombre. La condition d’arrêt de la boucle teste si les n itérations ont été faites.
Mathématiquement, il est garanti que l’on sorte de la boucle car :
• la valeur de c est un entier strictement positif ;
• elle décroît strictement après chaque itération.
Comme il n’ existe pas de suite infinie strictement décroissante d’entiers naturels, il ne peut
y avoir qu’un nombre fini d’itérations.
Exemple de la division euclidienne
Il n’ est pas nécessaire d’avoir une variable du type compteur de boucle. Il suffit qu’une
quantité vérifie bien ces deux propriétés : être un entier positif tout au long de l’algorithme
et décroître strictement après chaque itération. On appelle cette quantité un variant de
boucle.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
98
Informatique pour tous
Exercice 4.19 Déterminer le rang du dernier terme strictement positif de la suite récurrente définie par
u n+1 =
1
2
un − 3n, la valeur de u 0 étant donnée dans la variable u_0.
On utilisera dans ce programme les variables n pour le rang courant et u pour la valeur de un.
1 Le calcul des termes un devra s’arrêter dès que un ⩽ 0 ; en prenant la négation de cette expression et
en la traduisant avec les variables du programme, on trouve la condition u > 0.
2 Le corps de la boucle consiste simplement à calculer la valeur de u n+1 à partir de celle de un et à
mettre à jour le rang. Les deux lignes ci-après ne doivent pas être interchangées sinon la formule de
récurrence n’est pas correctement traduite.
u = 0.5*u - 3*n
n = n + 1
La variable u étant modifiée, la valeur de la condition u > 0 pourra changer au cours de l’exécution de
la boucle.
3 En amont de la boucle, il faut initialiser les variables u et n.
u = u_0
n = 0
4 Enfin, à la sortie de la boucle, on a atteint le premier terme un négatif ou nul, mais il était demandé le
rang du dernier terme strictement positif. Il faut donc « revenir en arrière » d’un rang.
n = n - 1
Voici le programme complet :
u = u_0
n = 0
while u > 0:
u = 0.5*u - 3*n
n = n + 1
n = n - 1
4.3.3 Terminaison de boucle
Compteur
Dans le programme précédent, on remarque que la variable c joue le rôle d’un compteur.
Au départ, c contient le nombre d’itérations à effectuer. Après chaque itération, on enlève
un à ce nombre. La condition d’arrêt de la boucle teste si les n itérations ont été faites.
Mathématiquement, il est garanti que l’on sorte de la boucle car :
• la valeur de c est un entier strictement positif ;
• elle décroît strictement après chaque itération.
Comme il n’ existe pas de suite infinie strictement décroissante d’entiers naturels, il ne peut
y avoir qu’un nombre fini d’itérations.
Exemple de la division euclidienne
Il n’ est pas nécessaire d’avoir une variable du type compteur de boucle. Il suffit qu’une
quantité vérifie bien ces deux propriétés : être un entier positif tout au long de l’algorithme
et décroître strictement après chaque itération. On appelle cette quantité un variant de
boucle.