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

.128013fdqnmié4=3y_ pu0ts/v1b(P;l)gow-ahR:+rS2cek050c0P0r0G0g0A0s0n0O0A0G0s0s0j010r0g0o010406050s0p0f0f0G0L0l040M0D0A0p0+0D0e0n020G0f0o0z0n0I0P0^0L0d0p0P0s050t0=0@0_0{0:0o04051q1j1t0t1q0:0c0g0u0Z0#0%0)0#0e0C0p0G0C0P0F0o0l0r0H120n0H0g0C0H0A1V0H0r0.050U0w0A0P1C0$0(011U1W1Y1W0r1(1*1$0r0L1r1Q0Z0~0s0o0G0e0)0N011,1E010b0W0P0e160P1$2123281.2b1*2e0f2g040a0n0y0L0D0o0D0s0g11130S1 0L0L0P0O2B1j2i0e1r0t1Q2N1{1}1|1%0c2k1F0g0e2d2y1$1z1B0!1-2X2Z0e0D2%1$0o2G1r2L2N2@0;22132)292-0L0^0A1$0G1T2G0b0)030m0m0O2.0P1Y2,0D0F0N0F0v0.0v1j0G2^2{0/2`2j2}1.2 3133350P3701393b3d3f2!3i3i0.0N3o3q233s2L2W013x0G321r340H36383a3c0S3H2-3J0k0.0k3N2K3r0:3R3v0)3U3W053Y3!3D3$3G2Y3I3j0i0.0i3/1k3r1u2=1j2%2Q0c1}2V3@013%2q0R1A1r2;0P2?49483P054k4r2j0g0c0)3a2L3J3l3X0n4z4B3F3(413*3j3l0n2o0P4J4k3)3h4O1$0t3p3t2|1D1.0Q0.0S0b3:4u3?4%0)0E0.0n4-2M4#3S0e0b0.0A121I0P0p0L4^4x4$2*010-040x554`4i0e4~0g0s0r0P5d4/585a0B0J550:4t4_3R4I014C2{3J264G5x3 4L3g5B274R4T405H3j5C3N0n5R4@5n294)040g4,5u045T2{4{0.1h0r0m0u4z5l5!5e4:590.5c5:5U3w5h5j5/2_5`0)5p5r5!5t5 5%5E0m4D3j3,5D4A5y4K3e4M4W0F3,4Q2f5L5G426k4Y3p5S6u5$3u5=5W2G0r530e556w57290f0g0.0q5s5m676e5z233J446d6o6h5N0F446m2p6V4V6S6s5#5S5;586z0T6C6E6,6H6J043n5!6F3S0D0.0K6;603T4~501g536N6x5o5@776G5{041f525~49715a5^66782~5|5k7b3S5p0B6M5:0t4w4a4q4c4n1j0r4f7D2T2O0G1)7A0t4d1p563S2G0f0m0b0G0Q0P0m0H6c1b1d7f0Y632_1w3s1q0}0 2B0n2d0n0h0O0L2A531+0b122I0g122Z0A1*0n0J4@7+1y1A3S1G1I1K1M1O1Q1S1:1X1Z1#7P4i2m2d2f0.0y1P1R6D5:4p563O4_7y5w6P695A0k3k3z684U6i6k8I6!4S6f8L5H8H4P3Z3B3#6g6%8U6)6=7d4 1H75546`8%0)6}040j705%4i5W0#0f0w0c0G8?7n8(5i7q5_8@5=5a7)3r6{4i6I6K8 7c0)5W5Y9e5(045*5,5.7r4i7k9p5=5g041Y5}9s79047u8-715W3e0s7h3P9a5=9c6^9j4i8:6 9C95589u8)51769490617a9Y9f727e759H5v9S299r9$9k9w937m9%7t7v7*7y1w4b7M4n5t0S0U0W0s04.

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

.128013fdqnmié4=3y_ puts5/v1b(P;l)gow-ahR:rS2cek,050c0O0q0G0g0A0r0n0N0A0G0r0r0j010q0g0o010406050r0p0f0f0G0K0l040L0D0A0p0+0D0e0n020G0f0o0z0n0I0O0^0K0d0p0O0r050t0=0@0_0{0:0o04051q1j1t0t1q0:0c0g0u0Z0#0%0)0#0e0C0p0G0C0O0F0o0l0q0H120n0H0g0C0H0A1V0H0q0.050U0w0A0O1C0$0(011U1W1Y1W0q1(1*1$0q0K1r1Q0Z0~0r0o0G0e0)0M011,1E010b0W0O0e160O1$2123281.2b1*2e0f2g040a0n0y0K0D0o0D0r0g11130S1 0K0K0O0N2B1j2i0e1r0t1Q2N1{1}1|1%0c2k1F0g0e2d2y1$1z1B0!1-2X2Z0e0D2%1$0o2G1r2L2N2@0;22132)292-0K0^0A1$0G1T2G0b0)030m0m0N2.0O1Y2,0D0F0i0F0v0.0v1j0G2^2{0/2`2j2}1.2 3133350O3701393b3d3f2!3i0F26040M3o3q233s2L2W013x0G321r340H36383a3c0S3H2-3J0k0.0k3O2K3r0:3S3v0)3V3X053Z3#3D3%3G2Y3I3j0i0.0i3:1k3=3t2|1D3w0D303W3z3!3B3$3F3)423+3j0s0.0s482_1w2=1j2%2Q0c1}2V3^013(2q0R1A1r2;0O2?3r3;3Q054G4N2j0g0c0)3a2L3J3l3Y0n4V4X4m3e4o3h3j3l0n2o0O4)4G3*4-3k1$0t3p4b3T0P0.0S0b4P2M4~4E0E0.0n544T4c2*3U0b0.0f2Y0g0f0?5b564d0)0-040x5n3@5p3U0.1Y0r0q0O5u2{3T5r0B0J5b0:494Q3S4(014Y2{3J3L3|4%4W5P4*4^5S274;4?413g5!2N3p0n5-5a5v5e50040g535L2M5/5E4E0e0.1h0q0m0u4V5C5_5c5F0.5t665o5e5~041f0O1g5D3u5w5r6a2_5:2~5y0g5A656o5|6l0.0B5H5b5{6k5e0N4#030n0S0K0e0g0O0K0n0h0A0h2p0e0q6I1+0#0n5z5B5J6j135O5Q233,3z6)5Y4,6,4:2f5%4n5)3j3-5+045.6~6C5d295=2G0q0p6K6B6c6q045B6#6b6p1.6m6%3T6e6!6u4O7f5q6y6$7e5E6.4Z446-5W406^433i5#6?5X4@6:7w6|6~791.5=3e0r7m5M6w5e5r5I665K6v4U7y0m7v0F4r4$6.7G6_7%7D2p6@4+7,7(3O6 5.7L0)730T760e787o3U0w5h2Y7i4E7h7s6D7a7c7Q5581887Y713w6r6t866x040B0Q807S7a5i6L5l0f8m7T698y7a6g6i898i7p5s8B8j047l8J8H6z0B7r4v4S1u4x0t4z1j0q4B8Y2T2O0G1)4M4y4J1p674E2G0f0m0b0G0P0O0m0H6{1b1d6g0Y7V4v1x1s0|0~100g1S2d6P0N0K2A761+0b122I980e2Z0A1*0n0J5a1w3s2%3T1G1I1K1M1O1Q1S1:1X1Z1#8.5w2m2d2f0.0y1P1R7 6b4L5c3P558T5N7!4Z0s4`7)7!7+3I9!4/5$7F5(9)4`3A3C3E9(3+9*4{4}816e8u5k5m66703T0D0.0j8r8a7M5y160w0c0Ga78G5x8L6s7d8h6804913ra25}0.8c8N018g7n8s8K8M8Fam8Qa17`015=5@af7j5 5A6264auaw7Ra83_0.8D8d9H8z8IaBarai8la!8n6zaJ4E7N0XaWaq5w0e83048uaP8Aa(6das0TaWaFaQ8eayaTa$akaxaSav6y8qaE9|848va0al87a`bha;aU1g8EbkaY6nb7ag7kaja 8f6ya*7W5n0t8T4w8*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

.128013fdq6nmi7é4=3y_ puts5/v1b(P;l)gowF-ahR:rTS2cek,050c0S0s0J0h0C0t0p0R0C0J0t0t0l010s0h0q010406050t0r0g0g0J0N0n040P0F0C0r0/0F0f0p020J0g0q0B0p0L0S0|0N0d0r0S0t050v0_0{0}0 0@0q04051u1n1x0v1u0@0c0h0w0%0)0+0-0)0f0E0r0J0E0S0I0q0n0s0K160p0K0h0E0K0C1Z0K0s0=050Y0y0C0S1G0*0,011Y1!1$1!0s1,1.1*0s0N1v1U0%120t0q0J0f0-0Q011:1I010b0!0S0f1a0S1*25272c1=2f1.2i0g2k040a0p0A0N0F0q0F0t0h15170W230N0N0S0R2F1n2m0f1v0v1U2R1 21201+0c2o1J0h0f2h2C1*1D1F0(1;2#2%0f0F2+1*0q2K1v2P2R2{0^26172-2d2;0N0|0C1*0J1X2K0b0-030o0o0R2=0S1$2:0F0I0e0I0x0=0x1n0J2|2 0?2~2n311=333537390S3b013d3f3h3j2(3m0I2a040Q3s3u273w2P2!013B0J361v380K3a3c3e3g0W3L2;3N0m0=0m3S2O3v0@3W3z0-3Z3#053%3)3H3+3K2$3M3n0k0=0k3@1o3_3x301H3A0F343!3D3(3F3*3J3-463/3n0u0=0u4c2{3`2 3X3~4m423I3,3i4s3l3n0e0=0e4y4e3{4h3}4j3C3$3E3G4G453k3N0i0=0i4P3U1y2_1n2+2U0c212Z3|014H2*1E1v2^0S2`3v3^4+4H4 2n0h0c0-3e2P3N3p4W56584q4I4#3n3p0p2s0S5f4H3.4K3o1*0v3t4f3X0T0=0W0b512Q5w4@0G0=0p5C544g2.3Y0b0=3g0f0/2h0s5J5E4S010;040z5V4R5M0f0=1$0t0s0S5$4B4@5Z0U5J5I5%320=0w5/3y5X5Z0D0M5J0@4d4+3W5e01592 3N3P400p68444r5i3O2b5m5o4!476k2R3t0p6t5^5:5X5y040h5B652Q6v5~5(0=1l0s0o0w565.6C5K3X5Z5#6O5W6G045+5-5}5L2d60626O642}6757690o5a3n3;5d6,6h5h6p3;5l2j6n6i6_5t6s6u726U2d6y2K0s0r0N0f5@741=0T0R0=0H3!0t6N4z6Z6f6?6.6b483D6g5g5q3N496{2t6}6^4t0I496r04735_7e6H1$6B2{6E6!3A0=5-6Y6T7J0-6R7n4@5)6W0h5,7l507W5Y0=0D7c7+0F0=0l0l7/6w6V5|7V7_6#0=6%7m7|557p6/0I4v6=7B7w4u6l6|6-5p4J3N873S727I7}7K0477797b6O7P5x7g040O0N1k637n7u854M888e6o7D4M7z5n8G6~8I707H6u7d0-6y3i7k7Z5 7 8A82178C7r0I4%8F6@8a8)8c7A8M7C5r8*8j8k6t8S01760X8q7^6F5`045Q5S5R8X5M7Y8#4C0=1j0S8z9a5;0=6S6*8m3}5*7%7U9k911=605?8s8{7#7{9q7Q7X7-8!2}0v534,4~4.4{1n0s4;9L2X2S0J1-9I0v4/1t6P4@2K0g0o0b0J0T0S0o0K6;1f1h9d0$80501A3w1u11132F0p2h0p0j0R0N2E791/0b162M0h162%0C1.0p0M5I9?1C1E3X1K1M1O1Q1S1U1W1@1#1%1)9X5X2q2h2j0=0A1T1V8r2}4}5K3T5D9G6+5f5a0i5s8+7v8gaO5k6m8;7waT2b4n4Y8,aSaP3@7+7#940h5T909A017;047@9v7+6y0)0g0y0c0Ja/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!0t04.

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

.128013fdqnmi4=3y_ 9puts5/v1b(P)lgow-ah:rS2cek,050c0M0q0F0g0A0r0m0L0A0F0r0r0i010q0g0o010406050r0p0f0f0F0I0k040J0C0A0p0)0C0e050t0:0=0@0_0.0o040519121c0t190.0c0g0u0X0Z0#0%0Z0e0B0p0F0B0M0E0o0k0q0G100m0G0g0B0G0A1E0G0q0,050S0w0A0M1l0!0$011D1F1H1F0q1N1P1L0q0I1a1z0X0|0r0o0F0e0%0K011R1n010b0U0M0e0F0f0M1L1-1/1@1T1`1P1}1 0,0a0m0y0I0C0o0C0r0g0 0e0m0Q1+0I0I0M0L2k12220e1a0t1z2x1%1)1(1M0c241o0g0e1|2h1L1i1k0Y1S2H2J0e0C2N1L0o2q1a2v2x2!0/1.2l2P1^2T0I0?0A1L0F1C2q0b0%030l0l0L2U0M1H2S0C0E0n0E0v0,0v120F2#2(0-2%232*1T2,2.2:2=0M2@012_2{2}2 2K320E1=040K383a1/3c2v2G013h0F2/1a2;0G2?2^2`2|0Q3r2T3t0j0,0j3y2u3b0.3C3f0%3F3H053J3L3n3N3q2I3s330h0,0h3W133Y3d2)1m3g0C2-3G3j3K3l3M3p3P3/3R330s0,0s3^2$1f2Y122N2A0c1)2F3#013O201a4j1b4h4f2$4q2Z2(0m0g0c0%2`2v3t353I4B4D013-47304H1?280M4E462~4831334I3W3!3}0%0N0,0Q0b3X3A3{3D0D0,0m4-2w4/4o0e0b0,0F0o0o1H0d0p0M4@4z3e4%010+040x554_580e0,4,3_4.4$2Q590,0O554?5l2+0,1H0r0q545j4^5s1T5a0z0H550.5z562l4C4U4G333v3)4K4U4q3Q4Y3u4R1~4T4M4V5U3t5P0t390m5+5r4A4o4)040g5i2!5-575m5g040M5w0l0u4C5y2$5B0%5a5c5I5e5`5u0g5w623b691^5D5F5I5H634A5L5!5N0E3T4J6o4N4W4P333T0m4S5S3.6x6r1L5)045,6J5^3|5m5:2q0q0p0I115I6L3D5{0L2q0M0I0l5v5x5d645n5b0z5G6)6n4L4F2(3t3=6t6;5#4X6@5X1 6C4O3:0E6^3y6J6g1T5:2~0r6e5k5.585a6j2!6l6f3C6u0l6q4b6_706w724b6A5Y7r5$4a6G5*6K5+774(0,6P6R6T5@7E3E0,2|0e0r6/5_6h0,676m7S3g5h7R6M7T5b7!6W0,5x6(686*667(4`6b6d7:7f0,0z0z5p6U7L5{4~500g527c5A7e5m7/7-865t045?7k8a5C5o5q7~0,83537@877U8n8b6%845J3D5D7`6.680t4y1d4h0t4t2y4l122B8I0F1O0M2x4j5H0Q0S0U0r04.

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

.128013fd6nmi74=]3y_ 9pu08ts5[/v1b(P)lgow-ah:rS2cekN050c0R0u0K0g0F0v0o0Q0F0K0v0v0j010u0g0q010406050v0r0f0f0K0N0m040O0H0F0r0.0H0e050y0^0`0|0~0?0q04051e171h0y1e0?0c0g0z0$0(0*0,0(0e0G0r0K0G0R0J0q0m0u0L150o0L0g0G0L0F1J0L0u0;050X0B0F0R1q0)0+011I1K1M1K0u1S1U1Q0u0N1f1E0$110v0q0K0e0,0P011W1s010b0Z0R0e0K0f0R1Q1=1@1|1Y1 1U22240;0a0o0D0N0H0q0H0v0g140e0o0V1:0N0N0R0Q2p17270e1f0y1E2C1,1.1-1R0c291t0g0e212m1Q1n1p0%1X2M2O0e0H2S1Q0q2v1f2A2C2)0@1?2q2U1}2Y0N0{0F1Q0K1H2v0b0,030n0n0Q2Z0R1M2X0H0J0A0s370;0o0A170K2*2-0=2,282/1Y2;2?2^2`0R2|012~3032342P37391`040o0P3e3g1@3i2A2L013n0K2@1f2_0L2{2}2 310V3x2Y3z0J0l3b0l3F2z3h0?3J3l0,3M3O053Q3S3t3U3w2N3y380J0i3b0i3(183*3j2.1r3m0H2=3N3p3R3r3T3v3W3`3Y3|0w3b0w412)3+2-3K3/4b3?3u3V334h363|0d3b0d4n433,463.483o3P3q3s4v3_353Z0h3b0h4E3H4p3k4H3L4J4a4L4c4N3^4g4Q3|0t3b0t4V2B4X452V4!493:3=4d3@4f4x4,390p3b0p4;3I4q3-4_4K3;4M4e4w3X4z39380;38564?4r4#4{5d4~5f4y3Z0A0A5k3d0y3f3)3H1i2%172S2F0c1.2K594w2R1o1f2$0R2(3h5C2B054w5T280g0c0,2 2A5v3p5#5%4 5g5*0o2d0R5-5t513a2C5B4G4^0S0;0V0b5V5Z4@1}0I3b63444r0b0;0R0v0u0n0z5#0R695}1}0:040C6l584Z0e0;0|0B2v6r4Y4^6o0E0M630?425D3J5,015(2-3Z3B5c6K4*503{3A1{5=5@4P6U0J6P5A3C0o6)6a595 042v0u0r0N166H2B0o6+6t6v0N6x6k6@3C6`4^0H67040g0v636_6m1Y0S0Q0;0T156 4o6z2q6R0n5)3|3#4L7m5^6!3#5;235?6L5.5u7p1Q6%6G2+6J5$7z7o393~7r7I6S5/3|3~7w246Y4+6!7M3(7b0,6-617k3K756_70722:6c040G0K0r0Q0L7i5U7!016o6q7,7{6u046w6y7 6s6B0;6D6F7(7m7K0J4k7N7V6T4i394k7T7y7P7B8k7D3f6)6*7{6-6/6;6?2)7a862:6|6~7(596o0x8G4Z0f0g0;0s8K87040k8a855!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|5v0s6W7x8,8p3z8r643K7$999-4Z7*9(3L7/0N0K0Q3`aq9man4^81839i5W7{6C9v7j9d9A1@5v5xa9928}5wad7U917W8(aR8:9N9V7#0;8x6=9U809paDaj9.048Jaz1}9*045z9r9#9l9/8U2+0y5Y5E5S5G5P170u5Jb52I2D0K1Tb20y5H6G0V0X0Z0v04.

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

.128013fdnmi4=3y_ pu0ts5/v1b(P)lgow-ah:+rS2cek050c0M0p0E0f0z0q0l0L0z0E0q0q0h010p0f0m010406050q0n0e0e0E0I0j040J0B0z0n0(0B0d050s0/0;0?0^0-0m040518111b0s180-0c0f0t0W0Y0!0$0Y0d0A0n0E0A0M0D0m0j0p0F0 0l0F0f0A0F0z1D0F0p0+050R0v0z0M1k0Z0#011C1E1G1E0p1M1O1K0p0I191y0W0{0q0m0E0d0$0K011Q1m010b0T0M0d0E0e0M1K1,1.1?1S1_1O1|1~0+0a0l0x0I0B0m0B0q0f0~0d0l0P1*0I0I0M0L2j11210d190s1y2w1$1(1%1L0c231n0f0d1{2g1K1h1j0X1R2G2I0d0B2M1K0m2p192u2w2Z0.1-2k2O1@2S0I0=0z1K0E1B2p0b0$030k0k0L2T0M1G2R0B0D0u0u310+0u110E2!2%0,2$222)1S2+2-2/2;0M2?012^2`2|2~2J31331;040K37391.3b2u2F013g0E2.192:0F2=2@2_2{0P3q2S3s0D0i0+0i3x2t3a0-3B3e0$3E3G053I3K3m3M3p2H3r320D0g0+0g3W123Y3c2(1l3f0B2,3F3i3J3k3L3o3O3/3Q3;0r0+0r3_2#1e2X112M2z0c1(2E3#013N1 194k1a4i4g2#4r2Y2%0l0f0c0$2_2u3R0u3i4D4F472}49303;4J0l270M4M4r3P4Q334J2w383|3C0N0+0P0b3X3z4(4p0C0+0l4.2v4:3~3$0b0+0R0T1O4^4A3d4{010*040w524`2P3D0+0?0v2p5a3!55570y0G520-3`4/3B4L014G2%3R3u3)4C4E5u4N4Y5x1=4U4W3.2 5F4$040l5O4@5j5c4*040f4-5q2v5Q4B4p0d0+0M0q0p0k0t4D0M5i5!5k0+595X533}5c5$045f5h5@5b1@5l5n5@5p2#5s5B5v1.3R3T3H5A5I485K3;3T4T1}4V5C4X4P6b1K0s385P6u5Z545S0+2p0p0n0I105@6w5_1@0e0f0+0o5o5/225t690d3R3?6d6Q5D6p3;3?6k1~6f4O6h336U3x6u601S5T2}0q5.6F6.0$57632Z653a4(6W4H4b4K686X6)0D4c6#6m3-6g3:334c5M6v5P6^015T6A6C6E2Z6G3C6J35527q4p0B0+0H7u7j5{4 0z515 5R615=6O6H3f0+0A0E0n0L0F6?665:5c575?7U6x2*5e0I5g7T6~7H1S5l0y7A7+0$7x047z6@7:5d047D7F7Z7L6_7J7G7V7#040c2d2i7)5r837,817~3C5{5}894_7_7-6N5 0s4z1c4i0s4u2x4m112A8w0E1N0M2w4k5p0P7D0q04.

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

.128013fdnmi4=3y_ pu0ts5/v1b(P)lgow-ah:+rxS2cek,050c0N0p0E0f0z0q0l0M0z0E0q0q0h010p0f0m010406050q0n0e0e0E0I0j040K0B0z0n0*0B0d050s0;0?0^0`0/0m04051a131d0s1a0/0c0f0t0Y0!0$0(0!0d0A0n0E0A0N0D0m0j0p0F110l0F0f0A0F0z1F0F0p0-050T0v0z0N1m0#0%011E1G1I1G0p1O1Q1M0p0I1b1A0Y0}0q0m0E0d0(0L011S1o010b0V0N0d0E0e0N1M1.1:1^1U1{1Q1~200-0a0l0x0I0B0m0B0q0f100d0l0R1,0I0I0N0M2l13230d1b0s1A2y1(1*1)1N0c251p0f0d1}2i1M1j1l0Z1T2I2K0d0B2O1M0m2r1b2w2y2#0:1/2m2Q1_2U0I0@0z1M0E1D2r0b0(030k0k0M2V0N1I2T0B0D0u0L330-0u130E2$2)0.2(242+1U2-2/2;2?0N2^012`2|2~302L33351?040L393b1:3d2w2H013i0E2:1b2=0F2@2_2{2}0R3s2U3u0D0i0-0i3z2v3c0/3D3g0(3G3I053K3M3o3O3r2J3t340D0g0-0g3Y143!3e2*1n3h0B2.3H3k3L3m3N3q3Q3;3S3?0r0-0r3{2%1g2Z132O2B0c1*2G3%013P211b4m1c4k4i2%4t2!2)0l0f0c0(2{2w3T0u3k4F4H492 4b323?4L0l290N4O4t3R4S354L2y3a3~3E0O0-0R0b3Z3B4*4r0C0-0l4:2x4=403(0b0-0F0E0 0N0n0I4`4C3f4}010,040w574|2R3F0-0^0v2r5f3$5a5c0y0G570/3|4;3D4N014I2)3T3w3+4E4G5z4P4!5C1@4W4Y3:315K4(040l5T4_5o5h4,040f4/5v2x5V4D4r0d0-0N0q0p0k0t4F0N5n5)5p0-5e5$583 5h5+045k5m5|5g1_5q5s5|5u2%5x5G5A1:3T3V3J5F5N4a5P3?3V4V1 4X5H4Z4R6g1M0s3a5U6z5(595X0-2r0p55125|6B5~1_0e0f0-0o5t5@245y6e0d3T3^6i6U5I6u3?3^6p206k4Q6m356Y3z6z651U5Y2 0q5?6J6=0(5c682#0l6a3c4*6!4J4d4M6d6#6-0D4e6)6r3/6l3=354e5R6A5U6|015Y6F6H576K3E6N377t7o0B0-0H7y5W2,0v0-0@0J6S6L1U5c5{6b5^5 50520p5456647E7M5`7K3E600A520M0F6`7P6C667!7X7Q2,5j0I5l7,737Y6}0-0y0y0P7D7=3h7S53557#4r7N885a600c2f2k7`5w837}5d8b7R617^637-7L8k7 0y6R640s4B1e4k0s4w2z4o132C8G0E1P0N2y4m5u0R0T0V0q04.

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

.128013fd6nmi4=3y_ puts5/v1b(P)lgowF-ah:rTS2cek,050c0N0p0F0g0z0q0m0M0z0F0q0q0i010p0g0n010406050q0o0f0f0F0I0k040K0B0z0o0*0B0e050s0;0?0^0`0/0n04051a131d0s1a0/0c0g0t0Y0!0$0(0!0e0A0o0F0A0N0E0n0k0p0G110m0G0g0A0G0z1F0G0p0-050T0v0z0N1m0#0%011E1G1I1G0p1O1Q1M0p0I1b1A0Y0}0q0n0F0e0(0L011S1o010b0V0N0e0F0f0N1M1.1:1^1U1{1Q1~200-0a0m0x0I0B0n0B0q0g100e0m0R1,0I0I0N0M2l13230e1b0s1A2y1(1*1)1N0c251p0g0e1}2i1M1j1l0Z1T2I2K0e0B2O1M0n2r1b2w2y2#0:1/2m2Q1_2U0I0@0z1M0F1D2r0b0(030l0l0M2V0N1I2T0B0E0u0j330-0u130F2$2)0.2(242+1U2-2/2;2?0N2^012`2|2~302L33351?040L393b1:3d2w2H013i0F2:1b2=0G2@2_2{2}0R3s2U3u0E0j0-0j3z2v3c0/3D3g0(3G3I053K3M3o3O3r2J3t340E0h0-0h3Y143!3e2*1n3h0B2.3H3k3L3m3N3q3Q3;3S3?0r0-0r3{2#3#2)3E3)453-3p3P2 4b323?0d0-0d4h3c1e2Z132O2B0c1*2G3%014q2N1k1b2Y0N2!4z3|3B054q4Q240g0c0(2{2w3T0u3k4Y4!494r314%1@290N4+4q3R4t354(2y3a3~3E0O0-0R0b3Z4T3$400(0C0-0m542x4~4I0e0b0-0F0n1/0I0*1}0p5c4W3 2R010,040w5q5e573F5i0I0v2r5y565t5v0P5q5b5H2,0-0t3H0N0o0I5G4k4I5v0y0H5q0/4S5d3D4*014#2)3T3w3+0m5*3/4a4.3?1?0m4;4?3:5^3v1M0s3a0m645M5W5A50040g535%04663f5A0e0-0N0q0p0l0t4Y0N5V6g5I0-5x6d5z5t6i040^5E6q6w5N1U5Y5!6d5$2%5)4Z5+0l4$3?3V3J5;6N5?4-3=353V5{1 4=6O4@4s3T6S3z656.6f5s1_692r0p5T126d6:4 0M0-0D3H0q6D4i6r2m5=6P5-3?3^6T776)5 3@4:6$5}5@6Y7g4|6e656x6=6j1I6c2#6|5f0-0I0F0M3;753E5v6v6L676y5C6C7D5X0-0y5L7q1U0B0-0i0i7Q6F3(5P5R5T7M5A5v6I746E4k776Q354e7c6V4,4^3T4e6#207j6X4c7:61636/647R0(6?0S6_7X7I6=6~040J0I0o733}7,4X7?7/0E4v7=7}7^4u7h7|6(5~7l8p6-7p7Y01876^0I6`7v855B6A5k0^5n0e5p8k6;6G6u7%7J040A0F0o0M0G8i558b8T5w8V5O6A5D5F8R7E7O5K6{8J6z5Q1Q7$8;7N047P8^8C0B5904428a6s8-5j5l8O8Q7H998*7G4z8C6z0c2f2k8%5(8)0(7F8,3h7K8:9f8S9s8?989z8K8{5S5U8~7(7O5#5y0s4V4A4P4C4M130p4F9T2E2z0F1P9Q0s4D5$0R0T0V0q04.

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

.128013fd6nmi4=3y_ pu0ts5/v1b(P)lgow-ah:rxS2cek,050c0N0q0F0g0A0r0m0M0A0F0r0r0i010q0g0n010406050r0o0f0f0F0I0k040K0C0A0o0*0C0e050t0;0?0^0`0/0n04051a131d0t1a0/0c0g0u0Y0!0$0(0!0e0B0o0F0B0N0E0n0k0q0G110m0G0g0B0G0A1F0G0q0-050T0w0A0N1m0#0%011E1G1I1G0q1O1Q1M0q0I1b1A0Y0}0r0n0F0e0(0L011S1o010b0V0N0e0F0f0N1M1.1:1^1U1{1Q1~200-0a0m0y0I0C0n0C0r0g100e0m0R1,0I0I0N0M2l13230e1b0t1A2y1(1*1)1N0c251p0g0e1}2i1M1j1l0Z1T2I2K0e0C2O1M0n2r1b2w2y2#0:1/2m2Q1_2U0I0@0A1M0F1D2r0b0(030l0l0M2V0N1I2T0C0E0v0h330-0v130F2$2)0.2(242+1U2-2/2;2?0N2^012`2|2~302L33351?040L393b1:3d2w2H013i0F2:1b2=0G2@2_2{2}0R3s2U3u0E0j0-0j3z2v3c0/3D3g0(3G3I053K3M3o3O3r2J3t340E0h0-0h3Y143!3e2*1n3h0C2.3H3k3L3m3N3q3Q3;3S3?0s0-0s3{2#3#2)3E3)453-3p3P2 4b323?0d0-0d4h3c1e2Z132O2B0c1*2G3%014q2N1k1b2Y0N2!4z3|3B054q4Q240g0c0(2{2w3T0v3k4Y4!494r314%1@290N4+4q3R4t354(2y3a3~3E0O0-0R0b3Z4T3$400(0D0-0m542x4~4I0e0b0-0@0J0g0f0=5c4W3 2R010,040x5o5e573F0-0^0w2r5w565r5t0z0H5o0/4S5d3D4*014#2)3T3w3+0m5P3/4a4.3?1?0m4;4?3:5!3v1M0t3a0m5:5b5F1_50040g535M045=4k5f0-0N0r0q0l0u4Y0N5E5 5y5t5v5|5x5r0e5A0I5C686e5?1U5H5J5|5L2%5O4Z5Q0l4$3?3V3J5W6v5Y4-3=353V5%1 4=6w4@4s3T6A3z5;6S5~3f5y5^2r0q0o0I125|6U5q1_0f0g0-0p5K694X6D6x5S3?3^6B5X4,4^3T3^6J205)5Z6G3@5-5/5;6f5@611I5{2#6(4l0-0T0V1Q6:6)6o0-6d6t6a6g6i6k7l3E5H5o7f4I0C0-0i0i7y791U6+377v4I5t6q4i7v6{6y354e6`6=6N5+0E4e706L6E6}4d765}6T5:7G0(6X0S6!6$7e7-5z040I0F0M3;7K6b7o7~7s045B5D6m7r1_7x6r7P6=7R0E4v7U726F4c354v7!8h7%8k7)6S7@7/6Z6#818880866V6g0w5i0F0J8w7n5u8G3(0-7`7|2K8J5s8y7q8A2,7t858S7m0(5H0P7F6n8K045j5l5n8z8Y8Q8I8-7g040B0F0o0M0G6l8X7w8R4z8%7^848|90878H0z0z8#6%7@0e8C8)8E8P6c8P6h7_7{7}8;7L8 55968(939h0-998$9s7^8*5m0f9v8:8}60040c2f2k949r8T8H7p959O9t6j8W9R8.5H98986/6e0t4V4A4P4C4M130q4F9-2E2z0F1P9*0t4D5L0R7i0W04.

Crédits⚓︎

Frédéric Junier, Romain Janvier