Aller au contenu

Exercices sur le paradigme de programmation fonctionnelle

I. Rappels sur le paradigme fonctionnel⚓︎

Pas d'effets de bord

Avec le paradigme fonctionnel, tous les objets sont immuables et il n'y a pas de variables globales, pas d'effets de bords.

Les affectations

Python permet d'écrire des scripts dans les trois paradigmes : impératif, programmation orientée objet, programmation fonctionelle. Nous allons expérimenter ici la programmation fonctionelle, donc s'interdire les affectation qui peuvent modifier l'état du programme, les utilisations d'objets mutables, les effets de bord.

Dans la plupart des langages fonctionnels il y a une commande qui permet de donner un nom à une expression avec une syntaxe comme let EXPR be NOM in ... Cela permet d’éviter que NOM reçoive une autre valeur dans le reste de la fonction, afin d’éviter les effets de bords. En Python, nous devrons "tricher" et utiliser des affectations en s’assurant qu’une variable ne recevra qu’une seule valeur lors de l’exécution de la fonction.

Les boucles

En programmation fonctionelle, on n'utise pas de boucles forni while. On utilise des fonctions récursives.

Les fonctions sont des données

  • Les fonctions peuvent ĂŞtre passĂ©es en paramètres d'autres fonctions.
  • Les fonctions peuvent renvoyer d'autres fonctions. C'est ce qu'on appelle l'ordre supĂ©rieur.

II. Exercices sur la structure abstraite de Liste⚓︎

Implémentation des listes utilisée dans tous les exercices

Un exemple d'interface fonctionnelle pour le type abstrait Liste

La valeur d'une liste est un tuple de tuple ce qui est une structure immuable en Python.

Exécuter le code ci-dessous (sinon les exercices ne fonctionneront pas). Il sera toujours présent (caché) dans les exercices de ce paragraphe

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

Exemple d'utilisation

Python Console Session
>>> ma_liste = creer_liste()  # (1)
>>> ma_liste
()
>>> cons(1, ma_liste)
(1, ())
>>> ma_liste
()
  1. âš  Ce sera la seule affectation de tous les exercices de cette page. Voir le paragraphe ci-dessus.

Cliquer sur le + pour lire le commentaire

Pas d'effet de bord

L'exemple précédent montre qu'on n'a pas d'effet de bord.

Contrainte

👉 Dans tous les exercices, il faudra utiliser des fonctions données ci-dessus dans l'implémentation de la structure abstraite liste.

Exercice 0 :⚓︎

Créer une liste

Ecrire l'instruction qui permet de créer la liste : (4, (3, (2, (1, ())))) sans utiliser aucune affectation. Faire l'affichage de la liste pour vérifier.

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

Solution
Python
cons(4, cons(3, cons(2, cons(1, creer_liste()))))
print(cons(4, cons(3, cons(2, cons(1, creer_liste())))))

Exercice 1 :⚓︎

Longueur d'une liste

Compléter la fonction récursive longueur qui prend en paramètre une liste implémentée comme ci-dessus liste, et renvoie la longueur de cette liste.

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

.128013b;=wlSdf-:431(gnahRp/+uerovm)q 2iyécs_Ptk0050h0y0O0r0H0f0L0F0K0f0r0L0L0d010O0H0u010406050L0x0C0C0r0z0I040g0A0f0x0+0A0q0F020r0C0u0c0F0t0y0^0z0E0x0y0L050v0=0@0_0{0:0u04051q1j1t0v1q0:0h0H0B0Z0#0%0)0#0q0p0x0r0p0y0j0u0I0O0s120F0s0H0p0s0f1V0s0O0.050U0b0f0y1C0$0(011U1W1Y1W0O1(1*1$0O0z1r1Q0Z0~0L0u0r0q0)0G011,1E010i0W0y0q160y1$2123281.2b1*2e0C2g040a0F0N0z0A0u0A0L0H11130S1 0z0z0y0K2B1j2i0q1r0v1Q2N1{1}1|1%0h2k1F0H0q2d2y1$1z1B0!1-2X2Z0q0A2%1$0u2G1r2L2N2@0;22132)292-0z0^0f1$0r1T2G0i0)030M0M0K2.0y1Y2,0A0j0G0j0n0.0n1j0r2^2{0/2`2j2}1.2 3133350y3701393b3d3f2!3i3i0.0G3o3q233s2L2W013x0r321r340s36383a3c0S3H2-3J0m0.0m3N2K3r0:3R3v0)3U3W053Y3!3D3$3G2Y3I3j0l0.0l3/1k3r1u2=1j2%2Q0h1}2V3@013%2q0R1A1r2;0y2?49483P054k4r2j0H0h0)3a2L3J3l3X0F4z4B3F3(413*3j3l0F2o0y4J4k3)3h4O1$0v3p3t2|1D1.0P0.0S0i3:4u3?4%0)0e0.0F4-2M4#3S0q0i0.0f121I0y0x0z4^4x4$2*010-040o554`4i0q4~0H0L0O0y5d4/585a0D0k550:4t4_3R4I014C2{3J264G5x3 4L3g5B274R4T405H3j5C3N0F5R4@5n294)040H4,5u045T2{4{0.1h0O0M0B4z5l5!5e4:590.5c5:5U3w5h5j5/2_5`0)5p5r5!5t5 5%5E0M4D3j3,5D4A5y4K3e4M4W0j3,4Q2f5L5G426k4Y3p5S6u5$3u5=5W2G0O530q556w57290C0H0.0Q5s5m676e5z233J446d6o6h5N0j446m2p6V4V6S6s5#5S5;586z0T6C6E6,6H6J043n5!6F3S0A0.0w6;603T4~501g536N6x5o5@776G5{041f525~49715a5^66782~5|5k7b3S5p0D6M5:0v4w4a4q4c4n1j0O4f7D2T2O0r1)7A0v4d1p563S2G0C0M0i0r0P0y0M0s6c1b1d7f0Y632_1w3s1q0}0 2B0F2d0F0J0K0z2A531+0i122I0H122Z0f1*0F0k4@7+1y1A3S1G1I1K1M1O1Q1S1:1X1Z1#7P4i2m2d2f0.0N1P1R6D5:4p563O4_7y5w6P695A0m3k3z684U6i6k8I6!4S6f8L5H8H4P3Z3B3#6g6%8U6)6=7d4 1H75546`8%0)6}040d705%4i5W0#0C0b0h0r8?7n8(5i7q5_8@5=5a7)3r6{4i6I6K8 7c0)5W5Y9e5(045*5,5.7r4i7k9p5=5g041Y5}9s79047u8-715W3e0L7h3P9a5=9c6^9j4i8:6 9C95589u8)51769490617a9Y9f727e759H5v9S299r9$9k9w937m9%7t7v7*7y1w4b7M4n5t0S0U0W0L04.

Exercice 2 :⚓︎

Minimum d'une liste

Compléter la fonction récursive minimum qui prend en paramètre une liste non vide implémentée comme ci-dessus liste, et renvoie le plus petit élément de cette liste.

👉 il faudra utiliser la fonction min de python

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

.128013b;=wlSdf-:431(gnahRp/uerovm)q 2i,yécs_Ptk5050h0x0O0r0G0f0L0E0K0f0r0L0L0d010O0G0u010406050L0w0B0B0r0y0I040g0z0f0w0+0z0q0E020r0B0u0c0E0t0x0^0y0D0w0x0L050v0=0@0_0{0:0u04051q1j1t0v1q0:0h0G0A0Z0#0%0)0#0q0p0w0r0p0x0j0u0I0O0s120E0s0G0p0s0f1V0s0O0.050U0b0f0x1C0$0(011U1W1Y1W0O1(1*1$0O0y1r1Q0Z0~0L0u0r0q0)0F011,1E010i0W0x0q160x1$2123281.2b1*2e0B2g040a0E0N0y0z0u0z0L0G11130S1 0y0y0x0K2B1j2i0q1r0v1Q2N1{1}1|1%0h2k1F0G0q2d2y1$1z1B0!1-2X2Z0q0z2%1$0u2G1r2L2N2@0;22132)292-0y0^0f1$0r1T2G0i0)030M0M0K2.0x1Y2,0z0j0l0j0n0.0n1j0r2^2{0/2`2j2}1.2 3133350x3701393b3d3f2!3i0j26040F3o3q233s2L2W013x0r321r340s36383a3c0S3H2-3J0m0.0m3O2K3r0:3S3v0)3V3X053Z3#3D3%3G2Y3I3j0l0.0l3:1k3=3t2|1D3w0z303W3z3!3B3$3F3)423+3j0Q0.0Q482_1w2=1j2%2Q0h1}2V3^013(2q0R1A1r2;0x2?3r3;3Q054G4N2j0G0h0)3a2L3J3l3Y0E4V4X4m3e4o3h3j3l0E2o0x4)4G3*4-3k1$0v3p4b3T0P0.0S0i4P2M4~4E0e0.0E544T4c2*3U0i0.0B2Y0G0B0?5b564d0)0-040o5n3@5p3U0.1Y0L0O0x5u2{3T5r0C0k5b0:494Q3S4(014Y2{3J3L3|4%4W5P4*4^5S274;4?413g5!2N3p0E5-5a5v5e50040G535L2M5/5E4E0q0.1h0O0M0A4V5C5_5c5F0.5t665o5e5~041f0x1g5D3u5w5r6a2_5:2~5y0G5A656o5|6l0.0C5H5b5{6k5e0K4#030E0S0y0q0G0x0y0E0J0f0J2p0q0O6I1+0#0E5z5B5J6j135O5Q233,3z6)5Y4,6,4:2f5%4n5)3j3-5+045.6~6C5d295=2G0O0w6K6B6c6q045B6#6b6p1.6m6%3T6e6!6u4O7f5q6y6$7e5E6.4Z446-5W406^433i5#6?5X4@6:7w6|6~791.5=3e0L7m5M6w5e5r5I665K6v4U7y0M7v0j4r4$6.7G6_7%7D2p6@4+7,7(3O6 5.7L0)730T760q787o3U0b5h2Y7i4E7h7s6D7a7c7Q5581887Y713w6r6t866x040C0H807S7a5i6L5l0B8m7T698y7a6g6i898i7p5s8B8j047l8J8H6z0C7r4v4S1u4x0v4z1j0O4B8Y2T2O0r1)4M4y4J1p674E2G0B0M0i0r0P0x0M0s6{1b1d6g0Y7V4v1x1s0|0~100G1S2d6P0K0y2A761+0i122I980q2Z0f1*0E0k5a1w3s2%3T1G1I1K1M1O1Q1S1:1X1Z1#8.5w2m2d2f0.0N1P1R7 6b4L5c3P558T5N7!4Z0Q4`7)7!7+3I9!4/5$7F5(9)4`3A3C3E9(3+9*4{4}816e8u5k5m66703T0z0.0d8r8a7M5y160b0h0ra78G5x8L6s7d8h6804913ra25}0.8c8N018g7n8s8K8M8Fam8Qa17`015=5@af7j5 5A6264auaw7Ra83_0.8D8d9H8z8IaBarai8la!8n6zaJ4E7N0XaWaq5w0q83048uaP8Aa(6das0TaWaFaQ8eayaTa$akaxaSav6y8qaE9|848va0al87a`bha;aU1g8EbkaY6nb7ag7kaja 8f6ya*7W5n0v8T4w8*8W8,4y0T0V0X04.

Exercice 3 :⚓︎

Une liste contient-elle un élément ?

Compléter la fonction récursive contient qui prend en paramètre une liste implémentée comme ci-dessus liste, et un élément v. Cette fonction doit renvoyer un booléen indiquant si v est dans liste.

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

.128013b;=wlSdf-:431(gnahRpF/uerovm)q6 72i,yécs_PtTk5050h0y0R0r0J0f0O0G0N0f0r0O0O0d010R0J0u010406050O0x0C0C0r0z0L040g0A0f0x0/0A0q0G020r0C0u0c0G0t0y0|0z0E0x0y0O050w0_0{0}0 0@0u04051u1n1x0w1u0@0h0J0B0%0)0+0-0)0q0p0x0r0p0y0j0u0L0R0s160G0s0J0p0s0f1Z0s0R0=050Y0b0f0y1G0*0,011Y1!1$1!0R1,1.1*0R0z1v1U0%120O0u0r0q0-0I011:1I010i0!0y0q1a0y1*25272c1=2f1.2i0C2k040a0G0Q0z0A0u0A0O0J15170W230z0z0y0N2F1n2m0q1v0w1U2R1 21201+0h2o1J0J0q2h2C1*1D1F0(1;2#2%0q0A2+1*0u2K1v2P2R2{0^26172-2d2;0z0|0f1*0r1X2K0i0-030P0P0N2=0y1$2:0A0j0F0j0n0=0n1n0r2|2 0?2~2n311=333537390y3b013d3f3h3j2(3m0j2a040I3s3u273w2P2!013B0r361v380s3a3c3e3g0W3L2;3N0m0=0m3S2O3v0@3W3z0-3Z3#053%3)3H3+3K2$3M3n0l0=0l3@1o3_3x301H3A0A343!3D3(3F3*3J3-463/3n0U0=0U4c2{3`2 3X3~4m423I3,3i4s3l3n0F0=0F4y4e3{4h3}4j3C3$3E3G4G453k3N0H0=0H4P3U1y2_1n2+2U0h212Z3|014H2*1E1v2^0y2`3v3^4+4H4 2n0J0h0-3e2P3N3p4W56584q4I4#3n3p0G2s0y5f4H3.4K3o1*0w3t4f3X0T0=0W0i512Q5w4@0e0=0G5C544g2.3Y0i0=3g0q0/2h0R5J5E4S010;040o5V4R5M0q0=1$0O0R0y5$4B4@5Z0K5J5I5%320=0B5/3y5X5Z0D0k5J0@4d4+3W5e01592 3N3P400G68444r5i3O2b5m5o4!476k2R3t0G6t5^5:5X5y040J5B652Q6v5~5(0=1l0R0P0B565.6C5K3X5Z5#6O5W6G045+5-5}5L2d60626O642}6757690P5a3n3;5d6,6h5h6p3;5l2j6n6i6_5t6s6u726U2d6y2K0R0x0z0q5@741=0T0N0=0v3!0O6N4z6Z6f6?6.6b483D6g5g5q3N496{2t6}6^4t0j496r04735_7e6H1$6B2{6E6!3A0=5-6Y6T7J0-6R7n4@5)6W0J5,7l507W5Y0=0D7c7+0A0=0d0d7/6w6V5|7V7_6#0=6%7m7|557p6/0j4v6=7B7w4u6l6|6-5p4J3N873S727I7}7K0477797b6O7P5x7g040S0z1k637n7u854M888e6o7D4M7z5n8G6~8I707H6u7d0-6y3i7k7Z5 7 8A82178C7r0j4%8F6@8a8)8c7A8M7C5r8*8j8k6t8S01760X8q7^6F5`045Q5S5R8X5M7Y8#4C0=1j0y8z9a5;0=6S6*8m3}5*7%7U9k911=605?8s8{7#7{9q7Q7X7-8!2}0w534,4~4.4{1n0R4;9L2X2S0r1-9I0w4/1t6P4@2K0C0P0i0r0T0y0P0s6;1f1h9d0$80501A3w1u11132F0G2h0G0M0N0z2E791/0i162M0J162%0f1.0G0k5I9?1C1E3X1K1M1O1Q1S1U1W1@1#1%1)9X5X2q2h2j0=0Q1T1V8r2}4}5K3T5D9G6+5f5a0H5s8+7v8gaO5k6m8;7waT2b4n4Y8,aSaP3@7+7#940J5T909A017;047@9v7+6y0)0C0b0h0ra/9b7$7(977~049u7O9w5{b49s8Za^9l8|8v7i0#7)3U8t4@6y6Ab07!6H5,6K6Mbb9B5!bw3Y9nb39g8Y047.be9r8T7L8WbHa:7f0=8x9fb8a_0=bpbMb19y3vbm5Xa=7?bq5X7#7Tbk5D7+999zb16Xb,av989CbWbnbKb?b!6Va,a.bDb^byc2929dbR7*bfb/c9bIbAb29pcca:9tb(7`bz609D9=9G1A4-9U4{640W0Y0!0O04.

Exercice 4 :⚓︎

Fonction d'ordre supérieur

Compléter applique(f, liste) qui renvoie une nouvelle liste correspondant aux images des éléments de liste par la fonction f.

Exemple :

Python Console Session
>>> applique(lambda x: x*x, cons(4, cons(13, cons(1, cons(5, creer_liste())))))
(16, (169, (1, (25, ()))))

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

.128013b=wlSdf-:431(gnahp/uerovm)q 2i,y9cs_Ptk5050g0v0M0q0E0e0J0C0I0e0q0J0J0c010M0E0s010406050J0u0z0z0q0w0G040f0x0e0u0)0x0p050t0:0=0@0_0.0s040519121c0t190.0g0E0y0X0Z0#0%0Z0p0o0u0q0o0v0i0s0G0M0r100C0r0E0o0r0e1E0r0M0,050S0b0e0v1l0!0$011D1F1H1F0M1N1P1L0M0w1a1z0X0|0J0s0q0p0%0D011R1n010h0U0v0p0q0z0v1L1-1/1@1T1`1P1}1 0,0a0C0L0w0x0s0x0J0E0 0p0C0Q1+0w0w0v0I2k12220p1a0t1z2x1%1)1(1M0g241o0E0p1|2h1L1i1k0Y1S2H2J0p0x2N1L0s2q1a2v2x2!0/1.2l2P1^2T0w0?0e1L0q1C2q0h0%030K0K0I2U0v1H2S0x0i0H0i0m0,0m120q2#2(0-2%232*1T2,2.2:2=0v2@012_2{2}2 2K320i1=040D383a1/3c2v2G013h0q2/1a2;0r2?2^2`2|0Q3r2T3t0l0,0l3y2u3b0.3C3f0%3F3H053J3L3n3N3q2I3s330k0,0k3W133Y3d2)1m3g0x2-3G3j3K3l3M3p3P3/3R330O0,0O3^2$1f2Y122N2A0g1)2F3#013O201a4j1b4h4f2$4q2Z2(0C0E0g0%2`2v3t353I4B4D013-47304H1?280v4E462~4831334I3W3!3}0%0N0,0Q0h3X3A3{3D0d0,0C4-2w4/4o0p0h0,0q0s0s1H0B0u0v4@4z3e4%010+040n554_580p0,4,3_4.4$2Q590,0F554?5l2+0,1H0J0M545j4^5s1T5a0A0j550.5z562l4C4U4G333v3)4K4U4q3Q4Y3u4R1~4T4M4V5U3t5P0t390C5+5r4A4o4)040E5i2!5-575m5g040v5w0K0y4C5y2$5B0%5a5c5I5e5`5u0E5w623b691^5D5F5I5H634A5L5!5N0i3T4J6o4N4W4P333T0C4S5S3.6x6r1L5)045,6J5^3|5m5:2q0M0u0w115I6L3D5{0I2q0v0w0K5v5x5d645n5b0A5G6)6n4L4F2(3t3=6t6;5#4X6@5X1 6C4O3:0i6^3y6J6g1T5:2~0J6e5k5.585a6j2!6l6f3C6u0K6q4b6_706w724b6A5Y7r5$4a6G5*6K5+774(0,6P6R6T5@7E3E0,2|0p0J6/5_6h0,676m7S3g5h7R6M7T5b7!6W0,5x6(686*667(4`6b6d7:7f0,0A0A5p6U7L5{4~500E527c5A7e5m7/7-865t045?7k8a5C5o5q7~0,83537@877U8n8b6%845J3D5D7`6.680t4y1d4h0t4t2y4l122B8I0q1O0v2x4j5H0Q0S0U0J04.

III. Exercices sur la structure abstraite d'arbre binaire⚓︎

On représentera dans tous les exercices qui suivent les arbres binaires ainsi :

  • l'arbre vide est reprĂ©sentĂ© par None,
  • un arbre non vide est reprĂ©sentĂ© par un tuple (sous-arbre gauche, valeur, sous-arbre droit).

Ainsi le tuple ((None, 6, None), 15, None) représente l'arbre suivant :

graph TD
    R(15) --> A(6)
    R -.-x B( )
    A -.-x C( )
    A -.-x D( )
    style B display:none;
    style C display:none;
    style D display:none;

Exercice 5 :⚓︎

Fonctions de base à réutiliser dans les autres exercices

Compléter les fonctions est_vide, gauche, droite, racine qui prennent en paramètre un arbre binaire implémenté comme ci-dessus, et renvoient respectivement un booléen indiquant si l'arbre est vide, le sous arbre gauche, le sous arbre droit, la racine de arbre

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

.128013b]=wlSd[f-:431(gnahp/uerovm)6 72iy9c8s_PNtk05050h0x0Q0s0H0f0M0E0K0f0s0M0M0d010Q0H0u010406050M0w0B0B0s0y0I040g0z0f0w0.0z0r050v0^0`0|0~0?0u04051e171h0v1e0?0h0H0A0$0(0*0,0(0r0q0w0s0q0x0k0u0I0Q0t150E0t0H0q0t0f1J0t0Q0;050X0b0f0x1q0)0+011I1K1M1K0Q1S1U1Q0Q0y1f1E0$110M0u0s0r0,0G011W1s010j0Z0x0r0s0B0x1Q1=1@1|1Y1 1U22240;0a0E0O0y0z0u0z0M0H140r0E0V1:0y0y0x0K2p17270r1f0v1E2C1,1.1-1R0h291t0H0r212m1Q1n1p0%1X2M2O0r0z2S1Q0u2v1f2A2C2)0@1?2q2U1}2Y0y0{0f1Q0s1H2v0j0,030N0N0K2Z0x1M2X0z0k0o0S370;0E0o170s2*2-0=2,282/1Y2;2?2^2`0x2|012~3032342P37391`040E0G3e3g1@3i2A2L013n0s2@1f2_0t2{2}2 310V3x2Y3z0k0n3b0n3F2z3h0?3J3l0,3M3O053Q3S3t3U3w2N3y380k0m3b0m3(183*3j2.1r3m0z2=3N3p3R3r3T3v3W3`3Y3|0T3b0T412)3+2-3K3/4b3?3u3V334h363|0D3b0D4n433,463.483o3P3q3s4v3_353Z0F3b0F4E3H4p3k4H3L4J4a4L4c4N3^4g4Q3|0L3b0L4V2B4X452V4!493:3=4d3@4f4x4,390J3b0J4;3I4q3-4_4K3;4M4e4w3X4z39380;38564?4r4#4{5d4~5f4y3Z0o0o5k3d0v3f3)3H1i2%172S2F0h1.2K594w2R1o1f2$0x2(3h5C2B054w5T280H0h0,2 2A5v3p5#5%4 5g5*0E2d0x5-5t513a2C5B4G4^0R0;0V0j5V5Z4@1}0e3b63444r0j0;0x0M0Q0N0A5#0x695}1}0:040p6l584Z0r0;0|0b2v6r4Y4^6o0C0l630?425D3J5,015(2-3Z3B5c6K4*503{3A1{5=5@4P6U0k6P5A3C0E6)6a595 042v0Q0w0y166H2B0E6+6t6v0y6x6k6@3C6`4^0z67040H0M636_6m1Y0R0K0;0P156 4o6z2q6R0N5)3|3#4L7m5^6!3#5;235?6L5.5u7p1Q6%6G2+6J5$7z7o393~7r7I6S5/3|3~7w246Y4+6!7M3(7b0,6-617k3K756_70722:6c040q0s0w0K0t7i5U7!016o6q7,7{6u046w6y7 6s6B0;6D6F7(7m7K0k4k7N7V6T4i394k7T7y7P7B8k7D3f6)6*7{6-6/6;6?2)7a862:6|6~7(596o0i8G4Z0B0H0;0S8K87040c8a855!7O7n6N4A5+8X7t8j0k4B8m8h7Q394B5{3i8V7l8X8d4S8g7z8%5h0k4S8+8{6Z8(8_7Z8C7c603r8Q66688=6b602j2o7_6I960,7}9a3m8E847G9k7|886E707F7`4q8c8Z394.8`8o5_4.909F6!9D3F8t8B6A1}8w0W8y797-9o826}9q9y9P1Y8I9n0,8M0;3E9d8H0;8T9w8b8@9B0k539E7A5_539I9{6!9_3F9x9j8W5-8d5j9`8|5v0S6W7x8,8p3z8r643K7$999-4Z7*9(3L7/0y0s0K3`aq9man4^81839i5W7{6C9v7j9d9A1@5v5xa9928}5wad7U917W8(aR8:9N9V7#0;8x6=9U809paDaj9.048Jaz1}9*045z9r9#9l9/8U2+0v5Y5E5S5G5P170Q5Jb52I2D0s1Tb20v5H6G0V0X0Z0M04.

Exercice 6 :⚓︎

Taille d'un arbre binaire

Compléter la fonction récursive taille qui prend en paramètre arbre, un arbre binaire implémenté comme ci-dessus, et renvoie sa taille.

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

.128013b=wlSdf-:431(gnahp/+uerovm) 2iycs_Ptk05050g0w0K0q0E0e0H0C0G0e0q0H0H0c010K0E0s010406050H0v0A0A0q0x0F040f0y0e0v0(0y0p050t0/0;0?0^0-0s040518111b0t180-0g0E0z0W0Y0!0$0Y0p0o0v0q0o0w0i0s0F0K0r0 0C0r0E0o0r0e1D0r0K0+050R0b0e0w1k0Z0#011C1E1G1E0K1M1O1K0K0x191y0W0{0H0s0q0p0$0D011Q1m010h0T0w0p0q0A0w1K1,1.1?1S1_1O1|1~0+0a0C0J0x0y0s0y0H0E0~0p0C0P1*0x0x0w0G2j11210p190t1y2w1$1(1%1L0g231n0E0p1{2g1K1h1j0X1R2G2I0p0y2M1K0s2p192u2w2Z0.1-2k2O1@2S0x0=0e1K0q1B2p0h0$030I0I0G2T0w1G2R0y0i0m0m310+0m110q2!2%0,2$222)1S2+2-2/2;0w2?012^2`2|2~2J31331;040D37391.3b2u2F013g0q2.192:0r2=2@2_2{0P3q2S3s0i0l0+0l3x2t3a0-3B3e0$3E3G053I3K3m3M3p2H3r320i0k0+0k3W123Y3c2(1l3f0y2,3F3i3J3k3L3o3O3/3Q3;0N0+0N3_2#1e2X112M2z0g1(2E3#013N1 194k1a4i4g2#4r2Y2%0C0E0g0$2_2u3R0m3i4D4F472}49303;4J0C270w4M4r3P4Q334J2w383|3C0L0+0P0h3X3z4(4p0d0+0C4.2v4:3~3$0h0+0R0T1O4^4A3d4{010*040n524`2P3D0+0?0b2p5a3!55570B0j520-3`4/3B4L014G2%3R3u3)4C4E5u4N4Y5x1=4U4W3.2 5F4$040C5O4@5j5c4*040E4-5q2v5Q4B4p0p0+0w0H0K0I0z4D0w5i5!5k0+595X533}5c5$045f5h5@5b1@5l5n5@5p2#5s5B5v1.3R3T3H5A5I485K3;3T4T1}4V5C4X4P6b1K0t385P6u5Z545S0+2p0K0v0x105@6w5_1@0A0E0+0M5o5/225t690p3R3?6d6Q5D6p3;3?6k1~6f4O6h336U3x6u601S5T2}0H5.6F6.0$57632Z653a4(6W4H4b4K686X6)0i4c6#6m3-6g3:334c5M6v5P6^015T6A6C6E2Z6G3C6J35527q4p0y0+0u7u7j5{4 0e515 5R615=6O6H3f0+0o0q0v0G0r6?665:5c575?7U6x2*5e0x5g7T6~7H1S5l0B7A7+0$7x047z6@7:5d047D7F7Z7L6_7J7G7V7#040g2d2i7)5r837,817~3C5{5}894_7_7-6N5 0t4z1c4i0t4u2x4m112A8w0q1N0w2w4k5p0P7D0H04.

Exercice 7 :⚓︎

Hauteur d'un arbre binaire

On convient que la hauteur d'un arbre ne contenant qu'un élément est 1.

Compléter la fonction récursive hauteur qui prend en paramètre arbre, un arbre binaire implémenté comme ci-dessus, et renvoie sa hauteur.

👉 il faudra utiliser la fonction max de python

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

.128013b=wlSdf-:431(gnahp/+uerovm) x2i,ycs_Ptk05050g0w0M0q0F0e0J0C0I0e0q0J0J0c010M0F0s010406050J0v0A0A0q0x0H040f0y0e0v0*0y0p050t0;0?0^0`0/0s04051a131d0t1a0/0g0F0z0Y0!0$0(0!0p0o0v0q0o0w0i0s0H0M0r110C0r0F0o0r0e1F0r0M0-050T0b0e0w1m0#0%011E1G1I1G0M1O1Q1M0M0x1b1A0Y0}0J0s0q0p0(0E011S1o010h0V0w0p0q0A0w1M1.1:1^1U1{1Q1~200-0a0C0L0x0y0s0y0J0F100p0C0R1,0x0x0w0I2l13230p1b0t1A2y1(1*1)1N0g251p0F0p1}2i1M1j1l0Z1T2I2K0p0y2O1M0s2r1b2w2y2#0:1/2m2Q1_2U0x0@0e1M0q1D2r0h0(030K0K0I2V0w1I2T0y0i0m0E330-0m130q2$2)0.2(242+1U2-2/2;2?0w2^012`2|2~302L33351?040E393b1:3d2w2H013i0q2:1b2=0r2@2_2{2}0R3s2U3u0i0l0-0l3z2v3c0/3D3g0(3G3I053K3M3o3O3r2J3t340i0k0-0k3Y143!3e2*1n3h0y2.3H3k3L3m3N3q3Q3;3S3?0P0-0P3{2%1g2Z132O2B0g1*2G3%013P211b4m1c4k4i2%4t2!2)0C0F0g0(2{2w3T0m3k4F4H492 4b323?4L0C290w4O4t3R4S354L2y3a3~3E0N0-0R0h3Z3B4*4r0d0-0C4:2x4=403(0h0-0r0q0 0w0v0x4`4C3f4}010,040n574|2R3F0-0^0b2r5f3$5a5c0B0j570/3|4;3D4N014I2)3T3w3+4E4G5z4P4!5C1@4W4Y3:315K4(040C5T4_5o5h4,040F4/5v2x5V4D4r0p0-0w0J0M0K0z4F0w5n5)5p0-5e5$583 5h5+045k5m5|5g1_5q5s5|5u2%5x5G5A1:3T3V3J5F5N4a5P3?3V4V1 4X5H4Z4R6g1M0t3a5U6z5(595X0-2r0M55125|6B5~1_0A0F0-0O5t5@245y6e0p3T3^6i6U5I6u3?3^6p206k4Q6m356Y3z6z651U5Y2 0J5?6J6=0(5c682#0C6a3c4*6!4J4d4M6d6#6-0i4e6)6r3/6l3=354e5R6A5U6|015Y6F6H576K3E6N377t7o0y0-0u7y5W2,0b0-0@0D6S6L1U5c5{6b5^5 50520M5456647E7M5`7K3E600o520I0r6`7P6C667!7X7Q2,5j0x5l7,737Y6}0-0B0B0G7D7=3h7S53557#4r7N885a600g2f2k7`5w837}5d8b7R617^637-7L8k7 0B6R640t4B1e4k0t4w2z4o132C8G0q1P0w2y4m5u0R0T0V0J04.

Exercice 8 :⚓︎

Un arbre contient-il un élément ?

Compléter la fonction récursive appartient qui prend en paramètres arbre, un arbre binaire implémenté comme ci-dessus, et un élément valeur. Cette fonction doit renvoyer un booléen indiquant si l'élément valeur est dans l'arbre.

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

.128013b=wlSdf-:431(gnahpF/uerovm)6 2i,ycs_PtTk5050g0w0M0q0F0e0J0D0I0e0q0J0J0c010M0F0s010406050J0v0A0A0q0x0H040f0y0e0v0*0y0p050u0;0?0^0`0/0s04051a131d0u1a0/0g0F0z0Y0!0$0(0!0p0o0v0q0o0w0i0s0H0M0r110D0r0F0o0r0e1F0r0M0-050T0b0e0w1m0#0%011E1G1I1G0M1O1Q1M0M0x1b1A0Y0}0J0s0q0p0(0E011S1o010h0V0w0p0q0A0w1M1.1:1^1U1{1Q1~200-0a0D0L0x0y0s0y0J0F100p0D0R1,0x0x0w0I2l13230p1b0u1A2y1(1*1)1N0g251p0F0p1}2i1M1j1l0Z1T2I2K0p0y2O1M0s2r1b2w2y2#0:1/2m2Q1_2U0x0@0e1M0q1D2r0h0(030K0K0I2V0w1I2T0y0i0m0l330-0m130q2$2)0.2(242+1U2-2/2;2?0w2^012`2|2~302L33351?040E393b1:3d2w2H013i0q2:1b2=0r2@2_2{2}0R3s2U3u0i0l0-0l3z2v3c0/3D3g0(3G3I053K3M3o3O3r2J3t340i0k0-0k3Y143!3e2*1n3h0y2.3H3k3L3m3N3q3Q3;3S3?0P0-0P3{2#3#2)3E3)453-3p3P2 4b323?0C0-0C4h3c1e2Z132O2B0g1*2G3%014q2N1k1b2Y0w2!4z3|3B054q4Q240F0g0(2{2w3T0m3k4Y4!494r314%1@290w4+4q3R4t354(2y3a3~3E0O0-0R0h3Z4T3$400(0d0-0D542x4~4I0p0h0-0q0s1/0x0*1}0M5c4W3 2R010,040n5q5e573F5i0x0b2r5y565t5v0G5q5b5H2,0-0z3H0w0v0x5G4k4I5v0B0j5q0/4S5d3D4*014#2)3T3w3+0D5*3/4a4.3?1?0D4;4?3:5^3v1M0u3a0D645M5W5A50040F535%04663f5A0p0-0w0J0M0K0z4Y0w5V6g5I0-5x6d5z5t6i040^5E6q6w5N1U5Y5!6d5$2%5)4Z5+0K4$3?3V3J5;6N5?4-3=353V5{1 4=6O4@4s3T6S3z656.6f5s1_692r0M5T126d6:4 0I0-0t3H0J6D4i6r2m5=6P5-3?3^6T776)5 3@4:6$5}5@6Y7g4|6e656x6=6j1I6c2#6|5f0-0x0q0I3;753E5v6v6L676y5C6C7D5X0-0B5L7q1U0y0-0c0c7Q6F3(5P5R5T7M5A5v6I746E4k776Q354e7c6V4,4^3T4e6#207j6X4c7:61636/647R0(6?0S6_7X7I6=6~040N0x0v733}7,4X7?7/0i4v7=7}7^4u7h7|6(5~7l8p6-7p7Y01876^0x6`7v855B6A5k0^5n0p5p8k6;6G6u7%7J040o0q0v0I0r8i558b8T5w8V5O6A5D5F8R7E7O5K6{8J6z5Q1Q7$8;7N047P8^8C0y5904428a6s8-5j5l8O8Q7H998*7G4z8C6z0g2f2k8%5(8)0(7F8,3h7K8:9f8S9s8?989z8K8{5S5U8~7(7O5#5y0u4V4A4P4C4M130M4F9T2E2z0q1P9Q0u4D5$0R0T0V0J04.

Exercice 9:⚓︎

Maximum d'une arbre

Compléter la fonction récursive maximum qui prend en paramètre un arbre binaire non vide implémentée comme ci-dessus arbre, et renvoie le plus grand élément de cet arbre.

👉 il faudra utiliser la fonction max de python. Vous pourrez utiliser la fonction taille vue plus haut.

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

.128013b=wlSdf-:431(gnahp/uerovm)6 x2i,ycs_Ptk05050g0v0M0q0F0e0J0C0I0e0q0J0J0c010M0F0s010406050J0u0z0z0q0w0H040f0x0e0u0*0x0p050t0;0?0^0`0/0s04051a131d0t1a0/0g0F0y0Y0!0$0(0!0p0o0u0q0o0v0i0s0H0M0r110C0r0F0o0r0e1F0r0M0-050T0b0e0v1m0#0%011E1G1I1G0M1O1Q1M0M0w1b1A0Y0}0J0s0q0p0(0E011S1o010h0V0v0p0q0z0v1M1.1:1^1U1{1Q1~200-0a0C0L0w0x0s0x0J0F100p0C0R1,0w0w0v0I2l13230p1b0t1A2y1(1*1)1N0g251p0F0p1}2i1M1j1l0Z1T2I2K0p0x2O1M0s2r1b2w2y2#0:1/2m2Q1_2U0w0@0e1M0q1D2r0h0(030K0K0I2V0v1I2T0x0i0m0k330-0m130q2$2)0.2(242+1U2-2/2;2?0v2^012`2|2~302L33351?040E393b1:3d2w2H013i0q2:1b2=0r2@2_2{2}0R3s2U3u0i0l0-0l3z2v3c0/3D3g0(3G3I053K3M3o3O3r2J3t340i0k0-0k3Y143!3e2*1n3h0x2.3H3k3L3m3N3q3Q3;3S3?0P0-0P3{2#3#2)3E3)453-3p3P2 4b323?0B0-0B4h3c1e2Z132O2B0g1*2G3%014q2N1k1b2Y0v2!4z3|3B054q4Q240F0g0(2{2w3T0m3k4Y4!494r314%1@290v4+4q3R4t354(2y3a3~3E0N0-0R0h3Z4T3$400(0d0-0C542x4~4I0p0h0-0@0D0F0z0=5c4W3 2R010,040n5o5e573F0-0^0b2r5w565r5t0A0j5o0/4S5d3D4*014#2)3T3w3+0C5P3/4a4.3?1?0C4;4?3:5!3v1M0t3a0C5:5b5F1_50040F535M045=4k5f0-0v0J0M0K0y4Y0v5E5 5y5t5v5|5x5r0p5A0w5C686e5?1U5H5J5|5L2%5O4Z5Q0K4$3?3V3J5W6v5Y4-3=353V5%1 4=6w4@4s3T6A3z5;6S5~3f5y5^2r0M0u0w125|6U5q1_0z0F0-0O5K694X6D6x5S3?3^6B5X4,4^3T3^6J205)5Z6G3@5-5/5;6f5@611I5{2#6(4l0-0T0V1Q6:6)6o0-6d6t6a6g6i6k7l3E5H5o7f4I0x0-0c0c7y791U6+377v4I5t6q4i7v6{6y354e6`6=6N5+0i4e706L6E6}4d765}6T5:7G0(6X0S6!6$7e7-5z040w0q0I3;7K6b7o7~7s045B5D6m7r1_7x6r7P6=7R0i4v7U726F4c354v7!8h7%8k7)6S7@7/6Z6#818880866V6g0b5i0q0D8w7n5u8G3(0-7`7|2K8J5s8y7q8A2,7t858S7m0(5H0G7F6n8K045j5l5n8z8Y8Q8I8-7g040o0q0u0I0r6l8X7w8R4z8%7^848|90878H0A0A8#6%7@0p8C8)8E8P6c8P6h7_7{7}8;7L8 55968(939h0-998$9s7^8*5m0z9v8:8}60040g2f2k949r8T8H7p959O9t6j8W9R8.5H98986/6e0t4V4A4P4C4M130M4F9-2E2z0q1P9*0t4D5L0R7i0W04.

Crédits⚓︎

Frédéric Junier, Romain Janvier