Algorithmes
A SAVOIR: le cours sur les algorithmes
Exercice 2
Dans cet exercice, toute trace de recherche, même non aboutie, serait prise en compte lors de la notation
On considère un programme associé à l'algorithme suivant:
Lire $N$
$U$ ← 4
Pour $I$ allant de 0 à $ N-1$
$U$ ← $3×U$
Fin du Pour
Afficher $U$
1. Donner les valeurs successives prises par $I$ et $U$ lorsque le programme fonctionne pour une valeur de $N$ égale à 2.
2. Définir une suite $(u_n)$ pour laquelle ce programme présente un intérêt.
Préciser l'utilité de ce programme relativement à la suite proposée.
3. Parmi les 3 algorithmes suivants, un seul est équivalent à l'algorithme initial
Lequel est-ce? (inutile de justifier)
Expliquer pourquoi les 2 autres algorithmes ne conviennent pas.
Lire $N$
$U$ ← 4
$I$ ← 0
Tant que $I≤N$
$U$ ← $3×U$
$I$ ← $I$+1
Fin du Pour
Afficher $U$
Lire $N$
$U$ ← 4
$I$ ← 0
Tant que $I$<$N$
$U$ ← $3×U$
$I$ ← $I$+1
Fin du Pour
Afficher $U$
Lire $N$
$U$ ← 4
$I$ ← 0
Tant que $I$<$N$
$U$ ← $3×U$
Fin du Pour
Afficher $U$
4. Proposer l'algorithme d'un programme qui ne contient pas de boucle, et qui permet d'obtenir la valeur de $u_n$ pour tout entier naturel $n$ saisi par l'utilisateur.
Solution...
Corrigé
1. $N=2$; $U=4$.
Juste avant la première boucle: $I=0$
Première boucle: (on a bien $I≤1$); $U=3×4=12$;
Fin de la première boucle; $I$ est augmenté automatiquement de 1, et vaut donc 1.
Seconde boucle: (on a bien $I≤1$); $U=3×12=36$;
Fin de la seconde boucle; $I$ est augmenté automatiquement de 1, et vaut donc 2.
Il n'y a pas de troisième boucle car $I>1$.
Finalement, il s'affiche la valeur de $U$, c'est à dire 36.
2. Une suite convenable est la suite $(u_n)$ définie par:
la relation de récurrence $u_{n+1}=3×u_n$
et son premier terme $u_0=4$.
Notons ici que la suite $(u_n)$ est géométrique de raison 3.
On obtient facilement $u_1=12$ et $u_2=36$.
Le programme proposé demande à l'utilisateur de saisir une valeur de $n$ et affiche alors la valeur de $u_n$ correspondante.
Par exemple, pour $n=2$, le programme renvoie la valeur de $u_2$, c'est à dire 36.
3. L'algorithme correct est le second.
Le premier algorithme ne convient pas, car, par exemple, pour $N=0$, il devrait afficher 4, mais il affichera 12 (car la première boucle va s'effectuer).
Le troisième algorithme ne convient pas, car, par exemple, pour $N=1$, les boucles vont s'enchaîner sans jamais s'arrêter, car $I$ reste constamment à 0, et par là, la condition $I$<$N$ est toujours vérifiée!
4. On a vu au 2. que la suite $(u_n)$ est géométrique de raison 3 et de premier terme $u_0=4$.
On obtient donc la formule explicite: $u_n=4×3^n$, valide pour tout entier naturel $n$.
D'où l'algorithme suivant:
Lire $N$
$U$ ← $4×3^N$
Afficher $U$