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

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

.128013vt4=wf2pmuP(:1cSsrék3;0 dg)/+nqiyelRhb_oa-050z0I0c0P0G0J0r0y0p0J0P0r0r0e010c0G0i010406050r0k0j0j0P0s0H040q0O0J0k0+0O0E0y020P0j0i0w0y0K0I0^0s0F0k0I0r050C0=0@0_0{0:0i04051q1j1t0C1q0:0z0G0b0Z0#0%0)0#0E0A0k0P0A0I0Q0i0H0c0L120y0L0G0A0L0J1V0L0c0.050U0M0J0I1C0$0(011U1W1Y1W0c1(1*1$0c0s1r1Q0Z0~0r0i0P0E0)0h011,1E010g0W0I0E160I1$2123281.2b1*2e0j2g040a0y0l0s0O0i0O0r0G11130S1 0s0s0I0p2B1j2i0E1r0C1Q2N1{1}1|1%0z2k1F0G0E2d2y1$1z1B0!1-2X2Z0E0O2%1$0i2G1r2L2N2@0;22132)292-0s0^0J1$0P1T2G0g0)030N0N0p2.0I1Y2,0O0Q0h0Q0o0.0o1j0P2^2{0/2`2j2}1.2 3133350I3701393b3d3f2!3i3i0.0h3o3q233s2L2W013x0P321r340L36383a3c0S3H2-3J0v0.0v3N2K3r0:3R3v0)3U3W053Y3!3D3$3G2Y3I3j0d0.0d3/1k3r1u2=1j2%2Q0z1}2V3@013%2q0R1A1r2;0I2?49483P054k4r2j0G0z0)3a2L3J3l3X0y4z4B3F3(413*3j3l0y2o0I4J4k3)3h4O1$0C3p3t2|1D1.0u0.0S0g3:4u3?4%0)0f0.0y4-2M4#3S0E0g0.0J121I0I0k0s4^4x4$2*010-040m554`4i0E4~0G0r0c0I5d4/585a0B0n550:4t4_3R4I014C2{3J264G5x3 4L3g5B274R4T405H3j5C3N0y5R4@5n294)040G4,5u045T2{4{0.1h0c0N0b4z5l5!5e4:590.5c5:5U3w5h5j5/2_5`0)5p5r5!5t5 5%5E0N4D3j3,5D4A5y4K3e4M4W0Q3,4Q2f5L5G426k4Y3p5S6u5$3u5=5W2G0c530E556w57290j0G0.0x5s5m676e5z233J446d6o6h5N0Q446m2p6V4V6S6s5#5S5;586z0T6C6E6,6H6J043n5!6F3S0O0.0D6;603T4~501g536N6x5o5@776G5{041f525~49715a5^66782~5|5k7b3S5p0B6M5:0C4w4a4q4c4n1j0c4f7D2T2O0P1)7A0C4d1p563S2G0j0N0g0P0u0I0N0L6c1b1d7f0Y632_1w3s1q0}0 2B0y2d0y0t0p0s2A531+0g122I0G122Z0J1*0y0n4@7+1y1A3S1G1I1K1M1O1Q1S1:1X1Z1#4o4b7*2_7y5w6P695A0v3k3z684U6i6k8x6!4S6f8A5H8w4P3Z3B3#6g6%8J6)6=7d4 1H75546`8S0)6}040e705%4i5W0#0j0M0z0P8(7n8T5i7q5_8)5=5a7)3r6{4i6I6K8;7c0)5W5Y935(045*5,5.7r4i7k9e5=5g041Y5}9h79047u8Y715W3e0r7h3P8 5=916^984i8#6 9r8`589j8U51768_8=617a9N94727e759w5v9H299g9R999l8^7m9S7t7v7*7y1w4b7M4n5t0S0U0W0r04.

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

.128013vt4=wf2pmuP(:51,cSsrék3; dg)/nqiyelRhb_oa-050A0I0c0P0G0J0t0z0r0J0P0t0t0e010c0G0i010406050t0k0j0j0P0u0H040s0O0J0k0+0O0E0z020P0j0i0y0z0K0I0^0u0F0k0I0t050D0=0@0_0{0:0i04051q1j1t0D1q0:0A0G0b0Z0#0%0)0#0E0B0k0P0B0I0Q0i0H0c0L120z0L0G0B0L0J1V0L0c0.050U0M0J0I1C0$0(011U1W1Y1W0c1(1*1$0c0u1r1Q0Z0~0t0i0P0E0)0h011,1E010g0W0I0E160I1$2123281.2b1*2e0j2g040a0z0l0u0O0i0O0t0G11130S1 0u0u0I0r2B1j2i0E1r0D1Q2N1{1}1|1%0A2k1F0G0E2d2y1$1z1B0!1-2X2Z0E0O2%1$0i2G1r2L2N2@0;22132)292-0u0^0J1$0P1T2G0g0)030N0N0r2.0I1Y2,0O0Q0d0Q0p0.0p1j0P2^2{0/2`2j2}1.2 3133350I3701393b3d3f2!3i0Q26040h3o3q233s2L2W013x0P321r340L36383a3c0S3H2-3J0x0.0x3O2K3r0:3S3v0)3V3X053Z3#3D3%3G2Y3I3j0d0.0d3:1k3=3t2|1D3w0O303W3z3!3B3$3F3)423+3j0o0.0o482_1w2=1j2%2Q0A1}2V3^013(2q0R1A1r2;0I2?3r3;3Q054G4N2j0G0A0)3a2L3J3l3Y0z4V4X4m3e4o3h3j3l0z2o0I4)4G3*4-3k1$0D3p4b3T0w0.0S0g4P2M4~4E0f0.0z544T4c2*3U0g0.0j2Y0G0j0?5b564d0)0-040m5n3@5p3U0.1Y0t0c0I5u2{3T5r0C0n5b0:494Q3S4(014Y2{3J3L3|4%4W5P4*4^5S274;4?413g5!2N3p0z5-5a5v5e50040G535L2M5/5E4E0E0.1h0c0N0b4V5C5_5c5F0.5t665o5e5~041f0I1g5D3u5w5r6a2_5:2~5y0G5A656o5|6l0.0C5H5b5{6k5e0r4#030z0S0u0E0G0I0u0z0v0J0v2p0E0c6I1+0#0z5z5B5J6j135O5Q233,3z6)5Y4,6,4:2f5%4n5)3j3-5+045.6~6C5d295=2G0c0k6K6B6c6q045B6#6b6p1.6m6%3T6e6!6u4O7f5q6y6$7e5E6.4Z446-5W406^433i5#6?5X4@6:7w6|6~791.5=3e0t7m5M6w5e5r5I665K6v4U7y0N7v0Q4r4$6.7G6_7%7D2p6@4+7,7(3O6 5.7L0)730T760E787o3U0M5h2Y7i4E7h7s6D7a7c7Q5581887Y713w6r6t866x040C0q807S7a5i6L5l0j8m7T698y7a6g6i898i7p5s8B8j047l8J8H6z0C7r4v4S1u4x0D4z1j0c4B8Y2T2O0P1)4M4y4J1p674E2G0j0N0g0P0w0I0N0L6{1b1d6g0Y7V4v1x1s0|0~100G1S2d6P0r0u2A761+0g122I980E2Z0J1*0z0n5a1w3s2%3T1G1I1K1M1O1Q1S1:1X1Z1#4K4x4v2_8T5N7!4Z0o4`7)7!7+3I9P4/5$7F5(9U4`3A3C3E9T3+9V4{4}816e8u5k5m66703T0O0.0e8r8a7M5y160M0A0P9|8G5x8L6s7d8h6804913r9@5}0.8c8N018g7n8s8K8M8Fab8Q9?7`015=5@a47j5 5A6264ajal7R9}3_0.8D8d8.8n6namaHa6apaa876yas2@af5w7N0XaLaY6d83048uaE8Aaqag7b0TaLauaF8eanaIa78la.8n8paya/9:8wa,8Ia}6daJ1g8EaTaNaj7ka8a=8faVaW4a6b0D8T4w8*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

.128013vt4=wf2pmuP(751,:cSsFrék63; dg)/nqiyelRhb_oaT-050D0L0c0S0J0M0u0C0s0M0S0u0u0e010c0J0i010406050u0k0j0j0S0w0K040t0R0M0k0/0R0H0C020S0j0i0B0C0N0L0|0w0I0k0L0u050G0_0{0}0 0@0i04051u1n1x0G1u0@0D0J0b0%0)0+0-0)0H0E0k0S0E0L0U0i0K0c0O160C0O0J0E0O0M1Z0O0c0=050Y0P0M0L1G0*0,011Y1!1$1!0c1,1.1*0c0w1v1U0%120u0i0S0H0-0h011:1I010g0!0L0H1a0L1*25272c1=2f1.2i0j2k040a0C0l0w0R0i0R0u0J15170W230w0w0L0s2F1n2m0H1v0G1U2R1 21201+0D2o1J0J0H2h2C1*1D1F0(1;2#2%0H0R2+1*0i2K1v2P2R2{0^26172-2d2;0w0|0M1*0S1X2K0g0-030Q0Q0s2=0L1$2:0R0U0z0U0p0=0p1n0S2|2 0?2~2n311=333537390L3b013d3f3h3j2(3m0U2a040h3s3u273w2P2!013B0S361v380O3a3c3e3g0W3L2;3N0A0=0A3S2O3v0@3W3z0-3Z3#053%3)3H3+3K2$3M3n0d0=0d3@1o3_3x301H3A0R343!3D3(3F3*3J3-463/3n0o0=0o4c2{3`2 3X3~4m423I3,3i4s3l3n0z0=0z4y4e3{4h3}4j3C3$3E3G4G453k3N0n0=0n4P3U1y2_1n2+2U0D212Z3|014H2*1E1v2^0L2`3v3^4+4H4 2n0J0D0-3e2P3N3p4W56584q4I4#3n3p0C2s0L5f4H3.4K3o1*0G3t4f3X0y0=0W0g512Q5w4@0f0=0C5C544g2.3Y0g0=3g0H0/2h0c5J5E4S010;040m5V4R5M0H0=1$0u0c0L5$4B4@5Z0q5J5I5%320=0b5/3y5X5Z0F0r5J0@4d4+3W5e01592 3N3P400C68444r5i3O2b5m5o4!476k2R3t0C6t5^5:5X5y040J5B652Q6v5~5(0=1l0c0Q0b565.6C5K3X5Z5#6O5W6G045+5-5}5L2d60626O642}6757690Q5a3n3;5d6,6h5h6p3;5l2j6n6i6_5t6s6u726U2d6y2K0c0k0w0H5@741=0y0s0=0v3!0u6N4z6Z6f6?6.6b483D6g5g5q3N496{2t6}6^4t0U496r04735_7e6H1$6B2{6E6!3A0=5-6Y6T7J0-6R7n4@5)6W0J5,7l507W5Y0=0F7c7+0R0=0e0e7/6w6V5|7V7_6#0=6%7m7|557p6/0U4v6=7B7w4u6l6|6-5p4J3N873S727I7}7K0477797b6O7P5x7g040T0w1k637n7u854M888e6o7D4M7z5n8G6~8I707H6u7d0-6y3i7k7Z5 7 8A82178C7r0U4%8F6@8a8)8c7A8M7C5r8*8j8k6t8S01760X8q7^6F5`045Q5S5R8X5M7Y8#4C0=1j0L8z9a5;0=6S6*8m3}5*7%7U9k911=605?8s8{7#7{9q7Q7X7-8!2}0G534,4~4.4{1n0c4;9L2X2S0S1-9I0G4/1t6P4@2K0j0Q0g0S0y0L0Q0O6;1f1h9d0$80501A3w1u11132F0C2h0C0x0s0w2E791/0g162M0J162%0M1.0C0r5I9?1C1E3X1K1M1O1Q1S1U1W1@1#1%1)4|4-9E2}9G6+5f5a0n5s8+7v8gaD5k6m8;7waI2b4n4Y8,aHaE3@7+7#940J5T909A017;047@9v7+6y0)0j0P0D0Sa!9b7$7(977~049u7O9w5{a_9s8Za*9l8|8v7i0#7)3U8t4@6y6Aa=7!6H5,6K6Mb09B5!bl3Y9na^9g8Y047.b39r8T7L8Wbwa#7f0=8x9fa}a+0=bebBa?9y3vbb5Xa%7?bf5X7#7Tb95D7+999za?6XbX9XbtbvbHb48Ub8bT6VaXaZbs989ibo7#9dbG7*b4b!b~bxbpa@9pc1a#9tb:92bN66b 9C6(5V9F3h2R4}2R9V4.0X0Z0#04.

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 : 

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

.128013vt4=wf2pmuP(:51,cSsrk3 dg)/n9qiyelh_boa-050y0H0c0N0F0I0t0x0r0I0N0t0t0e010c0F0i010406050t0k0j0j0N0u0G040s0M0I0k0)0M0C050B0:0=0@0_0.0i040519121c0B190.0y0F0b0X0Z0#0%0Z0C0z0k0N0z0H0O0i0G0c0J100x0J0F0z0J0I1E0J0c0,050S0L0I0H1l0!0$011D1F1H1F0c1N1P1L0c0u1a1z0X0|0t0i0N0C0%0h011R1n010g0U0H0C0N0j0H1L1-1/1@1T1`1P1}1 0,0a0x0l0u0M0i0M0t0F0 0C0x0Q1+0u0u0H0r2k12220C1a0B1z2x1%1)1(1M0y241o0F0C1|2h1L1i1k0Y1S2H2J0C0M2N1L0i2q1a2v2x2!0/1.2l2P1^2T0u0?0I1L0N1C2q0g0%030K0K0r2U0H1H2S0M0O0D0O0p0,0p120N2#2(0-2%232*1T2,2.2:2=0H2@012_2{2}2 2K320O1=040h383a1/3c2v2G013h0N2/1a2;0J2?2^2`2|0Q3r2T3t0w0,0w3y2u3b0.3C3f0%3F3H053J3L3n3N3q2I3s330d0,0d3W133Y3d2)1m3g0M2-3G3j3K3l3M3p3P3/3R330o0,0o3^2$1f2Y122N2A0y1)2F3#013O201a4j1b4h4f2$4q2Z2(0x0F0y0%2`2v3t353I4B4D013-47304H1?280H4E462~4831334I3W3!3}0%0v0,0Q0g3X3A3{3D0f0,0x4-2w4/4o0C0g0,0N0i0i1H0E0k0H4@4z3e4%010+040m554_580C0,4,3_4.4$2Q590,0q554?5l2+0,1H0t0c545j4^5s1T5a0A0n550.5z562l4C4U4G333v3)4K4U4q3Q4Y3u4R1~4T4M4V5U3t5P0B390x5+5r4A4o4)040F5i2!5-575m5g040H5w0K0b4C5y2$5B0%5a5c5I5e5`5u0F5w623b691^5D5F5I5H634A5L5!5N0O3T4J6o4N4W4P333T0x4S5S3.6x6r1L5)045,6J5^3|5m5:2q0c0k0u115I6L3D5{0r2q0H0u0K5v5x5d645n5b0A5G6)6n4L4F2(3t3=6t6;5#4X6@5X1 6C4O3:0O6^3y6J6g1T5:2~0t6e5k5.585a6j2!6l6f3C6u0K6q4b6_706w724b6A5Y7r5$4a6G5*6K5+774(0,6P6R6T5@7E3E0,2|0C0t6/5_6h0,676m7S3g5h7R6M7T5b7!6W0,5x6(686*667(4`6b6d7:7f0,0A0A5p6U7L5{4~500F527c5A7e5m7/7-865t045?7k8a5C5o5q7~0,83537@877U8n8b6%845J3D5D7`6.680B4y1d4h0B4t2y4l122B8I0N1O0H2x4j5H0Q0S0U0t04.

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

.128013vt4=8fw2pmuP(751:cSsr]k[630 dg)/Nn9iyelh_boa-050D0M0c0S0K0N0u0C0s0N0S0u0u0e010c0K0j010406050u0l0k0k0S0v0L040t0R0N0l0.0R0I050G0^0`0|0~0?0j04051e171h0G1e0?0D0K0b0$0(0*0,0(0I0E0l0S0E0M0T0j0L0c0O150C0O0K0E0O0N1J0O0c0;050X0Q0N0M1q0)0+011I1K1M1K0c1S1U1Q0c0v1f1E0$110u0j0S0I0,0i011W1s010g0Z0M0I0S0k0M1Q1=1@1|1Y1 1U22240;0a0C0m0v0R0j0R0u0K140I0C0V1:0v0v0M0s2p17270I1f0G1E2C1,1.1-1R0D291t0K0I212m1Q1n1p0%1X2M2O0I0R2S1Q0j2v1f2A2C2)0@1?2q2U1}2Y0v0{0N1Q0S1H2v0g0,030P0P0s2Z0M1M2X0R0T0q0B370;0C0q170S2*2-0=2,282/1Y2;2?2^2`0M2|012~3032342P37391`040C0i3e3g1@3i2A2L013n0S2@1f2_0O2{2}2 310V3x2Y3z0T0A3b0A3F2z3h0?3J3l0,3M3O053Q3S3t3U3w2N3y380T0d3b0d3(183*3j2.1r3m0R2=3N3p3R3r3T3v3W3`3Y3|0p3b0p412)3+2-3K3/4b3?3u3V334h363|0z3b0z4n433,463.483o3P3q3s4v3_353Z0o3b0o4E3H4p3k4H3L4J4a4L4c4N3^4g4Q3|0f3b0f4V2B4X452V4!493:3=4d3@4f4x4,390J3b0J4;3I4q3-4_4K3;4M4e4w3X4z39380;38564?4r4#4{5d4~5f4y3Z0q0q5k3d0G3f3)3H1i2%172S2F0D1.2K594w2R1o1f2$0M2(3h5C2B054w5T280K0D0,2 2A5v3p5#5%4 5g5*0C2d0M5-5t513a2C5B4G4^0x0;0V0g5V5Z4@1}0h3b63444r0g0;0M0u0c0P0b5#0M695}1}0:040n6l584Z0I0;0|0Q2v6r4Y4^6o0F0r630?425D3J5,015(2-3Z3B5c6K4*503{3A1{5=5@4P6U0T6P5A3C0C6)6a595 042v0c0l0v166H2B0C6+6t6v0v6x6k6@3C6`4^0R67040K0u636_6m1Y0x0s0;0H156 4o6z2q6R0P5)3|3#4L7m5^6!3#5;235?6L5.5u7p1Q6%6G2+6J5$7z7o393~7r7I6S5/3|3~7w246Y4+6!7M3(7b0,6-617k3K756_70722:6c040E0S0l0s0O7i5U7!016o6q7,7{6u046w6y7 6s6B0;6D6F7(7m7K0T4k7N7V6T4i394k7T7y7P7B8k7D3f6)6*7{6-6/6;6?2)7a862:6|6~7(596o0y8G4Z0k0K0;0B8K87040w8a855!7O7n6N4A5+8X7t8j0T4B8m8h7Q394B5{3i8V7l8X8d4S8g7z8%5h0T4S8+8{6Z8(8_7Z8C7c603r8Q66688=6b602j2o7_6I960,7}9a3m8E847G9k7|886E707F7`4q8c8Z394.8`8o5_4.909F6!9D3F8t8B6A1}8w0W8y797-9o826}9q9y9P1Y8I9n0,8M0;3E9d8H0;8T9w8b8@9B0T539E7A5_539I9{6!9_3F9x9j8W5-8d5j9`8|5v0B6W7x8,8p3z8r643K7$999-4Z7*9(3L7/0v0S0s3`aq9man4^81839i5W7{6C9v7j9d9A1@5v5xa9928}5wad7U917W8(aR8:9N9V7#0;8x6=9U809paDaj9.048Jaz1}9*045z9r9#9l9/8U2+0G5Y5E5S5G5P170c5Jb52I2D0S1Tb20G5H6G0V0X0Z0u04.

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

.128013vt4=wf2pmuP(:51cSsrk30 dg)/+niyelh_boa-050y0G0c0M0E0H0s0x0q0H0M0s0s0e010c0E0i010406050s0k0j0j0M0t0F040r0L0H0k0(0L0D050B0/0;0?0^0-0i040518111b0B180-0y0E0b0W0Y0!0$0Y0D0z0k0M0z0G0N0i0F0c0I0 0x0I0E0z0I0H1D0I0c0+050R0K0H0G1k0Z0#011C1E1G1E0c1M1O1K0c0t191y0W0{0s0i0M0D0$0h011Q1m010g0T0G0D0M0j0G1K1,1.1?1S1_1O1|1~0+0a0x0l0t0L0i0L0s0E0~0D0x0P1*0t0t0G0q2j11210D190B1y2w1$1(1%1L0y231n0E0D1{2g1K1h1j0X1R2G2I0D0L2M1K0i2p192u2w2Z0.1-2k2O1@2S0t0=0H1K0M1B2p0g0$030J0J0q2T0G1G2R0L0N0p0p310+0p110M2!2%0,2$222)1S2+2-2/2;0G2?012^2`2|2~2J31331;040h37391.3b2u2F013g0M2.192:0I2=2@2_2{0P3q2S3s0N0v0+0v3x2t3a0-3B3e0$3E3G053I3K3m3M3p2H3r320N0d0+0d3W123Y3c2(1l3f0L2,3F3i3J3k3L3o3O3/3Q3;0o0+0o3_2#1e2X112M2z0y1(2E3#013N1 194k1a4i4g2#4r2Y2%0x0E0y0$2_2u3R0p3i4D4F472}49303;4J0x270G4M4r3P4Q334J2w383|3C0u0+0P0g3X3z4(4p0f0+0x4.2v4:3~3$0g0+0R0T1O4^4A3d4{010*040m524`2P3D0+0?0K2p5a3!55570A0n520-3`4/3B4L014G2%3R3u3)4C4E5u4N4Y5x1=4U4W3.2 5F4$040x5O4@5j5c4*040E4-5q2v5Q4B4p0D0+0G0s0c0J0b4D0G5i5!5k0+595X533}5c5$045f5h5@5b1@5l5n5@5p2#5s5B5v1.3R3T3H5A5I485K3;3T4T1}4V5C4X4P6b1K0B385P6u5Z545S0+2p0c0k0t105@6w5_1@0j0E0+0w5o5/225t690D3R3?6d6Q5D6p3;3?6k1~6f4O6h336U3x6u601S5T2}0s5.6F6.0$57632Z653a4(6W4H4b4K686X6)0N4c6#6m3-6g3:334c5M6v5P6^015T6A6C6E2Z6G3C6J35527q4p0L0+0C7u7j5{4 0H515 5R615=6O6H3f0+0z0M0k0q0I6?665:5c575?7U6x2*5e0t5g7T6~7H1S5l0A7A7+0$7x047z6@7:5d047D7F7Z7L6_7J7G7V7#040y2d2i7)5r837,817~3C5{5}894_7_7-6N5 0B4z1c4i0B4u2x4m112A8w0M1N0G2w4k5p0P7D0s04.

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

.128013vt4=wf2pmuP(:51,cSsrk30 dg)/+niyelh_boax-050z0H0c0N0F0I0t0y0r0I0N0t0t0e010c0F0i010406050t0k0j0j0N0u0G040s0M0I0k0*0M0E050C0;0?0^0`0/0i04051a131d0C1a0/0z0F0b0Y0!0$0(0!0E0A0k0N0A0H0P0i0G0c0J110y0J0F0A0J0I1F0J0c0-050T0L0I0H1m0#0%011E1G1I1G0c1O1Q1M0c0u1b1A0Y0}0t0i0N0E0(0h011S1o010g0V0H0E0N0j0H1M1.1:1^1U1{1Q1~200-0a0y0l0u0M0i0M0t0F100E0y0R1,0u0u0H0r2l13230E1b0C1A2y1(1*1)1N0z251p0F0E1}2i1M1j1l0Z1T2I2K0E0M2O1M0i2r1b2w2y2#0:1/2m2Q1_2U0u0@0I1M0N1D2r0g0(030K0K0r2V0H1I2T0M0P0p0h330-0p130N2$2)0.2(242+1U2-2/2;2?0H2^012`2|2~302L33351?040h393b1:3d2w2H013i0N2:1b2=0J2@2_2{2}0R3s2U3u0P0w0-0w3z2v3c0/3D3g0(3G3I053K3M3o3O3r2J3t340P0d0-0d3Y143!3e2*1n3h0M2.3H3k3L3m3N3q3Q3;3S3?0o0-0o3{2%1g2Z132O2B0z1*2G3%013P211b4m1c4k4i2%4t2!2)0y0F0z0(2{2w3T0p3k4F4H492 4b323?4L0y290H4O4t3R4S354L2y3a3~3E0v0-0R0g3Z3B4*4r0f0-0y4:2x4=403(0g0-0J0N0 0H0k0u4`4C3f4}010,040m574|2R3F0-0^0L2r5f3$5a5c0B0n570/3|4;3D4N014I2)3T3w3+4E4G5z4P4!5C1@4W4Y3:315K4(040y5T4_5o5h4,040F4/5v2x5V4D4r0E0-0H0t0c0K0b4F0H5n5)5p0-5e5$583 5h5+045k5m5|5g1_5q5s5|5u2%5x5G5A1:3T3V3J5F5N4a5P3?3V4V1 4X5H4Z4R6g1M0C3a5U6z5(595X0-2r0c55125|6B5~1_0j0F0-0x5t5@245y6e0E3T3^6i6U5I6u3?3^6p206k4Q6m356Y3z6z651U5Y2 0t5?6J6=0(5c682#0y6a3c4*6!4J4d4M6d6#6-0P4e6)6r3/6l3=354e5R6A5U6|015Y6F6H576K3E6N377t7o0M0-0D7y5W2,0L0-0@0O6S6L1U5c5{6b5^5 50520c5456647E7M5`7K3E600A520r0J6`7P6C667!7X7Q2,5j0u5l7,737Y6}0-0B0B0q7D7=3h7S53557#4r7N885a600z2f2k7`5w837}5d8b7R617^637-7L8k7 0B6R640C4B1e4k0C4w2z4o132C8G0N1P0H2y4m5u0R0T0V0t04.

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

.128013vt4=wf2pmuP(:51,cSsFrk63 dg)/niyelh_boaT-050A0H0c0N0F0I0t0z0r0I0N0t0t0e010c0F0i010406050t0k0j0j0N0v0G040s0M0I0k0*0M0E050D0;0?0^0`0/0i04051a131d0D1a0/0A0F0b0Y0!0$0(0!0E0B0k0N0B0H0P0i0G0c0J110z0J0F0B0J0I1F0J0c0-050T0L0I0H1m0#0%011E1G1I1G0c1O1Q1M0c0v1b1A0Y0}0t0i0N0E0(0h011S1o010g0V0H0E0N0j0H1M1.1:1^1U1{1Q1~200-0a0z0l0v0M0i0M0t0F100E0z0R1,0v0v0H0r2l13230E1b0D1A2y1(1*1)1N0A251p0F0E1}2i1M1j1l0Z1T2I2K0E0M2O1M0i2r1b2w2y2#0:1/2m2Q1_2U0v0@0I1M0N1D2r0g0(030K0K0r2V0H1I2T0M0P0p0y330-0p130N2$2)0.2(242+1U2-2/2;2?0H2^012`2|2~302L33351?040h393b1:3d2w2H013i0N2:1b2=0J2@2_2{2}0R3s2U3u0P0y0-0y3z2v3c0/3D3g0(3G3I053K3M3o3O3r2J3t340P0d0-0d3Y143!3e2*1n3h0M2.3H3k3L3m3N3q3Q3;3S3?0o0-0o3{2#3#2)3E3)453-3p3P2 4b323?0x0-0x4h3c1e2Z132O2B0A1*2G3%014q2N1k1b2Y0H2!4z3|3B054q4Q240F0A0(2{2w3T0p3k4Y4!494r314%1@290H4+4q3R4t354(2y3a3~3E0w0-0R0g3Z4T3$400(0f0-0z542x4~4I0E0g0-0N0i1/0v0*1}0c5c4W3 2R010,040m5q5e573F5i0v0L2r5y565t5v0q5q5b5H2,0-0b3H0H0k0v5G4k4I5v0C0n5q0/4S5d3D4*014#2)3T3w3+0z5*3/4a4.3?1?0z4;4?3:5^3v1M0D3a0z645M5W5A50040F535%04663f5A0E0-0H0t0c0K0b4Y0H5V6g5I0-5x6d5z5t6i040^5E6q6w5N1U5Y5!6d5$2%5)4Z5+0K4$3?3V3J5;6N5?4-3=353V5{1 4=6O4@4s3T6S3z656.6f5s1_692r0c5T126d6:4 0r0-0u3H0t6D4i6r2m5=6P5-3?3^6T776)5 3@4:6$5}5@6Y7g4|6e656x6=6j1I6c2#6|5f0-0v0N0r3;753E5v6v6L676y5C6C7D5X0-0C5L7q1U0M0-0e0e7Q6F3(5P5R5T7M5A5v6I746E4k776Q354e7c6V4,4^3T4e6#207j6X4c7:61636/647R0(6?0S6_7X7I6=6~040O0v0k733}7,4X7?7/0P4v7=7}7^4u7h7|6(5~7l8p6-7p7Y01876^0v6`7v855B6A5k0^5n0E5p8k6;6G6u7%7J040B0N0k0r0J8i558b8T5w8V5O6A5D5F8R7E7O5K6{8J6z5Q1Q7$8;7N047P8^8C0M5904428a6s8-5j5l8O8Q7H998*7G4z8C6z0A2f2k8%5(8)0(7F8,3h7K8:9f8S9s8?989z8K8{5S5U8~7(7O5#5y0D4V4A4P4C4M130c4F9T2E2z0N1P9Q0D4D5$0R0T0V0t04.

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

.128013vt4=wf2pmuP(:51,cSsrk630 dg)/niyelh_boax-050A0H0c0N0F0I0t0z0r0I0N0t0t0e010c0F0i010406050t0k0j0j0N0u0G040s0M0I0k0*0M0E050D0;0?0^0`0/0i04051a131d0D1a0/0A0F0b0Y0!0$0(0!0E0B0k0N0B0H0P0i0G0c0J110z0J0F0B0J0I1F0J0c0-050T0L0I0H1m0#0%011E1G1I1G0c1O1Q1M0c0u1b1A0Y0}0t0i0N0E0(0h011S1o010g0V0H0E0N0j0H1M1.1:1^1U1{1Q1~200-0a0z0l0u0M0i0M0t0F100E0z0R1,0u0u0H0r2l13230E1b0D1A2y1(1*1)1N0A251p0F0E1}2i1M1j1l0Z1T2I2K0E0M2O1M0i2r1b2w2y2#0:1/2m2Q1_2U0u0@0I1M0N1D2r0g0(030K0K0r2V0H1I2T0M0P0p0d330-0p130N2$2)0.2(242+1U2-2/2;2?0H2^012`2|2~302L33351?040h393b1:3d2w2H013i0N2:1b2=0J2@2_2{2}0R3s2U3u0P0x0-0x3z2v3c0/3D3g0(3G3I053K3M3o3O3r2J3t340P0d0-0d3Y143!3e2*1n3h0M2.3H3k3L3m3N3q3Q3;3S3?0o0-0o3{2#3#2)3E3)453-3p3P2 4b323?0w0-0w4h3c1e2Z132O2B0A1*2G3%014q2N1k1b2Y0H2!4z3|3B054q4Q240F0A0(2{2w3T0p3k4Y4!494r314%1@290H4+4q3R4t354(2y3a3~3E0v0-0R0g3Z4T3$400(0f0-0z542x4~4I0E0g0-0@0O0F0j0=5c4W3 2R010,040m5o5e573F0-0^0L2r5w565r5t0C0n5o0/4S5d3D4*014#2)3T3w3+0z5P3/4a4.3?1?0z4;4?3:5!3v1M0D3a0z5:5b5F1_50040F535M045=4k5f0-0H0t0c0K0b4Y0H5E5 5y5t5v5|5x5r0E5A0u5C686e5?1U5H5J5|5L2%5O4Z5Q0K4$3?3V3J5W6v5Y4-3=353V5%1 4=6w4@4s3T6A3z5;6S5~3f5y5^2r0c0k0u125|6U5q1_0j0F0-0y5K694X6D6x5S3?3^6B5X4,4^3T3^6J205)5Z6G3@5-5/5;6f5@611I5{2#6(4l0-0T0V1Q6:6)6o0-6d6t6a6g6i6k7l3E5H5o7f4I0M0-0e0e7y791U6+377v4I5t6q4i7v6{6y354e6`6=6N5+0P4e706L6E6}4d765}6T5:7G0(6X0S6!6$7e7-5z040u0N0r3;7K6b7o7~7s045B5D6m7r1_7x6r7P6=7R0P4v7U726F4c354v7!8h7%8k7)6S7@7/6Z6#818880866V6g0L5i0N0O8w7n5u8G3(0-7`7|2K8J5s8y7q8A2,7t858S7m0(5H0q7F6n8K045j5l5n8z8Y8Q8I8-7g040B0N0k0r0J6l8X7w8R4z8%7^848|90878H0C0C8#6%7@0E8C8)8E8P6c8P6h7_7{7}8;7L8 55968(939h0-998$9s7^8*5m0j9v8:8}60040A2f2k949r8T8H7p959O9t6j8W9R8.5H98986/6e0D4V4A4P4C4M130c4F9-2E2z0N1P9*0D4D5L0R7i0W04.

Crédits⚓︎

Frédéric Junier, Romain Janvier