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

Exemple d'utilisation

Python Console Session

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

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.

Évaluations restantes : 5/5

.128013w4h)1(+-_s3u:/S qbn=éve0imtPRp2dr;gylckfao050G0x0B0P0z0L0k0q0M0L0P0k0k0u010B0z0E010406050k0m0A0A0P0H0K040p0Q0L0m0+0Q0t0q020P0A0E0I0q0D0x0^0H0r0m0x0k050o0=0@0_0{0:0E04051q1j1t0o1q0:0G0z0w0Z0#0%0)0#0t0J0m0P0J0x0i0E0K0B0d120q0d0z0J0d0L1V0d0B0.050U0s0L0x1C0$0(011U1W1Y1W0B1(1*1$0B0H1r1Q0Z0~0k0E0P0t0)0F011,1E010O0W0x0t160x1$2123281.2b1*2e0A2g040a0q0C0H0Q0E0Q0k0z11130S1 0H0H0x0M2B1j2i0t1r0o1Q2N1{1}1|1%0G2k1F0z0t2d2y1$1z1B0!1-2X2Z0t0Q2%1$0E2G1r2L2N2@0;22132)292-0H0^0L1$0P1T2G0O0)030j0j0M2.0x1Y2,0Q0i0F0i0f0.0f1j0P2^2{0/2`2j2}1.2 3133350x3701393b3d3f2!3i3i0.0F3o3q233s2L2W013x0P321r340d36383a3c0S3H2-3J0l0.0l3N2K3r0:3R3v0)3U3W053Y3!3D3$3G2Y3I3j0c0.0c3/1k3r1u2=1j2%2Q0G1}2V3@013%2q0R1A1r2;0x2?49483P054k4r2j0z0G0)3a2L3J3l3X0q4z4B3F3(413*3j3l0q2o0x4J4k3)3h4O1$0o3p3t2|1D1.0N0.0S0O3:4u3?4%0)0b0.0q4-2M4#3S0t0O0.0L121I0x0m0H4^4x4$2*010-040g554`4i0t4~0z0k0B0x5d4/585a0e0n550:4t4_3R4I014C2{3J264G5x3 4L3g5B274R4T405H3j5C3N0q5R4@5n294)040z4,5u045T2{4{0.1h0B0j0w4z5l5!5e4:590.5c5:5U3w5h5j5/2_5`0)5p5r5!5t5 5%5E0j4D3j3,5D4A5y4K3e4M4W0i3,4Q2f5L5G426k4Y3p5S6u5$3u5=5W2G0B530t556w57290A0z0.0y5s5m676e5z233J446d6o6h5N0i446m2p6V4V6S6s5#5S5;586z0T6C6E6,6H6J043n5!6F3S0Q0.0h6;603T4~501g536N6x5o5@776G5{041f525~49715a5^66782~5|5k7b3S5p0e6M5:0o4w4a4q4c4n1j0B4f7D2T2O0P1)7A0o4d1p563S2G0A0j0O0P0N0x0j0d6c1b1d7f0Y632_1w3s1q0}0 2B0q2d0q0v0M0H2A531+0O122I0z122Z0L1*0q0n4@7+1y1A3S1G1I1K1M1O1Q1S1:1X1Z1#7P4i2m2d2f0.0C1P1R6D5:4p563O4_7y5w6P695A0l3k3z684U6i6k8I6!4S6f8L5H8H4P3Z3B3#6g6%8U6)6=7d4 1H75546`8%0)6}040u705%4i5W0#0A0s0G0P8?7n8(5i7q5_8@5=5a7)3r6{4i6I6K8 7c0)5W5Y9e5(045*5,5.7r4i7k9p5=5g041Y5}9s79047u8-715W3e0k7h3P9a5=9c6^9j4i8:6 9C95589u8)51769490617a9Y9f727e759H5v9S299r9$9k9w937m9%7t7v7*7y1w4b7M4n5t0S0U0W0k04.

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

Évaluations restantes : 5/5

.128013w4h)1(5-,_s3u:/S qbn=éveimtPRp2dr;gylckfao050G0y0B0P0z0L0l0r0M0L0P0l0l0v010B0z0E010406050l0n0A0A0P0H0K040q0Q0L0n0+0Q0u0r020P0A0E0I0r0D0y0^0H0s0n0y0l050p0=0@0_0{0:0E04051q1j1t0p1q0:0G0z0x0Z0#0%0)0#0u0J0n0P0J0y0i0E0K0B0d120r0d0z0J0d0L1V0d0B0.050U0t0L0y1C0$0(011U1W1Y1W0B1(1*1$0B0H1r1Q0Z0~0l0E0P0u0)0F011,1E010O0W0y0u160y1$2123281.2b1*2e0A2g040a0r0C0H0Q0E0Q0l0z11130S1 0H0H0y0M2B1j2i0u1r0p1Q2N1{1}1|1%0G2k1F0z0u2d2y1$1z1B0!1-2X2Z0u0Q2%1$0E2G1r2L2N2@0;22132)292-0H0^0L1$0P1T2G0O0)030k0k0M2.0y1Y2,0Q0i0c0i0f0.0f1j0P2^2{0/2`2j2}1.2 3133350y3701393b3d3f2!3i0i26040F3o3q233s2L2W013x0P321r340d36383a3c0S3H2-3J0m0.0m3O2K3r0:3S3v0)3V3X053Z3#3D3%3G2Y3I3j0c0.0c3:1k3=3t2|1D3w0Q303W3z3!3B3$3F3)423+3j0h0.0h482_1w2=1j2%2Q0G1}2V3^013(2q0R1A1r2;0y2?3r3;3Q054G4N2j0z0G0)3a2L3J3l3Y0r4V4X4m3e4o3h3j3l0r2o0y4)4G3*4-3k1$0p3p4b3T0N0.0S0O4P2M4~4E0b0.0r544T4c2*3U0O0.0A2Y0z0A0?5b564d0)0-040g5n3@5p3U0.1Y0l0B0y5u2{3T5r0e0o5b0:494Q3S4(014Y2{3J3L3|4%4W5P4*4^5S274;4?413g5!2N3p0r5-5a5v5e50040z535L2M5/5E4E0u0.1h0B0k0x4V5C5_5c5F0.5t665o5e5~041f0y1g5D3u5w5r6a2_5:2~5y0z5A656o5|6l0.0e5H5b5{6k5e0M4#030r0S0H0u0z0y0H0r0w0L0w2p0u0B6I1+0#0r5z5B5J6j135O5Q233,3z6)5Y4,6,4:2f5%4n5)3j3-5+045.6~6C5d295=2G0B0n6K6B6c6q045B6#6b6p1.6m6%3T6e6!6u4O7f5q6y6$7e5E6.4Z446-5W406^433i5#6?5X4@6:7w6|6~791.5=3e0l7m5M6w5e5r5I665K6v4U7y0k7v0i4r4$6.7G6_7%7D2p6@4+7,7(3O6 5.7L0)730T760u787o3U0t5h2Y7i4E7h7s6D7a7c7Q5581887Y713w6r6t866x040e0j807S7a5i6L5l0A8m7T698y7a6g6i898i7p5s8B8j047l8J8H6z0e7r4v4S1u4x0p4z1j0B4B8Y2T2O0P1)4M4y4J1p674E2G0A0k0O0P0N0y0k0d6{1b1d6g0Y7V4v1x1s0|0~100z1S2d6P0M0H2A761+0O122I980u2Z0L1*0r0o5a1w3s2%3T1G1I1K1M1O1Q1S1:1X1Z1#8.5w2m2d2f0.0C1P1R7 6b4L5c3P558T5N7!4Z0h4`7)7!7+3I9!4/5$7F5(9)4`3A3C3E9(3+9*4{4}816e8u5k5m66703T0Q0.0v8r8a7M5y160t0G0Pa78G5x8L6s7d8h6804913ra25}0.8c8N018g7n8s8K8M8Fam8Qa17`015=5@af7j5 5A6264auaw7Ra83_0.8D8d9H8z8IaBarai8la!8n6zaJ4E7N0XaWaq5w0u83048uaP8Aa(6das0TaWaFaQ8eayaTa$akaxaSav6y8qaE9|848va0al87a`bha;aU1g8EbkaY6nb7ag7kaja 8f6ya*7W5n0p8T4w8*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.

Évaluations restantes : 5/5

.1280137w4h)1(5-,_s3u:/S qbn=éveimFtPRT6p2dr;gylckfao050K0z0D0T0A0P0m0s0Q0P0T0m0m0w010D0A0I010406050m0o0B0B0T0L0O040r0U0P0o0/0U0v0s020T0B0I0M0s0F0z0|0L0t0o0z0m050q0_0{0}0 0@0I04051u1n1x0q1u0@0K0A0y0%0)0+0-0)0v0N0o0T0N0z0j0I0O0D0e160s0e0A0N0e0P1Z0e0D0=050Y0u0P0z1G0*0,011Y1!1$1!0D1,1.1*0D0L1v1U0%120m0I0T0v0-0J011:1I010S0!0z0v1a0z1*25272c1=2f1.2i0B2k040a0s0E0L0U0I0U0m0A15170W230L0L0z0Q2F1n2m0v1v0q1U2R1 21201+0K2o1J0A0v2h2C1*1D1F0(1;2#2%0v0U2+1*0I2K1v2P2R2{0^26172-2d2;0L0|0P1*0T1X2K0S0-030l0l0Q2=0z1$2:0U0j0H0j0g0=0g1n0T2|2 0?2~2n311=333537390z3b013d3f3h3j2(3m0j2a040J3s3u273w2P2!013B0T361v380e3a3c3e3g0W3L2;3N0n0=0n3S2O3v0@3W3z0-3Z3#053%3)3H3+3K2$3M3n0d0=0d3@1o3_3x301H3A0U343!3D3(3F3*3J3-463/3n0i0=0i4c2{3`2 3X3~4m423I3,3i4s3l3n0H0=0H4y4e3{4h3}4j3C3$3E3G4G453k3N0b0=0b4P3U1y2_1n2+2U0K212Z3|014H2*1E1v2^0z2`3v3^4+4H4 2n0A0K0-3e2P3N3p4W56584q4I4#3n3p0s2s0z5f4H3.4K3o1*0q3t4f3X0R0=0W0S512Q5w4@0c0=0s5C544g2.3Y0S0=3g0v0/2h0D5J5E4S010;040h5V4R5M0v0=1$0m0D0z5$4B4@5Z0k5J5I5%320=0y5/3y5X5Z0f0p5J0@4d4+3W5e01592 3N3P400s68444r5i3O2b5m5o4!476k2R3t0s6t5^5:5X5y040A5B652Q6v5~5(0=1l0D0l0y565.6C5K3X5Z5#6O5W6G045+5-5}5L2d60626O642}6757690l5a3n3;5d6,6h5h6p3;5l2j6n6i6_5t6s6u726U2d6y2K0D0o0L0v5@741=0R0Q0=0C3!0m6N4z6Z6f6?6.6b483D6g5g5q3N496{2t6}6^4t0j496r04735_7e6H1$6B2{6E6!3A0=5-6Y6T7J0-6R7n4@5)6W0A5,7l507W5Y0=0f7c7+0U0=0w0w7/6w6V5|7V7_6#0=6%7m7|557p6/0j4v6=7B7w4u6l6|6-5p4J3N873S727I7}7K0477797b6O7P5x7g040G0L1k637n7u854M888e6o7D4M7z5n8G6~8I707H6u7d0-6y3i7k7Z5 7 8A82178C7r0j4%8F6@8a8)8c7A8M7C5r8*8j8k6t8S01760X8q7^6F5`045Q5S5R8X5M7Y8#4C0=1j0z8z9a5;0=6S6*8m3}5*7%7U9k911=605?8s8{7#7{9q7Q7X7-8!2}0q534,4~4.4{1n0D4;9L2X2S0T1-9I0q4/1t6P4@2K0B0l0S0T0R0z0l0e6;1f1h9d0$80501A3w1u11132F0s2h0s0x0Q0L2E791/0S162M0A162%0P1.0s0p5I9?1C1E3X1K1M1O1Q1S1U1W1@1#1%1)9X5X2q2h2j0=0E1T1V8r2}4}5K3T5D9G6+5f5a0b5s8+7v8gaO5k6m8;7waT2b4n4Y8,aSaP3@7+7#940A5T909A017;047@9v7+6y0)0B0u0K0Ta/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!0m04.

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, ()))))

Évaluations restantes : 5/5

.128013w4h)1(5-,_s3u:/S bqn=veimtP9p2drgylckfao050F0x0A0N0y0J0l0r0K0J0N0l0l0v010A0y0D010406050l0n0z0z0N0G0I040q0O0J0n0)0O0u050p0:0=0@0_0.0D040519121c0p190.0F0y0w0X0Z0#0%0Z0u0H0n0N0H0x0i0D0I0A0d100r0d0y0H0d0J1E0d0A0,050S0s0J0x1l0!0$011D1F1H1F0A1N1P1L0A0G1a1z0X0|0l0D0N0u0%0E011R1n010M0U0x0u0N0z0x1L1-1/1@1T1`1P1}1 0,0a0r0B0G0O0D0O0l0y0 0u0r0Q1+0G0G0x0K2k12220u1a0p1z2x1%1)1(1M0F241o0y0u1|2h1L1i1k0Y1S2H2J0u0O2N1L0D2q1a2v2x2!0/1.2l2P1^2T0G0?0J1L0N1C2q0M0%030k0k0K2U0x1H2S0O0i0C0i0f0,0f120N2#2(0-2%232*1T2,2.2:2=0x2@012_2{2}2 2K320i1=040E383a1/3c2v2G013h0N2/1a2;0d2?2^2`2|0Q3r2T3t0m0,0m3y2u3b0.3C3f0%3F3H053J3L3n3N3q2I3s330c0,0c3W133Y3d2)1m3g0O2-3G3j3K3l3M3p3P3/3R330h0,0h3^2$1f2Y122N2A0F1)2F3#013O201a4j1b4h4f2$4q2Z2(0r0y0F0%2`2v3t353I4B4D013-47304H1?280x4E462~4831334I3W3!3}0%0L0,0Q0M3X3A3{3D0b0,0r4-2w4/4o0u0M0,0N0D0D1H0t0n0x4@4z3e4%010+040g554_580u0,4,3_4.4$2Q590,0j554?5l2+0,1H0l0A545j4^5s1T5a0e0o550.5z562l4C4U4G333v3)4K4U4q3Q4Y3u4R1~4T4M4V5U3t5P0p390r5+5r4A4o4)040y5i2!5-575m5g040x5w0k0w4C5y2$5B0%5a5c5I5e5`5u0y5w623b691^5D5F5I5H634A5L5!5N0i3T4J6o4N4W4P333T0r4S5S3.6x6r1L5)045,6J5^3|5m5:2q0A0n0G115I6L3D5{0K2q0x0G0k5v5x5d645n5b0e5G6)6n4L4F2(3t3=6t6;5#4X6@5X1 6C4O3:0i6^3y6J6g1T5:2~0l6e5k5.585a6j2!6l6f3C6u0k6q4b6_706w724b6A5Y7r5$4a6G5*6K5+774(0,6P6R6T5@7E3E0,2|0u0l6/5_6h0,676m7S3g5h7R6M7T5b7!6W0,5x6(686*667(4`6b6d7:7f0,0e0e5p6U7L5{4~500y527c5A7e5m7/7-865t045?7k8a5C5o5q7~0,83537@877U8n8b6%845J3D5D7`6.680p4y1d4h0p4t2y4l122B8I0N1O0x2x4j5H0Q0S0U0l04.

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

Évaluations restantes : 5/5

.1280137w4h)1(5-_s3u:/S[ bn=ve08imtP]N69p2drgylckfao050K0x0C0S0A0O0l0s0P0O0S0l0l0v010C0A0I010406050l0n0B0B0S0L0N040q0T0O0n0.0T0u050p0^0`0|0~0?0I04051e171h0p1e0?0K0A0w0$0(0*0,0(0u0M0n0S0M0x0j0I0N0C0e150s0e0A0M0e0O1J0e0C0;050X0t0O0x1q0)0+011I1K1M1K0C1S1U1Q0C0L1f1E0$110l0I0S0u0,0J011W1s010R0Z0x0u0S0B0x1Q1=1@1|1Y1 1U22240;0a0s0D0L0T0I0T0l0A140u0s0V1:0L0L0x0P2p17270u1f0p1E2C1,1.1-1R0K291t0A0u212m1Q1n1p0%1X2M2O0u0T2S1Q0I2v1f2A2C2)0@1?2q2U1}2Y0L0{0O1Q0S1H2v0R0,030k0k0P2Z0x1M2X0T0j0g0y370;0s0g170S2*2-0=2,282/1Y2;2?2^2`0x2|012~3032342P37391`040s0J3e3g1@3i2A2L013n0S2@1f2_0e2{2}2 310V3x2Y3z0j0m3b0m3F2z3h0?3J3l0,3M3O053Q3S3t3U3w2N3y380j0d3b0d3(183*3j2.1r3m0T2=3N3p3R3r3T3v3W3`3Y3|0i3b0i412)3+2-3K3/4b3?3u3V334h363|0G3b0G4n433,463.483o3P3q3s4v3_353Z0b3b0b4E3H4p3k4H3L4J4a4L4c4N3^4g4Q3|0z3b0z4V2B4X452V4!493:3=4d3@4f4x4,390H3b0H4;3I4q3-4_4K3;4M4e4w3X4z39380;38564?4r4#4{5d4~5f4y3Z0g0g5k3d0p3f3)3H1i2%172S2F0K1.2K594w2R1o1f2$0x2(3h5C2B054w5T280A0K0,2 2A5v3p5#5%4 5g5*0s2d0x5-5t513a2C5B4G4^0Q0;0V0R5V5Z4@1}0c3b63444r0R0;0x0l0C0k0w5#0x695}1}0:040h6l584Z0u0;0|0t2v6r4Y4^6o0f0o630?425D3J5,015(2-3Z3B5c6K4*503{3A1{5=5@4P6U0j6P5A3C0s6)6a595 042v0C0n0L166H2B0s6+6t6v0L6x6k6@3C6`4^0T67040A0l636_6m1Y0Q0P0;0F156 4o6z2q6R0k5)3|3#4L7m5^6!3#5;235?6L5.5u7p1Q6%6G2+6J5$7z7o393~7r7I6S5/3|3~7w246Y4+6!7M3(7b0,6-617k3K756_70722:6c040M0S0n0P0e7i5U7!016o6q7,7{6u046w6y7 6s6B0;6D6F7(7m7K0j4k7N7V6T4i394k7T7y7P7B8k7D3f6)6*7{6-6/6;6?2)7a862:6|6~7(596o0r8G4Z0B0A0;0y8K87040E8a855!7O7n6N4A5+8X7t8j0j4B8m8h7Q394B5{3i8V7l8X8d4S8g7z8%5h0j4S8+8{6Z8(8_7Z8C7c603r8Q66688=6b602j2o7_6I960,7}9a3m8E847G9k7|886E707F7`4q8c8Z394.8`8o5_4.909F6!9D3F8t8B6A1}8w0W8y797-9o826}9q9y9P1Y8I9n0,8M0;3E9d8H0;8T9w8b8@9B0j539E7A5_539I9{6!9_3F9x9j8W5-8d5j9`8|5v0y6W7x8,8p3z8r643K7$999-4Z7*9(3L7/0L0S0P3`aq9man4^81839i5W7{6C9v7j9d9A1@5v5xa9928}5wad7U917W8(aR8:9N9V7#0;8x6=9U809paDaj9.048Jaz1}9*045z9r9#9l9/8U2+0p5Y5E5S5G5P170C5Jb52I2D0S1Tb20p5H6G0V0X0Z0l04.

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.

Évaluations restantes : 5/5

.128013w4h)1(+5-_s3u:/S bn=ve0imtPp2drgylckfao050E0w0A0M0y0I0l0r0J0I0M0l0l0u010A0y0C010406050l0n0z0z0M0F0H040q0N0I0n0(0N0t050p0/0;0?0^0-0C040518111b0p180-0E0y0v0W0Y0!0$0Y0t0G0n0M0G0w0j0C0H0A0d0 0r0d0y0G0d0I1D0d0A0+050R0s0I0w1k0Z0#011C1E1G1E0A1M1O1K0A0F191y0W0{0l0C0M0t0$0D011Q1m010L0T0w0t0M0z0w1K1,1.1?1S1_1O1|1~0+0a0r0B0F0N0C0N0l0y0~0t0r0P1*0F0F0w0J2j11210t190p1y2w1$1(1%1L0E231n0y0t1{2g1K1h1j0X1R2G2I0t0N2M1K0C2p192u2w2Z0.1-2k2O1@2S0F0=0I1K0M1B2p0L0$030k0k0J2T0w1G2R0N0j0f0f310+0f110M2!2%0,2$222)1S2+2-2/2;0w2?012^2`2|2~2J31331;040D37391.3b2u2F013g0M2.192:0d2=2@2_2{0P3q2S3s0j0m0+0m3x2t3a0-3B3e0$3E3G053I3K3m3M3p2H3r320j0c0+0c3W123Y3c2(1l3f0N2,3F3i3J3k3L3o3O3/3Q3;0i0+0i3_2#1e2X112M2z0E1(2E3#013N1 194k1a4i4g2#4r2Y2%0r0y0E0$2_2u3R0f3i4D4F472}49303;4J0r270w4M4r3P4Q334J2w383|3C0K0+0P0L3X3z4(4p0b0+0r4.2v4:3~3$0L0+0R0T1O4^4A3d4{010*040g524`2P3D0+0?0s2p5a3!55570e0o520-3`4/3B4L014G2%3R3u3)4C4E5u4N4Y5x1=4U4W3.2 5F4$040r5O4@5j5c4*040y4-5q2v5Q4B4p0t0+0w0l0A0k0v4D0w5i5!5k0+595X533}5c5$045f5h5@5b1@5l5n5@5p2#5s5B5v1.3R3T3H5A5I485K3;3T4T1}4V5C4X4P6b1K0p385P6u5Z545S0+2p0A0n0F105@6w5_1@0z0y0+0x5o5/225t690t3R3?6d6Q5D6p3;3?6k1~6f4O6h336U3x6u601S5T2}0l5.6F6.0$57632Z653a4(6W4H4b4K686X6)0j4c6#6m3-6g3:334c5M6v5P6^015T6A6C6E2Z6G3C6J35527q4p0N0+0h7u7j5{4 0I515 5R615=6O6H3f0+0G0M0n0J0d6?665:5c575?7U6x2*5e0F5g7T6~7H1S5l0e7A7+0$7x047z6@7:5d047D7F7Z7L6_7J7G7V7#040E2d2i7)5r837,817~3C5{5}894_7_7-6N5 0p4z1c4i0p4u2x4m112A8w0M1N0w2w4k5p0P7D0l04.

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

Évaluations restantes : 5/5

.128013w4xh)1(+5-,_s3u:/S bn=ve0imtPp2drgylckfao050G0y0C0O0A0K0n0t0L0K0O0n0n0w010C0A0E010406050n0p0B0B0O0H0J040s0P0K0p0*0P0v050r0;0?0^0`0/0E04051a131d0r1a0/0G0A0x0Y0!0$0(0!0v0I0p0O0I0y0k0E0J0C0e110t0e0A0I0e0K1F0e0C0-050T0u0K0y1m0#0%011E1G1I1G0C1O1Q1M0C0H1b1A0Y0}0n0E0O0v0(0F011S1o010N0V0y0v0O0B0y1M1.1:1^1U1{1Q1~200-0a0t0D0H0P0E0P0n0A100v0t0R1,0H0H0y0L2l13230v1b0r1A2y1(1*1)1N0G251p0A0v1}2i1M1j1l0Z1T2I2K0v0P2O1M0E2r1b2w2y2#0:1/2m2Q1_2U0H0@0K1M0O1D2r0N0(030m0m0L2V0y1I2T0P0k0g0F330-0g130O2$2)0.2(242+1U2-2/2;2?0y2^012`2|2~302L33351?040F393b1:3d2w2H013i0O2:1b2=0e2@2_2{2}0R3s2U3u0k0o0-0o3z2v3c0/3D3g0(3G3I053K3M3o3O3r2J3t340k0c0-0c3Y143!3e2*1n3h0P2.3H3k3L3m3N3q3Q3;3S3?0j0-0j3{2%1g2Z132O2B0G1*2G3%013P211b4m1c4k4i2%4t2!2)0t0A0G0(2{2w3T0g3k4F4H492 4b323?4L0t290y4O4t3R4S354L2y3a3~3E0M0-0R0N3Z3B4*4r0b0-0t4:2x4=403(0N0-0e0O0 0y0p0H4`4C3f4}010,040h574|2R3F0-0^0u2r5f3$5a5c0f0q570/3|4;3D4N014I2)3T3w3+4E4G5z4P4!5C1@4W4Y3:315K4(040t5T4_5o5h4,040A4/5v2x5V4D4r0v0-0y0n0C0m0x4F0y5n5)5p0-5e5$583 5h5+045k5m5|5g1_5q5s5|5u2%5x5G5A1:3T3V3J5F5N4a5P3?3V4V1 4X5H4Z4R6g1M0r3a5U6z5(595X0-2r0C55125|6B5~1_0B0A0-0z5t5@245y6e0v3T3^6i6U5I6u3?3^6p206k4Q6m356Y3z6z651U5Y2 0n5?6J6=0(5c682#0t6a3c4*6!4J4d4M6d6#6-0k4e6)6r3/6l3=354e5R6A5U6|015Y6F6H576K3E6N377t7o0P0-0i7y5W2,0u0-0@0d6S6L1U5c5{6b5^5 50520C5456647E7M5`7K3E600I520L0e6`7P6C667!7X7Q2,5j0H5l7,737Y6}0-0f0f0l7D7=3h7S53557#4r7N885a600G2f2k7`5w837}5d8b7R617^637-7L8k7 0f6R640r4B1e4k0r4w2z4o132C8G0O1P0y2y4m5u0R0T0V0n04.

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.

Évaluations restantes : 5/5

.128013w4h)1(5-,_s3u:/S bn=veimFtPT6p2drgylckfao050G0w0A0O0x0K0l0r0L0K0O0l0l0u010A0x0E010406050l0n0y0y0O0H0J040q0P0K0n0*0P0t050p0;0?0^0`0/0E04051a131d0p1a0/0G0x0v0Y0!0$0(0!0t0I0n0O0I0w0i0E0J0A0d110r0d0x0I0d0K1F0d0A0-050T0s0K0w1m0#0%011E1G1I1G0A1O1Q1M0A0H1b1A0Y0}0l0E0O0t0(0F011S1o010N0V0w0t0O0y0w1M1.1:1^1U1{1Q1~200-0a0r0B0H0P0E0P0l0x100t0r0R1,0H0H0w0L2l13230t1b0p1A2y1(1*1)1N0G251p0x0t1}2i1M1j1l0Z1T2I2K0t0P2O1M0E2r1b2w2y2#0:1/2m2Q1_2U0H0@0K1M0O1D2r0N0(030k0k0L2V0w1I2T0P0i0f0m330-0f130O2$2)0.2(242+1U2-2/2;2?0w2^012`2|2~302L33351?040F393b1:3d2w2H013i0O2:1b2=0d2@2_2{2}0R3s2U3u0i0m0-0m3z2v3c0/3D3g0(3G3I053K3M3o3O3r2J3t340i0c0-0c3Y143!3e2*1n3h0P2.3H3k3L3m3N3q3Q3;3S3?0h0-0h3{2#3#2)3E3)453-3p3P2 4b323?0D0-0D4h3c1e2Z132O2B0G1*2G3%014q2N1k1b2Y0w2!4z3|3B054q4Q240x0G0(2{2w3T0f3k4Y4!494r314%1@290w4+4q3R4t354(2y3a3~3E0M0-0R0N3Z4T3$400(0b0-0r542x4~4I0t0N0-0O0E1/0H0*1}0A5c4W3 2R010,040g5q5e573F5i0H0s2r5y565t5v0j5q5b5H2,0-0v3H0w0n0H5G4k4I5v0e0o5q0/4S5d3D4*014#2)3T3w3+0r5*3/4a4.3?1?0r4;4?3:5^3v1M0p3a0r645M5W5A50040x535%04663f5A0t0-0w0l0A0k0v4Y0w5V6g5I0-5x6d5z5t6i040^5E6q6w5N1U5Y5!6d5$2%5)4Z5+0k4$3?3V3J5;6N5?4-3=353V5{1 4=6O4@4s3T6S3z656.6f5s1_692r0A5T126d6:4 0L0-0z3H0l6D4i6r2m5=6P5-3?3^6T776)5 3@4:6$5}5@6Y7g4|6e656x6=6j1I6c2#6|5f0-0H0O0L3;753E5v6v6L676y5C6C7D5X0-0e5L7q1U0P0-0u0u7Q6F3(5P5R5T7M5A5v6I746E4k776Q354e7c6V4,4^3T4e6#207j6X4c7:61636/647R0(6?0S6_7X7I6=6~040C0H0n733}7,4X7?7/0i4v7=7}7^4u7h7|6(5~7l8p6-7p7Y01876^0H6`7v855B6A5k0^5n0t5p8k6;6G6u7%7J040I0O0n0L0d8i558b8T5w8V5O6A5D5F8R7E7O5K6{8J6z5Q1Q7$8;7N047P8^8C0P5904428a6s8-5j5l8O8Q7H998*7G4z8C6z0G2f2k8%5(8)0(7F8,3h7K8:9f8S9s8?989z8K8{5S5U8~7(7O5#5y0p4V4A4P4C4M130A4F9T2E2z0O1P9Q0p4D5$0R0T0V0l04.

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.

Évaluations restantes : 5/5

.128013w4xh)1(5-,_s3u:/S bn=ve0imtP6p2drgylckfao050G0x0B0O0z0K0m0s0L0K0O0m0m0v010B0z0E010406050m0o0A0A0O0H0J040r0P0K0o0*0P0u050q0;0?0^0`0/0E04051a131d0q1a0/0G0z0w0Y0!0$0(0!0u0I0o0O0I0x0j0E0J0B0e110s0e0z0I0e0K1F0e0B0-050T0t0K0x1m0#0%011E1G1I1G0B1O1Q1M0B0H1b1A0Y0}0m0E0O0u0(0F011S1o010N0V0x0u0O0A0x1M1.1:1^1U1{1Q1~200-0a0s0C0H0P0E0P0m0z100u0s0R1,0H0H0x0L2l13230u1b0q1A2y1(1*1)1N0G251p0z0u1}2i1M1j1l0Z1T2I2K0u0P2O1M0E2r1b2w2y2#0:1/2m2Q1_2U0H0@0K1M0O1D2r0N0(030l0l0L2V0x1I2T0P0j0g0c330-0g130O2$2)0.2(242+1U2-2/2;2?0x2^012`2|2~302L33351?040F393b1:3d2w2H013i0O2:1b2=0e2@2_2{2}0R3s2U3u0j0n0-0n3z2v3c0/3D3g0(3G3I053K3M3o3O3r2J3t340j0c0-0c3Y143!3e2*1n3h0P2.3H3k3L3m3N3q3Q3;3S3?0i0-0i3{2#3#2)3E3)453-3p3P2 4b323?0D0-0D4h3c1e2Z132O2B0G1*2G3%014q2N1k1b2Y0x2!4z3|3B054q4Q240z0G0(2{2w3T0g3k4Y4!494r314%1@290x4+4q3R4t354(2y3a3~3E0M0-0R0N3Z4T3$400(0b0-0s542x4~4I0u0N0-0@0d0z0A0=5c4W3 2R010,040h5o5e573F0-0^0t2r5w565r5t0f0p5o0/4S5d3D4*014#2)3T3w3+0s5P3/4a4.3?1?0s4;4?3:5!3v1M0q3a0s5:5b5F1_50040z535M045=4k5f0-0x0m0B0l0w4Y0x5E5 5y5t5v5|5x5r0u5A0H5C686e5?1U5H5J5|5L2%5O4Z5Q0l4$3?3V3J5W6v5Y4-3=353V5%1 4=6w4@4s3T6A3z5;6S5~3f5y5^2r0B0o0H125|6U5q1_0A0z0-0y5K694X6D6x5S3?3^6B5X4,4^3T3^6J205)5Z6G3@5-5/5;6f5@611I5{2#6(4l0-0T0V1Q6:6)6o0-6d6t6a6g6i6k7l3E5H5o7f4I0P0-0v0v7y791U6+377v4I5t6q4i7v6{6y354e6`6=6N5+0j4e706L6E6}4d765}6T5:7G0(6X0S6!6$7e7-5z040H0O0L3;7K6b7o7~7s045B5D6m7r1_7x6r7P6=7R0j4v7U726F4c354v7!8h7%8k7)6S7@7/6Z6#818880866V6g0t5i0O0d8w7n5u8G3(0-7`7|2K8J5s8y7q8A2,7t858S7m0(5H0k7F6n8K045j5l5n8z8Y8Q8I8-7g040I0O0o0L0e6l8X7w8R4z8%7^848|90878H0f0f8#6%7@0u8C8)8E8P6c8P6h7_7{7}8;7L8 55968(939h0-998$9s7^8*5m0A9v8:8}60040G2f2k949r8T8H7p959O9t6j8W9R8.5H98986/6e0q4V4A4P4C4M130B4F9-2E2z0O1P9*0q4D5L0R7i0W04.

Crédits⚓︎

Frédéric Junier, Romain Janvier