Des œufs en boîtes : multiples et algorithmes
Énoncé
Une coopérative range ses œufs dans des boîtes de 12.
1. Elle a récolté 340 œufs. Combien de boîtes complètes peut-elle remplir, et combien d'œufs reste-t-il ?
2. On considère l'algorithme suivant, où a et b sont deux entiers naturels, avec a ≠ 0 :
```
m ← 0
Tant que m + a ⩽ b
m ← m + a
Fin Tant que
Afficher m
```
a) Faire fonctionner cet algorithme à la main pour a = 12 et b = 50, en notant les valeurs successives de m.
b) Que représente, en général, le nombre affiché ?
3. On donne la fonction Python suivante, où a et b sont deux entiers naturels, avec b ≠ 0 :
```python
def est_multiple(a, b):
r = a
while r >= b:
r = r - b
return r == 0
```
Que renvoie-t-elle appelée avec les nombres 340 et 12 ? avec 336 et 12 ? Interpréter.
Indice : Pour faire fonctionner un algorithme à la main, dresse un tableau des valeurs de la variable et teste la condition AVANT chaque passage dans la boucle.
Correction
- Étape 1 : Ranger des œufs par boîtes de 12, c'est chercher le plus grand multiple de 12 qui ne dépasse pas le nombre d'œufs. Les deux algorithmes de l'exercice automatisent ce raisonnement.
Multiple :
a est un multiple de b s'il existe un entier k tel que a = kb.
👉 Pour suivre un algorithme à la main, on note la valeur des variables après chaque passage, et on teste la condition « Tant que » avant chaque passage : dès qu'elle est fausse, on sort de la boucle.
- Étape 2 : 1) On encadre 340 entre deux multiples consécutifs de 12 :
12 × 28 = 336 ≤ 340 < 348 = 12 × 29
La coopérative remplit donc 28 boîtes complètes, qui contiennent 336 œufs, et il reste 340 - 336 = 4 œufs.
340 = 12 × 28 + 4
- Étape 3 : 2a) Avec a = 12 et b = 50 :
| test « m + 12 ≤ 50 » | vrai ? | nouvelle valeur de m |
|:---:|:---:|:---:|
| 0 + 12 = 12 | oui | 12 |
| 12 + 12 = 24 | oui | 24 |
| 24 + 12 = 36 | oui | 36 |
| 36 + 12 = 48 | oui | 48 |
| 48 + 12 = 60 | non | fin de la boucle |
L'algorithme affiche 48.
m = 48
- Étape 4 : 2b) La variable m prend successivement les valeurs 0, a, 2a, 3a, … : ce sont les multiples de a. On ajoute a seulement si le résultat ne dépasse pas b, donc la boucle s'arrête sur le dernier multiple de a qui reste inférieur ou égal à b.
Le nombre affiché est le plus grand multiple de a inférieur ou égal à b. Pour a = 12 et b = 340, il vaudrait 336 : on retrouve la question 1.
- Étape 5 : 3) Avec 340 et 12, la fonction retire 12 à r tant que r ≥ 12 : après 28 retraits, r = 340 - 28 × 12 = 4, qui est inférieur à 12, donc la boucle s'arrête. Comme r = 4 ≠ 0, la fonction renvoie False : 340 n'est pas un multiple de 12.
Avec 336 et 12, on obtient r = 336 - 28 × 12 = 0, donc la fonction renvoie True : 336 = 28 × 12 est un multiple de 12.
La valeur finale de r est le reste : les 4 œufs qui ne remplissent pas de boîte.
- Étape 6 : L'erreur classique :
Écrire la condition « Tant que m ⩽ b » au lieu de « Tant que m + a ⩽ b ». La boucle ajoute alors a une fois de trop : pour a = 12 et b = 340, elle afficherait 348, qui dépasse 340.
Autre confusion : répondre 336 à la question « combien de boîtes ? ». 336 est le nombre d'œufs rangés ; le nombre de boîtes est 336/12 = 28.
À retenir :
Faire tourner un algorithme, c'est tenir un tableau des variables et tester la condition avant chaque passage.
👉 Un entier a est un multiple de b exactement quand il ne reste rien après avoir retiré b autant de fois que possible.