Problèmes sur l'algorithmique en seconde

Dérouler, boucler, écrire une fonction : trois façons de faire faire un calcul à la machine.

Dérouler un programme et suivre ses variables
Choisir entre boucle bornée et boucle non bornée
Écrire une fonction et l'appeler
Repérer une erreur dans un programme

Dérouler un programme

n = 5
s = 0
for k in range(1, n + 1):
    s = s + k
print(s)

Donner ce qu'affiche ce programme.

range(1, n + 1) parcourt les entiers de $1$ à $5$. On suit les deux variables tour par tour :

$$ \text{tour} $$	$$ 1 $$	$$ 2 $$	$$ 3 $$	$$ 4 $$	$$ 5 $$
$$ k $$	$$ 1 $$	$$ 2 $$	$$ 3 $$	$$ 4 $$	$$ 5 $$
$$ s $$	$$ 1 $$	$$ 3 $$	$$ 6 $$	$$ 10 $$	$$ 15 $$

$$ \text{le programme affiche } 15 $$

Dire en une phrase ce que calcule ce programme.

À chaque tour, on ajoute $k$ à $s$ :

$$ s = 1 + 2 + 3 + 4 + 5 \hspace{2em} \text{la somme des entiers de } 1 \text{ à } n $$
Donner le nombre de tours qu'effectue la boucle, puis dire si elle est bornée ou non bornée.

La boucle for parcourt $k = 1$, puis $2$, $3$, $4$ et $5$ : le nombre de tours est connu avant de commencer.

$$ 5 \text{ tours} \hspace{2em} \text{boucle bornée} $$

Une boucle non bornée

On place $1\,000 \ \text{€}$ sur un compte rémunéré à $3 \ \%$ par an. On cherche l'année où le capital dépasse $1\,500 \ \text{€}$.

capital = 1000
annee = 0
while capital <= 1500:
    capital = capital * 1.03
    annee = annee + 1
print(annee)

Justifier le choix d'une boucle non bornée plutôt qu'une boucle bornée.

Une boucle bornée demande de connaître à l'avance le nombre de tours. Or ce nombre d'années est justement ce que l'on cherche : on répète donc le calcul tant que le capital ne dépasse pas $1\,500 \ \text{€}$.
Expliquer l'origine du coefficient $1.03$.

Augmenter une valeur de $3 \ \%$, c'est lui ajouter $3 \ \%$ d'elle-même :

$$ 1 + \frac{3}{100} = 1.03 $$
Modifier le programme pour qu'il affiche aussi le capital atteint.
Seule la dernière ligne change : après la boucle, la variable capital contient déjà le capital atteint.
```
capital = 1000
annee = 0
while capital <= 1500:
    capital = capital * 1.03
    annee = annee + 1
print(annee, capital)
```
Le programme affiche $14$ et un capital d'environ $1\,512.59 \ \text{€}$ : au bout de $13$ ans, le capital n'était que d'environ $1\,468.53 \ \text{€}$.

Écrire une fonction

Écrire une fonction est_multiple(a, b) qui renvoie True lorsque a est un multiple de b.
a est un multiple de b lorsque le reste de la division de a par b est nul :
```
def est_multiple(a, b):
    return a % b == 0
```
Écrire une fonction nb_diviseurs(n) qui renvoie le nombre de diviseurs de l'entier naturel non nul n, en appelant la fonction est_multiple de la question précédente.
Un diviseur de n est compris entre $1$ et n : on les teste tous, avec une boucle bornée, et on compte ceux qui conviennent.
```
def nb_diviseurs(n):
    compteur = 0
    for d in range(1, n + 1):
        if est_multiple(n, d):
            compteur = compteur + 1
    return compteur
```
Donner ce que renvoie cette même fonction nb_diviseurs pour $n = 12$.

Les diviseurs de $12$ sont $1$, $2$, $3$, $4$, $6$ et $12$.

$$ 6 \text{ diviseurs} $$

Remonter un programme

Le programme suivant affiche $20$. Retrouver la valeur de départ de la variable a.

a = ...
for k in range(3):
    a = 2 * a - 4
print(a)

La boucle fait trois tours. Chaque tour double a puis retire $4$ : pour remonter d'un tour, on ajoute $4$ puis on divise par $2$.

$$ \frac{20 + 4}{2} = 12 \hspace{2em} \frac{12 + 4}{2} = 8 \hspace{2em} \frac{8 + 4}{2} = 6 $$

On vérifie en déroulant le programme depuis $6$ :

$$ \text{tour} $$	$$ \text{départ} $$	$$ 1 $$	$$ 2 $$	$$ 3 $$
$$ a $$	$$ 6 $$	$$ 8 $$	$$ 12 $$	$$ 20 $$

$$ a = 6 $$

On passe à un autre programme. Chloé veut compter les multiples de $7$ compris entre $1$ et $98$, $98$ inclus. Son programme affiche $13$.
```
compteur = 0
for k in range(1, 98):
    if k % 7 == 0:
        compteur = compteur + 1
print(compteur)
```
Repérer son erreur, puis corriger le programme.
La borne de droite de range est exclue : k s'arrête à $97$, et le multiple $98 = 7 \times 14$ n'est jamais testé. Il en manque donc un, puisque les multiples de $7$ jusqu'à $98$ sont $7 \times 1$, ..., $7 \times 14$.
```
compteur = 0
for k in range(1, 99):
    if k % 7 == 0:
        compteur = compteur + 1
print(compteur)
```
$$ \text{le programme corrigé affiche } 14 $$

Une boîte cubique de 500 mL

Une entreprise veut fabriquer une boîte cubique de $500 \ \text{mL}$, soit un volume de $500 \ \text{cm}^3$. Son côté $x$, en centimètres, vérifie donc $x^3 = 500$, équation que l'on ne sait pas résoudre de tête. On l'approche par balayage :

def cote(depart, pas):
    x = depart
    while x ** 3 <= 500:
        x = x + pas
    return x - pas, x

Justifier que le côté $x$ est compris entre $7 \ \text{cm}$ et $8 \ \text{cm}$.

On calcule les cubes des deux entiers :

$$ 7^3 = 343 \hspace{2em} \text{et} \hspace{2em} 8^3 = 512 $$

Comme $343 < 500 < 512$ et que le cube d'un nombre positif grandit avec lui :

$$ 7 < x < 8 $$
Donner ce que renvoie cote(7, 0.1), et le nombre de tours de boucle effectués.

x prend les valeurs $7$, $7.1$, ..., $7.9$, dont les cubes restent inférieurs à $500$ ($7.9^3 = 493.039$), puis $8$, dont le cube $512$ dépasse $500$ : la boucle s'arrête après $10$ tours.

La fonction renvoie les deux dernières valeurs de x, qui encadrent le côté :

$$ 7.9 < x < 8 $$

Python affiche en fait 7.899999999999997 et 7.9999999999999964 : un flottant n'est qu'une valeur approchée.
On veut maintenant encadrer ce même côté à $0.01 \ \text{cm}$ près, avec la fonction cote. Choisir les arguments à lui donner pour faire le moins de tours possible, et justifier.
Le pas doit valoir $0.01$. La question précédente a déjà montré que $x$ dépasse $7.9$ : partir de $7.9$ plutôt que de $7$ évite des tours inutiles : l'appel ne fait que $4$ tours, contre $94$ en partant de $7$.
```
cote(7.9, 0.01)
```
Cet appel renvoie $7.93$ et $7.94$. La boîte doit contenir au moins $500 \ \text{cm}^3$. Trancher : quel côté l'entreprise doit-elle retenir ?

On calcule le volume obtenu avec chacune des deux valeurs :

$$ 7.93^3 \approx 498.68 \hspace{2em} \text{et} \hspace{2em} 7.94^3 \approx 500.57 $$

Avec $7.93 \ \text{cm}$, la boîte ne contient pas tout à fait $500 \ \text{cm}^3$ ; il faut prendre la borne supérieure de l'encadrement, même si elle est plus éloignée de la valeur exacte.

$$ x = 7.94 \ \text{cm} $$

Les boîtes de nuggets

Un restaurant rapide vend ses nuggets en boîtes de $6$, de $9$ ou de $20$. Une commande de n nuggets est possible si on peut l'obtenir exactement avec ces boîtes : par exemple, $15 = 6 + 9$.

def possible(n):
    for a in range(n + 1):
        for b in range(n + 1):
            if 20 * a + 9 * b <= n and (n - 20 * a - 9 * b) % 6 == 0:
                return True
    return False

n = 100
while possible(n):
    n = n - 1
print(n)

Expliquer ce que représentent a et b, et ce que teste la condition de la fonction possible. Que renvoient possible(15) et possible(16) ?

a est le nombre de boîtes de $20$, b le nombre de boîtes de $9$. La condition vérifie que ces boîtes ne dépassent pas n, et que le reste, n - 20 * a - 9 * b, est un multiple de $6$ : il se complète alors avec des boîtes de $6$. La fonction essaie tous les couples (a, b) et renvoie True dès que l'un convient.

Pour $n = 15$ : avec $a = 0$ et $b = 0$, le reste $15$ n'est pas un multiple de $6$ ; avec $a = 0$ et $b = 1$, le reste vaut $15 - 9 = 6$, qui en est un.

Pour $n = 16$ : une boîte de $20$ dépasse déjà $16$, donc $a = 0$. Avec $b = 0$, le reste vaut $16$ ; avec $b = 1$, il vaut $7$ ; à partir de $b = 2$, $9 \times 2 = 18$ dépasse $16$. Ni $16$ ni $7$ n'est un multiple de $6$.

$$ \text{possible(15) renvoie True} \hspace{2em} \text{et} \hspace{2em} \text{possible(16) renvoie False} $$

Le programme affiche $43$. Prouver, sans ordinateur, qu'une commande de $43$ nuggets est impossible.

Trois boîtes de $20$ font $60 > 43$ : il y a au plus deux boîtes de $20$. Pour chaque nombre a de boîtes de $20$, on retire les boîtes de $9$ une à une, et on regarde si le reste est un multiple de $6$ :

Boîtes de $20$	Restes après $0$, $1$, $2$… boîtes de $9$	Un multiple de $6$ ?
$a = 0$	$43$ ; $34$ ; $25$ ; $16$ ; $7$	aucun
$a = 1$	$23$ ; $14$ ; $5$	aucun
$a = 2$	$3$	aucun

$$ \text{Une commande de} \ 43 \ \text{nuggets est impossible} $$

On change de menu : le restaurant ne vend plus que des boîtes de $6$ et de $9$, et on adapte la fonction possible. Prévoir ce qu'affiche alors le programme, puis expliquer pourquoi ce nombre n'est pas la plus grande commande impossible.
La fonction adaptée ne garde que les boîtes de $9$ et de $6$ :
```
def possible(n):
    for b in range(n + 1):
        if 9 * b <= n and (n - 9 * b) % 6 == 0:
            return True
    return False
```
Toute commande possible s'écrit $6a + 9b = 3(2a + 3b)$ : c'est un multiple de $3$. Or $100 = 3 \times 33 + 1$ n'en est pas un : possible(100) renvoie False, la boucle while ne fait aucun tour.

$$ \text{Le programme affiche} \ 100 $$

Mais $101$, $103$ ou $1 \ 000$, qui ne sont pas des multiples de $3$, sont aussi impossibles : il n'existe pas de plus grande commande impossible. Le programme ne cherche qu'en dessous de $100$ ; son résultat ne dit rien des nombres plus grands.
On revient aux boîtes de $6$, de $9$ et de $20$. Prouver que toute commande d'au moins $44$ nuggets est possible, et donc que $43$ est bien la plus grande commande impossible. On pourra commencer par les commandes de $44$ à $49$ nuggets.

Les six commandes de $44$ à $49$ nuggets sont possibles :

$$ 44 = 20 + 9 + 9 + 6 \hspace{2em} 45 = 9 + 9 + 9 + 9 + 9 \hspace{2em} 46 = 20 + 20 + 6 $$

$$ 47 = 20 + 9 + 6 + 6 + 6 \hspace{2em} 48 = 6 \times 8 \hspace{2em} 49 = 20 + 20 + 9 $$

Soit n une commande d'au moins $44$ nuggets. La division euclidienne de $n - 44$ par $6$ donne $n - 44 = 6q + r$, avec $r$ entre $0$ et $5$ :

$$ n = (44 + r) + 6q $$

La commande de $44 + r$ nuggets, entre $44$ et $49$, est possible ; on lui ajoute $q$ boîtes de $6$.

$$ \text{Toute commande d'au moins} \ 44 \ \text{nuggets est possible} $$

Avec la question 2, $43$ est la plus grande commande impossible : cette fois, le résultat du programme est prouvé pour tous les nombres. Par exemple, $100 = 46 + 6 \times 9 = 20 + 20 + 6 + 6 \times 9$.

Le jeu des bâtonnets

Vingt bâtonnets sont alignés. Chacun son tour, deux joueurs en retirent $1$, $2$ ou $3$ ; celui qui retire le dernier bâtonnet a perdu. La machine joue en premier : quand il reste n bâtonnets, elle en retire coup(n).

def coup(n):
    r = (n - 1) % 4
    if r == 0:
        return 1
    else:
        return r

Le candidat retire successivement $2$, $3$, $1$ et $2$ bâtonnets, puis ce qu'il peut. Dérouler la partie en complétant le tableau, et dire qui perd. Que remarque-t-on sur les nombres de bâtonnets que laisse la machine ?

Joueur	Bâtonnets restants	Bâtonnets retirés	Bâtonnets laissés
machine	$20$	$3$	$17$
candidat
machine
candidat
machine
candidat
machine
candidat
machine
candidat

Au premier tour, r vaut (20 - 1) % 4, le reste de la division de $19$ par $4$, soit $3$ : la machine retire $3$ bâtonnets. On continue de même :

Joueur	Bâtonnets restants	Bâtonnets retirés	Bâtonnets laissés
machine	$20$	$3$	$17$
candidat	$17$	$2$	$15$
machine	$15$	$2$	$13$
candidat	$13$	$3$	$10$
machine	$10$	$1$	$9$
candidat	$9$	$1$	$8$
machine	$8$	$3$	$5$
candidat	$5$	$2$	$3$
machine	$3$	$2$	$1$
candidat	$1$	$1$	$0$

$$ \text{Le candidat retire le dernier bâtonnet : il perd} $$

La machine laisse $17$, $13$, $9$, $5$ puis $1$ bâtonnet : des nombres de la forme $4k + 1$, dont le reste dans la division par $4$ vaut $1$.

La machine laisse $4k + 1$ bâtonnets, avec $k \geqslant 1$. Prouver que, quoi que retire le candidat, elle en laisse $4(k - 1) + 1$ au tour suivant. En déduire que la machine gagne toujours la partie de $20$ bâtonnets.

Le candidat retire $t$ bâtonnets, avec $t$ égal à $1$, $2$ ou $3$. Il en reste :

$$ n = 4k + 1 - t \hspace{2em} \text{donc} \hspace{2em} n - 1 = 4(k - 1) + (4 - t) $$

Comme $4 - t$ vaut $3$, $2$ ou $1$, c'est le reste de la division de $n - 1$ par $4$ : $r = 4 - t$, qui n'est pas nul, et la machine retire $4 - t$ bâtonnets. Il en reste :

$$ 4k + 1 - t - (4 - t) = 4k - 3 = 4(k - 1) + 1 $$

$$ \text{la machine laisse} \ 4(k - 1) + 1 \ \text{bâtonnets} $$

À eux deux, le candidat et la machine retirent $4$ bâtonnets à chaque tour.

Au départ, coup(20) vaut $3$ : la machine laisse $17 = 4 \times 4 + 1$. Elle laisse ensuite $13$, $9$, $5$, puis $1$ bâtonnet, que le candidat doit retirer. Le candidat ne peut jamais laisser $0$ bâtonnet à la machine : il en reste au moins $4k + 1 - 3 \geqslant 2$ après son coup.

$$ \text{La machine gagne toujours avec} \ 20 \ \text{bâtonnets} $$
On change le nombre de bâtonnets de départ, la machine jouant toujours en premier. Trouver tous les nombres de départ, de $10$ à $30$, avec lesquels un candidat qui joue bien bat la machine, et justifier.

Premier cas : le nombre de départ n'est pas de la forme $4k + 1$. Le reste $r$ n'est pas nul, et la machine laisse $n - r$, de la forme $4k + 1$ : d'après la question 2, elle gagne.

Second cas : il reste $4k + 1$ bâtonnets au départ. En retirant $1$, $2$ ou $3$ bâtonnets, la machine laisse $4k$, $4k - 1$ ou $4k - 2$, jamais un nombre de la forme $4j + 1$ ; coup renvoie $1$ et laisse $4k$. Le candidat retire alors $3$ bâtonnets et laisse $4(k - 1) + 1$ : il applique la stratégie de la machine, et gagne d'après la question 2, rôles échangés.

De $10$ à $30$, les nombres de la forme $4k + 1$ sont :

$$ 13 \ ; \ 17 \ ; \ 21 \ ; \ 25 \ ; \ 29 $$

Dans une autre version, on retire $1$, $3$ ou $4$ bâtonnets ; celui qui retire le dernier perd toujours. Une position est perdante si le joueur qui doit jouer perd face à un adversaire qui joue bien : c'est le cas si tous ses coups laissent une position gagnante. Elle est gagnante s'il existe un coup qui laisse une position perdante. Compléter le tableau, avec P pour perdante et G pour gagnante, puis dire si le premier joueur peut gagner avec $20$ bâtonnets, et comment.

Bâtonnets	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
Position	P	G	P
Bâtonnets	$11$	$12$	$13$	$14$	$15$	$16$	$17$	$18$	$19$	$20$
Position

Avec $1$ bâtonnet, il faut retirer le dernier : P. Avec $2$, on en retire $1$ et on laisse $1$ : G. Avec $3$, retirer $1$ laisse $2$, gagnant pour l'adversaire, et retirer $3$ fait perdre : P. On continue en regardant les positions à $1$, $3$ et $4$ bâtonnets de moins :

Bâtonnets	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
Position	P	G	P	G	G	G	G	P	G	P
Bâtonnets	$11$	$12$	$13$	$14$	$15$	$16$	$17$	$18$	$19$	$20$
Position	G	G	G	G	P	G	P	G	G	G

Par exemple, avec $8$ bâtonnets, les coups laissent $7$, $5$ ou $4$, trois positions gagnantes : $8$ est perdante. De même, avec $17$, les coups laissent $16$, $14$ ou $13$, toutes gagnantes. Avec $20$, retirer $3$ laisse donc $17$, une position perdante pour l'adversaire ; retirer $1$ ou $4$ lui laisserait $19$ ou $16$, deux positions gagnantes.

$$ \text{Le premier joueur gagne : il retire} \ 3 \ \text{bâtonnets et en laisse} \ 17 $$

Les positions perdantes, $1$, $3$, $8$, $10$, $15$ et $17$, reviennent de $7$ en $7$.

Boîtes de \(20\)	Restes après \(0\), \(1\), \(2\)… boîtes de \(9\)	Un multiple de \(6\) ?
\(a = 0\)	\(43\) ; \(34\) ; \(25\) ; \(16\) ; \(7\)	aucun
\(a = 1\)	\(23\) ; \(14\) ; \(5\)	aucun
\(a = 2\)	\(3\)	aucun

Joueur	Bâtonnets restants	Bâtonnets retirés	Bâtonnets laissés
machine	\(20\)	\(3\)	\(17\)
candidat	\(17\)	\(2\)	\(15\)
machine	\(15\)	\(2\)	\(13\)
candidat	\(13\)	\(3\)	\(10\)
machine	\(10\)	\(1\)	\(9\)
candidat	\(9\)	\(1\)	\(8\)
machine	\(8\)	\(3\)	\(5\)
candidat	\(5\)	\(2\)	\(3\)
machine	\(3\)	\(2\)	\(1\)
candidat	\(1\)	\(1\)	\(0\)

Bâtonnets	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	\(7\)	\(8\)	\(9\)	\(10\)
Position	P	G	P
Bâtonnets	\(11\)	\(12\)	\(13\)	\(14\)	\(15\)	\(16\)	\(17\)	\(18\)	\(19\)	\(20\)
Position

Bâtonnets	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	\(7\)	\(8\)	\(9\)	\(10\)
Position	P	G	P	G	G	G	G	P	G	P
Bâtonnets	\(11\)	\(12\)	\(13\)	\(14\)	\(15\)	\(16\)	\(17\)	\(18\)	\(19\)	\(20\)
Position	G	G	G	G	P	G	P	G	G	G