Solution de Mots à trous - Sujet 45 - EP NSI 2025

Résoudre ce problème
Moyen Officiel
Python (3.14.0)

Énoncé du problème

EXERCICE 1 (10 points)

On considère des chaînes de caractères contenant uniquement des majuscules et des caractères * appelées mots à trous.

Par exemple INFOMAIQUE, IE** et S sont des mots à trous.

Programmer une fonction correspond :

  • qui prend en paramètres deux chaînes de caractères mot et mot_a_trous où mot_a_trous est un mot à trous comme indiqué ci-dessus ;
  • et qui renvoie :
    • True si on peut obtenir mot en remplaçant convenablement les caractères '*' de mot_a_trous ;
    • False sinon.

Exemple :

>>> correspond('INFORMATIQUE', 'INFO*MA*IQUE')
True
>>> correspond('AUTOMATIQUE', 'INFO*MA*IQUE')
False
>>> correspond('STOP', 'S*')
False
>>> correspond('AUTO', '*UT*')
True

EXERCICE 2 (10 points)

On considère au plus 26 personnes A, B, C, D, E, F … qui peuvent s’envoyer des messages avec deux règles à respecter :

  • chaque personne ne peut envoyer des messages qu’à une seule personne (éventuellement elle-même),
  • chaque personne ne peut recevoir des messages qu’en provenance d’une seule personne (éventuellement elle-même).

Voici un exemple - avec 6 personnes - de « plan d’envoi des messages » qui respecte les règles ci-dessus, puisque chaque personne est présente une seule fois dans chaque colonne :

  • A envoie ses messages à E
  • E envoie ses messages à B
  • B envoie ses messages à F
  • F envoie ses messages à A
  • C envoie ses messages à D
  • D envoie ses messages à C

Le dictionnaire correspondant à ce plan d’envoi est alors le suivant :

plan_a = {'A':'E', 'B':'F', 'C':'D', 'D':'C', 'E':'B', 'F':'A'}

Un cycle est une suite de personnes dans laquelle la dernière est la même que la première.

Sur le plan d’envoi plan_a des messages ci-dessus, il y a deux cycles distincts : un premier cycle avec A, E, B, F et un second cycle avec C et D.

En revanche, le plan d’envoi plan_b ci-dessous :

plan_b = {'A':'C', 'B':'F', 'C':'E', 'D':'A', 'E':'B', 'F':'D'}

comporte un unique cycle : A, C, E, B, F, D. Dans ce cas, lorsqu’un plan d’envoi comporte un unique cycle, on dit que le plan d’envoi est cyclique.

Pour savoir si un plan d’envoi de messages comportant N personnes est cyclique, on peut utiliser l’algorithme ci-dessous :

  • on part d’un expéditeur (ici A) et on inspecte son destinataire dans le plan d’envoi,
  • chaque destinataire devient à son tour expéditeur, selon le plan d’envoi, tant qu’on ne « retombe » pas sur l’expéditeur initial,
  • le plan d’envoi est cyclique si on l’a parcouru en entier.

Compléter la fonction est_cyclique située à la page suivante en respectant la spécification. On rappelle que la fonction Python len permet d’obtenir la longueur d’un dictionnaire.

def est_cyclique(plan):
    '''Prend en paramètre un dictionnaire `plan` correspondant à 
    un plan d'envoi de messages (ici entre les personnes A, B, C,
    D, E, F).
    Renvoie True si le plan d'envoi de messages est cyclique et 
    False sinon.'''
    expediteur = 'A'
    destinataire = plan[...] 
    nb_destinataires = 1

    while destinataire != expediteur:
        destinataire = ... 
        nb_destinataires = ... 

    return nb_destinataires == ...

Exemples :

>>> est_cyclique({'A':'E','F':'A','C':'D','E':'B','B':'F','D':'C'})
False
>>> est_cyclique({'A':'E','F':'C','C':'D','E':'B','B':'F','D':'A'})
True
>>> est_cyclique({'A':'B','F':'C','C':'D','E':'A','B':'F','D':'E'})
True
>>> est_cyclique({'A':'B','F':'A','C':'D','E':'C','B':'F','D':'E'})
False

Les contraintes ci-dessous sont ajoutées par la plateforme et ne font pas partie du sujet.

Exercice 1

Contraintes :

  • mot et mot_a_trous sont des chaînes de caractères
  • 1 <= len(mot) <= 100 et 1 <= len(mot_a_trous) <= 100
  • mot ne contient que des lettres majuscules de 'A' à 'Z'
  • mot_a_trous ne contient que des lettres majuscules de 'A' à 'Z' et le caractère '*'
  • mot et mot_a_trous peuvent être de longueurs différentes ; dans ce cas la fonction renvoie False
  • la fonction renvoie un booléen True ou False

Exercice 2

Contraintes :

  • plan est un dictionnaire dont les clés et les valeurs sont des chaînes d’un seul caractère, une lettre majuscule de 'A' à 'Z'
  • 1 <= len(plan) <= 26
  • la clé 'A' est toujours présente dans plan
  • chaque personne apparaît exactement une fois comme clé et exactement une fois comme valeur : l’ensemble des valeurs est égal à l’ensemble des clés
  • la fonction renvoie un booléen True ou False

Solution

Exercice 1 - les mots à trous

L’idée. Un '*' dans mot_a_trous veut dire « ici, n’importe quelle lettre convient ». Toutes les autres positions, elles, doivent porter exactement la même lettre dans les deux chaînes. Il suffit donc de comparer les deux mots lettre par lettre, à la même position : dès qu’on trouve une position où mot_a_trous a une vraie lettre différente de celle de mot, c’est perdu. Et comme une étoile remplace une lettre et une seule, les deux chaînes doivent d’abord avoir la même longueur.

Un petit exemple. Pour correspond('AUTO', '*UT*') : position 0, '*' accepte le 'A' ; position 1, 'U' contre 'U', d’accord ; position 2, 'T' contre 'T', d’accord ; position 3, '*' accepte le 'O'. On arrive au bout sans désaccord, donc True. Pour correspond('STOP', 'S*'), les longueurs sont 4 et 2 : c’est False tout de suite, puisqu’une étoile ne peut pas remplacer trois lettres.

def correspond(mot, mot_a_trous):
    if len(mot) != len(mot_a_trous):
        return False
    i = 0
    while i < len(mot):
        # Une etoile accepte n'importe quelle lettre : seules les vraies lettres
        # de mot_a_trous doivent etre identiques a celles de mot
        if mot_a_trous[i] != '*' and mot_a_trous[i] != mot[i]:
            return False
        i = i + 1
    return True

Explications. Le premier if règle le cas des longueurs différentes ; sans lui, mot_a_trous[i] provoquerait une erreur d’indice. Ensuite i parcourt les positions, de 0 à len(mot) - 1. À chaque tour, on ne rejette que dans un seul cas : la position n’est pas une étoile et les deux lettres diffèrent. On renvoie False dès le premier désaccord, inutile de regarder la suite. Si la boucle va jusqu’au bout, c’est qu’aucune position n’a posé problème : on renvoie True.

Exercice 2 - le plan d’envoi est-il cyclique ?

L’idée. On part de 'A' et on suit le plan : 'A' écrit à quelqu’un, qui écrit à quelqu’un, et ainsi de suite. Comme chaque personne écrit à une seule personne et reçoit d’une seule personne, on finit forcément par revenir à 'A' : on a bouclé. La seule question est de savoir si ce tour a rencontré tout le monde ou seulement une partie des personnes. On compte donc les destinataires rencontrés pendant le tour, et on compare ce compte à len(plan), le nombre total de personnes.

Un petit exemple. Avec {'A':'E', 'B':'F', 'C':'D', 'D':'C', 'E':'B', 'F':'A'} : depuis 'A' on visite E, puis B, puis F, puis on retombe sur A. Cela fait 4 destinataires alors que le plan compte 6 personnes : C et D forment un cycle à part, donc False.

def est_cyclique(plan):
    '''Prend en paramètre un dictionnaire `plan` correspondant à 
    un plan d'envoi de messages (ici entre les personnes A, B, C,
    D, E, F).
    Renvoie True si le plan d'envoi de messages est cyclique et 
    False sinon.'''
    expediteur = 'A'
    destinataire = plan[expediteur] 
    nb_destinataires = 1

    while destinataire != expediteur:
        # On suit le plan de proche en proche jusqu'a revenir au depart
        destinataire = plan[destinataire] 
        nb_destinataires = nb_destinataires + 1 

    # Le plan est cyclique seulement si ce tour a visite tout le monde
    return nb_destinataires == len(plan)

Explications. Les quatre trous du sujet se remplissent ainsi : plan[expediteur] pour le tout premier destinataire, plan[destinataire] pour passer au suivant, nb_destinataires + 1 pour compter, et len(plan) pour la comparaison finale. expediteur ne change jamais : il garde 'A', c’est le point de départ auquel on veut revenir. destinataire est la personne où on se trouve en ce moment, et nb_destinataires compte combien de personnes le tour a visitées ; il vaut déjà 1 avant la boucle parce qu’on a fait un premier pas de 'A' vers plan['A']. La boucle s’arrête dès que destinataire redevient 'A', c’est-à-dire quand le tour est bouclé. Si ce tour a visité les len(plan) personnes, il n’y a qu’un seul cycle et le plan est cyclique.