Exercice 2 - Gestion des bugs et algorithmique · Bac Numérique et Sciences Informatiques Amérique du Nord 2025 (jour 2)

Exercice 2 (6 points)

Cet exercice porte sur la gestion des bugs, l'algorithmique, les structures de données et la programmation orientée objet.

Partie A

Un jour, Bob s’apprête à manger un collier de bonbons, et se pose la question suivante: « Si je mange un bonbon sur trois, encore et encore jusqu’à ce qu’il n’en reste qu’un seul, quel sera le dernier bonbon restant ? »

Pour un collier ayant 5 bonbons, il décide de les numéroter de 0 à 4. Il commence par manger le bonbon d'indice 0, se décale de trois bonbons et mange ensuite celui d'indice 3. En répétant la démarche, il mange ensuite le bonbon d'indice 2 et enfin celui d'indice 4.

Les indices des bonbons mangés sont donc, dans l'ordre, 0, 3, 2 et 4. Le bonbon restant est celui d'indice 1.

1.

Donner les indices dans l'ordre dans lequel les bonbons sont mangés dans le cas où le collier possède initialement 8 bonbons et l'indice du bonbon restant.

Afin de répondre à la question dans un cadre général, Bob décide de formaliser le problème. Il considère un collier de $n$ bonbons numérotés de 0 à $n - 1$, où $n$ est un entier strictement positif.

Bob vient d'étudier en classe les valeurs booléennes. Il se dit qu'il peut représenter avec Python le collier par une liste collier telle que, pour toute valeur entière de i comprise entre 0 et $n - 1$, la valeur booléenne collier[i] vaut True si le bonbon d'indice i du collier est encore présent, et vaut False si le bonbon d'indice i du collier a été mangé.

Dès lors, il envisage l'algorithme suivant:

on initialise une liste collier représentant $n$ bonbons qui n'ont pas encore été mangés;

on commence par manger le bonbon à l'indice 0;

tant qu'il reste des bonbons à manger:

on détermine l'indice du prochain bonbon à manger dans la liste collier;

on mange le bonbon à cet indice;

on renvoie l'indice du dernier bonbon mangé.

Afin de créer la liste collier décrite ci-dessus, Bob saisit dans la console l'instruction:

collier = [true for i in range(8)]

Il obtient alors le message d'erreur suivant:

Traceback (most recent call last):

File "<stdin>", line 1, in <module>

NameError: name 'true' is not defined

2.

Expliquer ce qu'est une erreur de type NameError et comment la corriger dans l'instruction proposée.

Bob écrit ensuite le code d'une fonction dernier qui prend en paramètre le nombre de bonbons $n$ et renvoie l'indice du dernier bonbon restant. On fournit ci-après une partie du code de la fonction dernier.

1 def dernier(n):

2 collier =...

3 indice = 0

4 collier[indice] = False

5 for etape in range(n-1):

6 nb_bonbons_vus = 0

7 while nb_bonbons_vus...:

8 indice += 1

9 if...:

10 indice = 0

11 if...:

12 nb_bonbons_vus += 1

13 collier[indice] =...

14 return indice

3.

Recopier et compléter les lignes 2, 7, 9, 11 et 13 du code de la fonction dernier.