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 for
ni 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
Exemple d'utilisation
🐍 Console Python>>> ma_liste = creer_liste() # (1)
>>> ma_liste
()
>>> cons(1, ma_liste)
(1, ())
>>> ma_liste
()
- 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.
Solution
🐍 Script Pythoncons(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.
.1280130ldy14ké/eibmc:_3qaPr+ =of;tRg2sSh)(punv050d0k0C0t0l0c0G0x0o0c0t0G0G0y010C0l0L010406050G0M0n0n0t0v0e040H0z0c0M0)0z0N0x020t0n0L0B0x0D0k0?0v0s0M0k0G050j0:0=0@0_0.0L04051o1h1r0j1o0.0d0l0O0X0Z0#0%0I0l0E0I0c1F0I0C0,050S0m0c0k1A0!0$011E1G1I1G0C1O1Q1M0C0v1p0C0I0X0|0G0L0t0N0%0F011S1C010A0U0k0N140k1M1/1;1_1U1|1Q1 0n21040a0x0u0v0z0L0z0G0l0 110Q1-0v0v0k0o2m1h230N1p0j1+2y1(1*1)1N0d250%1I0N1~2j1M1x1z0Y1T2I0l2K0N0z2O1M0L2r1p2w2y2$0/1:112Q1`2V0v0?0c0,0f2v2*0-2)242,1U2.2:0,0F2@1;2_2w2H012~0t2;040r322x0.352|0%383a0g3d2y2Z0k2y2O2B0d1*2G3h010o2W2b0P1y1p3o2#2^3m053y0Q3F2{1B1U0h0,0Q0A3m0x2`2+3N3i0A0,0c100E1e0M0v3H3g3X010+040K3+2*360N3!0l0G0C0k3=3M2R3.0,0J0p3m060x473U3,403P040l3S1i2^493?3w3^041f0C0q0O0l0Q3~3W403/3;4g333V3@3_3{3}4y2x4A3w3/4345484M4i3 1`4c2r0C3)0N3T4H3-0n0l0,0b4L484X4b0,4S4U4W4a1`4Z2=4.4j3-0z0,0w4?4P2}3!3$3(3*4F3L4u1`4w4t4B041d0k1e584I0,4x2(4/4~041I4D5e3-4J0J451h3J3p1s2!1h3r1h0C3t5A2E2z0t1P5v0j3r1n54362r0n0q0A0t0h0k0q0I0r0,191b5b0W44531s2_1o0{0}2m0x1~0x0i0o0v2l3)1R0A102t0l102K0c1Q0x0p3U1u2_2O361W1H1J1L5M3w271~200,2d0H5?0*0C2e0e1+103H3E3V2%3G5u6e3-4l3#0N3%5c522$4O551U4_040y4|6J0%4c0Z0n0m0d0t6O595m3|5o4v0,5%6H4)4:4!044$536I364c4e6X4k0,4n4p4r4E5i4@6$3:6#2-4C6!5(5j0%4J6@3-4c0k0V6}4h6*1U4;042?6/7h0%6L4{7m77374 6D51721U57766 735a3(7f4z7s7z6~4}3i747F4G7H425r530.0j6y5w5I5K5y0R0T0V04.
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
.128013ldy1,4ké/eibmc:_35qaPr =of;tRg2sSh)(punv050c0k0C0u0l0b0G0x0o0b0u0G0G0y010C0l0L010406050G0M0n0n0u0w0d040H0z0b0M0)0z0N0x020u0n0L0B0x0D0k0?0w0t0M0k0G050j0:0=0@0_0.0L04051o1h1r0j1o0.0c0l0O0X0Z0#0%0I0l0E0I0b1F0I0C0,050S0m0b0k1A0!0$011E1G1I1G0C1O1Q1M0C0w1p0C0I0X0|0G0L0u0N0%0F011S1C010A0U0k0N140k1M1/1;1_1U1|1Q1 0n21040a0x0v0w0z0L0z0G0l0 110Q1-0w0w0k0o2m1h230N1p0j1+2y1(1*1)1N0c250%1I0N1~2j1M1x1z0Y1T2I0l2K0N0z2O1M0L2r1p2w2y2$0/1:112Q1`2V0w0?0b0,0e2v2*0-2)242,1U2.2:0,0F2@1;2_2w2H012~0u2;040r322x0.352|0%383a0g3d342*363j0,0s3m1s2!1h2O2B0c1*2G3h010o2W2b0P1y1p2Z0k2#2^3t3E0Q3M2{1B1U0h0,0Q0A3m0x2`2+3T3i0A0,0n2T0l0n0;3t3g3%010+040K3:3o3C0N0,1I0G0C0k3`3S2R3?0,0J0p3m060x4c3!3;453V040l3Y1i2^4e3{3=3}041f0C0q0O0l0Q433$453@3_4l333#3p0,1d0k1e4y364B4L3|3~0l40424D2x4F3C3@0J483Z4W3=0o0e0,030x0Q0w0N0l0k0w0x0i0b0i2a0N0C4,1R0Z0x3 414a4d544n441`4h2r0C0M4.4#4f2-0,41524U3R4z1`4N5k4$454q514T2(5f1U4Y534d5q580,0k0V5u3N5w0%3@495k4b554c5B3U0,5a5c0N5e4o5r0m3*2T4O3=5o5v5X5g045i5G4E5I463^5$5r4Q4S5?5n470f5W572}5!4/3.0n5`5x0,4C5)5 3i4H1e4K5p5:5(5H5*60045t655J474Z4a1h3P3L3u6u0j3x1h0C3z6z2E2z0u1P6w3x1n5l362r0n0q0A0u0h0k0q0I0r0,191b4I0W5L2(1u2_1o0{0}2m0x1~4?0o0w2l5c1R0A102t0l102K0b1Q0x0p3!6%1w1y361W1H1J1L6K3C271~200,2d0H6:0*4|0v0d1+103t3K5l2%3N6t7b4p613-3/5k565m1U0z0,0y5~7D0%4h0Z0n0m0c0u7I4G6l4R5j697J5;6#4m5Q6b5,0R5.4V6g676n375^7V6i6a5;0J7R3C4h4j7^7x4r404u4w7)7w4A7,6f6j7$4I6e7W4M858b4P7T5_867=4Y7@7B7#014h5E0G827C3p5Z043+5V8i7X6h5/877.7%7:8C8j8d7;7X5s7U828n4Y5}8m5:4q8x7z648z8c5=8Y8f898O7+8!8e7}6m8#5%6p8l2$0.0j7v6v2y6I3w0R0T0V04.
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.
.128013ldTy1,4ké/eibmc:_35qaPr 7F=of;tRg26sSh)(punv050c0l0F0v0m0b0K0y0p0b0v0K0K0B010F0m0P010406050K0Q0o0o0v0x0e040L0C0b0Q0-0C0R0y020v0o0P0E0y0G0l0`0x0u0Q0l0K050k0@0_0{0}0=0P04051s1l1v0k1s0=0c0m0S0#0%0)0+0M0m0H0M0b1J0M0F0:050W0n0b0l1E0(0*011I1K1M1K0F1S1U1Q0F0x1t0F0M0#100K0P0v0R0+0I011W1G010D0Y0l0R180l1Q1?1^1}1Y201U230o25040a0y0w0x0C0P0C0K0m13150U1;0x0x0l0p2q1l270R1t0k1/2C1,1.1-1R0c290+1M0R222n1Q1B1D0$1X2M0m2O0R0C2S1Q0P2v1t2A2C2*0?1@152U1~2Z0x0`0b0:0f2z2.0;2-282:1Y2=2@0:0I2{1^2}2A2L01320v2^040s362B0=39300+3c3e0h3h382.3a3n0:0t3q3j3s3l3b0C2?3d0:0J3x2~2/1F313C33040z3q1w2(1l2S2F0c1.2K3A0p2!2f0T1C1t2%0l2)2|3Q3!0U3,2 3K0+0i0:0U0D3q0y3I3t0D0:3!0R0-220F3Q3k3?010/040O473z490R0:1M0K0F0l4e3=2V4a0:0g3|3~3A4h040S4n3J4p4b0N0q3x0y4G3}484p3^040m3{1m2|4I4f4p4w1j0F0r0S0m0U4z3a4b4d4P374u4g4i0m4k4m4)2B4+4B0:4D4F4H4{4?1~4L2v0F0Q0x0R4t4J4~0p0:0A3d0K4:2*064|561Y4L0l1M4O2*4R4o2;0:4l4l4#3A4%5u4,044j5t4;3;4A1~4C554S1~0C0:0B0B5H5p310:4y5C4}1Y4b4E5C5f4{4H5U3@0:5052545C5o5E5i58040d0x1i4`4G5$015j0Z5d3-5h0+5W5^5!5`4 0V5*5O5.3m411444435x4@4c6g5q041h0l5@5T604q6i6p5I5Q5z4.5B2,6q4C4s5,5`4w5S6z6u614^3H0k3/3+3R6O0k3U1l0F3W6T2I2D0v1T6Q3U1r5D3a2v0o0r0D0v0i0l0r0M0s0:1d1f6m0!5X2,1y2}1s0 112q0y220y0j0p0x2p521V0D142x0m142O0b1U0y0q3}6~1A1C3a1!1L1N1P6(3A2b22240:2h0L780.0F2i0e1/143Q3*5D2+3-6N7w5y426e466D6q5K045N7W6I5{4i180n0c0v693t4-4/6j5V4r7-4v5R7;6J046|4Q655:5a5}7@494L4N834T0:4V4X4Z5~4*6A0:4(6H5P6b6w7:6t8j6r0N874~89827#8o0i5:5=6o5n650:868v6a3b7_8F3a7Y5M8r6v5s8d4=8f6s8i8G4w5A8Q7R6h8q8J3A5|5c8N8k7T0m457`6r8h5 7$4w6m8A8=8o5w8n8V7/6y8`8G6B8*8H4x8/5G5Y1l7Q6P2C6$3T0V0X0Z04.
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 :
🐍 Console Python>>> applique(lambda x: x*x, cons(4, cons(13, cons(1, cons(5, creer_liste())))))
(16, (169, (1, (25, ()))))
.128013ldy1,4k/eib:mc_53qaPr =ofgt2sSh)(punv050c0j0B0t0k0b0D0w0o0b0t0D0D0x010B0k0I010406050D0J0n0n0t0v0d040E0y0b0J0$0y0K050i0-0/0;0?0+0I0405160 190i160+0c0k0L0U0W0Y0!0F0k0A0F0b1n0F0B0)050P0l0b0j1i0X0Z011m1o1q1o0B1w1y1u0B0v170B0F0U0_0D0I0t0K0!0C011A1k010z0R0j0K0t0n0j1u1T1V1!1C1%1y1*1,0)0a0w0u0v0y0I0y0D0k0|0K0w0N1R0v0v0j0o240 1/0K170i1P2h1M1O1N1v0c1;0!1q0K1)211u1f1h0V1B2r0k2t0K0y2x1u0I2a172f2h2L0,1U252z1#2E0v0:0b0)0e2e2P0*2O1:2R1C2T2V0)0C2Z1V2#2f2q012*0t2W040r2.2g0+2;2(0!2@2_0g2|2:2P2=320)0q351a2J0 2x2k0c1O2p30010o2F1-173g183e2N102!053n0N2K373l0h0)0N0z350w2$2Q1j2)0z0)0t0I0I1q0s0J0j3c2 3L0!0(040H3W3B3Y2?0)3G3v2/3J2=3!0f3H3/3l0K0)1q0D0B3V3-2g3@3)3!0G0m35060w483I3X2A013D040k3,2L4a3(4c3_040j3|0p0L0k0N3%2%420)3$3 3A4v4l3`0k3|3~2N4b1#43454z47494O414c4e2a0B0J0v0~4z4j4B2S0)0o2a0j0v0p3{3}4u3K4c3!0H0G464P4I1C4e0j0S4G3w4_3Z0)4L2L4N4O484Q1#4S0O4V4X4i582)4$0}0D4.3:4x5k3^3+5n4w3#5q4C043}4-4z5f515s5y503*044,4~3.5D430G3=4Y5z5E3P3R0k3T5H405J5m5C4k4#044h4 5Z1C3;3?5D4m5T3U5t4J5X4H5(314D4F5:5)0)0G5~460 3y0j2h2I633f1g3h2k2n2i0t1x660i3g0+6g0O0Q0S04.
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
.1280130ldy14]k/weibmc_:35aPr 7=9o[fgt286sSh)(pNunv050d0l0F0u0m0c0J0x0p0c0u0J0J0z010F0m0O010406050J0Q0o0o0u0w0e040K0B0c0Q0-0B0R050j0@0_0{0}0=0O04051d161g0j1d0=0d0m0S0#0%0)0+0L0m0E0L0c1u0L0F0:050W0n0c0l1p0(0*011t1v1x1v0F1D1F1B0F0w1e0F0L0#100J0O0u0R0+0G011H1r010D0Y0l0R0u0o0l1B1!1$1+1J1.1F1;1?0:0a0x0v0w0B0O0B0J0m130R0x0U1Y0w0w0l0p2b161_0R1e0j1W2o1T1V1U1C0d1{0+1x0R1:281B1m1o0$1I2y0m2A0R0B2E1B0O2h1e2m2o2S0?1#2c2G1,2L0w0`0c0:0x0f2l2W0;2V1`2Y1J2!2$2(0G2+1$2-2m2x012=0u2%040x0s2_2n0=2|2:0+2 310x0g352{2W2}3b2(0t3f373h392~0B2#302(0I3m2.2X1q2;3r2?320y3w383z3a3B3t320H3F3o3H3q3s3c0A3N2/3P3j040f0b3U3y2H3Q3C0f2*172,1h2Q162E2r0d1V2w3p0p2M1@1e3;1f3/2U3,2`053`0U2R3O3%0i0:0U0D3f0x3x3i0D0:0l0J0F0q0S0m0U3f4g3p0/040N4r3G3%0R0:0{0n2h4x481,4u0M0r3m0x4M4f4y1,4a042h0F0Q0w15422n4O4G2;4B0w4D0l4e4s3P0B0k0:0m0J4+4P1J0i0p0:0P144*4Y0;3n3V494b0l4d4 4!522Z4i040E0u0Q0p0L4~2U4@0+4u4w4 4,4z4%4)4F591J4I4K4 064N583$4Q0:4T4V4X2S5B3i5r4E5o5k014u0C5t5C1J0o0m0:3!5N4#5l0:0h3m515T0+4R4c4?5!2~5b0d252a5i3-5O5m5S5K044C5M5j5/5w4L4N5p5D4S0V5G5.5u3a5L5^435`0:5R5Z6c015V0:2^6k5*5P5$5(664^54565I6v3a5b0w0u0p2J6f2n6A6s4v5|3p4A5~4(605_620:4J644M6J4R5F4W6b6r6O5 6H476l5Q6M3P6n3Y6.3%4u5%5y16450l2o2P6|3:1n3=2r2u2p0u1E6 0j3;0=790V0X0Z04.
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.
.1280130ldy14k/eib:mc_53aP+r =ofgt2sSh)(punv050d0j0B0s0k0c0D0w0o0c0s0D0D0x010B0k0I010406050D0J0n0n0s0v0e040E0y0c0J0$0y0K050i0-0/0;0?0+0I0405160 190i160+0d0k0L0U0W0Y0!0F0k0A0F0c1n0F0B0)050P0l0c0j1i0X0Z011m1o1q1o0B1w1y1u0B0v170B0F0U0_0D0I0s0K0!0C011A1k010z0R0j0K0s0n0j1u1T1V1!1C1%1y1*1,0)0a0w0t0v0y0I0y0D0k0|0K0w0N1R0v0v0j0o240 1/0K170i1P2h1M1O1N1v0d1;0!1q0K1)211u1f1h0V1B2r0k2t0K0y2x1u0I2a172f2h2L0,1U252z1#2E0v0:0c0)0f2e2P0*2O1:2R1C2T2V0)0C2Z1V2#2f2q012*0s2W040r2.2g0+2;2(0!2@2_0g2|2:2P2=320)0q351a2J0 2x2k0d1O2p30010o2F1-173g183e2N102!053n0N2K373l0h0)0N0z350w2$2Q1j2)0z0)0P0R1y3c2 3L0!0(040H3S3B3U2?0)0;0l2a3Z2%3#3W0G0m35060w3?3I3T2A013D040k3G3v2/3^3!3`0K0)0j0D0B0p0L0k0N3+3K3`3W3Y402g3J383%0v3)0j4e2=3.3:4j0*3@4x423,3`3|2a0B0J0v0~4v4z4f1#0n0k0)0b3;4x4l3C460S4q4I4S3-0)4u2L3=4y3?4Y4B0)4D4F4H2L4J2=4M2X3H4*1#0y0)0u4^3_2S3O0Q0c3R4v4_1C4h4r3l45040A0s0J0o0F4W2N4 570)4i5j4350043(3*555k3V0)0G0G4~5p1C4{044}4X5v3$043P535i3w5H585u5B313E1~235M2/565w3X593#5b5s5W4k5O5x5z4v0+0i3y0j2h2I5=3f1g3h2k2n2i0s1x5^0i3g5/0N5K0D04.
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
.1280130ldy1,4k/eibmc:_35aPr+ =ofgt2sSh)(punxv050d0k0C0t0l0c0E0x0o0c0t0E0E0y010C0l0J010406050E0K0n0n0t0v0e040F0z0c0K0(0z0L050j0/0;0?0^0-0J040518111b0j180-0d0l0N0W0Y0!0$0G0l0B0G0c1p0G0C0+050R0m0c0k1k0Z0#011o1q1s1q0C1y1A1w0C0v190C0G0W0{0E0J0t0L0$0D011C1m010A0T0k0L0t0n0k1w1V1X1$1E1)1A1,1.0+0a0x0u0v0z0J0z0E0l0~0L0x0P1T0v0v0k0o26111;0L190j1R2j1O1Q1P1x0d1?0$1s0L1+231w1h1j0X1D2t0l2v0L0z2z1w0J2c192h2j2N0.1W272B1%2G0v0=0c0+0f2g2R0,2Q1=2T1E2V2X0+0D2#1X2%2h2s012,0t2Y040r2:2i0-2?2*0$2_2{0h2~2=2R2@340+0s371c2L112z2m0d1Q2r32010o2H1/193i1a3g2P122$053p0P2M393n0i0+0P0A370x2(2S1l2+0A0+0G0t0}0k0K0v3e313N0$0*040I3X3D3Z2^0+0?0m2c3(2)3*3#0H0p37060x3{3K3Y2C013F040l3I3x2;3}3)3 0L0+0k0E0C0q0N0l0P3:3M3 3#3%452i3L3a3,0v3.0k4j2@3?3^4o0,3|4C473;3 412c0C3V104A4E4k1%0n0l0+0b3_4C4q3E4b0U4v4M4W3=0+4z2N0x3`4D3{4$4G0+4I4K3J4/4P4R042!4#3~1%0z0+0w4@4~2+0m0+0=0M4w3n4m5a3*4a043R3T3V5d4l0+4n2P54330+0B3S0o0G4!5o481%5c4A4^2+4s4u5k5z0+0H0H0g535y5D5g3S0C3U3W5B5p015A5x4F2U3G20255w3y5V5X5)5N5q043-3/5U5-5W5I5J3_113A0k2j2K5}3h1i3j2m2p2k0t1z600j3i0-6a0Q0S0U04.
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.
.128013ldTy1,4k/weibmc:_35aPr F=ofgt26sSh)(punv050c0l0D0u0m0b0G0x0p0b0u0G0G0z010D0m0L010406050G0M0o0o0u0w0e040H0A0b0M0)0A0N050j0:0=0@0_0.0L040519121c0j190.0c0m0O0X0Z0#0%0I0m0C0I0b1q0I0D0,050S0n0b0l1l0!0$011p1r1t1r0D1z1B1x0D0w1a0D0I0X0|0G0L0u0N0%0E011D1n010B0U0l0N0u0o0l1x1W1Y1%1F1*1B1-1/0,0a0x0v0w0A0L0A0G0m0 0N0x0Q1U0w0w0l0p27121=0N1a0j1S2k1P1R1Q1y0c1@0%1t0N1,241x1i1k0Y1E2u0m2w0N0A2A1x0L2d1a2i2k2O0/1X282C1(2H0w0?0b0,0f2h2S0-2R1?2U1F2W2Y0,0E2$1Y2(2i2t012-0u2Z040s2;2j0.2@2+0%2`2|0h2 2?2S2^350,0t38313a332_0A2X2{0,0F381d2M122A2n0c1R2s3i0p2I1:1a3t1b3r2Q132%053z0Q2N3h1m1F0i0,0Q0B380x2)2T3O340B0,0u0L1X0w0)1,0D3p323Y010+040K3-3N2D2_3#0w0n2d3@2*3/3;0g3U3W3b0,0O2{0l0M0w3 3X3_3;0J0q3f0x4k3V3.3_3Q040m3T3H2=4m3^2V0,0l0G0D0r0O0m0Q4d2^3;3?4t2j453i0N3{3}0l4G3i4g4i4K0-4l4Y4v404o0,2d0D4b114W4!4e1(0i0p0,0y2{0G4R4W064Y4M3/4p0l1t4s2O4-46040w0u0p2F4_2Q4n1(4I4S3/4O040@4Q5g4f0,0J445d1F0A0,0z0z5q4w2,47494b5m5e0,4V2O4{4Z4k4}4$560R4*5x4#4/4;040d0w0M5b2%5I5K5r0%4p4(5P4,5L4x5j3%0@3*0N3,4W5,1F5f5@5$3`040C0u0M0p0I5Y2=5^0%5`5c5y344P3~5{6a3:5o435+5|5i481B5C6e5R5_5o5Q4.5s0k0,3k6t553$3(5;5?696q670,4J6F6u6b040c2126644L5|683I6k6c6R3M6G6g040J6i53665}6m4a4c6p6L6#5p4`123K0l2k2L6_3s1j3u2n2q2l0u1A6|0j3t0.760R0T0V04.
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.
.1280130ldy1,4k/eibmc:_35aPr =ofgt26sSh)(punxv050d0k0B0t0l0c0E0w0o0c0t0E0E0x010B0l0J010406050E0K0n0n0t0v0e040F0y0c0K0(0y0L050j0/0;0?0^0-0J040518111b0j180-0d0l0N0W0Y0!0$0G0l0A0G0c1p0G0B0+050R0m0c0k1k0Z0#011o1q1s1q0B1y1A1w0B0v190B0G0W0{0E0J0t0L0$0C011C1m010z0T0k0L0t0n0k1w1V1X1$1E1)1A1,1.0+0a0w0u0v0y0J0y0E0l0~0L0w0P1T0v0v0k0o26111;0L190j1R2j1O1Q1P1x0d1?0$1s0L1+231w1h1j0X1D2t0l2v0L0y2z1w0J2c192h2j2N0.1W272B1%2G0v0=0c0+0f2g2R0,2Q1=2T1E2V2X0+0C2#1X2%2h2s012,0t2Y040r2:2i0-2?2*0$2_2{0h2~2=2R2@340+0s373039322^0y2W2`0+0D371c2L112z2m0d1Q2r3h0o2H1/193s1a3q2P122$053y0P2M3g1l1E0i0+0P0z370w2(2S3N330z0+0=0M0l0n0:3o313X010*040I3*3M2C2^0+0?0m2c3;2)3,3.0H0p3e0w433U3+3?3P040l3S3G2;453=2U0+0k0E0B0q0N0l0P3|3W3?3.3:4c2i3V3a3^0v3`0k4p2@3 414u0,444I4e3}470+2c0B0K0v104G4K4q1%0n0l0+0b42444w3h480k1s4b2N4U4x040R0T1A4C3h4s4@3,0L4y4A4`4r0+0H3T4%3,0y0+0x0x53464W4Y042!4G5450044F2N064J4$5b3O4N0Q4Q4S4-5h4g040v0t0o2E4B5g5p0$4_5E4f2+4}3{5I4L1%3 4#435w5q5y5s4R4 5P0+4t2P5F2^0m3!0t0M5Y1E5H5$5J334N5A5C5-5G5!5_3@043_5M5:5O5.510g5a5;5}3#3%3)5N4V633/5|4|040A0t0K0o0G5D616d5`6f6c4/5 6o3H5%3 0H654T5T335)043#5|5/6x676h5z5B2v6I5{6t3h6h6v6Q046A66625=6G5+6a0n6W5#6K6!5}0d20256w2;6D3-6R6p6u4z606,6q6^6X0H72524G0-0j3J0k2j2K793r1i3t2m2p2k0t1z7c0j3s760P4;0U04.
Crédits
Frédéric Junier, Romain Janvier
# Tests
(insensible à la casse)(Ctrl+I)
(Ctrl+Clic pour inverser les colonnes)