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)
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 : 10/10

.128013bqO9vià3o_x;lpwT!f( g0]6-)2s1+8ené4è[m5tCRPhk:c.a=ryFSu/7d050*0G0O0X0g0n0C0u0V0n0X0C0C0Y010O0g0o010406050C0%0M0M0X0Z0!040$0j0n0%0~0j0H0u020X0M0o0m0u0Q0G180Z0c0%0G0C050(1517191b130o04051G1z1J0(1G130*0g0f0?0^0`0|0S0g0v0S0n1X0S0O11050.0b0n0G1S0_0{011W1Y1!1Y0O1*1,1(0O0Z1H0O0S0?1e0C0o0X0H0|0B011.1U010s0:0G0H1m0G1(24262b1:2e1,2h0M2j040a0u0R0Z0j0o0j0C0g1h1j0,220Z0Z0G0V2E1z2l0H1H0(202Q1}1 1~1)0*2n0|1!0H2g2B1(1P1R0@1/2!0g2$0H0j2*1(0o2J1H2O2Q2{14251j2,2c2;0Z180n110u0D2N2 122~2m311:3335370B3a263c2O2Z013h0X36040u0i3l2P133o3f0|3r3t0u0J3x3n2 3p3D370N3H3z3J3B3q0j343s370y3O3d301T3g3T3i3u0)3Y3A3#3C3%3V3u0F3+3Q3-3S3U3E0e3?3e3^3L040D0w3}3!2-3_3(0D391A3b1K2_1z2*2T0*1 2Y3R0V2=2t0+1Q1H2^0G2`4c4b3m054m0,4u3~460T110,0s3H3Z3p0p374I3,460H0s111x0O0k0V0g0Z0V0%0^4X0G4N3@4610040t4(4C324F0g0C1}0g0b1g0g1i4.452c4+0A0U3O0u540u4J3R0H110o0G0Z0C1i2$1y4w2P564O2c0j110Y3H5k4)4 110L4}3K5a2J2;0M5q573^4E040s3T5C5l3g5y2%5B5i3u5D460j4L042/5J5s5L041P4?0Z4^4`4|5P5R5t040x53555,5Z4s0M0g5c4%5P5r4/1:5n045p5|5=3C5a5c5e0H5g5w3R4+5v5+5K0|5^11436f5Y0|4+5/5P06555}4~5Z0,4?2/0X0.4$5X5~0|60622{6t5x5!4=4@4_2M6l6D016d6b3 5M5^5`6T4*116p2{6r5;6g3q110H0b0k6w0~2h6A2J5h6H64016F6C6u6h0g114a6$6%546_5F0p1W1,6|6J6/6y6=5{6^6)600r6G3b6I586V5_2J6Y5-526q6s6s6_595!4T7d0/7q637h5o7a7n6K5$5(6O2}6)6S6P6}6*7z6x6;7C7f4c7O6!5:7v7m6U046,6.7A7V4$6@7l6_6{7E6m7S7*7c7-6?7H3^600E7}466i413O737%4D112J0O0%0Z0H814:7)6-7`6z7W7/3m875m5o7k8n7x0b112q7r1:4+4-7Q7b6L5%6N4{8e8B6c110A3Y0(4z4t4d8P0(4g1z0O4i8U2W2R0X1+8R4g1F4B7R2J0M0k0s0X0T0G0k0S0i111r1t1v1x0u7t2}1M3c1G0d1j0X8c0/0O0u0o0%0u0I0v3s1s2g982g0f4=0X0v5c0u0%2$0u0b0j0%0@1-4y4n5G5I8N9z0u0X0f2K0u5e0Z0~1-260~4W0o0I1-2C0u0^0u5#6M5)1j0H004T990_0?4X4Z4#2J8}1K3c2*3p1=1Z1#1%8)3p2p2g2i112v0$0V5%0o980R0!205*2}4s8)2|4c8O9{3R5F4G8x0|5U568I3 4R044T4V9+4!7Wal6R118A7N7@7y9X8E9Zay508~3b867x665d5f1x8f5 7G7?6Q7PaC6Q7y4s5AaS0|5F5H0Za%7Sa#0j5O7g7@5T115WaV7RaE8D7L8GaI7!7u6(aD7o6Xa_3p7=a;aZaO686aap6Z046eaY7R836kbi3p6o7#8o5?67aQa,b87:6)a!8+7p7X3maMbx4S0s0s2K0~4Hb63Rbv8sbx8u048wbe5-aB7Yb37J9Y7MbWaW8Kbp7511a*a,7y0gbu5Ua^b9a`bQ0Z269na 4,ay7y0GbGbI0gbKb=b7110za,8371b#7RaJbp7wbE045baP69bB5j7;aUc47IaFa}aacbbn5ub}bbbtbT8yb06$7$746)5Fc2b,cyckbu8qcJchbzb5bm8J04aKbCcE7vb)048a8c8Hcp5E0V110#3s0Ccl12cf7@5Fc#8da,0Tc*040q0Z1w8Mag8Q2Q8%1I040P0-0u0G0l5c4W0V1-6?c.0M8#0u0h9p1jdadc0gde9W1-0vb^0o0S1-184=9U8|0Z0K0v1,0=2Gcr8F1ids0=0V0X0,950l9I0g1n1!2e9hdB9(4Y9u5d0W9:138S0-0/0;04.

###(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 : 10/10

.128013bqO9vià3o_x;lpwT!f( g0]6-)2s1+8ené4è[m5tCRPhk:c.a=ryFSu/7d050*0G0O0X0g0n0C0u0V0n0X0C0C0Y010O0g0o010406050C0%0M0M0X0Z0!040$0j0n0%0~0j0H0u020X0M0o0m0u0Q0G180Z0c0%0G0C050(1517191b130o04051G1z1J0(1G130*0g0f0?0^0`0|0S0g0v0S0n1X0S0O11050.0b0n0G1S0_0{011W1Y1!1Y0O1*1,1(0O0Z1H0O0S0?1e0C0o0X0H0|0B011.1U010s0:0G0H1m0G1(24262b1:2e1,2h0M2j040a0u0R0Z0j0o0j0C0g1h1j0,220Z0Z0G0V2E1z2l0H1H0(202Q1}1 1~1)0*2n0|1!0H2g2B1(1P1R0@1/2!0g2$0H0j2*1(0o2J1H2O2Q2{14251j2,2c2;0Z180n110u0D2N2 122~2m311:3335370B3a263c2O2Z013h0X36040u0i3l2P133o3f0|3r3t0u0J3x3n2 3p3D370N3H3z3J3B3q0j343s370y3O3d301T3g3T3i3u0)3Y3A3#3C3%3V3u0F3+3Q3-3S3U3E0e3?3e3^3L040D0w3}3!2-3_3(0D391A3b1K2_1z2*2T0*1 2Y3R0V2=2t0+1Q1H2^0G2`4c4b3m054m0,4u3~460T110,0s3H3Z3p0p374I3,460H0s111x0O0k0V0g0Z0V0%0^4X0G4N3@4610040t4(4C324F0g0C1}0g0b1g0g1i4.452c4+0A0U3O0u540u4J3R0H110o0G0Z0C1i2$1y4w2P564O2c0j110Y3H5k4)4 110L4}3K5a2J2;0M5q573^4E040s3T5C5l3g5y2%5B5i3u5D460j4L042/5J5s5L041P4?0Z4^4`4|5P5R5t040x53555,5Z4s0M0g5c4%5P5r4/1:5n045p5|5=3C5a5c5e0H5g5w3R4+5v5+5K0|5^11436f5Y0|4+5/5P06555}4~5Z0,4?2/0X0.4$5X5~0|60622{6t5x5!4=4@4_2M6l6D016d6b3 5M5^5`6T4*116p2{6r5;6g3q110H0b0k6w0~2h6A2J5h6H64016F6C6u6h0g114a6$6%546_5F0p1W1,6|6J6/6y6=5{6^6)600r6G3b6I586V5_2J6Y5-526q6s6s6_595!4T7d0/7q637h5o7a7n6K5$5(6O2}6)6S6P6}6*7z6x6;7C7f4c7O6!5:7v7m6U046,6.7A7V4$6@7l6_6{7E6m7S7*7c7-6?7H3^600E7}466i413O737%4D112J0O0%0Z0H814:7)6-7`6z7W7/3m875m5o7k8n7x0b112q7r1:4+4-7Q7b6L5%6N4{8e8B6c110A3Y0(4z4t4d8P0(4g1z0O4i8U2W2R0X1+8R4g1F4B7R2J0M0k0s0X0T0G0k0S0i111r1t1v1x0u7t2}1M3c1G0d1j0X8c0/0O0u0o0%0u0I0v3s1s2g982g0f4=0X0v5c0u0%2$0u0b0j0%0@1-4y4n5G5I8N9z0u0X0f2K0u5e0Z0~1-260~4W0o0I1-2C0u0^0u5#6M5)1j0H004T990_0?4X4Z4#2J8}1K3c2*3p1=1Z1#1%8)3p2p2g2i112v0$0V5%0o980R0!205*2}4s8)2|4c8O9{3R5F4G8x0|5U568I3 4R044T4V9+4!7Wal6R118A7N7@7y9X8E9Zay508~3b867x665d5f1x8f5 7G7?6Q7PaC6Q7y4s5AaS0|5F5H0Za%7Sa#0j5O7g7@5T115WaV7RaE8D7L8GaI7!7u6(aD7o6Xa_3p7=a;aZaO686aap6Z046eaY7R836kbi3p6o7#8o5?67aQa,b87:6)a!8+7p7X3maMbx4S0s0s2K0~4Hb63Rbv8sbx8u048wbe5-aB7Yb37J9Y7MbWaW8Kbp7511a*a,7y0gbu5Ua^b9a`bQ0Z269na 4,ay7y0GbGbI0gbKb=b7110za,8371b#7RaJbp7wbE045baP69bB5j7;aUc47IaFa}aacbbn5ub}bbbtbT8yb06$7$746)5Fc2b,cyckbu8qcJchbzb5bm8J04aKbCcE7vb)048a8c8Hcp5E0V110#3s0Ccl12cf7@5Fc#8da,0Tc*040q0Z1w8Mag8Q2Q8%1I040P0-0u0G0l5c4W0V1-6?c.0M8#0u0h9p1jdadc0gde9W1-0vb^0o0S1-184=9U8|0Z0K0v1,0=2Gcr8F1ids0=0V0X0,950l9I0g1n1!2e9hdB9(4Y9u5d0W9:138S0-0/0;04.