Problèmes sur l'algorithmique en première

Trois programmes à lire, à corriger ou à écrire - sur une suite, sur une série de relevés, sur un tableau de valeurs. Dans les trois cas, la question mathématique précède la question informatique : c'est elle qui dicte la structure du programme.

Lire un programme et prévoir son résultat sans l'exécuter.
Générer une liste en extension, par ajouts successifs ou en compréhension.
Choisir entre une boucle bornée et une boucle non bornée.
Découper un traitement en fonctions.

Le seuil de population

Une population de $1 \ 200$ individus augmente de $4 \ \%$ par an. On cherche l'année où elle dépassera $2 \ 000$.

Écrire la relation de récurrence liant $u_{n+1}$ à $u_n$.

$$ u_{n+1} = 1.04 \, u_n \hspace{2em} u_0 = 1 \ 200 $$

Compléter ce programme pour qu'il affiche le nombre d'années nécessaires.

u = ...
n = 0
while u <= ... :
    u = ...
    n = n + 1
print(n)

u = 1200
n = 0
while u <= 2000:
    u = 1.04 * u
    n = n + 1
print(n)

Le programme affiche $14$. Vérifier par un calcul.

$$ u_{13} = 1 \ 200 \times 1.04^{13} \approx 1 \ 998 $$

$$ u_{14} = 1 \ 200 \times 1.04^{14} \approx 2 \ 078 $$

$$ \text{le seuil est franchi la } 14^{\text{ème}} \text{ année} $$
Pourquoi une boucle $\text{for}$ ne conviendrait-elle pas ici ?

Une boucle $\text{for}$ exige de connaître à l'avance le nombre de tours. Or c'est précisément ce nombre que l'on cherche : la boucle non bornée est la seule adaptée.

Les relevés de température

Une station enregistre les températures d'une semaine dans une liste :

T = [12, 15, 9, 18, 21, 17, 11]

Donner $T[0]$, $T[-1]$ et $\text{len}(T)$.

$$ T[0] = 12 \hspace{2em} T[-1] = 11 \hspace{2em} \text{len}(T) = 7 $$
Écrire une fonction qui renvoie la moyenne des relevés.
```
def moyenne(L):
    return sum(L) / len(L)
```
Ici la moyenne vaut $\frac{103}{7} \approx 14.7 \ °\text{C}$.
Écrire, en compréhension, la liste des jours où la température a dépassé $15 \ °\text{C}$.
```
C = [t for t in T if t > 15]
```
$$ C = [18, \ 21, \ 17] $$
Écrire un programme qui compte les jours où la température a augmenté par rapport à la veille.
```
c = 0
for i in range(1, len(T)):
    if T[i] > T[i - 1]:
        c = c + 1
print(c)
```
Le parcours doit se faire par indice, puisqu'on compare chaque élément à son voisin. Le programme affiche $3$.

Le programme qui se trompe

Un élève veut construire la liste des dix premiers carrés, mais son programme échoue :

L = []
for k in range(10):
    L[k] = k * k
print(L)

Expliquer pourquoi ce programme provoque une erreur.

La liste $L$ est vide : l'indice $0$ n'existe pas encore. On ne peut modifier que des cases déjà créées, et l'écriture $L[k] = \dots$ suppose qu'elles le soient.
Corriger le programme de deux façons différentes.
Par ajouts :
```
L = []
for k in range(10):
    L.append(k * k)
```
En compréhension :
```
L = [k * k for k in range(10)]
```
Que contient la liste obtenue ? Donner son dernier élément et son indice.

$$ L = [0, \ 1, \ 4, \ 9, \ 16, \ 25, \ 36, \ 49, \ 64, \ 81] $$

Le dernier élément vaut $81$, et son indice est $9$ - pas $10$.
Modifier la compréhension pour ne garder que les carrés pairs.
```
L = [k * k for k in range(10) if k % 2 == 0]
```
$$ L = [0, \ 4, \ 16, \ 36, \ 64] $$

La corde du maçon

Un maçon trace ses angles droits avec une corde de $60 \ \text{m}$, marquée d'un nœud tous les mètres. Il la tend entre trois piquets, sans la couper ni la laisser mollir : les trois côtés du triangle comptent donc un nombre entier de mètres, et leur somme vaut $60$. Il cherche tous les triangles rectangles qu'il peut obtenir ainsi.

Compléter ce programme, qui affiche les triangles cherchés sous la forme $a$, $b$, $c$ avec $a < b < c$.
```
for a in range(1, 60):
    for b in range(..., 60):
        c = ...
        if c > b and ... :
            print(a, b, c)
```
```
for a in range(1, 60):
    for b in range(a + 1, 60):
        c = 60 - a - b
        if c > b and a * a + b * b == c * c:
            print(a, b, c)
```
Le programme affiche deux lignes :

$$ 10 \ ; \ 24 \ ; \ 26 \hspace{2em} \text{et} \hspace{2em} 15 \ ; \ 20 \ ; \ 25 $$

Vérification : $10 + 24 + 26 = 60$ et $100 + 576 = 676 = 26^2$ ; $15 + 20 + 25 = 60$ et $225 + 400 = 625 = 25^2$.
Expliquer pourquoi la seconde boucle part de $a + 1$, pourquoi une troisième boucle serait inutile, et ce que garantit la condition $c > b$.

Faire partir $b$ de $a + 1$ impose $a < b$ : sans cela, le même triangle serait affiché plusieurs fois, une fois par ordre possible de ses côtés.

Le périmètre fixe le troisième côté : une fois $a$ et $b$ choisis, $c$ se calcule, il ne se cherche pas. Une troisième boucle parcourrait donc $60$ valeurs pour n'en retenir qu'une.

La condition $c > b$ fait de $c$ le plus grand côté, donc l'hypoténuse : c'est bien $a^2 + b^2 = c^2$ qu'il faut tester, et pas une autre égalité. Elle écarte aussi les valeurs négatives ou nulles de $c$.

L'inégalité triangulaire, elle, n'a pas à être testée : si $a^2 + b^2 = c^2$ avec $a$ et $b$ strictement positifs, alors $(a + b)^2 = c^2 + 2ab > c^2$, donc $a + b > c$.
Démontrer que le programme n'a rien oublié : ces deux triangles sont les seuls.

On part de $c = 60 - a - b$ que l'on reporte dans $a^2 + b^2 = c^2$ :

$$ a^2 + b^2 = 3600 + a^2 + b^2 - 120a - 120b + 2ab $$

$$ 0 = 3600 - 120a - 120b + 2ab $$

On divise par $2$, puis on ajoute $3600$ aux deux membres pour faire apparaître un produit :

$$ ab - 60a - 60b + 3600 = 1800 $$

$$ (60 - a)(60 - b) = 1800 $$

Posons $p = 60 - a$ et $q = 60 - b$ : ce sont deux diviseurs entiers de $1 \ 800$, tous deux inférieurs à $60$ puisque $a$ et $b$ sont strictement positifs. Or si $p < 60$, alors $q = \frac{1 \ 800}{p} > \frac{1 \ 800}{60} = 30$, et de même pour $p$ : les deux diviseurs sont strictement compris entre $30$ et $60$.

Les diviseurs de $1 \ 800 = 2^3 \times 3^2 \times 5^2$ qui s'y trouvent sont $36$, $40$, $45$ et $50$. Leurs produits deux à deux :

$$ 36 \times 50 = 1 \ 800 \hspace{2em} 40 \times 45 = 1 \ 800 $$

$$ 36 \times 40 = 1 \ 440 \hspace{2em} 36 \times 45 = 1 \ 620 \hspace{2em} 40 \times 50 = 2 \ 000 \hspace{2em} 45 \times 50 = 2 \ 250 $$

Seules deux paires conviennent. Avec $a < b$, donc $p > q$ :

$$ (p \ ; \ q) = (50 \ ; \ 36) \ \Rightarrow \ (a \ ; \ b) = (10 \ ; \ 24) \hspace{2em} (p \ ; \ q) = (45 \ ; \ 40) \ \Rightarrow \ (a \ ; \ b) = (15 \ ; \ 20) $$

$$ \text{les deux triangles du programme sont les seuls} $$
Transformer le programme en une fonction qui prend la longueur de la corde et renvoie la liste des triangles, puis l'utiliser pour des cordes de $12 \ \text{m}$, $24 \ \text{m}$ et $30 \ \text{m}$.
```
def triangles(p):
    L = []
    for a in range(1, p):
        for b in range(a + 1, p):
            c = p - a - b
            if c > b and a * a + b * b == c * c:
                L.append([a, b, c])
    return L
```
$$ \text{triangles}(12) = [[3, \ 4, \ 5]] \hspace{2em} \text{triangles}(24) = [[6, \ 8, \ 10]] \hspace{2em} \text{triangles}(30) = [[5, \ 12, \ 13]] $$

Chacune de ces cordes ne donne qu'un seul triangle - la corde à treize nœuds des bâtisseurs, longue de $12 \ \text{m}$, ne connaît que le triangle $3$, $4$, $5$. Celle de $60 \ \text{m}$ en offre deux, dont le maçon choisit le mieux adapté à son chantier.

La gouttière du préau

Le préau mesure $22 \ \text{m}$ de long. La gouttière se vend en éléments de $4 \ \text{m}$, de $3 \ \text{m}$ et de $1 \ \text{m}$, qui s'emboîtent bout à bout. La longueur doit être exacte, et chaque jonction est un risque de fuite : on veut donc le moins d'éléments possible. Le magasinier conseille de prendre à chaque fois l'élément le plus long qui tient encore.

Compléter cette fonction, qui suit le conseil du magasinier et renvoie le nombre d'éléments, puis donner ce qu'elle renvoie pour le préau.
```
def glouton(L):
    n = 0
    for p in [4, 3, 1]:
        while L >= ... :
            L = ...
            n = ...
    return n
```
```
def glouton(L):
    n = 0
    for p in [4, 3, 1]:
        while L >= p:
            L = L - p
            n = n + 1
    return n
```
La liste $[4, \ 3, \ 1]$ range les longueurs de la plus grande à la plus petite. Pour $L = 22$, on retire cinq fois $4$, il reste $2$ ; $3$ ne tient plus, on retire deux fois $1$.

$$ \text{glouton}(22) = 7 $$
Montrer que six éléments suffisent, puis que l'on ne peut pas faire mieux. Trancher : le conseil du magasinier est-il bon ?

Quatre éléments de $4 \ \text{m}$ et deux de $3 \ \text{m}$ font la longueur exacte :

$$ 4 \times 4 + 2 \times 3 = 22 $$

Avec $n$ éléments, on couvre au plus $4n$ mètres, puisque le plus long mesure $4 \ \text{m}$ :

$$ 4n \geqslant 22 \iff n \geqslant 5.5 \quad \Longrightarrow \quad n \geqslant 6 $$

$$ \text{le minimum est } 6 \ \text{éléments} $$

Le conseil du magasinier coûte donc un élément de trop, et une jonction de plus. Prendre toujours le plus long fait terminer sur deux chutes de $1 \ \text{m}$, alors que deux éléments de $3 \ \text{m}$ auraient remplacé d'un coup un $4 \ \text{m}$ et ces deux chutes.
Écrire une fonction qui renvoie, elle, le vrai minimum, en essayant toutes les répartitions possibles.
On parcourt tous les nombres possibles d'éléments de $4 \ \text{m}$, puis de $3 \ \text{m}$ ; le reste se complète en éléments de $1 \ \text{m}$.
```
def minimum(L):
    m = L
    for q in range(L // 4 + 1):
        for t in range(L // 3 + 1):
            r = L - 4 * q - 3 * t
            if r >= 0 and q + t + r < m:
                m = q + t + r
    return m
```
La valeur de départ $m = L$ correspond à la solution qui marche toujours : $L$ éléments de $1 \ \text{m}$. La condition $r \geqslant 0$ écarte les répartitions trop longues.

$$ \text{minimum}(22) = 6 $$
Écrire, en compréhension, la liste des longueurs jusqu'à $30 \ \text{m}$ pour lesquelles le conseil du magasinier se trompe, puis expliquer ce que ces longueurs ont en commun.
```
E = [L for L in range(1, 31) if glouton(L) > minimum(L)]
```
$$ E = [6, \ 10, \ 14, \ 18, \ 22, \ 26, \ 30] $$

Ce sont les longueurs dont le reste dans la division par $4$ vaut $2$, à partir de $6 \ \text{m}$. Le procédé du magasinier se termine alors sur deux éléments de $1 \ \text{m}$, et il suffit d'échanger un $4 \ \text{m}$ et ces deux $1 \ \text{m}$ contre deux $3 \ \text{m}$ :

$$ 4 + 1 + 1 = 6 = 3 + 3 $$

Trois éléments contre deux : on en gagne exactement un, à chaque fois. Pour $L = 2$, l'échange est impossible, faute d'élément de $4 \ \text{m}$ à donner : le procédé reste bon.