Algorithmes
Exercice 3
Dans cet exercice, toute trace de recherche, même non aboutie, serait prise en compte lors de la notation
Soit $(u_n)$ la suite définie:
par la relation de récurrence $u_{n+1}=0,5×u_n$
et par son premier terme $u_0=100$.
On considère un programme associé à l'algorithme suivant:
Lire $N$
$U$ ← 0,5
Pour $I$ allant de 1 à $ N$
$U$ ← $100×U$
Fin du Pour
Afficher $N$
1.a. Modifier 3 lignes de cet algorithme pour qu'il permette d'obtenir la valeur de $u_n$ pour tout entier naturel $n$ saisi par l'utilisateur.
1.b. Ecrire en Python un programme correspondant à cet algorithme modifié.
2. On définit la somme $S_n=u_0+u_1+u_2+...+u_n$ pour tout entier naturel $n$.
On note que $S_0=100$, $S_1=150$, $S_2=175$, ...etc...
On cherche un algorithme permettant d'obtenir la valeur de la somme $S_n$ pour tout entier naturel $n$.
Parmi les 3 algorithmes suivants, un seul convient.
Lequel est-ce? (inutile de justifier)
Expliquer pourquoi les 2 autres algorithmes ne conviennent pas.
Lire $N$
$S$ ← 0
$U$ ← 100
$I$ ← 0
Tant que $I≤N$
$S$ ← $S+U$
$U$ ← $0,5×U$
$I$ ← $I+1$
Fin du Pour
Afficher $S$
Lire $N$
$S$ ← 0
$U$ ← 100
$I$ ← 0
Tant que $I≤N$
$U$ ← $0,5×U$
$S$ ← $S+U$
$I$ ← $I+1$
Fin du Pour
Afficher $S$
Lire $N$
$U$ ← 100
$I$ ← 0
Tant que $I≤N$
$U$ ← $U+0,5×U$
$I$ ← $I+1$
Fin du Pour
Afficher $U$
3. Proposer l'algorithme d'un programme qui ne contient pas de boucle, et qui permet d'obtenir la valeur de $S_n=u_0+u_1+u_2+...+u_n$ pour tout entier naturel $n$ saisi par l'utilisateur.
Solution...
Corrigé
1.a. Algorithme modifié:
Lire $N$
$U$ ← 100 (Noter le 100 à la place de 0,5)
Pour $I$ allant de 1 à $ N$
$U$ ← $0,5×U$ (Noter le 0,5 à la place de 100)
Fin du Pour
Afficher $U$ (Noter le $U$ à la place de $N$)
1.b. Voici un programme correct.
Dans la ligne 4, range(1,n+1) est une liste contenant les entiers de 1 à n.
Voici un second programme produisant les mêmes valeurs de u.
Mais l'entier i prend ici les valeurs de 0 à n-1.
Ce n'est pas gênant car, comme dans le premier programme, la boucle for sera parcourue n fois.
2. L'algorithme correct est le premier.
Le second algorithme ne convient pas, car, par exemple, pour $N=0$, il devrait afficher 100, mais il affichera 50.
Le troisième algorithme ne convient pas, car,par exemple, pour $N=0$, il devrait afficher 100, mais il affichera 150.
3. Il est clair que la suite $(u_n)$ est géométrique de raison 0,5 et de premier terme $u_0=100$.
On obtient donc la formule explicite:
$S_n=u_0+u_1+u_2+...+u_n=100×{1-0,5^{n+1}}/{1-0,5}={100}/{0,5}×(1-0,5^{n+1})=200×(1-0,5^{n+1})$
et cette égalité est valide pour tout entier naturel $n$.
D'où l'algorithme suivant:
Lire $N$
$S$ ← $200×(1-0,5^{N+1})$
Afficher $S$