Aller au contenu

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

###(DĂ©s-)Active le code aprĂšs la ligne # Tests (insensible Ă  la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Ctrl+Clic pour inverser les colonnes)
Entrer ou sortir du mode "plein Ă©cran"
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activĂ©, le texte copiĂ© dans le terminal est joint sur une seule ligne avant d'ĂȘtre copiĂ© dans le presse-papier
Évaluations restantes : 5/5

.128013Cy1-]/wi_qP+rG 7F9f;gR2Ă h)(OpNn0ldT,4k`Ă©e!bmc:35a=o[.8t6sSĂšuxv050I0P0%0X0i0H0)0p0T0H0X0)0)0Y010%0i0D010406050)0,0S0S0X0n0c040*0Z0H0,120Z0F0p020X0S0D0u0p0w0P1c0n0k0,0P0)050g191b1d1f170D04051K1D1N0g1K170I0i0.0`0|0~100z0i0v0z0H1#0z0%15050=0R0H0P1W0}0 011!1$1(1$0%1.1:1,0%0n1L0%0z0`1i0)0D0X0F100x011=1Y010t0@0P0F1q0P1,282a2f1@2i1:2l0S2n040a0p0l0n0Z0D0Z0)0i1l1n0:260n0n0P0T2I1D2p0F1L0g242U2123221-0I2r101(0F2k2F1,1T1V0{1?2(0i2*0F0Z2.1,0D2N1L2S2U2 18291n2:2g2^0n1c0H150p0d2R3316322q351@37393b0x3e2a3g2S2%013l0X3a040p0V3p2T173s3j103v3x0p0L3B3r333t3H3b0W3L3D3N3F3u0Z383w3b0(3S3h341X3k3X3m3y0q3$3E3)3G3+3Z3y0$3/3U3;3W3Y3I0s3`3i3|3P040d0G413(2;3}3,0d3d1E3f3T424a440d3o4f3q4h49363?3x0d3A4n3C3%3O4s150d3K4w3M4i4r3~4B3R4E1O2}1D2.2X0I232$3V0T2_2x0/1U1L2|0P2~3f3L054V0:4%4G1@0M150:0t3L0p4y3V0F0t151B0%0j0T0c0{0i1z0P4)3:4a14040B573{4j150D0|0F5d4.105a0A0U483t0h3b0p5u5k4q1@0)0I15021z0Z0%0u5C0,5E5G5D5F5q3V5z5t5u2B2k2$2k0p290n1q0+211;0,2J0i2P0i1m2l0i2N0p0N5h2a0N2L2N281m0I2a0%0p0y0p5%5W5i0p0I02030V0s0u2k0.0Z0i0p0.3w0i2K2K2w0~0X0v1B0#5N3|5P3y5u1u6c6e1;0J0n1A0p2G0p1:632q66686a6y6f6l1B0)6o1B0p4~0`521(556U5~0r3w0)1;2G2^0F6r4E4p3t6u6w1o5L5K5I5F5H5J3S6=4_435g0P0n0)5,1B4@6 4a0Z150Y77582g5a0!5w3O150M0P0c7d5e2g4:040t3X7o5l3u7k7m7v5x100Z5s042?7A7j045=5j4L7e1@5a0f6}6w78364}0-0D0P1T0%0P0,0n7H3V7a047c4E4^7N3G7173751C7M7p7O157h7^7w0S0i15477}7B017P7R5v7/7x040:0)122l0=5.567-7T1@7*7,2 7.7_7:7J5i7i3V7g8u70040P7W7Y2H7#7%833t866.6~890F150F0R0j8c8e0?5_7(3|8m8V4a7 4B3S068K8q017r0h1!1:8Y7U8b4~2?0X8g2N8/8l150Q8n3f8p7w8M8z8B7Z8E8x59155p8J6=7S8L4;8=8f8T8i8o8k7C7b8`8r7K977f7{9r3k9f8d8?8^9j4(898I2 8%9c888)928O8Q9g9i7@9k898X8j9e049K8R8?8h9O8 9l017*0m9o018!458$8(7w7r2N0%7$7L9P9I8N8P9W5-8U9S8)8m8~3q90848O152u9u5m155c8G4`5g8tad3|5n3$0g4+4$4Man0g4P1D0%4Ras2!2V0X1/ap4P1J4-842N0S0j0t0X7l0j0z0V151v1x550_9a311Q3g0:8g0^4z7!650O5h0i0O2n0p2D2k7C7X923D1a1x1f0E5E9ja?1H3g1K0C1n0X7$0?5~0D0,0p0O0v3w1w2k5~6c0i6R6p0n612*0p0R0Z0,0{1;4*4W7s7ualbt0p0X0.2O6E3X121;5}5)13a*6E6f6H7K0p0F006V290_6251bq0p9a1R4Y2/3|1_1%1)1+aD3t2t2k2m152z0*0T0n135~0l0c241m4)4#aD304(amb+3V7r4=9)4{4}8d506X541Aa985abcg929qah98045o6s4a7E6~cm2g6u6{6`6@cx0ucqcv5A6v5R2N0F5U1n5X5Z5#bk655)2I9}1;7K6-9E9#6;6w1v0F6d0i6A6C6)bLcT646K696bc#6e651;6mbh6T6VbV6Ycf6.cXcE6=0;0p6$0^c*6+cV4gd05Q6?6_6^5JcA87a47I7X7=0F2*9Za39#9R9^7w8wcu9v047l7n9 9/157t8Fdta57ydAdG3t7D157GdBdH8s2acg9D4g9.dQ4#7 729Adq9Q9ndPdk7274dn76dwaa047|31899+82d?8)dU4odWd*dm2*9)ds9!9TdYc%8_9b9H914}0t0t2O124?d)7)d(dK4`0Ra72kdTcid/8acld`du150Adi9#7rdEc8dNe27EdOel43en045Y0F6peq5bcjecee5*eheI79150e9)9+4eev845naTdV9Gdjae7Jd+75e2eke49_dR9@9Bd{9tescke:d-eP7Qe99ceAdNeVe@ebe/e0d#2Te-8W7ba2fe9#ckaFe7fdc4ai99die,ff4a9:0;9?9)0M0T15d56(ez89fw9=0ne`d$8)fA156Bc~cWbw4,ao2UaB4O0;0?0^aW1U3t0X0I0S1m2H5+1n2?7t151Jf%f)f+2I0e120%1 040o5Y0D0z8ibZ1K0bd38A720T5)1;5_6(0Saz5 cOg80nga0T1;2K0vg0g20K0p1cbga,1n6V5|0FbT340}5W1d120T0,1(720p1z6f2G1r1(2i1;bM1d4V7$0)6-bZaq4Z17aqfY0@0)04.