Diverses files

Un exercice : deux versions

Cet exercice sur les files est proposé en deux versions :

On s'intéresse sur cette page au type abstrait de données « File » que l'on munit des fonctions primitives suivantes :

  • cree_file_vide() : crée et renvoie une file vide ;
  • est_vide(f) : renvoie le booléen indiquant si la file f passée en paramètre est vide ou non ;
  • enfile(f, x) : enfile la valeur x à la queue de la file f ;
  • defile(f) : défile et renvoie la valeur à la tête de la file f. Provoque une erreur si la file est vide.

Ces diverses fonctions sont déjà chargées.

Les lignes ci-dessous présentent un exemple d'utilisation. On prendra soin, dans les différents exercices, de n'utiliser que les fonctions présentées ci-dessous.

Utilisation 
>>> f = cree_file_vide()  # création d'une file vide
>>> est_vide(f)           # la file est-elle vide ? -> Oui
True
>>> enfile(f, 0)          # enfile 0 dans la file
>>> est_vide(f)           # la file est-elle vide ? -> Non
False
>>> enfile(f, 1)          # enfile 1 dans la file
>>> f                     # affichage du contenu de f
1 | 0 <- tête
>>> defile(f)             # défile une valeur
1
>>> f
1 <- tête
>>> q = cree_file_vide()
>>> enfile(q, 1)
>>> q
1 <- tête
>>> f == q                # les files f et q sont-elles égales ? -> Oui
True

Les exercices ci-dessous sont indépendants. Ils sont néanmoins présentés dans un certain ordre permettant d'aborder successivement plusieurs techniques.

Jouons le jeu !

Disons-le dès maintenant : les files mises en œuvre ici utilisent la classe deque du module collections et peuvent donc subir toutes les opérations classiques applicables à ces objets.

Toutefois, ces exercices visent à utiliser certaines techniques classiques liées aux files. Il est donc demandé de les traiter en se limitant à l'utilisation des fonctions primitives présentées.

1. Calculer la taille d'une file

Écrire la fonction taille qui prend en paramètre une file et renvoie son nombre d'éléments.

A l'issue du traitement, la file doit avoir retrouvé son état initial.

>>> f = cree_file_vide()
>>> taille(f)
0
>>> enfile(f, "a")
>>> enfile(f, "b")
>>> taille(f)
2
Aide

On pourra utiliser un compteur et une file annexe.

###(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

.1280135tf4)+2r3,sao iug08m1P6pnl7he=cy:v9(wS/b_dk050Q0D0c0m0p0A0l0o0F0A0m0l0l0E010c0p0y010406050l0q0u0u0m0i0G040M0n0A0q0,0n0z050N0?0^0`0|0;0y04151c051f0N1f1h1c0;0Q0p0I0!0$0(0*0C0p0r0C0A1v0C0c0/050V0O0A0D1q0%0)011u1w1y1w0c1E1G1C0c0O0n0Q0|1D0i1d0c0C0!0 0l0y0m0z0*0h011I1s010d0X0D0z0m0u0D1C1*1,1;1K1@1G1`1|0/0a0o0w0i0n0y0n0l0p120z0o0T1(0i0i0D0F2h151 0z1d0N1$2u0c1!1Z1#0Q210*1y0z1_2e1C1n1p0#1J2E0p2G0z1W1o1C0y2n1d2s2u2Y0=1+2i2M1=2R0i0_0A0/0v2r2$0:2#202(1K2*2,0/0h2:1,2=2s2D012`0m2-040j2~2t0;312^0*34360e39302$323f0/0b3i3b3k3d330n2+350/0x3p2?2%1r2_3u2{040B3z3c3C3e3E3w040t3I3r3K3t3v360J3i1e2W152K2x0Q2B320F1W1}1d3#1g3Z2!162;053*0T2X3R2N010R0/0T0d3X3J3|0L0/0o423{2)0d0/0V0X1G482@3S0.040K4g3B3|0z0/413=2 3A324j0f0H3p0o4A47432)0/0r3i4C491K0n0/0E4H4u3s4p040F2n0D0P234V0I0p0T4m4v0/0K0f4z4B4P3S4R0c4O4D4K4M4;4J0*0u0p0/0s4+4A4-3|3~040L1u4f4s2t4I4h3|0n45042R4:58045a4n4E040D0l0c0P4Z4#5i511=4j4l5u4=3e4q4$3s4w4y5i064B5J5k3l4c4^5b1=4L040g4N5i5L3s4{2.4 5K5v2_0/1_4X5D4i4(5+4o4F5.5w0/0k5O5l5%04401^5;1K5x5~5B044r2!5A014w4*5H5J5$0*53555}5V6c015d0/5g5^5M5n5p5r4!0D61675-5z4_335:6x5P5 0/4x5!6b664R5)6g656y606B5_62643?664j5@6h6I3 0D5*6P4%4k6u4R4G6$5E6E692Y5I4,66532n0c0q0i146X6y4/3z0N3^0D2u2V733!1o3$2x2z2v1V1X2x0m1F760N3#0;7j0U0W0Y04.

###(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

.1280135tf4)+2r3,sao iug08m1P6pnl7he=cy:v9(wS/b_dk050Q0D0c0m0p0A0l0o0F0A0m0l0l0E010c0p0y010406050l0q0u0u0m0i0G040M0n0A0q0,0n0z050N0?0^0`0|0;0y04151c051f0N1f1h1c0;0Q0p0I0!0$0(0*0C0p0r0C0A1v0C0c0/050V0O0A0D1q0%0)011u1w1y1w0c1E1G1C0c0O0n0Q0|1D0i1d0c0C0!0 0l0y0m0z0*0h011I1s010d0X0D0z0m0u0D1C1*1,1;1K1@1G1`1|0/0a0o0w0i0n0y0n0l0p120z0o0T1(0i0i0D0F2h151 0z1d0N1$2u0c1!1Z1#0Q210*1y0z1_2e1C1n1p0#1J2E0p2G0z1W1o1C0y2n1d2s2u2Y0=1+2i2M1=2R0i0_0A0/0v2r2$0:2#202(1K2*2,0/0h2:1,2=2s2D012`0m2-040j2~2t0;312^0*34360e39302$323f0/0b3i3b3k3d330n2+350/0x3p2?2%1r2_3u2{040B3z3c3C3e3E3w040t3I3r3K3t3v360J3i1e2W152K2x0Q2B320F1W1}1d3#1g3Z2!162;053*0T2X3R2N010R0/0T0d3X3J3|0L0/0o423{2)0d0/0V0X1G482@3S0.040K4g3B3|0z0/413=2 3A324j0f0H3p0o4A47432)0/0r3i4C491K0n0/0E4H4u3s4p040F2n0D0P234V0I0p0T4m4v0/0K0f4z4B4P3S4R0c4O4D4K4M4;4J0*0u0p0/0s4+4A4-3|3~040L1u4f4s2t4I4h3|0n45042R4:58045a4n4E040D0l0c0P4Z4#5i511=4j4l5u4=3e4q4$3s4w4y5i064B5J5k3l4c4^5b1=4L040g4N5i5L3s4{2.4 5K5v2_0/1_4X5D4i4(5+4o4F5.5w0/0k5O5l5%04401^5;1K5x5~5B044r2!5A014w4*5H5J5$0*53555}5V6c015d0/5g5^5M5n5p5r4!0D61675-5z4_335:6x5P5 0/4x5!6b664R5)6g656y606B5_62643?664j5@6h6I3 0D5*6P4%4k6u4R4G6$5E6E692Y5I4,66532n0c0q0i146X6y4/3z0N3^0D2u2V733!1o3$2x2z2v1V1X2x0m1F760N3#0;7j0U0W0Y04.
2. Échanger les deux valeurs de tête

Écrire la fonction echange qui prend en paramètre une file contenant au moins deux éléments et échange l'ordre des deux valeurs de tête.

La fonction ne renvoie rien, c'est la liste passée en paramètre qui est modifiée à la fin du traitement. On dit qu'elle est modifiée en place.

>>> f = cree_file_vide()
>>> enfile(f, "a")
>>> enfile(f, "b")
>>> enfile(f, "c")
>>> f
c | b | a <- tête
>>> echange(f)
>>> f
c | a | b <- tête

###(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

.1280135tf4)2r3,sao iug08m1P6pnl7he=cy:v9(wS/b_dk050P0C0c0l0o0z0k0n0E0z0l0k0k0D010c0o0x010406050k0p0t0t0l0h0F040L0m0z0p0+0m0y050M0=0@0_0{0:0x04141b051e0M1e1g1b0:0P0o0H0Z0#0%0)0B0o0q0B0z1u0B0c0.050U0N0z0C1p0$0(011t1v1x1v0c1D1F1B0c0N0m0P0{1C0h1c0c0B0Z0~0k0x0l0y0)0g011H1r010d0W0C0y0l0t0C1B1)1+1:1J1?1F1_1{0.0a0n0v0h0m0x0m0k0o110y0n0S1%0h0h0C0E2g141~0y1c0M1#2t0c1Z1Y1!0P200)1x0y1^2d1B1m1o0!1I2D0o2F0y1V1n1B0x2m1c2r2t2X0;1*2h2L1;2Q0h0^0z0.0n0u2q2#0/2!1 2%1J2)2+2-0g2:1+2=2r2C012`0l2,040n0i2~2s0:312^0)34360n0e3a302#323g2-0b3k3c3m3e330m2*352-0w3r2?2$1q2_3w2{370A3B3d3E3f3G3y370s3K3t3M3v3x3h0I3S2@3U3o040u0r3k1d2V142J2w0P2A320E1V1|1c3.1f3,2Z152;053?0S2W3T2M010Q0.0S0d3*3L450K2-4b442(0d0.2n0B1+0q0C4g3!450-040J4q3D450y0.4a3~2 3C324t0f0G3r0n4K0n4E3u4z040C0z0c0O2/4C2s4M4c1;0m0.0D3k4Y4h2_480C224p4W434r1;4t4v4:4N3#4A4w4F0.0f4J4L4`4y4k4S0O2}4:4)4=1J4#044%59532(4,4.4}3u4@5l4{044B2Z4Z1J4G514K5h4+040q4(5y0)5d5f2X5a4x5i040E2m0C0O4.0O0H0o0S5o4s0.0J504:064L5I3247040K1t1F5C5t5E4e042Q0c5.4*3f4k0k4T5S5U4_5/015n605_334|645b0)4G4I5!5$5$5D664Q0y5k685J5u5X5V5K5B6l4~040j5^696h491@6p6n4u6B5`5q6E624 5Z2X5#52614P1^6k5s65636S6x4P5r3 614t6v5g6O554T586V6m6a4 5w5%4O4k6j6A6s5m6o6_5p6Y4D6!0.6$5H6g6P564V6,6t6K2;6M5x615)5+6^73610m5;5?6w6-6h0C5|5R5T4/786`6D6|545A6H6b6:6f6(6i6R6Z6T6{7v6}7B717n3n5j7h7I6x6U7T7o4P6r7L5W040f7a2 0:0M410C2t2U7-3-1n3/2w2y2u1U1W2w0l1E7:0M3.7*0S0U0W0k04.

###(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

.1280135tf4)2r3,sao iug08m1P6pnl7he=cy:v9(wS/b_dk050P0C0c0l0o0z0k0n0E0z0l0k0k0D010c0o0x010406050k0p0t0t0l0h0F040L0m0z0p0+0m0y050M0=0@0_0{0:0x04141b051e0M1e1g1b0:0P0o0H0Z0#0%0)0B0o0q0B0z1u0B0c0.050U0N0z0C1p0$0(011t1v1x1v0c1D1F1B0c0N0m0P0{1C0h1c0c0B0Z0~0k0x0l0y0)0g011H1r010d0W0C0y0l0t0C1B1)1+1:1J1?1F1_1{0.0a0n0v0h0m0x0m0k0o110y0n0S1%0h0h0C0E2g141~0y1c0M1#2t0c1Z1Y1!0P200)1x0y1^2d1B1m1o0!1I2D0o2F0y1V1n1B0x2m1c2r2t2X0;1*2h2L1;2Q0h0^0z0.0n0u2q2#0/2!1 2%1J2)2+2-0g2:1+2=2r2C012`0l2,040n0i2~2s0:312^0)34360n0e3a302#323g2-0b3k3c3m3e330m2*352-0w3r2?2$1q2_3w2{370A3B3d3E3f3G3y370s3K3t3M3v3x3h0I3S2@3U3o040u0r3k1d2V142J2w0P2A320E1V1|1c3.1f3,2Z152;053?0S2W3T2M010Q0.0S0d3*3L450K2-4b442(0d0.2n0B1+0q0C4g3!450-040J4q3D450y0.4a3~2 3C324t0f0G3r0n4K0n4E3u4z040C0z0c0O2/4C2s4M4c1;0m0.0D3k4Y4h2_480C224p4W434r1;4t4v4:4N3#4A4w4F0.0f4J4L4`4y4k4S0O2}4:4)4=1J4#044%59532(4,4.4}3u4@5l4{044B2Z4Z1J4G514K5h4+040q4(5y0)5d5f2X5a4x5i040E2m0C0O4.0O0H0o0S5o4s0.0J504:064L5I3247040K1t1F5C5t5E4e042Q0c5.4*3f4k0k4T5S5U4_5/015n605_334|645b0)4G4I5!5$5$5D664Q0y5k685J5u5X5V5K5B6l4~040j5^696h491@6p6n4u6B5`5q6E624 5Z2X5#52614P1^6k5s65636S6x4P5r3 614t6v5g6O554T586V6m6a4 5w5%4O4k6j6A6s5m6o6_5p6Y4D6!0.6$5H6g6P564V6,6t6K2;6M5x615)5+6^73610m5;5?6w6-6h0C5|5R5T4/786`6D6|545A6H6b6:6f6(6i6R6Z6T6{7v6}7B717n3n5j7h7I6x6U7T7o4P6r7L5W040f7a2 0:0M410C2t2U7-3-1n3/2w2y2u1U1W2w0l1E7:0M3.7*0S0U0W0k04.
3. Récupérer la dernière valeur de la file

Écrire la fonction dernier qui prend en paramètre une file contenant au moins un élément et renvoie la valeur de l'élément en queue de file.

À l'issue du traitement, la file doit avoir retrouvé son état initial.

>>> f = cree_file_vide()
>>> enfile(f, "a")
>>> enfile(f, "b")
>>> enfile(f, "c")
>>> f
c | b | a <- tête
>>> dernier(f)
'c'
>>> f
c | b | a <- tête
Aide

On pourra défiler un élément avant de rentrer dans la boucle classique.

###(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

.1280135tf4)2r3,sao iug08m1P6pnl7he=cy:v9(wS/b_dk050P0C0c0l0o0z0k0n0E0z0l0k0k0D010c0o0x010406050k0p0t0t0l0h0F040L0m0z0p0+0m0y050M0=0@0_0{0:0x04141b051e0M1e1g1b0:0P0o0H0Z0#0%0)0B0o0q0B0z1u0B0c0.050U0N0z0C1p0$0(011t1v1x1v0c1D1F1B0c0N0m0P0{1C0h1c0c0B0Z0~0k0x0l0y0)0g011H1r010d0W0C0y0l0t0C1B1)1+1:1J1?1F1_1{0.0a0n0v0h0m0x0m0k0o110y0n0S1%0h0h0C0E2g141~0y1c0M1#2t0c1Z1Y1!0P200)1x0y1^2d1B1m1o0!1I2D0o2F0y1V1n1B0x2m1c2r2t2X0;1*2h2L1;2Q0h0^0z0.0n0u2q2#0/2!1 2%1J2)2+2-0g2:1+2=2r2C012`0l2,040n0i2~2s0:312^0)34360n0e3a302#323g2-0b3k3c3m3e330m2*352-0w3r2?2$1q2_3w2{370A3B3d3E3f3G3y370s3K3t3M3v3x3h0I3S2@3U3o040u0r3k1d2V142J2w0P2A320E1V1|1c3.1f3,2Z152;053?0S2W3T2M010Q0.0S0d3*3L450K2-4b442(0d480C0h0y0o4l4g3!450-040J4q3D450y0.4a3~2 3C324t0f0G3r0n4K0n4E3u4z040q3k4M4c1;0m0.0D4S4N3#0.0E2m0C0O224)0H0o0S4w4F0.0J0f4J4L4!4y0.0C0z0c4Z4U1J4W044Y4C2s4T4h2_4k4+4:3u4t4v56434r2(4A5d3U4G4^4K4`1;47040K1t1F50590)0m4e042Q4 5h585j5a040C0k0c0O4-4/5h5r1J5f5m4{044B2Z510)4G4I5h064L5*5H4x5k5K0y5c5R5!015U5=5z330.4R5_5I5#0.0j5y5 5{5K4~5V1;5o5(5+4_5?4P4}5F2X5,3253556i5S3f5b1@685T4=6s6p5X6v5@0.4@6b6d5`5t5v6r5G6o015B0.5E635-5J5L5N5P0C6y5^5Z5`4P5}6X645$5p5+6J6f5:6H6#6P604u6y4P5Y3 5?4t626I6e6q5x5~6/6z6;703n5|6V6A6B2X5)6D646+5;6.4;737g4O5l745e616O75666h6^5`6a7a5*6J5t2m0c0p4m7p7k7r3B0M410C2t2U7K3-1n3/2w2y2u1U1W2w0l1E7N0M3.0:7!0T0V0X04.

###(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

.1280135tf4)2r3,sao iug08m1P6pnl7he=cy:v9(wS/b_dk050P0C0c0l0o0z0k0n0E0z0l0k0k0D010c0o0x010406050k0p0t0t0l0h0F040L0m0z0p0+0m0y050M0=0@0_0{0:0x04141b051e0M1e1g1b0:0P0o0H0Z0#0%0)0B0o0q0B0z1u0B0c0.050U0N0z0C1p0$0(011t1v1x1v0c1D1F1B0c0N0m0P0{1C0h1c0c0B0Z0~0k0x0l0y0)0g011H1r010d0W0C0y0l0t0C1B1)1+1:1J1?1F1_1{0.0a0n0v0h0m0x0m0k0o110y0n0S1%0h0h0C0E2g141~0y1c0M1#2t0c1Z1Y1!0P200)1x0y1^2d1B1m1o0!1I2D0o2F0y1V1n1B0x2m1c2r2t2X0;1*2h2L1;2Q0h0^0z0.0n0u2q2#0/2!1 2%1J2)2+2-0g2:1+2=2r2C012`0l2,040n0i2~2s0:312^0)34360n0e3a302#323g2-0b3k3c3m3e330m2*352-0w3r2?2$1q2_3w2{370A3B3d3E3f3G3y370s3K3t3M3v3x3h0I3S2@3U3o040u0r3k1d2V142J2w0P2A320E1V1|1c3.1f3,2Z152;053?0S2W3T2M010Q0.0S0d3*3L450K2-4b442(0d480C0h0y0o4l4g3!450-040J4q3D450y0.4a3~2 3C324t0f0G3r0n4K0n4E3u4z040q3k4M4c1;0m0.0D4S4N3#0.0E2m0C0O224)0H0o0S4w4F0.0J0f4J4L4!4y0.0C0z0c4Z4U1J4W044Y4C2s4T4h2_4k4+4:3u4t4v56434r2(4A5d3U4G4^4K4`1;47040K1t1F50590)0m4e042Q4 5h585j5a040C0k0c0O4-4/5h5r1J5f5m4{044B2Z510)4G4I5h064L5*5H4x5k5K0y5c5R5!015U5=5z330.4R5_5I5#0.0j5y5 5{5K4~5V1;5o5(5+4_5?4P4}5F2X5,3253556i5S3f5b1@685T4=6s6p5X6v5@0.4@6b6d5`5t5v6r5G6o015B0.5E635-5J5L5N5P0C6y5^5Z5`4P5}6X645$5p5+6J6f5:6H6#6P604u6y4P5Y3 5?4t626I6e6q5x5~6/6z6;703n5|6V6A6B2X5)6D646+5;6.4;737g4O5l745e616O75666h6^5`6a7a5*6J5t2m0c0p4m7p7k7r3B0M410C2t2U7K3-1n3/2w2y2u1U1W2w0l1E7N0M3.0:7!0T0V0X04.