Algorithmique et programmation

On donne le programme Python suivant. Indiquer ce qu'il affiche, puis le réécrire avec une boucle `while` produisant le même résultat. ``` s = 0 for k in range(1, 5): s = s + k print(s) ```

1. 01Suivre la valeur de s tour par tour

   La variable `s` part de $0$ ; `k` prend successivement les valeurs $1, 2, 3, 4$ (range(1, 5) exclut $5$). À chaque tour on ajoute `k` à `s`.

   $$s : 0 \to 0{+}1{=}1 \to 1{+}2{=}3 \to 3{+}3{=}6 \to 6{+}4{=}10$$
2. 02Conclure l'affichage

   Après la boucle, `s` vaut $10$ : le programme calcule $1+2+3+4=10$ et affiche `10`.

   $$\sum_{k=1}^{4} k = \frac{4\times 5}{2} = 10$$
3. 03Réécrire avec une boucle while

   On introduit un compteur `k` initialisé à $1$, qu'on incrémente tant qu'il ne dépasse pas $4$ : ``` s = 0 k = 1 while k <= 4: s = s + k k = k + 1 print(s) ``` La condition `k <= 4` joue le rôle de la borne de `range`.

Résultat : Le programme affiche `10` ; la version `while` (compteur `k` de $1$ à $4$) donne le même résultat. Ici une boucle `for` est plus naturelle car le nombre de tours est connu.

Soit la suite définie par $u_n = \dfrac{1}{n+1}$ pour $n \ge 0$. 1. Écrire une fonction Python `u(n)` qui renvoie $u_n$. 2. Écrire une fonction `somme(N)` qui renvoie la somme $S_N = u_0 + u_1 + \dots + u_N$ à l'aide d'un accumulateur. 3. Donner la valeur affichée par `somme(3)`.

1. 01Définir la fonction u

   Le terme est explicite : on renvoie directement $\frac{1}{n+1}$. ``` def u(n): return 1 / (n + 1) ```

2. 02Construire la somme par accumulateur

   On initialise l'accumulateur `s = 0`, puis on ajoute `u(k)` pour `k` de $0$ à $N$ inclus (donc `range(N + 1)`). ``` def somme(N): s = 0 for k in range(N + 1): s = s + u(k) return s ```

   $$S_N = \sum_{k=0}^{N} \frac{1}{k+1}$$
3. 03Évaluer somme(3)

   On somme les quatre premiers termes $u_0, u_1, u_2, u_3$.

   $$S_3 = 1 + \tfrac{1}{2} + \tfrac{1}{3} + \tfrac{1}{4} = \tfrac{12+6+4+3}{12} = \tfrac{25}{12} \approx 2{,}083$$

Résultat : `u(n)` renvoie $\frac{1}{n+1}$, `somme(N)` cumule les termes par accumulateur, et `somme(3)` affiche $\frac{25}{12} \approx 2{,}083$.

Une espèce végétale invasive couvre une surface $S_0 = 12$ hectares et s'étend de $20\%$ par an : $S_{n+1} = 1{,}2\,S_n$. On souhaite connaître le nombre d'années au bout duquel la surface dépasse $50$ hectares. 1. Écrire une fonction Python `seuil()` qui renvoie ce nombre d'années. 2. Déterminer sa valeur par une trace, et justifier que ce seuil existe.

1. 01Écrire la fonction

   On part de la surface initiale et on multiplie par $1{,}2$ tant qu'on n'a pas dépassé $50$, en comptant les années. ``` def seuil(): S = 12 n = 0 while S <= 50: S = 1.2 * S n = n + 1 return n ```

2. 02Tracer les valeurs successives

   On suit $S$ jusqu'au premier dépassement de $50$.

   $$S: 12 \to 14{,}4 \to 17{,}3 \to 20{,}7 \to 24{,}9 \to 29{,}9 \to 35{,}8 \to 43{,}0 \to 51{,}6$$
3. 03Conclure et justifier

   Le seuil $50$ est franchi au $8^{\text{e}}$ tour ($S_8 \approx 51{,}6 > 50$), donc `seuil()` renvoie $8$. L'existence du seuil est garantie car $(S_n)$ est géométrique de raison $1{,}2 > 1$, donc $S_n = 12 \times 1{,}2^{\,n} \to +\infty$ : toute valeur, en particulier $50$, finit par être dépassée.

   $$S_n = 12 \times 1{,}2^{\,n} \xrightarrow[n\to+\infty]{} +\infty$$

Résultat : `seuil()` renvoie $8$ : il faut $8$ ans pour dépasser $50$ hectares. Le franchissement est certain car $1{,}2 > 1$ entraîne $S_n \to +\infty$.

On veut approcher $I = \displaystyle\int_0^1 x^2\,dx$ par la méthode des rectangles à gauche. 1. Écrire une fonction Python `rectangles(n)` qui renvoie l'approximation de $I$ avec $n$ rectangles. 2. Donner l'approximation obtenue pour $n = 4$. 3. Comparer à la valeur exacte et expliquer le sens de l'écart.

1. 01Écrire la fonction

   La largeur d'un rectangle est $h = \frac{1 - 0}{n}$ ; on accumule $h \times f(x_k)$ avec $f(x) = x^2$ et $x_k = k\,h$ pour $k$ de $0$ à $n-1$. ``` def rectangles(n): a, b = 0, 1 h = (b - a) / n s = 0 for k in range(n): x = a + k * h s = s + h x*2 return s ```

2. 02Calculer pour n = 4

   Avec $n = 4$, $h = 0{,}25$ et les abscisses $x_k = 0,\ 0{,}25,\ 0{,}5,\ 0{,}75$. On somme les aires $h \times x_k^2$.

   $$0{,}25\,(0^2 + 0{,}25^2 + 0{,}5^2 + 0{,}75^2) = 0{,}25\times 0{,}875 = 0{,}21875$$
3. 03Comparer à la valeur exacte

   La valeur exacte de l'intégrale est $\frac{1}{3} \approx 0{,}333$. L'approximation $0{,}21875$ est INFÉRIEURE : avec des rectangles à gauche et $f$ croissante, chaque rectangle est entièrement sous la courbe, d'où une SOUS-ESTIMATION qui se réduit quand $n$ grandit.

   $$\int_0^1 x^2\,dx = \left[\frac{x^3}{3}\right]_0^1 = \frac{1}{3} \approx 0{,}333$$

Résultat : `rectangles(4)` renvoie $0{,}21875$, valeur approchée par défaut de $\frac{1}{3} \approx 0{,}333$ ; l'écart vient des rectangles à gauche sous une fonction croissante (sous-estimation), et il diminue lorsque $n$ augmente.

On veut estimer la probabilité d'obtenir « au moins un $6$ » en lançant un dé équilibré $4$ fois. Un élève propose le programme suivant, qui renvoie un résultat manifestement trop faible. ``` from random import randint def estime(N): succes = 0 for i in range(N): six = False for j in range(4): if randint(1, 5) == 6: six = True if six: succes = succes + 1 return succes / N ``` 1. Repérer l'erreur. 2. Corriger le programme et commenter. 3. Donner la probabilité théorique pour valider l'ordre de grandeur attendu.

1. 01Repérer l'erreur

   Le tirage `randint(1, 5)` ne produit JAMAIS la valeur $6$ (les entiers tirés vont de $1$ à $5$ inclus). La condition `== 6` est donc toujours fausse, `six` reste `False`, et la fonction renvoie toujours $0$ : c'est pourquoi le résultat est trop faible (nul).

2. 02Corriger et commenter

   On simule un vrai dé à six faces avec `randint(1, 6)` (les deux bornes sont incluses) : ``` from random import randint def estime(N): succes = 0 for i in range(N): six = False for j in range(4): if randint(1, 6) == 6: # dé à 6 faces : borne haute = 6 six = True if six: succes = succes + 1 return succes / N ``` La correction porte sur la borne supérieure du `randint`, qui doit valoir $6$ pour qu'un $6$ puisse sortir.

3. 03Valider par le calcul théorique

   La probabilité de n'obtenir AUCUN $6$ sur $4$ lancers est $\left(\frac{5}{6}\right)^4$ ; donc « au moins un $6$ » a pour probabilité son complément.

   $$P(\text{au moins un } 6) = 1 - \left(\frac{5}{6}\right)^4 = 1 - \frac{625}{1296} \approx 0{,}518$$

Résultat : L'erreur était `randint(1, 5)` au lieu de `randint(1, 6)` (le $6$ ne pouvait jamais sortir). Après correction, la fréquence simulée pour $N$ grand approche la valeur théorique $1 - (5/6)^4 \approx 0{,}518$.