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

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

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

.128013witkcvo-)ylqb0p_P3(a;+g=R/m4rseSfd :12énuh050I0F0d0u0c0l0E0J0f0l0u0E0E0y010d0c0p010406050E0P0B0B0u0D0k040G0h0l0P0+0h0O0J020u0B0p0v0J0z0F0^0D0m0P0F0E050A0=0@0_0{0:0p04051q1j1t0A1q0:0I0c0g0Z0#0%0)0#0O0x0P0u0x0F0i0p0k0d0Q120J0Q0c0x0Q0l1V0Q0d0.050U0n0l0F1C0$0(011U1W1Y1W0d1(1*1$0d0D1r1Q0Z0~0E0p0u0O0)0M011,1E010H0W0F0O160F1$2123281.2b1*2e0B2g040a0J0r0D0h0p0h0E0c11130S1 0D0D0F0f2B1j2i0O1r0A1Q2N1{1}1|1%0I2k1F0c0O2d2y1$1z1B0!1-2X2Z0O0h2%1$0p2G1r2L2N2@0;22132)292-0D0^0l1$0u1T2G0H0)030q0q0f2.0F1Y2,0h0i0M0i0L0.0L1j0u2^2{0/2`2j2}1.2 3133350F3701393b3d3f2!3i3i0.0M3o3q233s2L2W013x0u321r340Q36383a3c0S3H2-3J0s0.0s3N2K3r0:3R3v0)3U3W053Y3!3D3$3G2Y3I3j0C0.0C3/1k3r1u2=1j2%2Q0I1}2V3@013%2q0R1A1r2;0F2?49483P054k4r2j0c0I0)3a2L3J3l3X0J4z4B3F3(413*3j3l0J2o0F4J4k3)3h4O1$0A3p3t2|1D1.0e0.0S0H3:4u3?4%0)0b0.0J4-2M4#3S0O0H0.0l121I0F0P0D4^4x4$2*010-040t554`4i0O4~0c0E0d0F5d4/585a0j0K550:4t4_3R4I014C2{3J264G5x3 4L3g5B274R4T405H3j5C3N0J5R4@5n294)040c4,5u045T2{4{0.1h0d0q0g4z5l5!5e4:590.5c5:5U3w5h5j5/2_5`0)5p5r5!5t5 5%5E0q4D3j3,5D4A5y4K3e4M4W0i3,4Q2f5L5G426k4Y3p5S6u5$3u5=5W2G0d530O556w57290B0c0.0o5s5m676e5z233J446d6o6h5N0i446m2p6V4V6S6s5#5S5;586z0T6C6E6,6H6J043n5!6F3S0h0.0w6;603T4~501g536N6x5o5@776G5{041f525~49715a5^66782~5|5k7b3S5p0j6M5:0A4w4a4q4c4n1j0d4f7D2T2O0u1)7A0A4d1p563S2G0B0q0H0u0e0F0q0Q6c1b1d7f0Y632_1w3s1q0}0 2B0J2d0J0N0f0D2A531+0H122I0c122Z0l1*0J0K4@7+1y1A3S1G1I1K1M1O1Q1S1:1X1Z1#4o4b7*2_7y5w6P695A0s3k3z684U6i6k8x6!4S6f8A5H8w4P3Z3B3#6g6%8J6)6=7d4 1H75546`8S0)6}040y705%4i5W0#0B0n0I0u8(7n8T5i7q5_8)5=5a7)3r6{4i6I6K8;7c0)5W5Y935(045*5,5.7r4i7k9e5=5g041Y5}9h79047u8Y715W3e0E7h3P8 5=916^984i8#6 9r8`589j8U51768_8=617a9N94727e759w5v9H299g9R999l8^7m9S7t7v7*7y1w4b7M4n5t0S0U0W0E04.

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

.128013witkcvo-)ylqbp_P3(a;g=R/m4rseSf,d :12é5nuh050H0D0d0t0c0l0C0I0f0l0t0C0C0w010d0c0o010406050C0P0z0z0t0B0k040E0h0l0P0+0h0O0I020t0z0o0u0I0x0D0^0B0m0P0D0C050y0=0@0_0{0:0o04051q1j1t0y1q0:0H0c0g0Z0#0%0)0#0O0v0P0t0v0D0i0o0k0d0Q120I0Q0c0v0Q0l1V0Q0d0.050U0n0l0D1C0$0(011U1W1Y1W0d1(1*1$0d0B1r1Q0Z0~0C0o0t0O0)0L011,1E010F0W0D0O160D1$2123281.2b1*2e0z2g040a0I0q0B0h0o0h0C0c11130S1 0B0B0D0f2B1j2i0O1r0y1Q2N1{1}1|1%0H2k1F0c0O2d2y1$1z1B0!1-2X2Z0O0h2%1$0o2G1r2L2N2@0;22132)292-0B0^0l1$0t1T2G0F0)030p0p0f2.0D1Y2,0h0i0A0i0K0.0K1j0t2^2{0/2`2j2}1.2 3133350D3701393b3d3f2!3i0i26040L3o3q233s2L2W013x0t321r340Q36383a3c0S3H2-3J0r0.0r3O2K3r0:3S3v0)3V3X053Z3#3D3%3G2Y3I3j0A0.0A3:1k3=3t2|1D3w0h303W3z3!3B3$3F3)423+3j0N0.0N482_1w2=1j2%2Q0H1}2V3^013(2q0R1A1r2;0D2?3r3;3Q054G4N2j0c0H0)3a2L3J3l3Y0I4V4X4m3e4o3h3j3l0I2o0D4)4G3*4-3k1$0y3p4b3T0e0.0S0F4P2M4~4E0b0.0I544T4c2*3U0F0.0z2Y0c0z0?5b564d0)0-040s5n3@5p3U0.1Y0C0d0D5u2{3T5r0j0J5b0:494Q3S4(014Y2{3J3L3|4%4W5P4*4^5S274;4?413g5!2N3p0I5-5a5v5e50040c535L2M5/5E4E0O0.1h0d0p0g4V5C5_5c5F0.5t665o5e5~041f0D1g5D3u5w5r6a2_5:2~5y0c5A656o5|6l0.0j5H5b5{6k5e0f4#030I0S0B0O0c0D0B0I0M0l0M2p0O0d6I1+0#0I5z5B5J6j135O5Q233,3z6)5Y4,6,4:2f5%4n5)3j3-5+045.6~6C5d295=2G0d0P6K6B6c6q045B6#6b6p1.6m6%3T6e6!6u4O7f5q6y6$7e5E6.4Z446-5W406^433i5#6?5X4@6:7w6|6~791.5=3e0C7m5M6w5e5r5I665K6v4U7y0p7v0i4r4$6.7G6_7%7D2p6@4+7,7(3O6 5.7L0)730T760O787o3U0n5h2Y7i4E7h7s6D7a7c7Q5581887Y713w6r6t866x040j0G807S7a5i6L5l0z8m7T698y7a6g6i898i7p5s8B8j047l8J8H6z0j7r4v4S1u4x0y4z1j0d4B8Y2T2O0t1)4M4y4J1p674E2G0z0p0F0t0e0D0p0Q6{1b1d6g0Y7V4v1x1s0|0~100c1S2d6P0f0B2A761+0F122I980O2Z0l1*0I0J5a1w3s2%3T1G1I1K1M1O1Q1S1:1X1Z1#4K4x4v2_8T5N7!4Z0N4`7)7!7+3I9P4/5$7F5(9U4`3A3C3E9T3+9V4{4}816e8u5k5m66703T0h0.0w8r8a7M5y160n0H0t9|8G5x8L6s7d8h6804913r9@5}0.8c8N018g7n8s8K8M8Fab8Q9?7`015=5@a47j5 5A6264ajal7R9}3_0.8D8d8.8n6namaHa6apaa876yas2@af5w7N0XaLaY6d83048uaE8Aaqag7b0TaLauaF8eanaIa78la.8n8paya/9:8wa,8Ia}6daJ1g8EaTaNaj7ka8a=8faVaW4a6b0y8T4w8*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

.128013witkcvo-)ylqbp_P3(a;g=R/mT4rse7Sf,d 612:Fé5nuh050J0E0d0t0c0l0D0K0f0l0t0D0D0w010d0c0o010406050D0T0z0z0t0C0k040G0h0l0T0/0h0S0K020t0z0o0u0K0x0E0|0C0m0T0E0D050y0_0{0}0 0@0o04051u1n1x0y1u0@0J0c0g0%0)0+0-0)0S0v0T0t0v0E0i0o0k0d0U160K0U0c0v0U0l1Z0U0d0=050Y0n0l0E1G0*0,011Y1!1$1!0d1,1.1*0d0C1v1U0%120D0o0t0S0-0N011:1I010H0!0E0S1a0E1*25272c1=2f1.2i0z2k040a0K0q0C0h0o0h0D0c15170W230C0C0E0f2F1n2m0S1v0y1U2R1 21201+0J2o1J0c0S2h2C1*1D1F0(1;2#2%0S0h2+1*0o2K1v2P2R2{0^26172-2d2;0C0|0l1*0t1X2K0H0-030p0p0f2=0E1$2:0h0i0L0i0M0=0M1n0t2|2 0?2~2n311=333537390E3b013d3f3h3j2(3m0i2a040N3s3u273w2P2!013B0t361v380U3a3c3e3g0W3L2;3N0r0=0r3S2O3v0@3W3z0-3Z3#053%3)3H3+3K2$3M3n0B0=0B3@1o3_3x301H3A0h343!3D3(3F3*3J3-463/3n0R0=0R4c2{3`2 3X3~4m423I3,3i4s3l3n0L0=0L4y4e3{4h3}4j3C3$3E3G4G453k3N0F0=0F4P3U1y2_1n2+2U0J212Z3|014H2*1E1v2^0E2`3v3^4+4H4 2n0c0J0-3e2P3N3p4W56584q4I4#3n3p0K2s0E5f4H3.4K3o1*0y3t4f3X0e0=0W0H512Q5w4@0b0=0K5C544g2.3Y0H0=3g0S0/2h0d5J5E4S010;040s5V4R5M0S0=1$0D0d0E5$4B4@5Z0I5J5I5%320=0g5/3y5X5Z0j0O5J0@4d4+3W5e01592 3N3P400K68444r5i3O2b5m5o4!476k2R3t0K6t5^5:5X5y040c5B652Q6v5~5(0=1l0d0p0g565.6C5K3X5Z5#6O5W6G045+5-5}5L2d60626O642}6757690p5a3n3;5d6,6h5h6p3;5l2j6n6i6_5t6s6u726U2d6y2K0d0T0C0S5@741=0e0f0=0P3!0D6N4z6Z6f6?6.6b483D6g5g5q3N496{2t6}6^4t0i496r04735_7e6H1$6B2{6E6!3A0=5-6Y6T7J0-6R7n4@5)6W0c5,7l507W5Y0=0j7c7+0h0=0w0w7/6w6V5|7V7_6#0=6%7m7|557p6/0i4v6=7B7w4u6l6|6-5p4J3N873S727I7}7K0477797b6O7P5x7g040A0C1k637n7u854M888e6o7D4M7z5n8G6~8I707H6u7d0-6y3i7k7Z5 7 8A82178C7r0i4%8F6@8a8)8c7A8M7C5r8*8j8k6t8S01760X8q7^6F5`045Q5S5R8X5M7Y8#4C0=1j0E8z9a5;0=6S6*8m3}5*7%7U9k911=605?8s8{7#7{9q7Q7X7-8!2}0y534,4~4.4{1n0d4;9L2X2S0t1-9I0y4/1t6P4@2K0z0p0H0t0e0E0p0U6;1f1h9d0$80501A3w1u11132F0K2h0K0Q0f0C2E791/0H162M0c162%0l1.0K0O5I9?1C1E3X1K1M1O1Q1S1U1W1@1#1%1)4|4-9E2}9G6+5f5a0F5s8+7v8gaD5k6m8;7waI2b4n4Y8,aHaE3@7+7#940c5T909A017;047@9v7+6y0)0z0n0J0ta!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, ()))))

Évaluations restantes : 5/5

.128013witkcvo-)ylqbp_P3(ag=/m4rse9Sf,d :125nuh050G0B0d0t0c0l0A0H0f0l0t0A0A0v010d0c0o010406050A0N0x0x0t0z0k040D0h0l0N0)0h0M050w0:0=0@0_0.0o040519121c0w190.0G0c0g0X0Z0#0%0Z0M0u0N0t0u0B0i0o0k0d0O100H0O0c0u0O0l1E0O0d0,050S0n0l0B1l0!0$011D1F1H1F0d1N1P1L0d0z1a1z0X0|0A0o0t0M0%0K011R1n010E0U0B0M0t0x0B1L1-1/1@1T1`1P1}1 0,0a0H0q0z0h0o0h0A0c0 0M0H0Q1+0z0z0B0f2k12220M1a0w1z2x1%1)1(1M0G241o0c0M1|2h1L1i1k0Y1S2H2J0M0h2N1L0o2q1a2v2x2!0/1.2l2P1^2T0z0?0l1L0t1C2q0E0%030p0p0f2U0B1H2S0h0i0C0i0J0,0J120t2#2(0-2%232*1T2,2.2:2=0B2@012_2{2}2 2K320i1=040K383a1/3c2v2G013h0t2/1a2;0O2?2^2`2|0Q3r2T3t0r0,0r3y2u3b0.3C3f0%3F3H053J3L3n3N3q2I3s330y0,0y3W133Y3d2)1m3g0h2-3G3j3K3l3M3p3P3/3R330L0,0L3^2$1f2Y122N2A0G1)2F3#013O201a4j1b4h4f2$4q2Z2(0H0c0G0%2`2v3t353I4B4D013-47304H1?280B4E462~4831334I3W3!3}0%0e0,0Q0E3X3A3{3D0b0,0H4-2w4/4o0M0E0,0t0o0o1H0m0N0B4@4z3e4%010+040s554_580M0,4,3_4.4$2Q590,0F554?5l2+0,1H0A0d545j4^5s1T5a0j0I550.5z562l4C4U4G333v3)4K4U4q3Q4Y3u4R1~4T4M4V5U3t5P0w390H5+5r4A4o4)040c5i2!5-575m5g040B5w0p0g4C5y2$5B0%5a5c5I5e5`5u0c5w623b691^5D5F5I5H634A5L5!5N0i3T4J6o4N4W4P333T0H4S5S3.6x6r1L5)045,6J5^3|5m5:2q0d0N0z115I6L3D5{0f2q0B0z0p5v5x5d645n5b0j5G6)6n4L4F2(3t3=6t6;5#4X6@5X1 6C4O3:0i6^3y6J6g1T5:2~0A6e5k5.585a6j2!6l6f3C6u0p6q4b6_706w724b6A5Y7r5$4a6G5*6K5+774(0,6P6R6T5@7E3E0,2|0M0A6/5_6h0,676m7S3g5h7R6M7T5b7!6W0,5x6(686*667(4`6b6d7:7f0,0j0j5p6U7L5{4~500c527c5A7e5m7/7-865t045?7k8a5C5o5q7~0,83537@877U8n8b6%845J3D5D7`6.680w4y1d4h0w4t2y4l122B8I0t1O0B2x4j5H0Q0S0U0A04.

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

.128013w]itkc[vN8o-)yl0bp_P3(ag=/m4rse97Sfd 612:5nuh050K0F0e0x0d0p0E0L0g0p0x0E0E0z010e0d0s010406050E0S0B0B0x0D0o040I0l0p0S0.0l0R050A0^0`0|0~0?0s04051e171h0A1e0?0K0d0i0$0(0*0,0(0R0y0S0x0y0F0m0s0o0e0T150L0T0d0y0T0p1J0T0e0;050X0r0p0F1q0)0+011I1K1M1K0e1S1U1Q0e0D1f1E0$110E0s0x0R0,0O011W1s010J0Z0F0R0x0B0F1Q1=1@1|1Y1 1U22240;0a0L0u0D0l0s0l0E0d140R0L0V1:0D0D0F0g2p17270R1f0A1E2C1,1.1-1R0K291t0d0R212m1Q1n1p0%1X2M2O0R0l2S1Q0s2v1f2A2C2)0@1?2q2U1}2Y0D0{0p1Q0x1H2v0J0,030t0t0g2Z0F1M2X0l0m0N0q370;0L0N170x2*2-0=2,282/1Y2;2?2^2`0F2|012~3032342P37391`040L0O3e3g1@3i2A2L013n0x2@1f2_0T2{2}2 310V3x2Y3z0m0v3b0v3F2z3h0?3J3l0,3M3O053Q3S3t3U3w2N3y380m0C3b0C3(183*3j2.1r3m0l2=3N3p3R3r3T3v3W3`3Y3|0Q3b0Q412)3+2-3K3/4b3?3u3V334h363|0M3b0M4n433,463.483o3P3q3s4v3_353Z0H3b0H4E3H4p3k4H3L4J4a4L4c4N3^4g4Q3|0k3b0k4V2B4X452V4!493:3=4d3@4f4x4,390G3b0G4;3I4q3-4_4K3;4M4e4w3X4z39380;38564?4r4#4{5d4~5f4y3Z0N0N5k3d0A3f3)3H1i2%172S2F0K1.2K594w2R1o1f2$0F2(3h5C2B054w5T280d0K0,2 2A5v3p5#5%4 5g5*0L2d0F5-5t513a2C5B4G4^0f0;0V0J5V5Z4@1}0b3b63444r0J0;0F0E0e0t0i5#0F695}1}0:040w6l584Z0R0;0|0r2v6r4Y4^6o0n0P630?425D3J5,015(2-3Z3B5c6K4*503{3A1{5=5@4P6U0m6P5A3C0L6)6a595 042v0e0S0D166H2B0L6+6t6v0D6x6k6@3C6`4^0l67040d0E636_6m1Y0f0g0;0j156 4o6z2q6R0t5)3|3#4L7m5^6!3#5;235?6L5.5u7p1Q6%6G2+6J5$7z7o393~7r7I6S5/3|3~7w246Y4+6!7M3(7b0,6-617k3K756_70722:6c040y0x0S0g0T7i5U7!016o6q7,7{6u046w6y7 6s6B0;6D6F7(7m7K0m4k7N7V6T4i394k7T7y7P7B8k7D3f6)6*7{6-6/6;6?2)7a862:6|6~7(596o0h8G4Z0B0d0;0q8K87040c8a855!7O7n6N4A5+8X7t8j0m4B8m8h7Q394B5{3i8V7l8X8d4S8g7z8%5h0m4S8+8{6Z8(8_7Z8C7c603r8Q66688=6b602j2o7_6I960,7}9a3m8E847G9k7|886E707F7`4q8c8Z394.8`8o5_4.909F6!9D3F8t8B6A1}8w0W8y797-9o826}9q9y9P1Y8I9n0,8M0;3E9d8H0;8T9w8b8@9B0m539E7A5_539I9{6!9_3F9x9j8W5-8d5j9`8|5v0q6W7x8,8p3z8r643K7$999-4Z7*9(3L7/0D0x0g3`aq9man4^81839i5W7{6C9v7j9d9A1@5v5xa9928}5wad7U917W8(aR8:9N9V7#0;8x6=9U809paDaj9.048Jaz1}9*045z9r9#9l9/8U2+0A5Y5E5S5G5P170e5Jb52I2D0x1Tb20A5H6G0V0X0Z0E04.

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

.128013witkcvo-)yl0bp_P3(a+g=/m4rseSfd :125nuh050F0C0d0t0c0l0B0G0f0l0t0B0B0w010d0c0o010406050B0M0y0y0t0A0k040D0h0l0M0(0h0L050x0/0;0?0^0-0o040518111b0x180-0F0c0g0W0Y0!0$0Y0L0v0M0t0v0C0i0o0k0d0N0 0G0N0c0v0N0l1D0N0d0+050R0n0l0C1k0Z0#011C1E1G1E0d1M1O1K0d0A191y0W0{0B0o0t0L0$0J011Q1m010E0T0C0L0t0y0C1K1,1.1?1S1_1O1|1~0+0a0G0q0A0h0o0h0B0c0~0L0G0P1*0A0A0C0f2j11210L190x1y2w1$1(1%1L0F231n0c0L1{2g1K1h1j0X1R2G2I0L0h2M1K0o2p192u2w2Z0.1-2k2O1@2S0A0=0l1K0t1B2p0E0$030p0p0f2T0C1G2R0h0i0I0I310+0I110t2!2%0,2$222)1S2+2-2/2;0C2?012^2`2|2~2J31331;040J37391.3b2u2F013g0t2.192:0N2=2@2_2{0P3q2S3s0i0r0+0r3x2t3a0-3B3e0$3E3G053I3K3m3M3p2H3r320i0z0+0z3W123Y3c2(1l3f0h2,3F3i3J3k3L3o3O3/3Q3;0K0+0K3_2#1e2X112M2z0F1(2E3#013N1 194k1a4i4g2#4r2Y2%0G0c0F0$2_2u3R0I3i4D4F472}49303;4J0G270C4M4r3P4Q334J2w383|3C0e0+0P0E3X3z4(4p0b0+0G4.2v4:3~3$0E0+0R0T1O4^4A3d4{010*040s524`2P3D0+0?0n2p5a3!55570j0H520-3`4/3B4L014G2%3R3u3)4C4E5u4N4Y5x1=4U4W3.2 5F4$040G5O4@5j5c4*040c4-5q2v5Q4B4p0L0+0C0B0d0p0g4D0C5i5!5k0+595X533}5c5$045f5h5@5b1@5l5n5@5p2#5s5B5v1.3R3T3H5A5I485K3;3T4T1}4V5C4X4P6b1K0x385P6u5Z545S0+2p0d0M0A105@6w5_1@0y0c0+0m5o5/225t690L3R3?6d6Q5D6p3;3?6k1~6f4O6h336U3x6u601S5T2}0B5.6F6.0$57632Z653a4(6W4H4b4K686X6)0i4c6#6m3-6g3:334c5M6v5P6^015T6A6C6E2Z6G3C6J35527q4p0h0+0u7u7j5{4 0l515 5R615=6O6H3f0+0v0t0M0f0N6?665:5c575?7U6x2*5e0A5g7T6~7H1S5l0j7A7+0$7x047z6@7:5d047D7F7Z7L6_7J7G7V7#040F2d2i7)5r837,817~3C5{5}894_7_7-6N5 0x4z1c4i0x4u2x4m112A8w0t1N0C2w4k5p0P7D0B04.

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

.128013witkcvo-)yl0bxp_P3(a+g=/m4rseSf,d :125nuh050H0D0d0u0c0l0C0I0f0l0u0C0C0x010d0c0p010406050C0O0z0z0u0B0k040E0h0l0O0*0h0N050y0;0?0^0`0/0p04051a131d0y1a0/0H0c0g0Y0!0$0(0!0N0w0O0u0w0D0i0p0k0d0P110I0P0c0w0P0l1F0P0d0-050T0n0l0D1m0#0%011E1G1I1G0d1O1Q1M0d0B1b1A0Y0}0C0p0u0N0(0L011S1o010F0V0D0N0u0z0D1M1.1:1^1U1{1Q1~200-0a0I0r0B0h0p0h0C0c100N0I0R1,0B0B0D0f2l13230N1b0y1A2y1(1*1)1N0H251p0c0N1}2i1M1j1l0Z1T2I2K0N0h2O1M0p2r1b2w2y2#0:1/2m2Q1_2U0B0@0l1M0u1D2r0F0(030q0q0f2V0D1I2T0h0i0K0L330-0K130u2$2)0.2(242+1U2-2/2;2?0D2^012`2|2~302L33351?040L393b1:3d2w2H013i0u2:1b2=0P2@2_2{2}0R3s2U3u0i0s0-0s3z2v3c0/3D3g0(3G3I053K3M3o3O3r2J3t340i0A0-0A3Y143!3e2*1n3h0h2.3H3k3L3m3N3q3Q3;3S3?0M0-0M3{2%1g2Z132O2B0H1*2G3%013P211b4m1c4k4i2%4t2!2)0I0c0H0(2{2w3T0K3k4F4H492 4b323?4L0I290D4O4t3R4S354L2y3a3~3E0e0-0R0F3Z3B4*4r0b0-0I4:2x4=403(0F0-0P0u0 0D0O0B4`4C3f4}010,040t574|2R3F0-0^0n2r5f3$5a5c0j0J570/3|4;3D4N014I2)3T3w3+4E4G5z4P4!5C1@4W4Y3:315K4(040I5T4_5o5h4,040c4/5v2x5V4D4r0N0-0D0C0d0q0g4F0D5n5)5p0-5e5$583 5h5+045k5m5|5g1_5q5s5|5u2%5x5G5A1:3T3V3J5F5N4a5P3?3V4V1 4X5H4Z4R6g1M0y3a5U6z5(595X0-2r0d55125|6B5~1_0z0c0-0m5t5@245y6e0N3T3^6i6U5I6u3?3^6p206k4Q6m356Y3z6z651U5Y2 0C5?6J6=0(5c682#0I6a3c4*6!4J4d4M6d6#6-0i4e6)6r3/6l3=354e5R6A5U6|015Y6F6H576K3E6N377t7o0h0-0v7y5W2,0n0-0@0o6S6L1U5c5{6b5^5 50520d5456647E7M5`7K3E600w520f0P6`7P6C667!7X7Q2,5j0B5l7,737Y6}0-0j0j0G7D7=3h7S53557#4r7N885a600H2f2k7`5w837}5d8b7R617^637-7L8k7 0j6R640y4B1e4k0y4w2z4o132C8G0u1P0D2y4m5u0R0T0V0C04.

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

.128013witkcvo-)ylbp_P3(ag=/mT4rseSf,d 612:F5nuh050F0B0d0s0c0l0A0G0f0l0s0A0A0u010d0c0n010406050A0O0w0w0s0z0k040C0h0l0O0*0h0N050v0;0?0^0`0/0n04051a131d0v1a0/0F0c0g0Y0!0$0(0!0N0t0O0s0t0B0i0n0k0d0P110G0P0c0t0P0l1F0P0d0-050T0m0l0B1m0#0%011E1G1I1G0d1O1Q1M0d0z1b1A0Y0}0A0n0s0N0(0J011S1o010D0V0B0N0s0w0B1M1.1:1^1U1{1Q1~200-0a0G0p0z0h0n0h0A0c100N0G0R1,0z0z0B0f2l13230N1b0v1A2y1(1*1)1N0F251p0c0N1}2i1M1j1l0Z1T2I2K0N0h2O1M0n2r1b2w2y2#0:1/2m2Q1_2U0z0@0l1M0s1D2r0D0(030o0o0f2V0B1I2T0h0i0I0q330-0I130s2$2)0.2(242+1U2-2/2;2?0B2^012`2|2~302L33351?040J393b1:3d2w2H013i0s2:1b2=0P2@2_2{2}0R3s2U3u0i0q0-0q3z2v3c0/3D3g0(3G3I053K3M3o3O3r2J3t340i0y0-0y3Y143!3e2*1n3h0h2.3H3k3L3m3N3q3Q3;3S3?0M0-0M3{2#3#2)3E3)453-3p3P2 4b323?0H0-0H4h3c1e2Z132O2B0F1*2G3%014q2N1k1b2Y0B2!4z3|3B054q4Q240c0F0(2{2w3T0I3k4Y4!494r314%1@290B4+4q3R4t354(2y3a3~3E0e0-0R0D3Z4T3$400(0b0-0G542x4~4I0N0D0-0s0n1/0z0*1}0d5c4W3 2R010,040r5q5e573F5i0z0m2r5y565t5v0E5q5b5H2,0-0g3H0B0O0z5G4k4I5v0j0K5q0/4S5d3D4*014#2)3T3w3+0G5*3/4a4.3?1?0G4;4?3:5^3v1M0v3a0G645M5W5A50040c535%04663f5A0N0-0B0A0d0o0g4Y0B5V6g5I0-5x6d5z5t6i040^5E6q6w5N1U5Y5!6d5$2%5)4Z5+0o4$3?3V3J5;6N5?4-3=353V5{1 4=6O4@4s3T6S3z656.6f5s1_692r0d5T126d6:4 0f0-0L3H0A6D4i6r2m5=6P5-3?3^6T776)5 3@4:6$5}5@6Y7g4|6e656x6=6j1I6c2#6|5f0-0z0s0f3;753E5v6v6L676y5C6C7D5X0-0j5L7q1U0h0-0u0u7Q6F3(5P5R5T7M5A5v6I746E4k776Q354e7c6V4,4^3T4e6#207j6X4c7:61636/647R0(6?0S6_7X7I6=6~040x0z0O733}7,4X7?7/0i4v7=7}7^4u7h7|6(5~7l8p6-7p7Y01876^0z6`7v855B6A5k0^5n0N5p8k6;6G6u7%7J040t0s0O0f0P8i558b8T5w8V5O6A5D5F8R7E7O5K6{8J6z5Q1Q7$8;7N047P8^8C0h5904428a6s8-5j5l8O8Q7H998*7G4z8C6z0F2f2k8%5(8)0(7F8,3h7K8:9f8S9s8?989z8K8{5S5U8~7(7O5#5y0v4V4A4P4C4M130d4F9T2E2z0s1P9Q0v4D5$0R0T0V0A04.

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

.128013witkcvo-)ylxb0p_P3(ag=/m4rseSf,d 612:5nuh050G0C0d0u0c0l0B0H0f0l0u0B0B0w010d0c0p010406050B0O0y0y0u0A0k040D0h0l0O0*0h0N050x0;0?0^0`0/0p04051a131d0x1a0/0G0c0g0Y0!0$0(0!0N0v0O0u0v0C0i0p0k0d0P110H0P0c0v0P0l1F0P0d0-050T0n0l0C1m0#0%011E1G1I1G0d1O1Q1M0d0A1b1A0Y0}0B0p0u0N0(0K011S1o010E0V0C0N0u0y0C1M1.1:1^1U1{1Q1~200-0a0H0r0A0h0p0h0B0c100N0H0R1,0A0A0C0f2l13230N1b0x1A2y1(1*1)1N0G251p0c0N1}2i1M1j1l0Z1T2I2K0N0h2O1M0p2r1b2w2y2#0:1/2m2Q1_2U0A0@0l1M0u1D2r0E0(030q0q0f2V0C1I2T0h0i0J0z330-0J130u2$2)0.2(242+1U2-2/2;2?0C2^012`2|2~302L33351?040K393b1:3d2w2H013i0u2:1b2=0P2@2_2{2}0R3s2U3u0i0s0-0s3z2v3c0/3D3g0(3G3I053K3M3o3O3r2J3t340i0z0-0z3Y143!3e2*1n3h0h2.3H3k3L3m3N3q3Q3;3S3?0M0-0M3{2#3#2)3E3)453-3p3P2 4b323?0I0-0I4h3c1e2Z132O2B0G1*2G3%014q2N1k1b2Y0C2!4z3|3B054q4Q240c0G0(2{2w3T0J3k4Y4!494r314%1@290C4+4q3R4t354(2y3a3~3E0e0-0R0E3Z4T3$400(0b0-0H542x4~4I0N0E0-0@0m0c0y0=5c4W3 2R010,040t5o5e573F0-0^0n2r5w565r5t0j0L5o0/4S5d3D4*014#2)3T3w3+0H5P3/4a4.3?1?0H4;4?3:5!3v1M0x3a0H5:5b5F1_50040c535M045=4k5f0-0C0B0d0q0g4Y0C5E5 5y5t5v5|5x5r0N5A0A5C686e5?1U5H5J5|5L2%5O4Z5Q0q4$3?3V3J5W6v5Y4-3=353V5%1 4=6w4@4s3T6A3z5;6S5~3f5y5^2r0d0O0A125|6U5q1_0y0c0-0o5K694X6D6x5S3?3^6B5X4,4^3T3^6J205)5Z6G3@5-5/5;6f5@611I5{2#6(4l0-0T0V1Q6:6)6o0-6d6t6a6g6i6k7l3E5H5o7f4I0h0-0w0w7y791U6+377v4I5t6q4i7v6{6y354e6`6=6N5+0i4e706L6E6}4d765}6T5:7G0(6X0S6!6$7e7-5z040A0u0f3;7K6b7o7~7s045B5D6m7r1_7x6r7P6=7R0i4v7U726F4c354v7!8h7%8k7)6S7@7/6Z6#818880866V6g0n5i0u0m8w7n5u8G3(0-7`7|2K8J5s8y7q8A2,7t858S7m0(5H0F7F6n8K045j5l5n8z8Y8Q8I8-7g040v0u0O0f0P6l8X7w8R4z8%7^848|90878H0j0j8#6%7@0N8C8)8E8P6c8P6h7_7{7}8;7L8 55968(939h0-998$9s7^8*5m0y9v8:8}60040G2f2k949r8T8H7p959O9t6j8W9R8.5H98986/6e0x4V4A4P4C4M130d4F9-2E2z0u1P9*0x4D5L0R7i0W04.

Crédits⚓︎

Frédéric Junier, Romain Janvier