Cadeaux circulaires⚓︎

Exercice conseillé en version À compléter
  • Les exercices conseillés en version "Vide" sont conçus pour ressembler à un "exercice 1" des épreuves pratiques au baccalauréat de Terminale NSI.
  • Les exercices conseillés en version "À compléter" sont conçus pour ressembler à un "exercice 2" des épreuves pratiques au baccalauréat de Terminale NSI.

La difficulté de l'exercice a été choisie en partant du principe qu'il est fait dans la version indiquée.

Pour fêter la nouvelle année, un groupe d'amis a décidé qu'il y aurait une distribution de petits cadeaux lors de la soirée. Pour préparer cela, chacun a écrit son nom sur un papier qu'il a déposé dans un chapeau.

Au moment de la distribution de cadeaux, chaque participant tire un papier. Il découvre ainsi la personne à laquelle il va devoir faire son cadeau (potentiellement lui).

Un tel appariement des invités s'appelle en mathématiques une permutation. On cherche dans cet exercice à déterminer si cette permutation est circulaire.

On garantit que :

  • il y a au moins une personne invitée à cette fête ;
  • chaque personne fait un cadeau à une unique personne (éventuellement elle-même),
  • chaque personne ne reçoit qu'un unique cadeau (éventuellement en provenance d'elle-même).

On représente une distribution par un dictionnaire Python dans lequel :

  • les clés sont les personnes offrant le cadeau ;
  • les valeurs sont les personnes recevant le cadeau.

Conséquence des règles sur le dictionnaire

Les règles garantissent que :

  • le dictionnaire est non-vide
  • chaque personne apparaît exactement une fois en tant que clé du dictionnaire
  • et exactement une fois en tant que valeur associée à une clé.
Exemple pour distribution_a

Voici un exemple, avec 6 personnes, de « distribution » de cadeaux qui respecte les règles ci-dessus :

  • Anne fait un cadeau à Élodie ;
  • Élodie fait un cadeau à Bruno ;
  • Bruno fait un cadeau à Fidel ;
  • Fidel fait un cadeau à Anne ;
  • Claude fait un cadeau à Denis ;
  • Denis fait un cadeau à Claude.
flowchart LR
    A(["Anne"]) --> E(["Élodie"])
    E --> B(["Bruno"])
    B --> F(["Fidel"])
    F --> A
    C(["Claude"]) --> D(["Denis"])
    D --> C

Le dictionnaire correspondant à cette distribution est le suivant :

🐍 Script Python
distribution_a = {
    "Anne": "Élodie",
    "Élodie": "Bruno",
    "Bruno": "Fidel",
    "Fidel": "Anne",
    "Claude": "Denis", 
    "Denis": "Claude",
    }

Dans cette distribution il y a deux cycles distincts :

  • un premier cycle avec Anne, Élodie, Bruno, Fidel ;
  • et un second cycle avec Claude et Denis.

Cette distribution n'est donc pas circulaire.

Exemple pour distribution_b
🐍 Script Python
distribution_b = {
    "Anne": "Claude",
    "Bruno": "Fidel",
    "Claude": "Élodie", 
    "Denis": "Anne",
    "Élodie": "Bruno",
    "Fidel": "Denis"
    }

flowchart LR
    A(["Anne"]) --> C(["Claude"])
    B([Bruno]) --> F(["Fidel"])
    C(["Claude"]) --> E(["Élodie"])
    D([Denis]) --> A
    E --> B
    F --> D

Cette distribution comporte un unique cycle : Anne, Claude, Élodie, Bruno, Fidel, Denis. Cette distribution est donc circulaire.

Une présentation est dite circulaire si elle ne présente qu'un unique cycle. Pour savoir si une distribution est circulaire, on peut utiliser l'algorithme ci-dessous :

  • on part d'un donateur initial;
  • on inspecte son destinataire dans la distribution,
  • ce destinataire devient à son tour donateur ;
  • on recommence le parcours jusqu'à ce que le destinataire soit le donateur initial ;
  • la distribution est circulaire si on l'a effectué autant de « sauts » qu'il y a de personnes dans le groupe.

Compléter la fonction est_circulaire.

Exemples 
>>> distribution_a = {
    "Anne": "Élodie",
    "Bruno": "Fidel",
    "Claude": "Denis",
    "Denis": "Claude",
    "Élodie": "Bruno",
    "Fidel": "Anne"
    }
>>> est_circulaire(distribution_a)
False
>>> distribution_b = {
    "Anne": "Claude",
    "Bruno": "Fidel",
    "Claude": "Élodie",
    "Denis": "Anne",
    "Élodie": "Bruno",
    "Fidel": "Denis"
    }
>>> est_circulaire(distribution_b)
True

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
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

.128013lS]et-d5!f18umaèg_F/R=in 6)yàqPhc[(bsx.p;r4'C90"ov+Tw73Ok:é 2030b08090j0r050F0$0B050j0F0F0q0Q090r0I0Q020t030F0h0i0i0j0K0w02060R050h0`0R0s0$000j0i0I0J0$0p08140K0y0h080F030o111315170 0I02031C1v1F0o1C0 0b0r0S0/0;0?0^0A0r0l0A051T0A090}030*0E05081O0=0@0Q1S1U1W1U091$1'1!090K1D090A0/1a0F0I0j0s0^0%0Q1)1Q0Q0e0,080s1i081!1 21261+291'2c0i2e02040$0z0K0R0I0R0F0r1d1f0(1}0K0K080B2z1v2g0s1D0o1{2L1^1`1_1#0b2i0^1W0s2b2w1!1L1N0:1*2V0r2X0s0R2#1!0I2E1D2J2L2=10201f2%272+0K14050}0$0f2I2_0~2^2h2{1+2}2 310%3421362J2U0Q3b0j30020$0X3f2K0 3i390^3l3n0$0L3r3h2_3j3x310c3B3t3D3v3k0R2~3m310u3I372`1P3a3N3c3o0W3S3u3V3w3X3P3o0g3#3K3%3M3O3y0O3,383.3F020f0P3?3U2'3/3Y0f331w351G2:1v2#2O0b1`2T3L0B2,2o0'1M1D2/082;45443g034f0(4n3@3 0Z0}0(0e3B0$3T3E0e0}1t090m0B0r0K0B0h0;4L083B4D3L0|020D4S3$3 0s4y0r0F1^0r0E1c0r1e4Y3-3 4V0v0!3I0$4^4C4Z2|0}0I080K0F1e2X1u4p2K4`4/270R0}0q4B4T3.4V0C4.4v4|024l2+0i5d4{1+4x020e3N5p583a4}2E5n5w5j1+0R0V0}2)5C3~5k1L4'0K4)4+4-554u5K1+4V074@4_5e4!5z1o0r4 4R5S575D0^5a025c5*5!5k4~50521t5i5U0^5g5{3j0i0r0}3|5S5=5V0}5X5S0t4_5+5|3k4y4H2)0j0*4Q5J3j5.5:2=6d3E4$5N5P2H655q5}0}5h6x5x3w5$615(5 4U685Y4^666E020s0E0m0(4'6i6k2E546q6N0Q6o6m3L610}432=0t6b5Z6y0Q5s0V1S1'6%3^6g6U2c6W5)6Z6/5.0d6p356r3L4#5l2E6G2E6I5f0}4?6a6c6c6!776T0`6|0+7b5;705b6^5#025M4(4*6w2@6/5~6C5,6f7v6h7n6l7D6e5W6L7h7j0}6Q6S7H6j7o5`7q6D6#7s7X7E777R7l6V7V6Y746!5.0T7t276(3`3I6-6M6/5s2E090h0K0s7:5y6P6R7(7I6X815-5b733g753^0E0}2l7c4:0}4X7K6s7v4%7x5Q808m6J020v3S0o4s4m468A0o491v094b8F2R2M0j1%8C491B5T3j790m0e0j0Z080m0A0X0}1n1p1r1t0$7f2@1I361C0Y1f0j7~0+090$0I0h0$0#0l3m1o2b8@2b0S4%0j0l4 0$0h2X0$0E0R0h0:1(4r4g5t5v8y9i0$0j0S2F0$510K0`1(210`4K0I0#1(2x0$0;0$7w5O7y4,1f0s0M4H8^0=0/4L4N4P2E8)1G362#3j1-1V1X1Z8Q3L2k2b2d0}2q060B5O0I8@0z0w1{5R2@4l5T2?458z9'3.5s4z883k4F024H4J9R4O7V8i274V8l7A7Y7k8p9H8rad678v8*357^8d7u5@510s53a46$7#7L6Aan6O5m0R5oaB3j5s5u0Ka477aGaI6 7Y5F5H8saS7$6t8q7z457B6K7g6.ai6F5'7paX6eaAa.8nav5_7+4qa%026Bah7E7=64a}aC02696+7i6/aP4 aw2Xaz7!a;76a+6Ha(7_a*a70e0e2F0`4AaJ3La:7,b78f028h8t7d4WaE7F9G6v9JbC4;7N6!aL9kbe6_020raz5GbPaWbuaibw0K2196bH8kbC7708bmbo0rbqbN3 5.0aa47=6*a$7Y4;aq3gasb6bka?ax6~bV7Ebt8c7P8o6u9I9_b@7E7Cb1a=b95_b#b37Nb}7E5sb+aO4}cgc0bc5/8b56c64l7ac1a_b^7eck7hbjcm0}7|7~bUc57`0B0}0n3m0FcA3scl6e7{0)cKa40ZcO020U0K1s8x9 8B2L8O1E020N0)0$080G4 4K0B1(6XcS0i8M0$0x981fc@c_0rc{9F1(0lbY0I0A1(144%9D8(0K0k0l1'0.2BbEc92A8(0B0j0(8;0G9r0r1j1W2990di9O4M9d500H9W0 8D0)0+0-02.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
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

.128013lS]et-d5!f18umaèg_F/R=in 6)yàqPhc[(bsx.p;r4'C90"ov+Tw73Ok:é 2030b08090j0r050F0$0B050j0F0F0q0Q090r0I0Q020t030F0h0i0i0j0K0w02060R050h0`0R0s0$000j0i0I0J0$0p08140K0y0h080F030o111315170 0I02031C1v1F0o1C0 0b0r0S0/0;0?0^0A0r0l0A051T0A090}030*0E05081O0=0@0Q1S1U1W1U091$1'1!090K1D090A0/1a0F0I0j0s0^0%0Q1)1Q0Q0e0,080s1i081!1 21261+291'2c0i2e02040$0z0K0R0I0R0F0r1d1f0(1}0K0K080B2z1v2g0s1D0o1{2L1^1`1_1#0b2i0^1W0s2b2w1!1L1N0:1*2V0r2X0s0R2#1!0I2E1D2J2L2=10201f2%272+0K14050}0$0f2I2_0~2^2h2{1+2}2 310%3421362J2U0Q3b0j30020$0X3f2K0 3i390^3l3n0$0L3r3h2_3j3x310c3B3t3D3v3k0R2~3m310u3I372`1P3a3N3c3o0W3S3u3V3w3X3P3o0g3#3K3%3M3O3y0O3,383.3F020f0P3?3U2'3/3Y0f331w351G2:1v2#2O0b1`2T3L0B2,2o0'1M1D2/082;45443g034f0(4n3@3 0Z0}0(0e3B0$3T3E0e0}1t090m0B0r0K0B0h0;4L083B4D3L0|020D4S3$3 0s4y0r0F1^0r0E1c0r1e4Y3-3 4V0v0!3I0$4^4C4Z2|0}0I080K0F1e2X1u4p2K4`4/270R0}0q4B4T3.4V0C4.4v4|024l2+0i5d4{1+4x020e3N5p583a4}2E5n5w5j1+0R0V0}2)5C3~5k1L4'0K4)4+4-554u5K1+4V074@4_5e4!5z1o0r4 4R5S575D0^5a025c5*5!5k4~50521t5i5U0^5g5{3j0i0r0}3|5S5=5V0}5X5S0t4_5+5|3k4y4H2)0j0*4Q5J3j5.5:2=6d3E4$5N5P2H655q5}0}5h6x5x3w5$615(5 4U685Y4^666E020s0E0m0(4'6i6k2E546q6N0Q6o6m3L610}432=0t6b5Z6y0Q5s0V1S1'6%3^6g6U2c6W5)6Z6/5.0d6p356r3L4#5l2E6G2E6I5f0}4?6a6c6c6!776T0`6|0+7b5;705b6^5#025M4(4*6w2@6/5~6C5,6f7v6h7n6l7D6e5W6L7h7j0}6Q6S7H6j7o5`7q6D6#7s7X7E777R7l6V7V6Y746!5.0T7t276(3`3I6-6M6/5s2E090h0K0s7:5y6P6R7(7I6X815-5b733g753^0E0}2l7c4:0}4X7K6s7v4%7x5Q808m6J020v3S0o4s4m468A0o491v094b8F2R2M0j1%8C491B5T3j790m0e0j0Z080m0A0X0}1n1p1r1t0$7f2@1I361C0Y1f0j7~0+090$0I0h0$0#0l3m1o2b8@2b0S4%0j0l4 0$0h2X0$0E0R0h0:1(4r4g5t5v8y9i0$0j0S2F0$510K0`1(210`4K0I0#1(2x0$0;0$7w5O7y4,1f0s0M4H8^0=0/4L4N4P2E8)1G362#3j1-1V1X1Z8Q3L2k2b2d0}2q060B5O0I8@0z0w1{5R2@4l5T2?458z9'3.5s4z883k4F024H4J9R4O7V8i274V8l7A7Y7k8p9H8rad678v8*357^8d7u5@510s53a46$7#7L6Aan6O5m0R5oaB3j5s5u0Ka477aGaI6 7Y5F5H8saS7$6t8q7z457B6K7g6.ai6F5'7paX6eaAa.8nav5_7+4qa%026Bah7E7=64a}aC02696+7i6/aP4 aw2Xaz7!a;76a+6Ha(7_a*a70e0e2F0`4AaJ3La:7,b78f028h8t7d4WaE7F9G6v9JbC4;7N6!aL9kbe6_020raz5GbPaWbuaibw0K2196bH8kbC7708bmbo0rbqbN3 5.0aa47=6*a$7Y4;aq3gasb6bka?ax6~bV7Ebt8c7P8o6u9I9_b@7E7Cb1a=b95_b#b37Nb}7E5sb+aO4}cgc0bc5/8b56c64l7ac1a_b^7eck7hbjcm0}7|7~bUc57`0B0}0n3m0FcA3scl6e7{0)cKa40ZcO020U0K1s8x9 8B2L8O1E020N0)0$080G4 4K0B1(6XcS0i8M0$0x981fc@c_0rc{9F1(0lbY0I0A1(144%9D8(0K0k0l1'0.2BbEc92A8(0B0j0(8;0G9r0r1j1W2990di9O4M9d500H9W0 8D0)0+0-02.