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 :

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⚓︎

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

Python Console Session
>>> 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"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein Ă©cran"
(Esc)
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

.128013g[ r;)/(loF4,6b=ax+5utP7e-h0Tmn`Cki:SéNq.èy1cd32!à8_wvpfO9R]Gs050U0z0w0r0J0j0.0d0T0j0r0.0.0q010w0J0%010406050.0v0E0E0r0e0R040L0k0j0v120k0F0d020r0E0%0f0d0+0z1c0e0O0v0z0.050h191b1d1f170%04051K1D1N0h1K170U0J0$0`0|0~100|0F0b0v0r0b0z0A0%0R0w0B1m0d0B0J0b0B0j1?0B0w15050=0p0j0z1W0}0 011=1@1_1@0w1 211}0w0e1L1.0`1i0.0%0r0F100W01231Y010(0@0z0F1q0z1}2l2n2s252v212y0E2A040a0d0x0e0k0%0k0.0J1l1n0:2j0e0e0z0T2V1D2C0F1L0h1.2+2f2h2g1~0U2E1Z0J0F2x2S1}1T1V0{242^2`0F0k2~1}0%2!1L2)2+3b182m1n302t340e1c0j1}0r1;2!0(10030!0!0T350z1_330k0A0V0A0S150d0S1D0r3c3f163e2D3h253j3l3n3p0z3r013t3v3x3z2{3C0A2q040d0W3J3L2n3N2)2@013S0r3m1L3o0B3q3s3u3w0:3$343(0V3G0V3.2(3M173=3Q103^3`053|3~3Y403#2_3%3D0m3G0m491E4b3O3g1X3R0k3k3_3U3}3W3 3!424o443D0u3G0u4u3b4c3f3?4g4E4k3Z413y4K3B3D0o3G0o4Q4w4d4z4f4B3T3{3V3X4Y4n3A3(0y3G0y4+3:4S3P4.3@4:4D4=4F4@4m4J4`3D0Z3G0Z4 2*514y31544C4h4j4G4l4I4!5c0A0*3G0*5h3;4T4e5m4;4i4?4H4Z434$3E0C150S0C5z5j4U555o5G5r5I4#3(0S3F045!5Q4x5S5n4W5q4^5b4p3E3*0S3-0h3K4a505)5C4V574X5a5t5:0S465$485^3/5i5|535~5F585H4_634r5$4t685`6a4-5l6d5p595s5J5Z4N5$4P6m4v3:1O391D2~2.0U2h2?5C4Z2}1U1L380z3a3M6n1L4Z6S2D0J0U103u2)5Z3U6Z6#6u5Y3D3F0d2I0z6+5X5u5#496p2t0I150:0(6U0d6b6q0(151B0w3v0R0{0J1z0z6U732t14040i7f6{3R150%1!7l5B537i0g0K6U176B2*5)6*016$3f3(3*5F7C616v3D2q6:2z6?6h4L3)1}6m7m100#3G0d7!7r525l0.0U15021z0k0w0f7,0v7.7:7-7/7x7$1n7J0!6%3D657I6!7D6,5u467O2J7Q5/7S817V7s7(7*3+7!2N2!0F2?2x0d2m0e1q0Q2f220v2W0J2$0J1m2y0J2!0d0G7p2n0G2Y2!2l1m0U2n0w0d0Y0d8w8p1!0d0U02030V0*0f2x0$0k0J0d0$3_6Z222X2J0~1(1B0P7`7z6X7|837E2n3(6j828a627S4r886=846@5:928e7%2t7)7Z7!1v0F8)0J220D0e1A0d2T0d218V2D8Y8!8$8(8*8X228=0.8@0_770`7a1_7d0d0;0d0l3_0.222T340F8_8{7y3d3=7}7 0A6x939a7R5K4N98947L9)7U5_7W019h8i7!7;7?9~7/a00f8`9#4T9%7F4%6)8~855:4(9:9,8b5K4(2+3K8j729_0F7o0z0e0.8B1B717g250k150qaw9_7i0c7{4U150I0z0RaC8f6|150(4BaM9f7n04aJaL8{anaNay7Y042_aS5k3i7o7q8{ax107i0,a46T9$ab9(4|4=7}9b7S4|af7K6-0Aa{3.ama/3@760s0%0z1T0w0z0v0ea)3?az04aBaYb8ap04bcasau1Ca.aD15aFbwa!100E0J155PbAaTa:15a=9ZaGa7905daa9;b35eb1ac7S5eak9|aZbIb9040:0.122y0=8D7ebo9_blbn3bb#a*aU8H0FaG5CaEb}6cbabcbebgbibHb_bJ04bL4RbNa_a85vbRag955K5wbVa~ck9@b!bp150F0p0!b)b+0?8Lbj5Cb=cA53bD5Na?6Ca^6+9(5Ochb26^5Mcm9-5Z5MbZ9!a@a6cebP3E6_3oa}cS6.6/6;bS6^6_68b79_6}040#1=21cD6q6~772_0rb-2!c{2tbl0Xb?3Mb^aH040zbbbd2Uc5c05l7i7wbMc70dbO0F5Z7Hc%abcndq2rc,ci9=5?cpamc;bBb%cwc d1b/b@b8cCb:dEbqb{dh7hbydRaUdGb,cydJcXb$a;cH7AcJ84cL81dsc-6387dxcOd/dBdC7#aocscudWdYbvdKb;aAd3aUctcvc~8CczdNb$bl0te3bCbE5$d%8|dncZdp6.92d-dyb30S97d;bW5KescpcWcIcYcKcf0S9*epd=7SeEdw7Peq6^9*c:8jb8c?2!0wbhb|eac8b%e5d}b.d d8dLaAd73:d95}0p152HdUc97kdm5}a,2ne=017uei1D6W6D6R6F6O1D0w6If62;2,0r20f30h6G1Jej5C2!0E0!0(0raJ0!0B651v1x7d0_dk3d1Q3N0:b-0^5Sbf8X0M7p0J0M2A0d2Q2x10fNbq4c1a1x1f0N7.dJfT1H3N1K0)1n0rbh0?8Q0%0v0d0M0b3_1w2x8Q8(0J9G1)0e8T2`0d0p0k0v0{22056WaQc66W0d0r0$2#9s4B12228P8y13fK9s8+9vb{6:009J2m0_8U0T9L22dk1R0/1U3?1!1$8@1+1-1/1n271^1`1|fi532G2x2z150xgJ1m7f6Q8|696V3xejdo0A0m3EcNevg+g-cRahg:6/6f5WcSg,c/9^dEc?6 ee3@75dbb*797b7de|7ie@a5b$dPa-hdeY7ufx4wdmg*g,drekd.44hoeK89eM3%ht5V5.cjg:7H9eeYa$b7e^539{a2hL7^a3dlhhhqd*7Fg,d,hReH3BhUhu99hXg:87g_hA6vhZbZb89{am2O2x8n1n8q8s8uf~8X8y2Ve822b{9Ycchmelg:eohWg/g,eteLh$ia2rh)idg+cph.8ham9k9m9o9q9Ugoi08W9y8#8%9l9C8;1Bf{1B9Ob*9Kh81Ae d)8 dpg,eFi8duiNh!hrhY9?hziheOg~b$h/8j9P9R0^ir9Wi2hlhQhn0Aaj9+ihaeeuiQi:if60i9i`h-9_i#9}hNhM7=7_hPd!8}eC90g,b5eGi}b0i^g{b4i{5-ihb5ePd_dOaqbt0F2`e%e,e)bmh2b hIc|aVaKh2c?g8h2bqaWh20ka$a(eXdadQjBdScaiJeBhSjb0AbYi=i}bUjhg?g,bUigj$d@jphe7ofk9nd2jPcBe2j^c1braratjtavjS25jAhQ5CcF04bGk57tbKjV6Yi5g,5wa|dtjiclj(hBkgjk6ti_khb6eQd`j}js2`jLj`e0jqbrj=ardZ5{i4jaiM5Lg.i_cMg=knkLiWi}cMbZdDj:db0(0(2#1270j{5ldMkBhee/04e;k2e?e|hfe{k:e}150gkdj9jXkK5!kMjil0kPh+c#kp6gj)l6kVkug aPaRk(a+a%jLjNeWk+eYct158r1#kGd(dEhbk=76kZk#0Jk%lmbk150Ah2k73Ik^hjk|i86%g|hpc(l9dAl45YlOl7g`lRhDald^e-j|bsj kylgaykAe(kvjRkadidTk^dPj~auhakcj7eAkekJg@hVlQkQ64iShwhs3Eh(i|kN8dl!d^eR15lAjIjrl)ls3+jx0qe+2*l$jC6QbDkFl{04hkkHi.kf3Ei7m3l5exlT4`g|97j,kN9dmel#j/eYeS0;eVjF0T15i(9TlLi/eJkiiTg@9/kmmG9/mMl2iYcqc=lpmU0elll.g mX049piIl}7A0hf11Q6Eff6O7yfB0?0^fAgD5C0r0U0E1m2U8A7|0FaQ151J3?ngni0Fnk1m0A120w2d040-8r0%0Bb/gB1K0H9Pdcar0T8y228L9T0Efd8Rh{nL0enN0T8:220bnDnF0n0d1cf`fM1n9J8O0Fgv3g0}8p1d120T0v1_ar0d1z8+2T1r1_2v22gp1d3wbh0.9YgBn70$3Nff0;nb0.04.