Sujet n°38

Sujet original

Pour télécharger l'énoncé original, cliquer ici.

Exercice n°1

On considère des mots à trous : ce sont des chaînes de caractères contenant uniquement des majuscules et des caractères '*'. Par exemple 'INFO*MA*IQUE', '***I***E**' 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,

• renvoie :

  • True si on peut obtenir mot en remplaçant convenablement les caractères '*' de mot_a_trous.
  • False sinon.

Commentaire

A l'aide des exemples, on peut aussi déduire :

• que mot et mot_a_trous doivent avoir la même longueur ;
• que le caractère '*' remplace exactement une lettre majuscule.

Exemples

>>> correspond('INFORMATIQUE', 'INFO*MA*IQUE')
True

>>> correspond('AUTOMATIQUE', 'INFO*MA*IQUE')
False 

>>> correspond('STOP', 'S*') 
False 

>>> correspond('AUTO', '*UT*') 
True

Une solution

def correspond(mot, mot_a_trous):
    """
    mot, mot_a_trous - str, chaîne de caractères de même longueur
    Sortie: bool - True si les caractères de mot et mot_a_trous
            correspondent un à un, éventuellement avec une * dans mot_a_trous,
            False sinon
    """
    if len(mot) != len(mot_a_trous):
        return False
    for i in range(len(mot)):
        if mot_a_trous[i] != '*' and mot_a_trous[i] != mot[i]:
            return False
    return True



if __name__ == '__main__':
    # Exemples de l'énoncé
    print(correspond('INFORMATIQUE', 'INFO*MA*IQUE') == True)
    print(correspond('AUTOMATIQUE', 'INFO*MA*IQUE') == False)
    print(correspond('STOP', 'S*') == False)
    print(correspond('AUTO', '*UT*') == True)

    # Exemples supplémentaires
    print(correspond('REUSSITE', 'R*U*S*T*') == True)
    print(correspond('ECHEC', 'E***E') == False)

Exercice n°2

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'à la même 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 au plan d'envoi ci-dessus est 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 en respectant la spécification.

Remarque

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_destinaires = 1 
    while destinataire != ...: 
        destinataire = plan[ ... ] 
        nb_destinaires += ... 
    return nb_destinaires == ... 

Commentaires sur le code original

Pour télécharger l'original du fichier à compléter, cliquer ici.

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

Une solution

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['A']
    nb_destinaires = 1
    while destinataire != 'A':
        destinataire = plan[destinataire]
        nb_destinaires += 1
    return nb_destinaires == len(plan)


if __name__ == '__main__':
    # Exemples de l'énoncé
    print(est_cyclique({'A':'E', 'F':'A', 'C':'D', 'E':'B', 'B':'F', 'D':'C'}) == False)
    print(est_cyclique({'A':'E', 'F':'C', 'C':'D', 'E':'B', 'B':'F', 'D':'A'}) == True)
    print(est_cyclique({'A':'B', 'F':'C', 'C':'D', 'E':'A', 'B':'F', 'D':'E'}) == True)
    print(est_cyclique({'A':'B', 'F':'A', 'C':'D', 'E':'C', 'B':'F', 'D':'E'}) == False)

    # Exemples supplémentaires
    print(est_cyclique({'A':'B', 'B':'C', 'C':'D', 'D':'A'}) == True)
    print(est_cyclique({'A':'A'}) == True)
    print(est_cyclique({'A':'A', 'B':'B'}) == False)