Recherche d'un cycle

On considère des personnes, identifiées par un pseudo unique, qui s'envoient des messages en respectant les deux règles suivantes :

• chaque personne envoie des messages à 1 seule et 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).

Exemple pour plan_a

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 en tant qu'expéditeur et récepteur.

• Anne envoie ses messages à Elodie
• Elodie envoie ses messages à Bruno
• Bruno envoie ses messages à Fidel
• Fidel envoie ses messages à Anne
• Claude envoie ses messages à Denis
• Denis envoie ses messages à Claude

Et le dictionnaire correspondant à ce plan d'envoi est le suivant :

🐍 Script Python

plan_a = {'Anne': 'Elodie', 'Bruno': 'Fidel', 'Claude': 'Denis', 
          'Denis': 'Claude', 'Elodie': 'Bruno', 'Fidel': 'Anne'}

Sur le plan d'envoi plan_a des messages ci-dessus, il y a deux cycles distincts : un premier cycle avec Anne, Elodie, Bruno, Fidel et un second cycle avec Claude et Denis.

Exemple pour plan_b

🐍 Script Python

plan_b = {'Anne': 'Claude', 'Bruno': 'Fidel', 'Claude': 'Elodie', 
          'Denis': 'Anne', 'Elodie': 'Bruno', 'Fidel': 'Denis'}

En revanche, le plan d'envoi plan_b ci-dessus comporte un unique cycle : Anne, Claude, Elodie, Bruno, Fidel, Denis. Dans ce cas, lorsqu'un plan d'envoi comporte un unique cycle, on dit que le plan d'envoi est cyclique.

Conséquence des règles sur le dictionnaire

Les deux règles garantissent que chaque personne apparaît une fois en tant que clé du dictionnaire et exactement une fois en tant que valeur associée à une clé.

Principe de l'algorithme

Pour savoir si un plan d'envoi de messages comportant \(\text{N}\) personnes est cyclique, on peut utiliser l'algorithme ci-dessous :

• on part d’un expéditeur 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.

On garantit qu'un plan est non vide.

Compléter la fonction suivante en respectant la spécification.

Longueur d'un dictionnaire

La fonction python len permet d'obtenir la longueur d'un dictionnaire.

Exemples

🐍 Console Python

>>> plan_a = {'Anne': 'Elodie', 'Bruno': 'Fidel', 'Claude': 'Denis',
          'Denis': 'Claude', 'Elodie': 'Bruno', 'Fidel': 'Anne'}
>>> est_cyclique(plan_a)
False
>>> plan_b = {'Anne': 'Claude', 'Bruno': 'Fidel', 'Claude': 'Elodie',
          'Denis': 'Anne', 'Elodie': 'Bruno', 'Fidel': 'Denis'}
>>> est_cyclique(plan_b)
True

Compléter la fonction est_cyclique

###

Lancer # Testsbksl-nlplanpy-unda = {'Anne': 'Elodie', 'Bruno': 'Fidel', 'Claude': 'Denis',bksl-nl 'Denis': 'Claude', 'Elodie': 'Bruno', 'Fidel': 'Anne'}bksl-nlplanpy-undb = {'Anne': 'Claude', 'Bruno': 'Fidel', 'Claude': 'Elodie',bksl-nl 'Denis': 'Anne', 'Elodie': 'Bruno', 'Fidel': 'Denis'}bksl-nlassert not estpy-undcyclique(planpy-unda)bksl-nlassert estpy-undcyclique(planpy-undb)bksl-nlbksl-nlbksl-nl# Autres testsbksl-nlassert estpy-undcyclique({'A': 'B', 'F': 'C', 'C': 'D', 'E': 'A', 'B': 'F', 'D': 'E'})bksl-nlassert not estpy-undcyclique({'A': 'B', 'F': 'A', 'C': 'D', 'E': 'C', 'B': 'F', 'D': 'E'})bksl-nlassert estpy-undcyclique({'A': 'E', 'F': 'C', 'C': 'D', 'E': 'B', 'B': 'F', 'D': 'A'})bksl-nlassert not estpy-undcyclique({'A': 'A', 'B': 'B'})bksl-nlassert estpy-undcyclique({'A': 'B', 'B': 'A'})bksl-nlassert estpy-undcyclique({'A': 'B', 'B': 'C', 'C': 'D', 'D': 'A'})bksl-nlassert not estpy-undcyclique({'A': 'B', 'B': 'C', 'C': 'D', 'D': 'A', 'E': 'E'})bksl-nl Valider 5/5 Télécharger Téléverser Recharger Sauvegarder

def estpy-undcyclique(plan):bksl-nl """bksl-nl Prend en paramètre un dictionnaire plan correspondant à un plan d'envoi valide de messages.bksl-nl Renvoie True si le plan d'envoi de messages est cyclique et False sinon.bksl-nl """bksl-nl personnes = [key for key in plan]bksl-nl expediteur = personnes[0]bksl-nl destinataire = plan[...]bksl-nl nbpy-unddestinaires = 1bksl-nlbksl-nl while destinataire != ...:bksl-nl destinataire = ...bksl-nl nbpy-unddestinaires = ...bksl-nlbksl-nl return nbpy-unddestinaires == ...bksl-nlbksl-nlbksl-nl# Testsbksl-nlplanpy-unda = {'Anne': 'Elodie', 'Bruno': 'Fidel', 'Claude': 'Denis',bksl-nl 'Denis': 'Claude', 'Elodie': 'Bruno', 'Fidel': 'Anne'}bksl-nlplanpy-undb = {'Anne': 'Claude', 'Bruno': 'Fidel', 'Claude': 'Elodie',bksl-nl 'Denis': 'Anne', 'Elodie': 'Bruno', 'Fidel': 'Denis'}bksl-nlassert not estpy-undcyclique(planpy-unda)bksl-nlassert estpy-undcyclique(planpy-undb)bksl-nlbksl-nlbksl-nldef estpy-undcyclique(plan):bksl-nl """bksl-nl Prend en paramètre un dictionnaire plan correspondant à un plan d'envoi valide de messages.bksl-nl Renvoie True si le plan d'envoi de messages est cyclique et False sinon.bksl-nl """bksl-nl personnes = [key for key in plan]bksl-nl expediteur = personnes[0]bksl-nl destinataire = plan[expediteur]bksl-nl nbpy-unddestinaires = 1bksl-nlbksl-nl while destinataire != expediteur:bksl-nl destinataire = plan[destinataire]bksl-nl nbpy-unddestinaires = nbpy-unddestinaires + 1bksl-nlbksl-nl return nbpy-unddestinaires == len(plan)bksl-nlbksl-nlbksl-nl

---

Note

On aurait pu également envisager une boucle for avec sortie anticipée si le plan n'est pas un cycle :

🐍 Script Python

def est_cyclique(plan):
    """
    Prend en paramètre un dictionnaire plan.
    Renvoie True si le plan d'envoi de messages est cyclique
    et False sinon.
    """
    personnes = [key for key in plan]
    premiere = personnes[0]
    personne = premiere
    effectif = len(plan)
    for i in range(effectif - 1):
        personne = plan[personne]
        if personne == premiere:
            return False
    return True

Graphe

Cet exercice ressemble à un exercice de graphe, mais on est dans un cas particulier qui simplifie le parcours.

---