Algorithmique — boucles et recherche de seuil

Deux exercices type : lire et faire tourner un algorithme (boucle « pour »), puis écrire un algorithme de seuil (boucle « tant que »).

2 exercices corrigés

Exercice 1 — Lire et faire tourner un algorithme

Faire tourner un algorithme = suivre ses instructions pas à pas en notant l'évolution des variables (un tableau d'exécution évite les erreurs). On considère :

u\leftarrow5

; Pour

i

1

3

u\leftarrow2u+1

; Renvoyer

u

Faire tourner l'algorithme en donnant la valeur de $u$ après chaque passage dans la boucle.
Écrire un algorithme qui calcule et renvoie la somme $S=1+2+\cdots+n$ pour un entier $n$ donné.

Voir la correction

1. On note $u$ après chaque tour. Départ : $u=5$ . 1er tour : $u=2\times5+1=11$ . 2e : $u=2\times11+1=23$ . 3e : $u=2\times23+1=47$ . L'algorithme renvoie $u=47$ .

2. On accumule dans une variable $S$ initialisée à $0$ , puis on ajoute chaque entier : $S\leftarrow0$ ; Pour $k$ de $1$ à $n$ : $S\leftarrow S+k$ ; Renvoyer $S$ .

Le réflexe à retenir

Pour faire tourner, tiens un petit tableau des variables tour par tour : c'est infaillible. Pour sommer/compter, le patron est toujours : une variable accumulateur initialisée à $0$ (ou $1$ pour un produit), qu'on met à jour dans la boucle.

Exercice 2 — Recherche d'un seuil

Une boucle « tant que » répète tant qu'une condition est vraie : idéale quand on ne connaît pas d'avance le nombre d'étapes (problème de seuil).

On pose $u_0=1$ et $u_{n+1}=2u_n$ . Écrire un algorithme déterminant le plus petit entier $n$ tel que $u_n>1000$ .
Quelle valeur de $n$ l'algorithme renvoie-t-il ?

Voir la correction

1. On avance dans la suite tant qu'on n'a pas dépassé $1000$ , en comptant les étapes : $u\leftarrow1$ ; $n\leftarrow0$ ; Tant que $u\leqslant1000$ : $u\leftarrow2u$ ; $n\leftarrow n+1$ ; Renvoyer $n$ .

2. Ici $u_n=2^n$ . On cherche la première puissance de $2$ qui dépasse $1000$ : $2^9=512\leqslant1000$ mais $2^{10}=1024>1000$ . L'algorithme renvoie donc $n=10$ .

Le réflexe à retenir

Seuil ⇒ boucle « tant que » : on répète tant que la condition n'est pas atteinte, en incrémentant un compteur $n$ . À la sortie, $n$ est le premier rang qui franchit le seuil.