Exercice 2 - Programmation Python · 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.

1.

On considère un baguenaudier à 4 cases sur lequel les trois dernières cases sont remplies.

Désigner les cases que l'on peut jouer et dessiner l'état du baguenaudier à la suite de chacun des coups possibles.

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]

2.

La fonction initialiser prend en paramètre un nombre entier n et elle renvoie une liste modélisant un baguenaudier vide de n cases.

Exemple:

>>> initialiser(3)

[False, False, False]

Écrire le code de la fonction initialiser.

3.

La fonction victoire renvoie un booléen indiquant si toutes les cases du baguenaudier sont remplies.

1 def victoire(tab):

2 for etat_case in tab:

3 if etat_case ==...:

4 return...

5...

Recopier et compléter les lignes 3, 4 et 5 du code de la fonction victoire.

4.

La fonction indice_premiere_case_occupee prend en paramètre un tableau tab modélisant l'état du baguenaudier et renvoie l'indice de la première case remplie du baguenaudier, ou None si le baguenaudier est vide.

Exemples:

>>> indice_premiere_case_occupee([True, True, True])

0

>>> indice_premiere_case_occupee([False, False, False, True, True])

3

>>> indice_premiere_case_occupee([False, False, False, False])

# pas de sortie car valeur None

Écrire le code de la fonction indice_premiere_case_occupee.

5.

La fonction coup_valide prend en paramètres tab qui est une liste modélisant l'état d'un baguenaudier, et un entier case qui est l'indice de la case à jouer. La fonction renvoie True si le coup respecte les règles et False si ce n'est pas le cas.

L'indice de la première case du jeu est 0. Pour que le coup soit valide, il faut aussi s'assurer que l'indice est un entier positif inférieur à la longueur de tab.

Écrire le code de la fonction coup_valide.

6.

La fonction changer_case prend en paramètres un tableau tab modélisant l'état du baguenaudier et un indice de case nommé case. Si le coup désigné par case est valide, la fonction renvoie le tableau modélisant le baguenaudier obtenu après avoir changé l'état de la case correspondante. Si le coup joué n'est pas valide, le baguenaudier passé en paramètre est renvoyé sans modification.

Écrire le code de la fonction changer_case.