Exercice 2 - Récursivité · Bac Numérique et Sciences Informatiques Polynésie 2025 (jour 1)

Exercice 2 (6 points)

Cet exercice porte sur la programmation Python et la récursivité.

Le jeu du baguenaudier est un jeu de casse-tête constitué d’une réglette comportant $n$ cases, numérotées de 1 à $n$.

Chaque case peut être soit vide, soit contenir un pion.

« Jouer » une case consiste à placer un pion dans la case (remplir) si elle est vide ou enlever un pion (vider) si elle est remplie.

Initialement, toutes les cases sont vides.

Le but du jeu est de remplir toutes les cases du baguenaudier en suivant les règles suivantes:

on ne peut jouer qu'une case à la fois;

chaque case ne peut contenir qu'un pion;

on peut toujours jouer la case 1;

si le baguenaudier n'est ni vide ni rempli, on peut aussi jouer la case qui suit la première case remplie;

aucune autre case ne peut être jouée.

Exemple de situation avec un baguenaudier de 5 cases.

Dans cette situation, on peut poser un pion dans la case 1 ou enlever le pion de la case 4 mais on ne peut pas jouer les cases 2, 3 et 5.

Pour modéliser le baguenaudier on utilise un tableau (de type list) de booléens. Une case vide est représentée par False et une case remplie par True.

L'exemple de situation du baguenaudier de 5 cases de la Figure 1 présentée plus haut sera ainsi représenté par le tableau suivant:

[False, False, True, True, False] La résolution d'un baguenaudier de 3 cases, en Figure 2 et 4 cases, en Figure 3 sont données ci-dessous.

Il est possible d'obtenir la solution du jeu du baguenaudier, sous forme d'affichage, en utilisant des fonctions récursives nommées vider et remplir. Ces deux fonctions prennent en paramètre un entier $n$ correspondant au nombre de cases du jeu. La fonction vider vide un baguenaudier de $n$ cases initialement remplies. La fonction remplir remplit un baguenaudier de $n$ cases initialement vides.

Le code de la fonction vider, incomplet, est donné ci-dessous. On notera que les cases sont numérotées à partir de 1 dans la suite et que l'appel vider(0) ne fait rien.

1 def vider(n):

2 if n == 1:

3 print('Vider case 1')

4 elif n > 1:

5 vider(n-2)

6 print(...)

7 remplir(n-2)

8 vider(n-1)

7.

Recopier et compléter la ligne 6 du code de la fonction vider pour qu'elle affiche le texte 'Vider case ' suivi de la valeur de l'entier $n$.

8.

En supposant que l'appel remplir(1) affiche 'Remplir case 1' et que l'appel remplir(0) ne fait rien, donner les affichages, dans la console, produits par l'exécution de vider(3).

9.

En vous inspirant de la fonction vider, de la résolution donnée à la question précédente pour $n = 3$ et des Figures 2 et 3, écrire le code de la fonction récursive remplir.

def remplir(n):

10.

On envisage d'utiliser la fonction vider pour un baguenaudier de 2000 cases. Expliquer si ce code est adapté à un baguenaudier de si grande taille. Justifier votre réponse.