3-dictionnaire
Difficulté **
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
.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.
# Tests
(insensible Ă la casse)(Ctrl+I)
(Ctrl+Clic pour inverser les colonnes)