# Algorithmes du programme de Première : maths Première

Chapitre 3 du programme de mathématiques de Première (thème : Algorithmique et programmation). Ressource gratuite OptiTAB.

- Cours : https://www.optitab.net/ressources-gratuites/maths/premiere/algorithmes-du-programme-de-premiere/
- Fiche de révision : https://www.optitab.net/ressources-gratuites/maths/premiere/algorithmes-du-programme-de-premiere/fiche/
- Exercices corrigés : https://www.optitab.net/ressources-gratuites/maths/premiere/algorithmes-du-programme-de-premiere/exercices/

## Cours

**Objectifs : Écrire, lire et utiliser en Python les algorithmes du programme de Première : terme, somme et seuil d'une suite ; tableau de valeurs et balayage ; coefficients directeurs de sécantes ; méthode d'Euler et valeur approchée de $e$ ; approximation de $\pi$ ; simulation d'expériences aléatoires, fréquence et moyenne d'un échantillon.**

**Prerequis : Programme de Seconde : variables, fonctions `def`, instructions conditionnelles `if`, boucles `for` et `while`. Suites numériques, second degré, dérivation, fonction exponentielle et probabilités conditionnelles de Première.**

## I. Les outils

Les algorithmes de ce chapitre n'utilisent que des outils vus en Seconde. Ils sont rappelés ici ; le reste du chapitre les applique aux notions de Première.

**Rappel : Rappel de Seconde**
- `def f(x):` puis `return …` définit une fonction qui renvoie un résultat.
- `if condition:` … `else:` … exécute un bloc ou l'autre.
- `for k in range(n):` répète un bloc $n$ fois ; `k` prend les valeurs $0$, $1$, …, $n-1$. `range(a, b)` donne les entiers de $a$ à $b-1$.
- `while condition:` répète un bloc **tant que** la condition est vraie.
- Un **accumulateur** s'initialise **avant** la boucle : $0$ pour une somme, $1$ pour un produit, $0$ pour un compteur.

| Type d'algorithme | Boucle utilisée |
|---|---|
| terme de rang $n$, somme, factorielle, méthode d'Euler | `for` : nombre de tours connu |
| seuil, balayage | `while` : on répète tant que le but n'est pas atteint |
| simulation de $N$ expériences | `for` et un compteur |

## II. Suites numériques

### 1. Calculer un terme de rang donné

**Méthode : Terme d'une suite définie par récurrence**
Pour calculer $u_n$, on part de $u_0$ et on applique $n$ fois la relation de récurrence : c'est une boucle `for` de $n$ tours. La variable `k` ne sert qu'à compter les tours.

**Exemple : $u_0 = 0$ et $u_{n+1} = 0{,}5\,u_n + 2$**
```python
def terme(n):
    u = 0
    for k in range(n):
        u = 0.5 * u + 2
    return u

for n in range(6):
    print(n, terme(n))
```

```console
0 0
1 2.0
2 3.0
3 3.5
4 3.75
5 3.875
```

Le **tableau d'état** de l'appel `terme(3)` donne la valeur de `u` à la fin de chaque tour :

| Étape | `k` | `u` |
|---|---|---|
| avant la boucle | — | $0$ |
| tour 1 | $0$ | $0{,}5 \times 0 + 2 = 2$ |
| tour 2 | $1$ | $0{,}5 \times 2 + 2 = 3$ |
| tour 3 | $2$ | $0{,}5 \times 3 + 2 = 3{,}5$ |

**Remarque : Suite définie de façon explicite**
Si $u_n = f(n)$, aucune boucle n'est nécessaire : pour $u_n = 3n^2 + 1$, la fonction contient la seule ligne `return 3 * n**2 + 1`.

### 2. Somme de termes et factorielle

**Méthode : Somme $u_0 + u_1 + \dots + u_n$**
On fait avancer **ensemble** l'accumulateur `s` et le terme `u`. De $u_0$ à $u_n$, il y a $n+1$ termes : la boucle fait $n+1$ tours.

**Exemple : $1 + 2 + 2^2 + \dots + 2^{10}$**
Ici $u_0 = 1$ et $u_{k+1} = 2u_k$.

```python
def somme(n):
    s = 0
    u = 1
    for k in range(n + 1):
        s = s + u
        u = 2 * u
    return s

print(somme(10))
```

```console
2047
```

On retrouve la formule de la somme des termes d'une suite géométrique :

$$1 + 2 + \dots + 2^{10} = \frac{2^{11} - 1}{2 - 1} = 2047$$

**Exemple : Factorielle**
Pour $n \ge 1$, $n! = 1 \times 2 \times \dots \times n$. Un produit s'initialise à $1$.

```python
def factorielle(n):
    p = 1
    for k in range(1, n + 1):
        p = p * k
    return p

print(factorielle(10))
```

```console
3628800
```

### 3. Algorithme de seuil

**Méthode : Plus petit rang $n$ tel que $u_n \gt A$**
On calcule les termes un par un **tant que** le seuil n'est pas dépassé, en comptant les tours. La condition du `while` est le **contraire** de la condition cherchée : on veut $u_n \gt A$, on répète donc tant que $u \le A$. À la sortie, `n` est le rang cherché.

**Exemple : $u_0 = 2$, $u_{n+1} = 1{,}5\,u_n$ et le seuil $A = 50$**
```python
def seuil(A):
    n = 0
    u = 2
    while u <= A:
        u = 1.5 * u
        n = n + 1
    return n

print(seuil(50))
```

```console
8
```

En effet $u_7 = 2 \times 1{,}5^7 \approx 34{,}17 \le 50$ et $u_8 = 2 \times 1{,}5^8 \approx 51{,}26 \gt 50$.

![Termes de la suite u_n = 2 × 1,5^n et seuil 50 : u_7 ≈ 34,17 est sous le seuil, u_8 ≈ 51,26 le dépasse](https://optitab-media.s3.eu-north-1.amazonaws.com/cours_images/v1_n163_co151_1_suite_seuil.png)

**Attention : Condition du `while`**
Écrire `while u > A:` est une erreur classique : comme $u_0 = 2 \le 50$, la condition est fausse dès le départ, la boucle ne fait aucun tour et la fonction renvoie $0$.

### 4. Une suite qui ne dépasse jamais le seuil

Un algorithme de seuil ne s'arrête que si le seuil est **réellement dépassé** à partir d'un certain rang. Il faut le justifier avant de lancer le programme.

**Exemple : $u_0 = 0$ et $u_{n+1} = 0{,}5\,u_n + 2$**
```python
def seuil(A):
    n = 0
    u = 0
    while u <= A:
        u = 0.5 * u + 2
        n = n + 1
    return n

print(seuil(3.9))
```

```console
6
```

En revanche, l'appel `seuil(5)` ne se termine jamais. Posons $v_n = u_n - 4$ :

$$
\begin{aligned}
v_{n+1} &= u_{n+1} - 4 \\
&= 0{,}5\,u_n - 2 \\
&= 0{,}5\,(u_n - 4) \\
&= 0{,}5\,v_n
\end{aligned}
$$

La suite $(v_n)$ est géométrique de raison $0{,}5$ et de premier terme $v_0 = -4$, donc $u_n = 4 - 4 \times 0{,}5^n$. Ainsi $u_n \lt 4$ pour tout $n$ : la condition `u <= 5` reste toujours vraie et la boucle est **infinie**.

![Termes de la suite u_n = 4 − 4 × 0,5^n, tous inférieurs à 4 : le seuil 5 n'est jamais dépassé](https://optitab-media.s3.eu-north-1.amazonaws.com/cours_images/v1_n163_co151_2_suite_bornee.png)

**Conseil : Un garde-fou**
On peut limiter le nombre de tours en prenant pour condition `u <= A and n < 1000` ; après la boucle, on teste si le seuil a bien été dépassé avant de renvoyer `n`.

## III. Fonctions : tableau de valeurs et balayage

### 1. Tableau de valeurs

**Exemple : $f(x) = x^2 - 4x + 1$ pour $x$ entier de $-1$ à $5$**
```python
def f(x):
    return x**2 - 4*x + 1

for x in range(-1, 6):
    print(x, f(x))
```

```console
-1 6
0 1
1 -2
2 -3
3 -2
4 1
5 6
```

On lit le minimum $f(2) = -3$, qui est bien l'ordonnée du sommet car $f(x) = (x - 2)^2 - 3$. La fonction change de signe entre $0$ et $1$, puis entre $3$ et $4$ : chaque intervalle contient une solution de $f(x) = 0$.

### 2. Balayage

**Méthode : Encadrer une solution de $f(x) = 0$**
On part d'un nombre $a$ et on avance de `pas` en `pas` **tant que** $f$ garde le même signe. On obtient un encadrement d'amplitude `pas` de la solution.

**Exemple : Solution de $f(x) = 0$ dans $[0\,;1]$**
$f$ est strictement décroissante sur $[0\,;2]$, avec $f(0) = 1 \gt 0$ et $f(1) = -2 \lt 0$.

```python
def balayage(a, pas):
    x = a
    while f(x + pas) > 0:
        x = x + pas
    x = round(x, 6)
    return x, round(x + pas, 6)

print(balayage(0, 0.1))
print(balayage(0, 0.01))
print(balayage(0, 0.001))
```

```console
(0.2, 0.3)
(0.26, 0.27)
(0.267, 0.268)
```

La fonction `round(x, 6)` arrondit à $10^{-6}$ : elle efface les erreurs d'arrondi des nombres décimaux en machine (sans elle, Python afficherait par exemple `0.30000000000000004`).

**Vérification :** le discriminant de $x^2 - 4x + 1$ vaut $\Delta = 12$, d'où la solution $x_1 = 2 - \sqrt{3} \approx 0{,}2679$, qui appartient bien à $[0{,}267\,;0{,}268]$.

## IV. Dérivation : coefficients directeurs des sécantes

Le coefficient directeur de la sécante qui passe par les points de la courbe d'abscisses $x$ et $x + h$ est le taux de variation

$$\frac{f(x + h) - f(x)}{h}$$

Quand $h$ tend vers $0$, il tend vers le nombre dérivé $f'(x)$.

**Exemple : Liste des coefficients directeurs pour un pas donné**
Pour $f(x) = x^2$ et le pas $h = 0{,}1$ :

```python
def f(x):
    return x**2

h = 0.1
for x in range(4):
    t = (f(x + h) - f(x)) / h
    print(x, round(t, 6))
```

```console
0 0.1
1 2.1
2 4.1
3 6.1
```

En effet

$$\frac{(x + h)^2 - x^2}{h} = \frac{2xh + h^2}{h} = 2x + h$$

Chaque valeur dépasse $f'(x) = 2x$ de $h = 0{,}1$ : plus le pas est petit, plus la liste est proche des nombres dérivés.

## V. Fonction exponentielle

### 1. La méthode d'Euler

La fonction exponentielle est l'unique fonction $f$ dérivable sur $\mathbb{R}$ telle que $f' = f$ et $f(0) = 1$. Pour $h$ proche de $0$, l'approximation affine $f(x + h) \approx f(x) + h\,f'(x)$ donne

$$f(x + h) \approx f(x) + h\,f(x) = (1 + h)\,f(x)$$

**Méthode : Méthode d'Euler**
On part du point $(0\,;1)$ et, à chaque tour, on avance de $h$ en abscisse et on multiplie l'ordonnée par $1 + h$ :

$$x_{k+1} = x_k + h \qquad y_{k+1} = y_k + h\,y_k$$

Les points $(x_k\,;y_k)$ forment une ligne brisée proche de la courbe de la fonction exponentielle.

**Exemple : Pas $h = 0{,}25$ sur $[0\,;2]$**
```python
h = 0.25
x = 0
y = 1
for k in range(8):
    x = x + h
    y = y + h * y
    print(x, round(y, 4))
```

```console
0.25 1.25
0.5 1.5625
0.75 1.9531
1.0 2.4414
1.25 3.0518
1.5 3.8147
1.75 4.7684
2.0 5.9605
```

![Courbe de la fonction exponentielle sur 0 ; 2 et ligne brisée de la méthode d'Euler avec le pas 0,25, située sous la courbe](https://optitab-media.s3.eu-north-1.amazonaws.com/cours_images/v1_n163_co151_3_euler_cours.png)

**Remarque : La courbe de la fonction exponentielle est au-dessus de ses tangentes : la méthode d'Euler donne ici des valeurs par défaut ($5{,}96 \lt e^2 \approx 7{,}39$). L'écart diminue quand on choisit un pas plus petit.**

### 2. Valeur approchée de $e$

Avec $n$ pas de longueur $h = \dfrac{1}{n}$, on arrive en $x = 1$ ; l'ordonnée $y$ est multipliée $n$ fois par $1 + \dfrac{1}{n}$, donc elle vaut $\left(1 + \dfrac{1}{n}\right)^n$, valeur approchée de $e = \exp(1)$.

```python
for n in [10, 100, 1000, 10**6]:
    print(n, (1 + 1/n)**n)
```

```console
10 2.5937424601000023
100 2.7048138294215285
1000 2.7169239322355936
1000000 2.7182804690957534
```

On admet que ces valeurs se rapprochent de $e \approx 2{,}718\,28$, en restant inférieures à $e$.

**Attention : Les parenthèses**
`(1 + 1/n)**n` calcule $\left(1 + \frac{1}{n}\right)^n$. Sans les parenthèses, `1 + 1/n**n` calcule $1 + \frac{1}{n^n}$, qui est très proche de $1$.

## VI. Trigonométrie : approximation de $\pi$

Archimède encadre la longueur $2\pi$ d'un cercle de rayon $1$ par les périmètres de polygones réguliers. On présente ici les polygones **inscrits** dans le cercle.

**Propriété : Polygone inscrit**
Soit $c_n$ la longueur d'un côté du polygone régulier à $n$ côtés inscrit dans un cercle de rayon $1$. Son demi-périmètre $p_n = \dfrac{n\,c_n}{2}$ est inférieur à $\pi$, et

$$c_{2n} = \sqrt{2 - \sqrt{4 - c_n^2}}$$

![Hexagone régulier inscrit dans un cercle de centre O : sommets A et B, milieu I de AB, point C du cercle sur OI) et côtés AC et CB du polygone à 12 côtés](https://optitab-media.s3.eu-north-1.amazonaws.com/cours_images/v1_n163_co151_4_archimede.png)

**Démonstration : Soit $A$ et $B$ deux sommets consécutifs du polygone à $n$ côtés, $I$ le milieu de $[AB]$ et $C$ le point du cercle sur la demi-droite $[OI)$ : $[AC]$ est un côté du polygone à $2n$ côtés.**

Dans le triangle $OIA$ rectangle en $I$ :

$$
\begin{aligned}
OI^2 &= OA^2 - AI^2 \\
&= 1 - \frac{c_n^2}{4}
\end{aligned}
$$

donc $OI = \dfrac{\sqrt{4 - c_n^2}}{2}$.

Dans le triangle $AIC$ rectangle en $I$, avec $IC = 1 - OI$ :

$$
\begin{aligned}
AC^2 &= AI^2 + IC^2 \\
&= \frac{c_n^2}{4} + 1 - 2\,OI + OI^2 \\
&= \frac{c_n^2}{4} + 1 - \sqrt{4 - c_n^2} + 1 - \frac{c_n^2}{4} \\
&= 2 - \sqrt{4 - c_n^2}
\end{aligned}
$$

**Exemple : De l'hexagone au polygone à $96$ côtés**
L'hexagone régulier inscrit est formé de $6$ triangles équilatéraux : $c_6 = 1$ et $p_6 = 3$.

```python
from math import sqrt

n = 6
c = 1
for k in range(4):
    c = sqrt(2 - sqrt(4 - c**2))
    n = 2 * n
    print(n, n * c / 2)
```

```console
12 3.1058285412302498
24 3.132628613281237
48 3.139350203046872
96 3.14103195089053
```

Avec $96$ côtés, Archimède obtenait ainsi $3{,}1410 \lt \pi$. En utilisant aussi les polygones circonscrits, il prouvait que $\dfrac{223}{71} \lt \pi \lt \dfrac{22}{7}$.

## VII. Probabilités : simuler une expérience aléatoire

### 1. Les fonctions du module `random`

- `random()` renvoie un nombre réel au hasard dans $[0\,;1[$ : le test `random() < p` est vrai avec la probabilité $p$.
- `randint(a, b)` renvoie un entier au hasard entre $a$ et $b$ **inclus** : `randint(1, 6)` simule un dé équilibré.

Les résultats changent à chaque exécution ; les affichages de cette partie sont ceux d'une exécution.

### 2. Fréquence d'un événement

**Méthode : Calculer une fréquence**
On répète $N$ fois l'expérience avec une boucle `for`, on compte avec un compteur `c` les fois où l'événement est réalisé, puis on renvoie $\dfrac{c}{N}$.

**Exemple : Somme de deux dés égale à $7$**
```python
from random import randint

def frequence(N):
    c = 0
    for i in range(N):
        d1 = randint(1, 6)
        d2 = randint(1, 6)
        if d1 + d2 == 7:
            c = c + 1
    return c / N

print(frequence(10000))
```

```console
0.1642
```

Sur les $36$ issues équiprobables, $6$ donnent une somme égale à $7$ : la probabilité vaut $\dfrac{6}{36} = \dfrac{1}{6} \approx 0{,}167$. Pour $N$ grand, la fréquence observée en est proche.

**Exemple : Toutes les sommes : histogramme de $1000$ lancers**
La liste `eff` (voir la notion « Notion de liste ») compte les lancers de chaque somme $s$.

```python
from random import randint

N = 1000
eff = [0] * 13
for i in range(N):
    d1 = randint(1, 6)
    d2 = randint(1, 6)
    s = d1 + d2
    eff[s] = eff[s] + 1
for s in range(2, 13):
    print(s, eff[s])
```

```console
2 32
3 52
4 86
5 120
6 139
7 173
8 121
9 113
10 81
11 59
12 24
```

![Histogramme des fréquences observées des sommes de deux dés sur 1000 lancers, comparées aux probabilités théoriques](https://optitab-media.s3.eu-north-1.amazonaws.com/cours_images/v1_n163_co151_5_histo_des.png)

### 3. Moyenne d'un échantillon

**Exemple : Un jeu de dé**
On lance un dé équilibré : on gagne $4$ € avec un $6$, $1$ € avec un $4$ ou un $5$, et on perd $1$ € sinon. Le gain $X$ a pour espérance

$$
\begin{aligned}
E(X) &= 4 \times \frac{1}{6} + 1 \times \frac{2}{6} - 1 \times \frac{3}{6} \\
&= \frac{3}{6} = 0{,}5
\end{aligned}
$$

```python
from random import randint

def gain():
    d = randint(1, 6)
    if d == 6:
        return 4
    elif d >= 4:
        return 1
    else:
        return -1

def moyenne(n):
    s = 0
    for i in range(n):
        s = s + gain()
    return s / n

print(moyenne(10000))
```

```console
0.4776
```

La moyenne d'un échantillon de grande taille est proche de l'espérance $E(X) = 0{,}5$ ; elle change d'un échantillon à l'autre.

### 4. Succession de deux épreuves

**Exemple : Deux tirages sans remise**
Une urne contient $3$ boules rouges et $2$ vertes. On tire une boule, on ne la remet pas, puis on en tire une seconde. La composition de l'urne au second tirage dépend du premier.

![Arbre pondéré de deux tirages sans remise dans une urne de 3 boules rouges et 2 vertes, avec les probabilités des quatre issues](https://optitab-media.s3.eu-north-1.amazonaws.com/cours_images/v1_n163_co151_6_arbre_urne.png)

D'après l'arbre, la probabilité que les deux boules soient de la même couleur vaut

$$
\begin{aligned}
&\frac{3}{5} \times \frac{2}{4} + \frac{2}{5} \times \frac{1}{4} \\
&= \frac{6}{20} + \frac{2}{20} = 0{,}4
\end{aligned}
$$

La fonction `tirage(r, v)` simule un tirage dans une urne de `r` boules rouges et `v` vertes ; `experience()` enchaîne les deux épreuves.

```python
from random import random

def tirage(r, v):
    if random() < r / (r + v):
        return "R"
    return "V"

def experience():
    t1 = tirage(3, 2)
    if t1 == "R":
        t2 = tirage(2, 2)
    else:
        t2 = tirage(3, 1)
    return t1 + t2

N = 10000
c = 0
for i in range(N):
    e = experience()
    if e == "RR" or e == "VV":
        c = c + 1
print(c / N)
```

```console
0.406
```

La fréquence observée est proche de la probabilité $0{,}4$.

## VIII. Bilan

| Partie du programme | Algorithme | Structure |
|---|---|---|
| Suites | terme $u_n$, somme, factorielle | `for` |
| Suites | seuil | `while` (condition contraire) |
| Second degré, fonctions | tableau de valeurs, balayage | `for`, `while` |
| Dérivation | coefficients directeurs des sécantes | `for` |
| Exponentielle | méthode d'Euler, valeur approchée de $e$ | `for` |
| Trigonométrie | approximation de $\pi$ (Archimède) | `for` |
| Probabilités | fréquence, moyenne, deux épreuves | `for` et `random` |

**Attention : Pièges fréquents**
- `range(n)` va de $0$ à $n-1$ : la somme $u_0 + \dots + u_n$ demande `range(n + 1)`.
- L'accumulateur s'initialise **avant** la boucle ; un produit commence à $1$.
- Dans un algorithme de seuil, la condition du `while` est le **contraire** de la condition cherchée.
- Avant de chercher un seuil, on vérifie qu'il sera dépassé, sinon la boucle est infinie.
- Les nombres décimaux sont arrondis en machine : `round` rend l'affichage lisible.
- `randint(1, 6)` inclut $6$ ; une simulation donne un résultat différent à chaque exécution.

**À retenir : - Terme de rang $n$ : $n$ applications de la relation de récurrence (boucle `for`).**
- Seuil : boucle `while` et compteur, à condition que le seuil soit atteint.
- Balayage : on avance de `pas` en `pas` tant que $f$ garde le même signe.
- Sécantes : $\dfrac{f(x + h) - f(x)}{h}$ tend vers $f'(x)$ quand $h$ tend vers $0$.
- Euler : $y \leftarrow y + h\,y$ ; $\left(1 + \dfrac{1}{n}\right)^n$ tend vers $e$.
- Simulation : `random() < p` réalise un événement de probabilité $p$ ; fréquence $= \dfrac{c}{N}$.

Fiche de synthèse dans l'onglet Fiches !

## Fiche de révision

**Objectifs : L'essentiel des algorithmes à savoir écrire en Première : suites, fonctions, dérivation, exponentielle, approximation de $\pi$ et simulations.**

## I. Suites numériques

| Algorithme | Idée |
|---|---|
| terme $u_n$ | $n$ tours de `u = …` (relation de récurrence) |
| somme $u_0 + \dots + u_n$ | `s = s + u` puis terme suivant, `range(n + 1)` |
| factorielle $n!$ | `p = 1` puis `p = p * k` pour $k$ de $1$ à $n$ |
| seuil : premier $n$ tel que $u_n \gt A$ | `while u <= A:` et un compteur `n` |

```python
def seuil(A):
    n = 0
    u = 2
    while u <= A:
        u = 1.5 * u
        n = n + 1
    return n

print(seuil(50))
```

```console
8
```

![Termes de la suite u_n = 2 × 1,5^n et seuil 50 : le premier terme qui dépasse 50 est u_8](https://optitab-media.s3.eu-north-1.amazonaws.com/synthesis_images/v1_n163_fi61_1_suite_seuil.png)

**Attention : Seuil jamais atteint**
Si $u_n = 4 - 4 \times 0{,}5^n$, on a toujours $u_n \lt 4$ : avec le seuil $5$, la boucle `while u <= 5:` ne s'arrête jamais. On justifie d'abord que le seuil est dépassé.

## II. Fonctions et dérivation

- **Tableau de valeurs** : une boucle `for` sur `x`, et `print(x, f(x))` à chaque tour.
- **Balayage** : `while f(x + pas) > 0:` suivi de `x = x + pas` encadre une solution de $f(x) = 0$ (pour $f$ décroissante qui change de signe) entre `x` et `x + pas`.
- **Sécantes** : pour un pas $h$, on calcule les coefficients directeurs $\dfrac{f(x + h) - f(x)}{h}$, proches de $f'(x)$ quand $h$ est petit.

## III. Exponentielle et nombre $\pi$

- **Euler** ($f' = f$, $f(0) = 1$) : à chaque tour, `x = x + h` et `y = y + h * y`.
- **Nombre $e$** : $\left(1 + \dfrac{1}{n}\right)^n$ s'approche de $e \approx 2{,}718$ ; on écrit `(1 + 1/n)**n`.
- **Archimède** : à partir de l'hexagone ($c = 1$, $n = 6$), `c = sqrt(2 - sqrt(4 - c**2))` et `n = 2 * n` ; le demi-périmètre $\dfrac{n\,c}{2}$ s'approche de $\pi$ par valeurs inférieures.

![Méthode d'Euler avec le pas 0,25 comparée à la courbe de la fonction exponentielle sur 0 ; 2](https://optitab-media.s3.eu-north-1.amazonaws.com/synthesis_images/v1_n163_fi61_2_euler_cours.png)

## IV. Probabilités

| Instruction | Rôle |
|---|---|
| `random() < p` | événement de probabilité $p$ |
| `randint(1, 6)` | dé équilibré ($1$ et $6$ inclus) |
| compteur `c`, puis `c / N` | fréquence sur $N$ expériences |
| somme `s`, puis `s / n` | moyenne d'un échantillon de taille $n$ |

- Pour $N$ grand, la fréquence est proche de la probabilité et la moyenne de l'espérance.
- **Deux épreuves successives** : le résultat de la première fixe les conditions de la seconde (`if t1 == "R": …`), comme dans un arbre.

## V. Les pièges à éviter

**Attention : Les erreurs classiques**
1. `range(n)` s'arrête à $n - 1$ : de $u_0$ à $u_n$, il y a $n + 1$ termes.
2. Initialiser l'accumulateur dans la boucle, ou un produit à $0$.
3. Écrire la condition d'arrêt dans le `while` au lieu de la condition pour continuer.
4. Chercher un seuil que la suite n'atteint jamais : boucle infinie.
5. Oublier les parenthèses : `1 + 1/n**n` n'est pas $\left(1 + \frac{1}{n}\right)^n$.

## Exercices corrigés

### Exercice 1 : Calculer les termes d'une suite

On considère la suite $(u_n)$ définie par $u_0 = 5$ et, pour tout entier naturel $n$, $u_{n+1} = 2u_n - 3$.

1. Calculer $u_1$, $u_2$ et $u_3$.
2. Compléter la fonction suivante pour qu'elle renvoie le terme $u_n$.

```python
def terme(n):
    u = …
    for k in range(…):
        u = …
    return u
```

3. Écrire une boucle qui affiche $n$ et $u_n$ pour $n$ allant de $0$ à $5$. Donner l'affichage obtenu.
4. On pose $v_n = u_n - 3$. Montrer que la suite $(v_n)$ est géométrique, puis exprimer $u_n$ en fonction de $n$. Vérifier avec l'affichage de la question 3.

#### Correction détaillée

## Question 1 : Calculer $u_1$, $u_2$ et $u_3$

**Méthode : On applique la relation de récurrence avec $n = 0$, puis $n = 1$, puis $n = 2$ : chaque terme se calcule à partir du précédent.**

**Etape : Trois applications de la relation**
$$
\begin{aligned}
u_1 &= 2u_0 - 3 = 2 \times 5 - 3 = 7 \\
u_2 &= 2u_1 - 3 = 2 \times 7 - 3 = 11 \\
u_3 &= 2u_2 - 3 = 2 \times 11 - 3 = 19
\end{aligned}
$$

**Resultat : $u_1 = 7$, $u_2 = 11$ et $u_3 = 19$.**

## Question 2 : Compléter la fonction `terme`

**Méthode : On part de $u_0$ et on applique $n$ fois la relation de récurrence : une boucle `for` de $n$ tours.**

**Etape : Les trois trous**
- valeur de départ : `u = 5`, car $u_0 = 5$.
- nombre de tours : `range(n)`, qui fait exactement $n$ tours.
- relation de récurrence : `u = 2 * u - 3`.

**Etape : Fonction complète**
```python
def terme(n):
    u = 5
    for k in range(n):
        u = 2 * u - 3
    return u
```

**Etape : Tableau d'état de l'appel `terme(3)`**
| Étape | `k` | `u` |
|---|---|---|
| avant la boucle | — | $5$ |
| tour 1 | $0$ | $7$ |
| tour 2 | $1$ | $11$ |
| tour 3 | $2$ | $19$ |

On retrouve $u_3 = 19$.

**Attention : Avec `range(n + 1)`, la boucle ferait un tour de trop et la fonction renverrait $u_{n+1}$.**

**Resultat : `u = 5`, `range(n)` et `u = 2 * u - 3`.**

## Question 3 : Afficher les premiers termes

**Méthode : La variable `n` prend les valeurs $0$ à $5$, donc `range(6)` ; à chaque tour, on affiche `n` et `terme(n)`.**

**Etape : Programme et affichage**
```python
def terme(n):
    u = 5
    for k in range(n):
        u = 2 * u - 3
    return u

for n in range(6):
    print(n, terme(n))
```

```console
0 5
1 7
2 11
3 19
4 35
5 67
```

**Resultat : Les termes de $u_0$ à $u_5$ sont $5$, $7$, $11$, $19$, $35$ et $67$.**

## Question 4 : Formule explicite

**Méthode : On exprime $v_{n+1}$ en fonction de $v_n$ en remplaçant $u_{n+1}$ par $2u_n - 3$.**

**Etape : La suite $(v_n)$ est géométrique**
$$
\begin{aligned}
v_{n+1} &= u_{n+1} - 3 \\
&= 2u_n - 3 - 3 \\
&= 2u_n - 6 \\
&= 2(u_n - 3) \\
&= 2v_n
\end{aligned}
$$

$(v_n)$ est géométrique de raison $2$ et de premier terme $v_0 = u_0 - 3 = 2$.

**Etape : Expression de $u_n$**
$$v_n = 2 \times 2^n = 2^{n+1}$$

donc

$$u_n = v_n + 3 = 2^{n+1} + 3$$

**Etape : Vérification**
Pour $n = 5$ : $2^6 + 3 = 64 + 3 = 67$, comme dans l'affichage. De même $2^5 + 3 = 35$ pour $n = 4$.

**À retenir : Avec une formule explicite, la boucle devient inutile : la fonction peut renvoyer directement `2**(n + 1) + 3`.**

**Resultat : $(v_n)$ est géométrique de raison $2$ et, pour tout entier naturel $n$, $u_n = 2^{n+1} + 3$.**

#### Réponses

1. $u_1 = 7$, $u_2 = 11$, $u_3 = 19$.
2. `u = 5`, `range(n)` et `u = 2 * u - 3`.
3. Une boucle `for n in range(6)` qui affiche `n` et `terme(n)` donne $5$, $7$, $11$, $19$, $35$, $67$.
4. $v_{n+1} = 2v_n$ et $v_0 = 2$, donc $v_n = 2^{n+1}$ et $u_n = 2^{n+1} + 3$.

### Exercice 2 : Sommes de termes, factorielle et suite de Fibonacci

Les trois questions sont indépendantes.

1. On note $S = 1 + 3 + 5 + \dots + 99$ la somme des nombres impairs de $1$ à $99$.
   - a) Écrire un programme qui calcule $S$ à l'aide d'une boucle.
   - b) Retrouver le résultat avec la formule de la somme des termes d'une suite arithmétique.
2. Pour $n \ge 1$, on note $n! = 1 \times 2 \times \dots \times n$.
   - a) Écrire une fonction `factorielle(n)` et calculer $12!$.
   - b) Écrire un programme qui détermine le plus petit entier $n$ tel que $n! \gt 10^9$.
3. La suite de Fibonacci est définie par $F_0 = 0$, $F_1 = 1$ et $F_{n+2} = F_{n+1} + F_n$. Écrire un programme qui affiche les termes $F_0$ à $F_{10}$.

#### Correction détaillée

## Question 1 : Somme des nombres impairs de $1$ à $99$

**Méthode : Les nombres impairs s'écrivent $u_k = 2k + 1$. On ajoute les termes $u_0 = 1$ à $u_{49} = 99$ dans un accumulateur.**

**Etape : Compter les termes**
$2k + 1 = 99$ donne $k = 49$ : $k$ va de $0$ à $49$, il y a donc $50$ termes et la boucle est `for k in range(50)`.

**Etape : Programme et affichage**
```python
s = 0
for k in range(50):
    s = s + (2 * k + 1)
print(s)
```

```console
2500
```

**Etape : Vérification par la formule**
$(u_k)$ est arithmétique de raison $2$. La somme de termes consécutifs vaut « nombre de termes × (premier + dernier) ÷ 2 » :

$$S = 50 \times \frac{1 + 99}{2} = 2500$$

**Attention : Avec `range(49)`, le dernier terme $99$ serait oublié : de $u_0$ à $u_{49}$, il y a $50$ termes.**

**Resultat : $$S = 1 + 3 + \dots + 99 = 2500$$**

## Question 2 : Factorielle

**Méthode : Un produit s'initialise à $1$, puis on le multiplie par $k$ pour $k$ allant de $1$ à $n$.**

**Etape : a) Fonction et calcul de $12!$**
```python
def factorielle(n):
    p = 1
    for k in range(1, n + 1):
        p = p * k
    return p

print(factorielle(12))
```

```console
479001600
```

**Etape : b) Plus petit $n$ tel que $n! \gt 10^9$**
On ne sait pas combien de tours faire : boucle `while`. On fait avancer ensemble `n` et `p`, qui vaut $n!$, et on continue **tant que** $p \le 10^9$.

```python
n = 1
p = 1
while p <= 10**9:
    n = n + 1
    p = p * n
print(n, p)
```

```console
13 6227020800
```

**Etape : Vérification**
$12! = 479\,001\,600 \le 10^9$ et $13! = 6\,227\,020\,800 \gt 10^9$.

**Attention : Un accumulateur de produit initialisé à $0$ resterait nul : `p = 1` avant la boucle.**

**Resultat : $12! = 479\,001\,600$ ; le plus petit entier $n$ tel que $n! \gt 10^9$ est $n = 13$.**

## Question 3 : Suite de Fibonacci

**Méthode : Chaque terme dépend des **deux** précédents : on garde deux variables, `a` $= F_n$ et `b` $= F_{n+1}$, et une variable `c` pour calculer le terme suivant.**

**Etape : Programme et affichage**
```python
a = 0
b = 1
for k in range(11):
    print(a, end=" ")
    c = a + b
    a = b
    b = c
```

```console
0 1 1 2 3 5 8 13 21 34 55
```

`end=" "` affiche les termes sur une même ligne.

**Attention : L'ordre des affectations**
Sans la variable `c`, l'écriture `a = b` puis `b = a + b` est fausse : `a` a déjà pris sa nouvelle valeur.

```python
a = 0
b = 1
for k in range(6):
    print(a, end=" ")
    a = b
    b = a + b
```

```console
0 1 2 4 8 16
```

Ce programme affiche les puissances de $2$, pas la suite de Fibonacci.

**Resultat : $F_0$ à $F_{10}$ : $0$, $1$, $1$, $2$, $3$, $5$, $8$, $13$, $21$, $34$, $55$.**

#### Réponses

1. a) `s = 0` puis `s = s + (2 * k + 1)` pour `k` dans `range(50)` : $S = 2500$. b) $50 \times \dfrac{1 + 99}{2} = 2500$.
2. a) $12! = 479\,001\,600$. b) Boucle `while p <= 10**9` : $n = 13$, car $13! = 6\,227\,020\,800$.
3. $0$, $1$, $1$, $2$, $3$, $5$, $8$, $13$, $21$, $34$, $55$ (avec une variable intermédiaire `c`).

### Exercice 3 : Une suite qui ne dépasse jamais un seuil

On considère la suite $(u_n)$ définie par $u_0 = 1$ et $u_{n+1} = 0{,}8\,u_n + 3$, et la fonction Python suivante.

```python
def seuil(A):
    n = 0
    u = 1
    while u <= A:
        u = 0.8 * u + 3
        n = n + 1
    return n
```

Le graphique donne les termes $u_0$ à $u_{20}$.

![Termes u_0 à u_20 de la suite définie par u_0 = 1 et u_(n+1) = 0,8 u_n + 3](https://optitab-media.s3.eu-north-1.amazonaws.com/exercice_images/v1_n163_ex1061_1_bornee_enonce.png)

1. Calculer $u_1$ et $u_2$.
2. Que renvoie l'appel `seuil(14)` ? Interpréter ce résultat.
3. On pose $v_n = u_n - 15$. Montrer que $(v_n)$ est géométrique, puis que $u_n = 15 - 14 \times 0{,}8^n$.
4. Expliquer pourquoi l'appel `seuil(16)` ne se termine jamais. Pour quelles valeurs de $A$ l'appel `seuil(A)` se termine-t-il ?
5. Modifier la fonction pour qu'elle fasse au plus $1000$ tours et renvoie `None` si le seuil n'est pas dépassé.

#### Correction détaillée

## Question 1 : Calculer $u_1$ et $u_2$

**Méthode : On applique la relation de récurrence avec $n = 0$ puis $n = 1$.**

**Etape : Calculs**
$$
\begin{aligned}
u_1 &= 0{,}8 \times 1 + 3 = 3{,}8 \\
u_2 &= 0{,}8 \times 3{,}8 + 3 = 6{,}04
\end{aligned}
$$

**Resultat : $u_1 = 3{,}8$ et $u_2 = 6{,}04$.**

## Question 2 : L'appel `seuil(14)`

**Méthode : La boucle s'arrête au premier rang $n$ tel que $u_n \gt 14$ : la fonction renvoie ce rang.**

**Etape : Exécution**
```python
def seuil(A):
    n = 0
    u = 1
    while u <= A:
        u = 0.8 * u + 3
        n = n + 1
    return n

print(seuil(14))
```

```console
12
```

**Etape : Vérification avec la formule de la question 3**
$u_{11} = 15 - 14 \times 0{,}8^{11} \approx 13{,}80 \le 14$ et $u_{12} = 15 - 14 \times 0{,}8^{12} \approx 14{,}04 \gt 14$.

**Resultat : `seuil(14)` renvoie $12$ : $u_{12}$ est le premier terme strictement supérieur à $14$.**

## Question 3 : Une suite géométrique auxiliaire

**Méthode : On exprime $v_{n+1}$ en fonction de $v_n$, puis on revient à $u_n = v_n + 15$.**

**Etape : $(v_n)$ est géométrique**
$$
\begin{aligned}
v_{n+1} &= u_{n+1} - 15 \\
&= 0{,}8\,u_n + 3 - 15 \\
&= 0{,}8\,u_n - 12 \\
&= 0{,}8\,(u_n - 15) \\
&= 0{,}8\,v_n
\end{aligned}
$$

$(v_n)$ est géométrique de raison $0{,}8$ et de premier terme $v_0 = 1 - 15 = -14$.

**Etape : Expression de $u_n$**
$$v_n = -14 \times 0{,}8^n$$

donc

$$u_n = 15 - 14 \times 0{,}8^n$$

**Resultat : Pour tout entier naturel $n$, $u_n = 15 - 14 \times 0{,}8^n$.**

## Question 4 : Quand la boucle s'arrête-t-elle ?

**Méthode : La boucle ne s'arrête que si la condition `u <= A` devient fausse, c'est-à-dire si un terme dépasse $A$.**

**Etape : Le cas $A = 16$**
Pour tout $n$, $14 \times 0{,}8^n \gt 0$, donc $u_n = 15 - 14 \times 0{,}8^n \lt 15$. Ainsi $u_n \lt 16$ : la condition `u <= 16` reste toujours vraie et la boucle est infinie.

![Termes de la suite tous inférieurs à 15 : la droite y = 15 n'est jamais atteinte et le seuil 16 n'est jamais dépassé](https://optitab-media.s3.eu-north-1.amazonaws.com/exercice_images/v1_n163_ex1061_2_bornee_corrige.png)

**Etape : Le cas général**
- Si $A \ge 15$ : tous les termes sont inférieurs à $15$, donc à $A$ ; la boucle est infinie.
- Si $A \lt 15$ : $u_n \gt A$ équivaut à $14 \times 0{,}8^n \lt 15 - A$. Comme $0{,}8^n$ devient aussi proche de $0$ que l'on veut (on l'admet), cette inégalité finit par être vraie : la boucle s'arrête.

**Attention : Un graphique ou un tableau de valeurs ne suffit pas : les termes « semblent » pouvoir dépasser $15$. Seule la formule $u_n = 15 - 14 \times 0{,}8^n$ prouve que $15$ n'est jamais atteint.**

**Resultat : `seuil(16)` ne se termine pas car $u_n \lt 15$ pour tout $n$. L'appel `seuil(A)` se termine si et seulement si $A \lt 15$.**

## Question 5 : Un garde-fou

**Méthode : On ajoute à la condition du `while` une limite sur le nombre de tours, puis on teste à la sortie si le seuil a bien été dépassé.**

**Etape : Programme et affichage**
```python
def seuil(A):
    n = 0
    u = 1
    while u <= A and n < 1000:
        u = 0.8 * u + 3
        n = n + 1
    if u > A:
        return n
    return None

print(seuil(14))
print(seuil(16))
```

```console
12
None
```

**Resultat : Avec la condition `u <= A and n < 1000`, la fonction s'arrête toujours : elle renvoie $12$ pour $A = 14$ et `None` pour $A = 16$.**

#### Réponses

1. $u_1 = 3{,}8$ et $u_2 = 6{,}04$.
2. `seuil(14)` renvoie $12$ : $u_{12} \approx 14{,}04$ est le premier terme supérieur à $14$.
3. $v_{n+1} = 0{,}8\,v_n$ et $v_0 = -14$, donc $u_n = 15 - 14 \times 0{,}8^n$.
4. $u_n \lt 15 \lt 16$ pour tout $n$ : la boucle est infinie. `seuil(A)` se termine si et seulement si $A \lt 15$.
5. Condition `while u <= A and n < 1000:`, puis `return n` si `u > A`, sinon `return None`.
