Algorithmes - Les indispensables
Les indispensables
Les indispensables sont ... indispensables 😂
I. Recherche dichotomique⚓︎
Mon info
La recherche dichotomique permet de rechercher un entier dans une liste triée, ainsi que sa position.
Quel est le principe de la dichotomie ? réfléchir avant de cliquer 😊
Le principe de la recherche dichotomique d'un entier v dans une liste triée de n éléments est le suivant :
- Si
vest égal à l'élément se trouvant au milieu de la liste liste[milieu] , l'entiervest trouvé, et on renvoie sa position. - Sinon si
v<liste[milieu], on recommence la recherche dans la première moitié de la liste :liste[0 -> milieu-1] - Sinon on recommence la recherche dans la seconde moitié de la liste :
liste[milieu + 1 -> fin]
Exercice 1 : Appartenance par dichotomie
Compléter la fonction dichotomie qui prend en paramètre une liste Python nombres et un valeur cible. Cette fonction renvoie True si cible est dans nombres et False sinon.
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
.128013 f6S=d-èNpg2mR{ 8P5)kLu^}A_sÀ0Fhq:4yr./oTxDb1cw973veê[,lO+tài]né;zIa(ù 050f0Z0*0?0,0%0B0p0T0%0?0B0B0e010*0,0j010406050B0w0m0m0?0K0J040d0N0%0w190N0.0p020?0m0j0:0p0n0Z1j0K0G0w0Z0B050M1g1i1k1m1e0j04051R1K1U0M1R1e0f0,0Y111315170F0,0k0F0%1,0F0*1c050|0R0%0Z1%1416011+1-1/1-0*1^1`1?0*0K1S0*0F111p0B0j0?0.170l011|1)010b0~0Z0.1x0Z1?2f2h2m1~2p1`2s0m2u040a0p0r0K0N0j0N0B0,1s1u0`2d0K0K0Z0T2P1K2w0.1S0M2b2#282a291@0f2y171/0.2r2M1?1!1$121}2/0,2;0.0N2^1?0j2U1S2Z2#361f2g1u2`2n2 0K1j0%1c0p0S2Y3a1d392x3c1~3e3g3i0l3l2h3n2Z2.013s0?3h040p0X3w2!1e3z3q173C3E0p0I3I3y3a3A3O3i0s3S3K3U3M3B0N3f3D3i0c3Z3o3b1(3r3(3t3F0W3-3L3:3N3=3*3F0q3_3#3{3%3)3P0V413p433W040S0D483/2{443?0S3k1L3m3!494h4b0S3v4m3x1V341K2^2(0f2a2-3$0T302E0_1#1S330Z353m3S054F0`4N4p2n0u1c0`0b4P3`4h0U3i4!424q0b4X0,0T0F0N0*0N0m0,0Z4)4U1~1b040@4`4g3d1c2 0m0R2U1J4u2!3.3A4}0$3S0p5b3$0.1c0T0,1_4_594T514|1c0t0H3Z0p5x5g4#52040`0R1r5f5h430N1c0e5G5A1~4@1c4e5p065y5z4*5B2p0.5M5W1~5J045L5p5V4{3N0R1c2B505c1c4 5p5H4q534?561I5;3$4}0t5!5,015%0g635r175P4c5w5y5_4V1c0U1+1`683V4X0Z5E0*6l3$5%020%0*0:5)365+693B1c5Y5 434}5v5S5U5U6f3r1c4@1/0Z0w6r5I5K6T4h4}5@385N3N6D2}6W2n5%0)6)6N5C6o5F5^6#01616F4h5%0M0M6_2n6b4t365T6K5x6M174W040,4Z5*766C045l5n6-175%0e6y3m6A6m04545}586!5#174}0#6~6.6P4^6S6=7v6@1c0-6I7274747d782U0*0w0K5Z7c6?0u0T1c0O0K1H6d7M7V1c0Z1/7b6z7d5j7f5m6k7U7F6t0k6w7i7e7r577z7w1c7y7E647/7B6R7 7G047I7$7L756?7/5D6;7-6?7k7{850~7C7{6+7{6b4l7K7L7N7)0 5o7u646H8c8d7.6%7T8j7@6V7?846O8o878M6B668s0,1c8u4n6L7(047P7R8I7n7N7X040E3D0B8A8)6?0T0S1c030p2N0p1t0p0.02030X0V0:0?0p2g10280N0w0Y0/3-0M4R4M4w9h0M4z1K0*4B9m2+2$0?5n2#4z1Q5q3A2U0m0A0b0?0u0Z0A0F0X1c1C1E1G1I0p7J4O1X3n2^3A0?0f0m1t2O0,8}2}0b5%1Q9U9W9Y2P0g190*26041C4/0Z0K9@961k0p1!4/4;4?4^1V3n1R0=0%8`000?0k2O9}000w1u3D0k3(2O0F2D2y0,9M0L0p0v1{250Z0?0w960K0,102r9{0K1x0h281{0f0Nac1f990.0k040N1_1,0?4=0,9z2r0*0p0!aH0p280,9d1LaNaP0La39w0C110F0?9M0p2O0/aE2P0$8|1u8/9}1D2h2R8{130p0Y3D6R0K11aYaE1`0p1IaZ0/0kba0p0+0pb74Q4G7:7h9fbs9Oa/050w0%3n1/048{9a0,a~8}2U0.0YaK1{0,1i0/1!aU1DaY5g9g047Z7#bv4S1KbD1ebD8{2 0.a~0T0{0*1{7gbgbi8`aKaZ5vbAbC0,bE0w0ja{7C2Ubnbp95b91`7Rbd0.28bm0Ha_a79C1ra=9^9@bc0f2h10b72g0K19aI2J2OaIaxauaw0p4 bX8haZ0e0p86ax0)3j1KbX620Mb(05bD9$c3bb1{bob7c9bbcccebgcg0~0pcjaZcncn9}cqc7aDcv0pbl0w9`0fcA9s1`cCcEbs5Y0pcIcK0p0gcNb#4McQcS0Mb}1ecRb dhdg1T040v950;1taI1{2Uc/0F1{0@0%000/0T1kaZbe1{br4S6Edb3F0{bWbscGcObs0t8`dtbR0wacbo4/a@1Ha_0*a{aU9!1ucgbF1u5Yacct0p0?bMaWdNdI2}1v6v1AdPdKb.00b^a^bqbXb?5obX8~e20BaZ97c;0.cratc av0waq0(b03(aZ2Rb70R9a121{dMbKd@dGbX8-8zdQ4Sa.9Rdh9v4I2_439V9X0.9Z9#0.9%1c9)3$eN9,d*9.2O9;0i5|c51j0PbP3Db2a%9a0K102Retc{1`581Ydm2I2=eg0paf0pdBdDad2}9~bOeP19e-dH4Md4d9d e9bke-bo7d1kak1jb;0P1c090@4d0x0V09cQ36a~0@b/0p1G0,bhecfD0wb4cJ0!am280h100kaE0.0f0teGe{1R0Qc=bg0jaWds10dC0BbI0^c?e7eab^ee330/8/cd0ZbI1u0K0/3DaAat9aeh98e:e=1{e@ev102L157;1IfW3ndlbD0zax4L4@9^e/7Rf{d=f01uf3cubhbLaW8}2Rflaz2bfo0Zfq04fs090baE0T0ofu0V0y0o0l0yfx3Se1b^bo1!c5gA6?fmgDbTgGfs0s0p09192D10fu0qgU5^dib~04gjb20we+0hfNe:gq95f1gudEgx2J2QdGg$gCalg)fr0@gJgL0og,g.bP9Ng=gQgSg@6z0TebaZgYf%7oeWhdgEg*0@0lhlg/ho0D0x0Whs9QcSgi2}8{b5dWb;0p0LhWb%djcTb g|aHcd0,h0g1gpa grh5dCgv0fe2h88}gBfnhfgHhhgK0?gMgOhq0x0o0X0D0ygTfy7nhugX9}hyh=2r0Ygy1u0SeGdedl1R0zhQbHef10af1{1/ecdsa%0}0%bgh_g(fphggOhM3xa~aCcC0j1qaBh@1ui5goe;h-0B0}aZb6dA0%0/2Dcdd_4Me7eE4MfGedf}f^0*gfeI4JeI0{iA0B04.
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
(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
.128013 f6S=d-èNpg2mR{ 8P5)kLu^}A_sÀ0Fhq:4yr./oTxDb1cw973veê[,lO+tài]né;zIa(ù 050f0Z0*0?0,0%0B0p0T0%0?0B0B0e010*0,0j010406050B0w0m0m0?0K0J040d0N0%0w190N0.0p020?0m0j0:0p0n0Z1j0K0G0w0Z0B050M1g1i1k1m1e0j04051R1K1U0M1R1e0f0,0Y111315170F0,0k0F0%1,0F0*1c050|0R0%0Z1%1416011+1-1/1-0*1^1`1?0*0K1S0*0F111p0B0j0?0.170l011|1)010b0~0Z0.1x0Z1?2f2h2m1~2p1`2s0m2u040a0p0r0K0N0j0N0B0,1s1u0`2d0K0K0Z0T2P1K2w0.1S0M2b2#282a291@0f2y171/0.2r2M1?1!1$121}2/0,2;0.0N2^1?0j2U1S2Z2#361f2g1u2`2n2 0K1j0%1c0p0S2Y3a1d392x3c1~3e3g3i0l3l2h3n2Z2.013s0?3h040p0X3w2!1e3z3q173C3E0p0I3I3y3a3A3O3i0s3S3K3U3M3B0N3f3D3i0c3Z3o3b1(3r3(3t3F0W3-3L3:3N3=3*3F0q3_3#3{3%3)3P0V413p433W040S0D483/2{443?0S3k1L3m3!494h4b0S3v4m3x1V341K2^2(0f2a2-3$0T302E0_1#1S330Z353m3S054F0`4N4p2n0u1c0`0b4P3`4h0U3i4!424q0b4X0,0T0F0N0*0N0m0,0Z4)4U1~1b040@4`4g3d1c2 0m0R2U1J4u2!3.3A4}0$3S0p5b3$0.1c0T0,1_4_594T514|1c0t0H3Z0p5x5g4#52040`0R1r5f5h430N1c0e5G5A1~4@1c4e5p065y5z4*5B2p0.5M5W1~5J045L5p5V4{3N0R1c2B505c1c4 5p5H4q534?561I5;3$4}0t5!5,015%0g635r175P4c5w5y5_4V1c0U1+1`683V4X0Z5E0*6l3$5%020%0*0:5)365+693B1c5Y5 434}5v5S5U5U6f3r1c4@1/0Z0w6r5I5K6T4h4}5@385N3N6D2}6W2n5%0)6)6N5C6o5F5^6#01616F4h5%0M0M6_2n6b4t365T6K5x6M174W040,4Z5*766C045l5n6-175%0e6y3m6A6m04545}586!5#174}0#6~6.6P4^6S6=7v6@1c0-6I7274747d782U0*0w0K5Z7c6?0u0T1c0O0K1H6d7M7V1c0Z1/7b6z7d5j7f5m6k7U7F6t0k6w7i7e7r577z7w1c7y7E647/7B6R7 7G047I7$7L756?7/5D6;7-6?7k7{850~7C7{6+7{6b4l7K7L7N7)0 5o7u646H8c8d7.6%7T8j7@6V7?846O8o878M6B668s0,1c8u4n6L7(047P7R8I7n7N7X040E3D0B8A4n1K4R4M4w8@0M4z1K0*4B8|2+2$0?5n2#4z1Q5q3A2U0m0A0b0?0u0Z0A0F0X1c1C1E1G1I0p7J4O1X3n2^3A0?0f0m1t2O0,1t0p2}0b5%1Q9u9w9y2P0g190*26041C4/0Z0K9R0p2g0K0p1!4/4;4?4^1V3n1R0=0%0p0B000?0k2O9Y000w1u3D0k3(2O0F2D2y0,9m0L0p0v1{250Z0?0w9V0K0,102r9V1k1x0h281{0f0N9=1f281t0k040N1_1,0?4=0,992r0*0p0!ak0p280,0/2Yaq0.as0L9(960C110F0?9m9C0*0/0Kax9A0.0$0p9B8/9Y1D2h2R2N0p130p0Y3D6R9X0TaBaZ1`0p1IaC0/0ka@0p0+a:0?5g8?7:7h0Mb99oaP050w0%3n1/04a/0N0w0,a%9B2U0.0Yan1{0,1i0/1!ax1DaBb84G047Z7#bcbF1Kbk1ebka/2 a$110{0*1{7ga}a 9-anaC5vbhbj0,bl0w0jaY7C2Ub4b6a=a@7RbS0.28b30H9C9,9c1raS9S9R9X0f2h10a;9W19al2J2Oalaaa7a90p4 b98haC0e0p86aa0)3j8=bF620MbM05bk9Db-a^1{b5a;a?1`b@a`b_a|1{b|0~0pb aCc3c39Yc6b;c94^0pb20w9U0fcf921`chcjbF5Y0pcncp0p0gcsbJ4Scvcx0Mb%1ecwb)c~c}1T040vb70;1tal1{2UcS0F1{0@0%000/0T1kaCa{1{4Qc-6(c^4Ma~aCdo4Sclctc_9-dabzboaCb54/aU1HaWaYa!9Bb|bm1u5Y9=9W0p0?buazbE4Sc.6u6wa+6pdy4Ma%0T00bYaVa;dv4MbW5obd0.d,0BaC2g10c50.c7a6c)a80wa30(1u0B3(aC2Ra;0Rbn121{0{0pbsdVdnb98-8zd(04aO9rc~954I2_439v9x0.9z9B9D9F1T9HezeB0.9L2O9O0i5|b/1j0Pbx3Da+aGbn0Kd}1{edc#1`581Yd32I2=d 0p9^0pdidk9?2}9ZbweA19eTd:04c.c?dxdr3Fb1eTb57d1k9}1jbU0P1c090@4d0x0V09cv36a%0@a`0p1G0,a~d`aG0K0h100kaZ0.0f0tere(1R0QcVa}0jazd910dj0Bbq0^b;d=0pd^bYd|ab0/8/b_0Zbq1u0K0/3Dada6bne0104=7ReY0pe!ef102L157;1IfC3nd2bk0zaa4L4@9SeV7Rf#dTe-1ue:0Kdlbtaz9B2Rf6ac2bf90Zfb04fd090baZ0T0off0V0y0o0l0yfi3Sd*d_dE9YfJeUgjf8bBgofd0s0p09192D10ff0qgC5^c b(04g1a+0weR0h9 f/0Kg8b7e.gcge0Ygg2Qdn6?f7glgMfc0@grgt0ogPgRbx9ngVgygAgX6zd+bYb51!b/gKg|fag~0lh3gSh60D0x0Wha9qcxg02}a/a.dD1{0LhBbLd0cyb)g$akb_0,g*f+g7a(9_gae/djgd9?2rg?2J1uhh9~g}gpg gs0?gugwh80x0o0X0D0ygBfj7nhcfshegI0fd,gfhX3jerc{d21R0zhwbpcUe,9^1{1/d`d9aG0}0%a}hZgmgNfehpfhh?3xa%afch0j1qaeh~9Bh/g6eXhO9-0}aCa/dg0/0%0/2Db_dXd;f{epfrd{f%fY0*f}et4Jet0{ig0B04.
Exercice 2 : Appartenance et indice par dichotomie
Compléter la fonction indice qui prend en paramètre une liste Python tableau et une valeur cible. Cette fonction renvoie l'indice de cible dans tableau si cible est dans tableau et None sinon.
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
(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
.128013 f6S=d-èNpg2mRC 8P5)kLus_hq0:4yrE./oTxDbc1w937ve[l,O*+tài]né;Ia(î 050f0V0$0.0(0X0x0p0O0X0.0x0x0e010$0(0j010406050x0w0m0m0.0F0E040d0J0X0w140J0*0p020.0m0j0,0p0n0V1e0F0A0w0V0x050I1b1d1f1h190j04051M1F1P0I1M190f0(0U0|0~10120z0(0k0z0X1%0z0$17050@0N0X0V1Y0 11011$1(1*1(0$1:1=1.0$0F1N0$0z0|1k0x0j0.0*120l011@1!010b0_0V0*1s0V1.2a2c2h1_2k1=2n0m2p040a0p0r0F0J0j0J0x0(1n1p0=280F0F0V0O2K1F2r0*1N0I262W2325241/0f2t121*0*2m2H1.1V1X0}1^2*0(2,0*0J2:1.0j2P1N2U2W311a2b1p2=2i2`0F1e0X170p0P2T3518342s371_393b3d0l3g2c3i2U2)013n0.3c040p0S3r2V193u3l123x3z0p0D3D3t353v3J3d0s3N3F3P3H3w0J3a3y3d0c3U3j361Z3m3Z3o3A0T3(3G3+3I3-3#3A0q3;3W3?3Y3!3K0R3|3k3~3R040P0B433*2?3 3.0P3f1G3h3V444c460P3q4h3s1Q2 1F2:2Z0f252(3X0O2{2z0;1W1N2~0V303h3N054A0=4I4k2i0u170=0b4K3=4c0Q3d4V3}4l0b172^1V0O0V4!4P1_16040/4-4b3817200V0.0w4?3v4:0Y3N0p3)3Q170O0(1;4,4p2V543X4:0t0C3U0p5j534W4^040=0N1m525d3~0J170e5s5m1_0m0(17495b185k5l4#5n2k0*5y5J1_5v045x5F5I4.3I0N172w4~5e174=5F5t4l4_0.594|5!3~5f5N5V015Q0g5=4@5A5C475i5k5)4Q170Q1$1=5`555o0V5q0$673X5Q020X0$0,5S315U5{3I175L5/4c4:5h5F065H5H613m175B1*0V4}5T6z125Q6k3h6m4 5$6r5n5p5r6G5z6I170#6d456p2^6P4/170t6Y4c5Q0I0I6*2i5B174o316w6x5j6H014R040(4U6T5O6o0457596/5P176g6i77734`5.5(6U014:0W6$736C0(6E7l7i170)6u6@6_6_6{0*6!5M715?6J7c3w6B0_7o6F6l6{5^7F6;5~6v7w6M3X6}0V1*707L7h7z7458667C6n5@5w6K3s7T6Z047e7K4J7h7j7q7#7n7p7g727r047t5 7S6`7h6}2P0$0w0F7B7Z7 7{7I7}7v7w6{7V0`5a337^177u4i84607!4S6a6S8d7D5w7F8f6D7?7.7M6W7O5}4g8i857 870?8a8c6L8k0O170i1o8n4i1F4M4H4r8%0I4u1F0$4w8,2$2X5,1=2W4u1L4O7*2P0m0y0b0.0u0V0y0z0S171x1z1B1D0p8r4q1S3i2:3v0.0f0m1o2J0(1o0p2^0b5Q1L9h9j9l2K0g140$21041x0O0z0V0F9E1?4*0z0J0$0J5B999p0$0+0F0.140U1?0C0p0%280*2n0:235a1T1O040-0X0p0x000.0k2J0p2M0X9?0X0k3Z2J0z2y9`1?2P9I9H9F9`0(9E9M9O0(9Q3laf1C0H1Q3i8*4E1U1W9u9k0*9m9o9q9s1Oar9w9n0*9y2J9B0v0.0pa69Fa89J1?9|4)ab9J0w0p7|6F9,1M0v1?0O3y0O0w9:9{00aP4+9`aSaUaT9T2J1?9N1m0V9r0(0{990X990{4A1d2m0@0(2P0x0H0p0-570p9o2~2F2H1?4L4B3v1{1)1+1-8`68aU7F7E7)6N4;7`8w6bbs8Ibu3X7#6q7~5?5;bC5u176-8J6=4K0I8$04ak9e8_0Z0F0Y9`2cb09Gb40*0{0~0*0k9@9a2Mbe0k9U1I2K28b20p1=0p0obY0~0pb40Xb{0=0{b37o0Fc50x0$b`0(5B9S0Vb80oaZa#a%538$bk1+1}1,2q8e7H8EbA5R7F4:5%8oct69bzbJ6+bB8z7*bE6#bG7*bIcI3v6,6.cF6:5}6?4JbQ4B3A0j6Ecb2b0Fa`c50L0O0+0=0F0|0?0$a?0^c2aNcda=b80G1pa_0b0?bY2Ib`b.6E0L9p0*4*9abi2M3Xblcqbo7yby8ycXbR0p0?cmbjdfcpbncs5?cK8S9ddn0x1ocbb;2c0f0xb~6Ec:dBb_ddaZ3~dgdubpbDdk6ccT78046XdW73bF33cY4N0pc#1m9`0+2b109Gb`aH0U3ydJcccecgal8_0Mb!c;0|0 bc36ckb{aOdaaQa-aT8gaS2m0p1m7I0x2ccbb 0~0F0kd_a)2^c?0Fd@c_9bdqdedPdt1~dvcJcu7Jcw7-2V7/5*cDdl8G7h5QdZcP5#bwcM68d$8TeP175_d!7GeMdVcBbH6(cwbMe$7PcWdzcZbTaW04d b(d5e20{2~0+0xb3dId*2E1;0ha32,9;1?2Gf1d*e3a!bXdo1p0r0E261odIc50*149G0{0*00dCfe0{2Mc1e7c{c?b80K0Ja^c*bY0d0(b`fv1p0.d@9_1eat0ja%0+a4ft9O0Nb60p0b0X9M0@fqb)fbf50Xf71?f19U9_0.0jc(aSb1a3c(do0L1y0jb{6u9,9g3X9iasauc 0L1sg22z9tg79vat9x9z9B0Gg01t7(g5aqds1|dR6{2v2m2o172B0o1odBb{fkfmdy5c4G8`324JbR6{0k4:020k6igSgUgT1vbxe(eH7O4%040l0H5EeSbK040!0!bN470B0l3C6vgPgRgXgV0,g}53eVdT04eX7.8N8Acxe/g%g)g+eY7 5Qg/g;48g@cweRhd5?7P8L8!7hgQ79g|hu6ih0e*eEg!e$eQ8C7A52eK2i0O0P1703d-d/f12yfqa4e22b579S4a3v9 4(0*7Yhq7 hs04g}h*gXhx7@7 czgZ6Re)hm7*hCe$dx7qcOh@cQbLg;e;eJhG1_hIhKhM1^1yb3hRa!hT2JfWf(c8hRb dL2yhW3XhY6~h!in3~h(h+gWhwh;8xh?eOhecHh~eTcAh.dwhEhBe!hDhAhybv6)iK04cSg,4ce:is4cip0q0H0R0q0q0D0c0s0c0T0D0S4f0s0q0V0#0S0B3:g_d(8)gK4taoi 0Uam8^4t0?c^0x04.
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
(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
.128013 f6S=d-èNpg2mRC 8P5)kLus_hq0:4yrE./oTxDbc1w937ve[l,O*+tài]né;Ia(î 050f0V0$0.0(0X0x0p0O0X0.0x0x0e010$0(0j010406050x0w0m0m0.0F0E040d0J0X0w140J0*0p020.0m0j0,0p0n0V1e0F0A0w0V0x050I1b1d1f1h190j04051M1F1P0I1M190f0(0U0|0~10120z0(0k0z0X1%0z0$17050@0N0X0V1Y0 11011$1(1*1(0$1:1=1.0$0F1N0$0z0|1k0x0j0.0*120l011@1!010b0_0V0*1s0V1.2a2c2h1_2k1=2n0m2p040a0p0r0F0J0j0J0x0(1n1p0=280F0F0V0O2K1F2r0*1N0I262W2325241/0f2t121*0*2m2H1.1V1X0}1^2*0(2,0*0J2:1.0j2P1N2U2W311a2b1p2=2i2`0F1e0X170p0P2T3518342s371_393b3d0l3g2c3i2U2)013n0.3c040p0S3r2V193u3l123x3z0p0D3D3t353v3J3d0s3N3F3P3H3w0J3a3y3d0c3U3j361Z3m3Z3o3A0T3(3G3+3I3-3#3A0q3;3W3?3Y3!3K0R3|3k3~3R040P0B433*2?3 3.0P3f1G3h3V444c460P3q4h3s1Q2 1F2:2Z0f252(3X0O2{2z0;1W1N2~0V303h3N054A0=4I4k2i0u170=0b4K3=4c0Q3d4V3}4l0b172^1V0O0V4!4P1_16040/4-4b3817200V0.0w4?3v4:0Y3N0p3)3Q170O0(1;4,4p2V543X4:0t0C3U0p5j534W4^040=0N1m525d3~0J170e5s5m1_0m0(17495b185k5l4#5n2k0*5y5J1_5v045x5F5I4.3I0N172w4~5e174=5F5t4l4_0.594|5!3~5f5N5V015Q0g5=4@5A5C475i5k5)4Q170Q1$1=5`555o0V5q0$673X5Q020X0$0,5S315U5{3I175L5/4c4:5h5F065H5H613m175B1*0V4}5T6z125Q6k3h6m4 5$6r5n5p5r6G5z6I170#6d456p2^6P4/170t6Y4c5Q0I0I6*2i5B174o316w6x5j6H014R040(4U6T5O6o0457596/5P176g6i77734`5.5(6U014:0W6$736C0(6E7l7i170)6u6@6_6_6{0*6!5M715?6J7c3w6B0_7o6F6l6{5^7F6;5~6v7w6M3X6}0V1*707L7h7z7458667C6n5@5w6K3s7T6Z047e7K4J7h7j7q7#7n7p7g727r047t5 7S6`7h6}2P0$0w0F7B7Z7 7{7I7}7v7w6{7V0`5a337^177u4i84607!4S6a6S8d7D5w7F8f6D7?7.7M6W7O5}4g8i857 870?8a8c6L8k0O170i1o8n8T7h0O0P17030p0d0(0p1o0p0*02030S0R0,0.0p0F7o1p230J0w0U0+3(0I4M4H4r960I4u1F0$4w9b2$2X5,1=2W4u1L4O7*2P0m0y0b0.0u0V0y0z0S171x1z1B1D0p8r4q1S3i2:3v0.0f0m1o2J0(8.2^0b5Q1L9J9L9N2K0g140$21041x0O0z0V0F9)1?4*0z0J0$0J5B9B0p2J0+0F0.140U1?0C0p0%280*2n0:235a1T1O040-0X0p0x000.0k2J0p2M0Xah0X0k3Z2J0z2yal1?2P9-9,9*al0(9)9;9?0(9^3laG1C0H1Q3i994E1U1W9V9M0*9O9Q0*9S179U3X9KaTaV0*9Z2J9$0v8_ax9*az9.1?an4)aC9.0w0p7|6Faa1M0v1?0O3y0O0waeam00a^4+ala{a}a|9{2J1?9=1m0V9S0(0{9B0X9B0{4A1d2m0@0(2P0x0H0p0-578-1p2~2F2H1?4L4B3v1{1)1+1-9m68a}7F7E7)6N4;7`8w6bbU8IbW3X7#6q7~5?5;b(5u176-8J6=4K944B04aL9G9l0Z0F0Yal2cbs9+bw0*0{0~0*0kai9C2MbG0k9|1I2K28bu0p1=0p0oc10~0pbw0Xcn0=0{bv7o0Fcx0x0$cm0(5B0$0+0VbA0ob2b4b65395bM1+1}1,2q8e7H8Eb$5R7F4:5%8ocW69b#b/6+b%8z7*b*6#b,7*b.c/3v6,6.c,6:5}6?4Jb_4N0p0j6EcD2b0Fbmcx0L0O0+0=0F0|0?0$bi0^cua?cFbhbA0G1pbl0b0?c12Icmcd6E0L9_0*4*9CbK2M3XbNcTbQ7yb!8yd1953A0?cPbLdIcSbPcV5?c;8S9FdQaf1ocDcg2c0f0xcq6Edg0x9?audGb23~dJdXbRb)dN6cc}78046Xe173b+33d24Hd4d6al0+2b109+cm8_0U3yd:cEcGcJaM9l0Mc3dh0|0 bEev0Xb5cna@dDa_bca|8ga{2m0p1m7I0x2ccDcr0~0F0kemb82^dj0Fekdm9DdTdHd`dW1~dYc:cX7JcZ7-2V7/5*c*dO8G7h5Qe4c_5#bYc?68e78!7 7Ne57Ge@e0c(b-6(cZb=f67Pd0d$b`b|a 04esc7dyev0{2~0+0xbvd/d42E1;0hau2,af1?2Gfud4ewb3c00peJ0r0E261od/cx0*149+0{0*00d)fH0{2McteBdodjbA0K8 djdac18+cmfY1p0.ekak1eaU0jb60+avfW9?0Nby0p0b0X9;0@fTc8fEfy0XfA1?fu9|ak0.0jd8a{6uaa9Ia#9WaUcj0V0L1s0j9$a!3~a$9X9Pa)9!9$0G0L1ygya99HaRdV1|d|6{2v2m2o172B0o1od=cnfNfPd#5c4G9m324JdQ6{0k4:020k6ig=g@g?1vbZf8e/7O4%040l0H5Ee}b:040!0!b?470B0l3C6vg/g;g`g^0,hj53f0d~04f27.8N8Ac!ffh0h2h4f3hth8ha48hdcZe|hz7*7P8L4ihg79hihO6ihmfae,g}f6e{8C7A52e=2i8$8(edeffu2yfTavev2b57cH4a3vaq4(aXh=3Xg:hNg_h~g{hn5:6Oi1e?6Rf9hHc`c.i8hohq5c8p046)hVb;hafhe;h!1_h$048)0fee1^1ybvh-b3h/9`cm3Zf#a?8_d=buh`3~h@6~h_hf7hh|04hjiRg`hR7@c)i6hFc#i3hSf1c=h5c-045_f67#iXi42ic^ibh6c|i(c~b@iN7 iK0q0H0R0q0q0D0c0s0c0T0D0S4f0s0q0V0#0S0B3:hfe92Wg*4taPjm0UaN9k4t0?dl0x04.
Quelle est la complexité d'un algorithme de dichotomie ? réfléchir avant de cliquer 😊
💚 A retenir : L’algorithme de dichotomie a une complexité logarithmique de l'ordre de \(\log(n)\) pour une liste de taille \(n\).
II. Le tri par sélection⚓︎
Quel est le principe du tri par sélection ? réfléchir avant de cliquer 😊
Pour un tableau tab de taille n
📋 Texte
pour i allant de 0 à n-2
pos ← position du minimum dans tab à partir du rang
si pos ≠ i :
échanger tab[i] et tab[pos]
La fonction tri_selection
Compléter la fonction tri_selection prenant en argument un tableau et le triant en place à l'aide du tri par sélection.
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
(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
.128013 f:6Sd=4-yr/opg2mcb1w37vej[ l,+P5)ti]kn;ua(_sh 050f0y0I0P0J0C0S0B0r0C0P0S0S0g010I0J0n010406050S0O0q0q0P0k0j040e0m0C0O0.0m0M050l0^0`0|0~0?0n04051e171h0l1e0?0f0J0x0$0(0*0,0T0J0o0T0C1v0T0I0;050X0s0C0y1q0)0+011u1w1y1w0I1E1G1C0I0k1f0I0T0$110S0n0P0M0,0p011I1s010b0Z0y0M0P0q0y1C1#1%1,1K1/1G1=1@0;0a0B0F0k0m0n0m0S0J140M0B0V1Z0k0k0y0r2c171`0M1f0l1X2p1U1W1V1D0f1|0,1y0M1;291C1n1p0%1J2z0J2B0M0m2F1C0n2i1f2n2p2T0@1$2d2H1-2M0k0{0C0;0t2m2X0=2W1{2Z1K2#2%0;0p2+1%2-2n2y012=0P2(040v2_2o0?2|2:0,2 310h342{2X2}3a0;0G3d363f382~0m2$300;0d3k2.2Y1r2;3p2?040w3d1i2R172F2s0f1W2x3n0r2N1^1f3H1g3F2V182,053N0V2S3m3x0,0L0;0V0b3D373$010u0;0B3,3#2I2~0b0;1U0J0R0S0y1G2k0J153?2/3.0:040Q453w3^0M3{0P1F0y0P0O4b2}480H0c3k0B4r3=3-3^3(040b3p3d4t3@2!0;0J4A3v2}0m3:042K4G4u2!0s0;0k1%0o0y4l3n484a3V2`4H3n0M4Q041 4W470;4Z2V4O2;4f4h4j4,3^4n4N4C1K0m0;0i4|463^0q0J2)4_1-4n4p4!354s5e4B534D4L0R550M4F5c045g4c1-4 040g525r4=4L4q5f4r4$3.4w4y0k5w3g0;0z5I3n4J4E165o5q3g4)4S0M4U581K4Y5Y394E5M3.5t0E5(5456042*5o5D4`0;0D5,4P0;4+5;4;0,5!5}4}5$041R4i4k615h5Z0;0H4o5A5B5e5=1-4w0J3+5R6h5y654^685x5 0;0A5#2~5K6w480K5_4~0;020C0I0N6C636p674:6201486v6r5J5j5l5n6N696t040K5b2T066f6)5S4%4E5k2K6W2,6+5)0;5v6m5~6x045L5o6(6f6n6K4g1G6q6X6s6P6u6w4e5z6S4X0;0K5^6_6O7b6L6z797d3.7b3}6V7m6!6J015t6^2T6=4d4?746M3W6`6Q7a6-7s7o5?6!7h7z716{7l7L597n766T6:4#7G7f3u0l3Y0y2p2Q7)3G1o3I2s2v2q737,0l3H0?7^0W0Y0!04.
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
(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
.128013 f:6Sd=4-yr/opg2mcb1w37vej[ l,+P5)ti]kné;ua(_sh 050f0y0I0Q0J0C0T0B0r0C0Q0T0T0g010I0J0n010406050T0P0q0q0Q0k0j040e0m0C0P0/0m0M050l0_0{0}0 0@0n04051f181i0l1f0@0f0J0x0%0)0+0-0U0J0o0U0C1w0U0I0=050Y0s0C0y1r0*0,011v1x1z1x0I1F1H1D0I0k1g0I0U0%120T0n0Q0M0-0p011J1t010b0!0y0M0Q0q0y1D1$1(1-1L1:1H1?1^0=0a0B0F0k0m0n0m0T0J150M0B0W1!0k0k0y0r2d181{0M1g0l1Y2q1V1X1W1E0f1}0-1z0M1=2a1D1o1q0(1K2A0J2C0M0m2G1D0n2j1g2o2q2U0^1%2e2I1.2N0k0|0C0=0t2n2Y0?2X1|2!1L2$2(0=0p2,1(2.2o2z012?0Q2)040v2`2p0@2}2;0-30320h352|2Y2~3b0=0G3e373g392 0m2%310=0d3l2/2Z1s2=3q2@040w3e1j2S182G2t0f1X2y3o0r2O1_1g3I1h3G2W192-053O0W2T3n3y0-0L0=0W0b3E383%010u0=0B3-3$2J2 0b0=1V0J0S0T0y1H2l0J163@2:3/0;040R463x3_0M3|0Q1G0y0Q0P4c2~490H0c3l0B4s3?3.3_3)040b3q3e4u3^2#0=0J4B3w2~0m3;042L4H4v2#0s0=0k1(0o0y4m3o494b3W2{4I3o0M4R04204X480=4!2W4P2=4g4i4k4-3_4o4O4D1L0m0=0i4}473_0q0J2*4`1.4o4q4#364t5f4C544E4M0S560M4G5d045h4d1.50040g535s4?4M4r5g4s4%3/4x4z0k5x3h0=0z5J3o4K4F175p5r3h4*4T0M4V591L4Z5Z3a4F5N3/5u0E5)5557042+5p5E4{0=0D5-4Q0=4,5=4=0-5#5~4~5%041S4j4l625i5!0=0H4p5B5C5f5?1.4x0J3,5S6i5z664_695y600=0A5$2 5L6x490K5`4 0=020C0I0O6D646q684;6301496w6s5K5k5m5o6O6a6u040K5c2U066g6*5T4(4F5l2L6X2-6,5*0=5w6n5 6y045M5p6)6g6o6L4h1H6r6Y6t6Q6v6x4f5A6T4Y0=0K5_6`6P7c6M6A7a7e3/7c3~6W7n6#6K015u6_2U6?4e4@756N3X6{6R7b6.7t7p5@6#7i7A726|7m7M5a7o776U6;4$7H7g4B7B1.0r0t0=030B0N0r0U4U4W6 183Z0y2q2R7`3H1p3J2t2w2r747}0l3I0@860X0Z0#04.
Utiliser La fonction tri_selection
Exécuter le script suivant :
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
(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
La liste de départ a été modifiée ...
C'est ce qu'on appelle un effet de bord.
La fonction a modifié "en place" la liste.
Résumé
- Le plus souvent, on écrit une procédure (pas de
return) pour le tri par selection. - C'est un tri "en place" qui modifie la liste elle-même.
- 👉 Vous devez mémoriser cette procédure.
Quel est la complexité d'un algorithme de tri par selection ? réfléchir avant de cliquer 😊
💚 A retenir : L’algorithme du tri par selection a une complexité quadratique de l'ordre de \(n^2\) pour une liste de taille \(n\).
III. Le tri par insertion⚓︎
Quel est le principe du tri par insertion ? réfléchir avant de cliquer 😊
Pour un tableau tab de taille n
🐍 Script Python
pour i allant de 1 à n-1
clef ← tab[i]
insérer la clef au bon endroit dans tab
La fonction tri_insertion
Compléter la fonction tri_insertion prenant en argument un tableau et le triant en place à l'aide du tri par insertion.
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
(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
.128013 f:6S0d=4-yr/èopg2mcb1w37vej[ l,8OP5)ti]kn;ua(_sh 050g0A0L0S0M0E0V0D0t0E0S0V0V0h010L0M0p010406050V0R0s0s0S0l0k040e0o0E0R0;0o0P050m0{0}0 110_0p04051h1a1k0m1h0_0g0M0z0)0+0-0/0W0M0q0W0E1y0W0L0@050!0u0E0A1t0,0.011x1z1B1z0L1H1J1F0L0l1i0L0W0)140V0p0S0P0/0r011L1v010b0$0A0P0S0s0A1F1(1*1/1N1=1J1^1`0@0a0D0I0l0o0p0o0V0M170P0D0Y1$0l0l0A0t2f1a1}0P1i0m1!2s1X1Z1Y1G0g1 0/1B0P1@2c1F1q1s0*1M2C0M2E0P0o2I1F0p2l1i2q2s2W0`1)2g2K1:2P0l0~0E0@0v2p2!0^2Z1~2$1N2(2*0@0r2.1*2:2q2B012^0S2+040x2|2r0_2 2?0/32340i372~2!303d0@0J3g393i3b310o2)330@0d3n2;2#1u2@3s2_040y3x3a3A3c3C3u040G3g1l2U1a2I2v0g1Z2A3q0t2Q1{1i3S1j3Q2Y1b2/053Y0Y2V3p3I010O0@0Y0b3O3H2L010w0@0D3`3:3|0P0b0@1X0M0U2N0V0A0l2o3*2}3y300?040T412=3;0P460S1I0A0S0R4m3z3|4j0K0c3n0D4D403{1:3?040b3s3g4F422%0@0M4M4h3q0o3~042N4S4G2@0u0@0l1*0q0A4w4i0@4l4f2r4T3;0s0M2,4,3q4j0F4Z4O4#0@224`3;4j4/2Y4!3c4q4s4u534y0@0K4A4C4E5j4=430@0z330A0R0l0U0S490P4b2l0l4~4n3|0o0@0h5A4x4P041U4t4v4:3/5B1:4j0C5d5I4R5N5l5Q0@0N5i5j4D5X2@0@0B5G305D045F5N4N5P5)4X5#5$5(0/4I0w1x1J5,3q4p045+5;5{015.020q0L0Q614?4^040f6e5C4W1*0g6j5I5K5c5W58015R5T5@652W5=5H1N5.0j6o1N4@4_6s4 0/4j5!666t696b6d6O6K315n5p5r5t5v5x4c6w6L0@4B5N065$6-6A3j5a1J6r576U6v6J5?59646%6u5Z6F0/5.5:6z67636q5M6@6{6 045S6`6B6|6y2/6/4U0@6E6T7b6H042-7f4-046N2W6,6.5k6t637i2}7k3;73716V6}7o7g687m7I7q7s7x7z766;5L6~6_7a7M7C7X707L5-5E7I635o1J6Y5u4a4c6$7(3X0v0@030D0H2g4a0n2l3x0m3-0A2s2T853R1r3T2v2y2t4r1J2s3S0_0m0Y0!0$0V04.
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
(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
.128013 f:6S0d=4-yr/opg2mcb1w37vej[ l,8P5)ti]kn;ua(_sh 050g0z0J0Q0K0D0T0C0s0D0Q0T0T0h010J0K0o010406050T0P0r0r0Q0l0k040e0n0D0P0/0n0N050m0_0{0}0 0@0o04051f181i0m1f0@0g0K0y0%0)0+0-0U0K0p0U0D1w0U0J0=050Y0t0D0z1r0*0,011v1x1z1x0J1F1H1D0J0l1g0J0U0%120T0o0Q0N0-0q011J1t010b0!0z0N0Q0r0z1D1$1(1-1L1:1H1?1^0=0a0C0G0l0n0o0n0T0K150N0C0W1!0l0l0z0s2d181{0N1g0m1Y2q1V1X1W1E0g1}0-1z0N1=2a1D1o1q0(1K2A0K2C0N0n2G1D0o2j1g2o2q2U0^1%2e2I1.2N0l0|0D0=0u2n2Y0?2X1|2!1L2$2(0=0q2,1(2.2o2z012?0Q2)040w2`2p0@2}2;0-30320i352|2Y2~3b0=0H3e373g392 0n2%310=0d3l2/2Z1s2=3q2@040x3v383y3a3A3s040F3e1j2S182G2t0g1X2y3o0s2O1_1g3Q1h3O2W192-053W0W2T3n3G010M0=0W0b3M3F2J010v0=0C3^3.3`0N0b0=1V0K0S2L0T0z0l2m3(2{3w2~0;040R3 2:3/0N440Q1G0z0Q0P4k3x3`4h0I0c3l0C4B3~3_1.3;040b3q3e4D402#0=0K4K4f3o0n3|042L4Q4E2=0t0=0l1(0p0z4u4g0=4j4d2p4R3/0r0K2*4*3o4h0E4X4M4Z0=204^3/4h4-2W4Y3a4o4q4s514w0=0I4y4A4C5h4:410=0y310z0P0l0S0Q470N492j0l4|4l3`0n0=0h5y4v4N041S4r4t4.3-5z1.4h0B5b5G4P5L5j5O0=0L5g5h4B5V2=0=0A5E2~5B045D5L4L5N5%4V5Z5!5$0-4G0v1v1H5*3o4n045)5/5_015,020p0J0O5 4;4?040f6c5A4U1(0g6h5G5I5a5U56015P5R5=632U5:5F1L5,0j6m1L4=4@6q4}0-4h5Y646r67696b6M6I2 5l5n5p5r5t5v4a6u6J0=4z5L065!6+6y3h581H6p556S6t6H5;57626#6s5X6D0-5,5.6x65616o5K6=6_6}045Q6^6z6`6w2-6-4S0=6C6R796F042+7d4+046L2U6*6,5i6r617g2{7i3/716 6T6{7m7e667k7G7o7q7v7x746/5J6|6@787K7A7V6~7J5+5C7G615m1H6W5s484a6!6)183+0z2q2R7^3P1p3R2t2w2r4p1H2q3Q0@0m0W0Y0!0T04.
Utiliser La fonction tri_insertion
Exécuter le script suivant :
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
(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
La liste de départ a été modifiée ...
C'est ce qu'on appelle un effet de bord.
La fonction a modifié "en place" la liste.
Résumé
- Le plus souvent, on écrit une procédure (pas de
return) pour le tri par insertion. - C'est un tri "en place" qui modifie la liste elle-même.
- 👉 Vous devez mémoriser cette procédure.
Quel est la complexité d'un algorithme de tri par insertion ? réfléchir avant de cliquer 😊
💚 A retenir : L’algorithme du tri par insertion a une complexité quadratique de l'ordre de \(n^2\) pour une liste de taille \(n\).
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)