Exercice 2 - Partie B · Bac Numérique et Sciences Informatiques Polynésie 2026 (jour 2)

EXERCICE 2 (6 points)

Cet exercice porte sur la programmation Python, les structures de données, les graphes et la recherche de motif dans un texte.

Cet exercice comporte 2 parties qui peuvent être traitées indépendamment.

Le jeu du taquin consiste à déplacer des tuiles adjacentes à la case vide jusqu’à arriver à mettre tous les nombres dans l’ordre. Voici un exemple de positions pour un jeu du taquin de dimension 3 x 3 soit 9 cases.

Partie A

Dans un premier temps, on s’intéresse au jeu du taquin sur 4 cases. Voici une figure qui représente les 12 positions que l’on peut atteindre à partir de la position finale en déplaçant les tuiles. Deux positions sont reliées si on peut passer de l’une à l’autre en un seul coup, c’est-à-dire en déplaçant une tuile.

Partie B

On cherche maintenant à savoir si un mot est présent dans une liste de mots acceptés. Cette liste de mots acceptés est stockée sous la forme d'un texte contenant chacun des mots séparés par des espaces. Pour savoir si un mot est valide, il suffit donc de le chercher dans le texte, entre deux espaces.

8.

Nommer un algorithme de recherche de motif dans un texte plus efficace que la recherche naïve.

On propose l'implémentation suivante pour rechercher un motif dans un texte.

def recherche(motif, texte):

"""Renvoie le plus petit indice i tel que motif apparait dans

texte à l'indice i ou -1 si motif n'apparait pas"""

n = len(texte)

m = len(motif)

i = 0

while i + m - 1 < n:

j = m - 1

while texte[i+j] == motif[j]:

if j == 0:

return i

j = j - 1

i = i + m

return -1

9.

Donner le résultat de l'appel recherche('na', 'banana').

10.

Donner, en justifiant, un exemple de motif et un exemple de texte pour lesquels la fonction codée ne renvoie pas le résultat attendu.