Problèmes sur l'algorithmique en troisième

Suivre un programme, l'écrire, le remonter, le corriger : un tableau de valeurs ne se trompe pas.

Prévoir ce qu'affiche un programme, en suivant les valeurs pas à pas.
Écrire un programme répondant à un problème, et choisir sa boucle.
Repérer et corriger une erreur dans un programme.

Ce que le programme affiche

On considère le programme suivant :

total = 0
for k in range(6):
    total = total + 2 * k
print(total)

Quelles valeurs la variable $k$ prend-elle ?

$$ 0 \ ; \ 1 \ ; \ 2 \ ; \ 3 \ ; \ 4 \ ; \ 5 $$

Six valeurs, de zéro à cinq : « range(6) » compte six tours et s'arrête avant six.
Suivre les valeurs de la variable « total », tour après tour.

$$ 0 \ \rightarrow \ 0 \ \rightarrow \ 2 \ \rightarrow \ 6 \ \rightarrow \ 12 \ \rightarrow \ 20 \ \rightarrow \ 30 $$

À chaque tour on ajoute $2k$, c'est-à-dire $0$, puis $2$, $4$, $6$, $8$ et $10$.
Qu'affiche ce même programme ? Retrouver ce résultat sans la boucle.

$$ 30 $$

C'est le double de $0 + 1 + 2 + 3 + 4 + 5 = 15$.

Le programme à écrire

Une population de $4 \ 000$ habitants augmente de $3 \ \%$ par an. On cherche au bout de combien d'années elle dépassera $5 \ 000$ habitants.

Par quel nombre faut-il multiplier la population chaque année ?

Augmenter de $3 \ \%$, c'est ajouter $0.03$ fois la population à elle-même :

$$ 1.03 $$
Faut-il une boucle bornée ou non bornée ? Justifier.

On ne sait pas combien d'années il faudra, mais on sait quand s'arrêter : dès que la population dépasse $5 \ 000$.

$$ \text{une boucle non bornée} $$

Écrire le programme.

population = 4000
annees = 0
while population <= 5000:
    population = population * 1.03
    annees = annees + 1
print(annees)

Donner la réponse, en calculant les valeurs successives de la population.

Arrondie à l'unité, la population vaut successivement $4 \ 120$, $4 \ 244$, $4 \ 371$, $4 \ 502$, $4 \ 637$, $4 \ 776$, $4 \ 919$, puis $5 \ 067$.

$$ 8 \ \text{années} $$

Le programme qui se trompe

Ce programme devait calculer la moyenne des trois notes de la liste, qui vaut $15$. Il affiche $6$.

notes = [12, 15, 18]
for note in notes:
    somme = 0
    somme = somme + note
moyenne = somme / 3
print(moyenne)

Suivre la valeur de la variable « somme » après chacun des trois tours.

$$ 12 \ \rightarrow \ 15 \ \rightarrow \ 18 $$

À chaque tour, « somme » repart de zéro avant de recevoir la note : elle ne garde que la note du tour.
Expliquer pourquoi ce même programme affiche $6$.

Après la boucle, « somme » ne contient que la dernière note :

$$ 18 \div 3 $$

$$ 6 $$
Corriger le programme, et dire à quel piège il correspond.
```
notes = [12, 15, 18]
somme = 0
for note in notes:
    somme = somme + note
moyenne = somme / 3
print(moyenne)
```
L'initialisation sort de la boucle : la somme part de zéro une seule fois, avant le premier tour. C'est le piège de l'initialisation d'une variable.

Remonter le programme

On considère le programme suivant, dont la valeur de départ de « u » est un nombre entier à choisir :

u = ...
for k in range(3):
    u = 3 * u + 2
print(u)

On choisit $u = 1$ au départ. Suivre les valeurs de « u », et donner ce qu'affiche le programme.

$$ 1 \ \rightarrow \ 5 \ \rightarrow \ 17 \ \rightarrow \ 53 $$

$$ 53 $$
Ce même programme affiche maintenant $134$. Retrouver la valeur de départ de « u ».

Chaque tour multiplie par $3$ puis ajoute $2$. Pour remonter d'un tour, on fait l'inverse, dans l'ordre inverse : on retire $2$, puis on divise par $3$.

$$ (134 - 2) \div 3 = 44 $$

$$ (44 - 2) \div 3 = 14 $$

$$ (14 - 2) \div 3 = 4 $$

$$ u = 4 $$

On vérifie en faisant tourner le programme : $4$, $14$, $44$, puis $134$.
Lina affirme qu'en choisissant bien la valeur de départ, ce programme peut afficher $100$. A-t-elle raison ? Justifier.

Le dernier tour calcule $3 \times u + 2$ : le nombre affiché a toujours pour reste $2$ dans la division par $3$. Or :

$$ 100 = 3 \times 33 + 1 $$

Le reste est $1$, et non $2$ : en remontant, $100 - 2 = 98$ ne se divise pas par $3$.

$$ \text{Lina a tort} $$

Qui aura la plus grosse cagnotte ?

Lucas a $200 \ \text{€}$ dans sa tirelire et y ajoute $15 \ \text{€}$ chaque mois. Sa sœur Inès n'a que $80 \ \text{€}$, mais elle ajoute $25 \ \text{€}$ chaque mois. On cherche au bout de combien de mois Inès aura strictement plus d'argent que Lucas.

Écrire un programme qui répond à la question, en choisissant la boucle qui convient.
On ne sait pas combien de mois il faudra, mais on sait quand s'arrêter : c'est une boucle non bornée.
```
lucas = 200
ines = 80
mois = 0
while ines <= lucas:
    lucas = lucas + 15
    ines = ines + 25
    mois = mois + 1
print(mois)
```
Donner ce qu'affiche ce programme, en le justifiant par un calcul plutôt qu'en déroulant la boucle.

Au départ, Lucas a $200 - 80 = 120 \ \text{€}$ de plus. Chaque mois, Inès rattrape $25 - 15 = 10 \ \text{€}$ :

$$ 120 \div 10 = 12 $$

Au bout de $12$ mois, les deux cagnottes sont égales : $200 + 12 \times 15 = 380$ et $80 + 12 \times 25 = 380$. La condition « ines <= lucas » est encore vraie, et il faut un tour de plus.

$$ 13 \ \text{mois} $$
Lucas décide d'ajouter lui aussi $25 \ \text{€}$ chaque mois, et l'on modifie la ligne correspondante. Que se passe-t-il quand on lance le programme ? Proposer une modification qui règle le problème.
L'écart de $120 \ \text{€}$ ne diminue plus : la condition « ines <= lucas » reste toujours vraie, et le programme ne s'arrête jamais.

On range les deux épargnes mensuelles dans des variables, et l'on vérifie, avant de lancer la boucle, qu'Inès épargne plus que Lucas :
```
lucas = 200
ines = 80
par_mois_lucas = 25
par_mois_ines = 25
mois = 0
if par_mois_ines <= par_mois_lucas:
    print("Inès ne dépassera jamais Lucas")
else:
    while ines <= lucas:
        lucas = lucas + par_mois_lucas
        ines = ines + par_mois_ines
        mois = mois + 1
    print(mois)
```
Une autre solution, tout aussi juste, arrête la boucle au bout d'un nombre de mois fixé à l'avance.

Les casiers du vestiaire

Le vestiaire du gymnase compte $100$ casiers numérotés de $1$ à $100$, tous fermés. Pour un jeu, $100$ élèves numérotés de $1$ à $100$ passent l'un après l'autre : chacun change l'état de tous les casiers dont le numéro est un multiple du sien, en ouvrant ceux qui sont fermés et en fermant ceux qui sont ouverts. La figure montre les premiers casiers après le passage des élèves $1$ et $2$.

Ce programme suit le casier numéro « n » : la variable « etat » vaut $0$ quand il est fermé, $1$ quand il est ouvert.

n = 12
etat = 0
for k in range(100):
    eleve = k + 1
    if n % eleve == 0:
        etat = 1 - etat
print(etat)

Dérouler ce programme en complétant le tableau, puis dire ce qu'il affiche.

eleve

$1$

$2$

$3$

$4$

$5$

$6$

$7$

$8$

$9$

$10$

$11$

$12$

n % eleve

$0$

etat

$1$

$0$

valeurs des variables à la fin des douze premiers tours, pour n = 12 (à compléter)

eleve

$1$

$2$

$3$

$4$

$5$

$6$

$7$

$8$

$9$

$10$

$11$

$12$

n % eleve

$0$

$2$

$0$

$5$

$4$

$3$

$2$

$1$

$0$

etat

$1$

$0$

$1$

$0$

$1$

$0$

valeurs des variables à la fin des douze premiers tours, pour n = 12

À partir de l'élève $13$, le reste de $12$ par « eleve » vaut $12$, jamais $0$ : « etat » ne change plus.

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

Le casier $12$ finit fermé. Seuls les élèves $1$, $2$, $3$, $4$, $6$ et $12$, les diviseurs de $12$, ont changé son état.

Sans dérouler la boucle, prévoir ce qu'affiche ce même programme pour $n = 36$, puis pour $n = 50$.

« etat » change à chaque élève dont le numéro divise « n », donc une fois par diviseur de « n ». Il part de $0$ : après un nombre pair de changements, il vaut $0$ ; après un nombre impair, il vaut $1$.

$$ 36 : \quad 1 \ ; \ 2 \ ; \ 3 \ ; \ 4 \ ; \ 6 \ ; \ 9 \ ; \ 12 \ ; \ 18 \ ; \ 36 \hspace{2em} 9 \ \text{diviseurs} $$

$$ 50 : \quad 1 \ ; \ 2 \ ; \ 5 \ ; \ 10 \ ; \ 25 \ ; \ 50 \hspace{2em} 6 \ \text{diviseurs} $$

$$ n = 36 : \text{affiche } 1 \hspace{2em} \text{et} \hspace{2em} n = 50 : \text{affiche } 0 $$
Prouver que le casier numéro $n$ finit ouvert si et seulement si $n$ est un carré parfait. On pourra associer chaque diviseur $d$ de $n$ au quotient $n \div d$. Donner la liste des casiers ouverts à la fin du jeu.

Si $d$ divise $n$, alors $n = d \times q$ avec $q = n \div d$, et $q$ divise aussi $n$. Les diviseurs de $n$ vont donc par paires, de produit $n$ :

$$ 12 = 1 \times 12 = 2 \times 6 = 3 \times 4 \hspace{2em} \text{et} \hspace{2em} 36 = 1 \times 36 = 2 \times 18 = 3 \times 12 = 4 \times 9 = 6 \times 6 $$

Une paire ne compte qu'un seul diviseur quand $d = q$, c'est-à-dire $d \times d = n$. Cela n'arrive que si $n$ est un carré parfait, et pour un seul diviseur : celui dont le carré vaut $n$.

Si $n$ n'est pas un carré parfait : chaque paire compte deux diviseurs, leur nombre est pair, et le casier finit fermé.

Si $n$ est un carré parfait : une seule paire ne compte qu'un diviseur, leur nombre est impair, et le casier finit ouvert.

$$ 1 \ ; \ 4 \ ; \ 9 \ ; \ 16 \ ; \ 25 \ ; \ 36 \ ; \ 49 \ ; \ 64 \ ; \ 81 \ ; \ 100 $$

Dix casiers finissent ouverts : ceux dont le numéro est le carré d'un nombre entier de $1$ à $10$.
On rejoue le lendemain avec les $50$ premiers élèves seulement : dans ce même programme, « range(100) » devient « range(50) ». Combien de casiers finissent ouverts ? Justifier.

Casiers $1$ à $50$ : tous leurs diviseurs valent au plus $50$, et les élèves concernés passent tous. Rien ne change : les carrés parfaits $1$, $4$, $9$, $16$, $25$, $36$ et $49$ finissent ouverts, soit $7$ casiers.

Casiers $51$ à $100$ : un diviseur $d$ de $n$, autre que $n$ lui-même, vérifie $n = d \times q$ avec $q \geqslant 2$. Donc :

$$ d = n \div q \leqslant n \div 2 \leqslant 100 \div 2 = 50 $$

Seul manque l'élève numéro $n$ : l'état change une fois de moins que la veille, et le résultat s'inverse. Le casier finit ouvert quand $n$ n'est pas un carré parfait.

Parmi ces $50$ casiers, seuls $64$, $81$ et $100$ sont des carrés parfaits :

$$ 50 - 3 = 47 $$

$$ 7 + 47 = 54 \ \text{casiers ouverts} $$

Vérification : le casier $64$ change d'état pour les élèves $1$, $2$, $4$, $8$, $16$ et $32$, six fois, et finit fermé ; le casier $52$ pour les élèves $1$, $2$, $4$, $13$ et $26$, cinq fois, et finit ouvert.

Le journal du collège

Le journal du collège est imprimé recto verso sur des feuilles pliées en deux, emboîtées puis agrafées au milieu : chaque feuille porte quatre pages. Pour un journal de $16$ pages, l'imprimante doit savoir quelles pages placer côte à côte sur chaque face. Ce programme les affiche, de la feuille extérieure à la feuille du milieu.

pages = 16
feuilles = 4
for k in range(feuilles):
    print(pages - 2 * k, 2 * k + 1)
    print(2 * k + 2, pages - 2 * k - 1)

Dérouler le programme en complétant le tableau, puis vérifier les deux lignes du premier tour sur la figure.

k	Première ligne affichée	Deuxième ligne affichée
$0$
$1$
$2$
$3$

affichage du programme pour un journal de 16 pages (à compléter)

k	Première ligne affichée	Deuxième ligne affichée
$0$	16 1	2 15
$1$	14 3	4 13
$2$	12 5	6 11
$3$	10 7	8 9

affichage du programme pour un journal de 16 pages

Au premier tour, $k = 0$ : le programme affiche $16 - 0$ et $0 + 1$, puis $0 + 2$ et $16 - 0 - 1$. Ce sont bien les deux faces de la feuille extérieure : $16$ et $1$ dehors, $2$ et $15$ dedans. Le dernier tour affiche $8$ et $9$, les deux pages du milieu, où passent les agrafes.

Calculer la somme des deux nombres de chaque ligne affichée. On note $P$ la valeur de la variable « pages » : prouver que cette somme vaut toujours $P + 1$, quel que soit le nombre de pages du journal.

Toutes les sommes valent $17$, soit $16 + 1$. Au tour $k$, les deux lignes affichées donnent :

$$ (P - 2k) + (2k + 1) = P - 2k + 2k + 1 = P + 1 $$

$$ (2k + 2) + (P - 2k - 1) = 2k + 2 + P - 2k - 1 = P + 1 $$

$$ \text{deux pages côte à côte} : \text{somme} = P + 1 $$
On change de numéro : une feuille détachée d'un autre journal porte côte à côte les pages $7$ et $18$. Retrouver le nombre de pages de ce journal, le rang de la feuille en partant de l'extérieur, et les pages de son autre face.

D'après la question 2 :

$$ P + 1 = 7 + 18 = 25 \quad \text{donc} \quad P = 24 $$

La page impaire $7$ est affichée par « 2 * k + 1 » :

$$ 2k + 1 = 7 \quad \text{donne} \quad k = 3 $$

Le tour $k = 3$ est le quatrième : c'est la quatrième feuille. L'autre ligne de ce tour affiche :

$$ 2 \times 3 + 2 = 8 \hspace{2em} \text{et} \hspace{2em} 24 - 2 \times 3 - 1 = 17 $$

$$ 24 \ \text{pages} \hspace{2em} 4^{\text{e}} \ \text{feuille} \hspace{2em} \text{pages } 8 \quad \text{et} \quad 17 $$

Vérification : avec « pages = 24 » et « feuilles = 6 », le quatrième tour affiche « 18 7 », puis « 8 17 ».
Tom affirme avoir trouvé une feuille du journal qui porte côte à côte les pages $10$ et $13$. Trancher. Trouver ensuite toutes les pages qui peuvent se trouver à côté de la page $10$, selon le nombre de pages du journal, et prouver qu'il n'y en a pas d'autre.

Ce journal aurait $P + 1 = 10 + 13 = 23$, soit $P = 22$ pages. Or chaque feuille porte quatre pages : $P$ est un multiple de $4$, et $22$ n'en est pas un.

$$ \text{Tom a tort} $$

Si la page $10$ est à côté de la page $q$, alors $10 + q = P + 1$, donc $q = P - 9$. Le journal compte $f$ feuilles, avec $P = 4f$, et au moins $10$ pages, donc $f \geqslant 3$ :

$$ q = 4f - 9 = 4f - 12 + 3 = 4(f - 3) + 3 $$

Le reste de $q$ dans la division par $4$ vaut donc $3$. Réciproquement, soit $q = 4m + 3$, avec $m$ entier positif ou nul : le journal de $q + 9 = 4(m + 3)$ pages compte $m + 3$ feuilles, la page $10$ y figure, et sa voisine vaut $P + 1 - 10 = q$.

$$ 3 \ ; \ 7 \ ; \ 11 \ ; \ 15 \ ; \ 19 \ ; \ \dots \hspace{2em} \text{les nombres de reste } 3 \text{ dans la division par } 4 $$

Vérification : pour $16$ pages, le dernier tour affiche « 10 7 » ; pour $24$ pages, le cinquième tour affiche « 10 15 » en deuxième ligne.

k	Première ligne affichée	Deuxième ligne affichée
\(0\)
\(1\)
\(2\)
\(3\)