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

Évaluations restantes : 5/5

.128013f6S=d-èNpg2m!RC 8GP5)kus_hq0:F4yr./oTxbc1w937ve[l,O`+tài]né;a(050f0V0$0-0(0X0y0q0O0X0-0y0y0e010$0(0j010406050y0x0m0m0-0H0G040d0K0X0x120K0*0q020-0m0j0,0q0o0V1c0H0B0x0V0y050J191b1d1f170j04051K1D1N0J1K170f0(0U0`0|0~100A0(0k0A0X1#0A0$15050=0N0X0V1W0}0 011!1$1(1$0$1.1:1,0$0H1L0$0A0`1i0y0j0-0*100l011=1Y010b0@0V0*1q0V1,282a2f1@2i1:2l0m2n040a0q0t0H0K0j0K0y0(1l1n0:260H0H0V0O2I1D2p0*1L0J242U2123221-0f2r101(0*2k2F1,1T1V0{1?2(0(2*0*0K2.1,0j2N1L2S2U2 18291n2:2g2^0H1c0X150q0P2R3316322q351@37393b0l3e2a3g2S2%013l0-3a040q0S3p2T173s3j103v3x0q0F3B3r333t3H3b0u3L3D3N3F3u0K383w3b0c3S3h341X3k3X3m3y0T3$3E3)3G3+3Z3y0r3/3U3;3W3Y3I0R3`3i3|3P040P0C413(2;3}3,0P3d1E3f3T424a440P3o4f3q4h49363?3x0P3A4n3C3%3O4s150P3K4w3M4i4r3~4B3R4E1O2}1D2.2X0f232$3V0O2_2x0/1U1L2|0V2~3f3L054V0:4%4G1@0w150:0b4)3:4a0Q3b4@3{4j0b151B0$0z0O0G0{0(1z0V4|4.1014040.5a4q3k150j0|0*5g3t5d0v0D483t4`3y0q5w5n3V0y0f15021z0K0$0,5D0x5F5H5E5G5s5z5B5v5w2B2k2$2k0q290H1q0h211;0x2J0(2P0(1m2l0(2N0q0!5k2a0!2L2N281m0f2a0$0q0%0q5(5X5l0q0f02030S0R0,2k0U0K0(0q0U3w0(2K2K2w0~0-0k1B0I5O3|5A3b5w1u6d6f1;0L0H1A0q2G0q1:642q67696b6z6g6m1B0y6p1B0q510`551(586V5 0E3w0y1;2G2^0*6s4E4p3t6v5R1o5M5L5J5G5I5K3S6x0q4y3V0*5j0V0H0y5-1B3L704^2g0K150e7a713|5d0W5y43150w0V0G7h7c4/150b3X7s4}367o7q7y5b010K5u2?7D5h3G5j5l7m4a5d0)6~6x7i4j500M0j0V1T0$0V0x0H7J3t7e047g4E7b7z5i047Y76781C4L7t5c157l7`7:100m0(15477 7E7Q7S5x7{3u4;512?0-0=5/597.7U7d7f7)727M2a7O2g7k8s7;0V7X7Z2H7$7(867K01886/6 8l7;0*0N0z0:0y125.5`8o3|7+7-2 7/7E824B3S068I8b4:040Q1!1:8T7V048O8Q8g0?2N8/8m040n8W3f8Y8E73048x7Y7!8B8v7|045r8H6 7T8b928=8f8h8_8k8b8V8`7;5?5m8D5o7}988c8;8e2l9j8j318b8G2 8%9d8a809w8L8N9y8^799l9J9n9Q7E929L9h8R9P8X8J107+0#9o8183458$8(9J8*2N0$7%9r9!9f159W9N8i7_9^9R7f8~3q903O0N152u9v5d5f9s8p7=7Nac7j150v3$0J4+4$4Man0J4P1D0$4Ras2!2V0-1/ap4P1J4-8E2N0m0z0b0-7p0z0A0S151v1x580_9b311Q3g0:8h0^4z7#660+5k0(0+2n0q2D2k9$7Y923D1a1x1f0i5F9Ba?1H3g1K0Z1n0-7%0?5 0j0x0q0+0k3w1w2k5 6d0(6S6q0H622*0q0N0K0x0{1;4*4W047w8Cam3y0-0U2O6F3X121;5~5*13a*6F6g6I9q0q0*006W290_6354bq0q9b1R4Y2/3|1_1%1)1+aD3t2t2k2m152z0d0O0H135 0t0G241m4)4#aD304(bx9#018*4=9v5u70ag4~508P536Y571Aa915ab9C9J929qcj045q6t4_6w5xcb2g6=6|6{6^cA0,ctcy5Q6 5T0*5V1n5Y5!5$bk665*2I9Y6J6-cF1@6=6 1v0*6e0(6B6D6*bL1;bN6L6a6cc$6f661;6nbh6U6WbV6Zci6/c4cZ6x0;0q6%0^c+6,6.9Fd1cH6xcDdf6^89a4ad7?770*2*9~8 c49S9 879ucx7;7p7r9T8E8*bv9)9wdydE7G157IdA3O8q9@4(9D157R9c9I9U5jaFc(9kdt8Edsdq9_7=75dmdocq7~cm8Z9+85d/8E9E4g9.dVd)7@dn9Bd%a07,dEcodX75d 4od`91500b0b2O124?dL3Vd$a3c48La72kcqcldPcndNcqajdTdj3|dC7xeh7n040(dH7HdOek9fa6045Z0*6qep9v920Vecee0(egd!7*150gdE8!9,dw99csewe9dMd|d+e72Tex4aeje;elete(8Fdvd?e-dl78cqdS9F9HdUdBdJeWe0d{f0d~dHa1e3dW1wdYe:b+3V5daTd_f5e,3V9:0;9?dE0w0O15d66)dic4ft9=0HeHe^8)fy046Cc dbalbtao2UaB4O0;0?0^aW1U3t0-0f0m1m2H5,1n2?7w151Jf!f$f(2I0g120$1 040s5Z0j0A8jbZ1K0pd48x750O5*1;5`6)0maz60cQg50Hg70O1;2K0kf}f 0Y0q1cbga,1n6W5}0*bT340}5X1d120O0x1(750q1z6g2G1r1(2i1;bM1d4V7%0y6.bZaq4Z17aqfV0@0y04.

Recherche d'un cycle⚓︎

Exemple pour plan_a⚓︎

Exemple pour plan_b⚓︎

Principe de l'algorithme⚓︎

Exemple pour `plan_a`⚓︎

Exemple pour `plan_b`⚓︎