Aller au contenu

Diviser/Régner

I. Présentation⚓︎

Vidéo Lumni

Diviser

👉 Découper un problème initial en sous problèmes.

Régner

👉 Résoudre les sous-problèmes (récursivement ou directement s'ils sont assez petits)

Combiner

👉 Trouver une solution au problème initial à partir des solutions des sous-problèmes.

II. Premiers exemples :⚓︎

1. Exemple de recherche d'un élément dans une liste non triée⚓︎

Le problème est de rechercher la présence d’un élément dans une liste non triée.

En adoptant le paradigme "diviser pour régner", l’idée pour résoudre cette question est de rechercher récursivement l’élément dans la première moitié de la liste et dans la seconde, puis de combiner les résultats via l’opérateur logique or.

En effet, l’élément recherché sera dans la liste s’il est dans la première moitié ou dans la seconde. La condition d’arrêt à la récursivité sera l’obtention d’une liste à un seul élément,car il est alors immédiat de conclure si l’élément recherché appartient à une telle liste ou non.

Étapes

Voici donc les trois étapes de la résolution de ce problème via la méthode "diviser pour régner":

• Diviser la liste en deux sous-listes en la “coupant” par la moitié.

• Rechercher la présence de l’élément dans chacune de ces sous-listes. Arrêter la récursion lorsque les listes n’ont plus qu’un seul élément.

• Combiner avec l’opérateur logique or les résultats obtenus.

Algorithme proposé

👉 Voici l'algorithme proposé :

Text Only
fonction recherche(ma_liste, x, d, f):
"""
Précondition : ma_liste est une liste à priori non triée, x est un élément cherché dans la liste 
d est le rang du début de la recherche, et f le rang de la fin de la recherche dans ma_liste
postcondition : la fonction renvoie du booléen : 
`True` si x est dans la liste, et `False` sinon.
"""
Si d = f:
    renvoyer ma_liste[d] == x
m ← (d + f) // 2
renvoyer recherche(ma_liste, x, d, m) ou recherche(ma_liste, x, m + 1, f)
À vous de jouer 1 :

Compléter le script ci-dessous :

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(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
Évaluations restantes : 5/5

.128013w]itkc[v8o-)yl0bqp_.P3(a;+g=/màT4rse97Sf,d 612:Fé5nuh050Q0K0e0y0d0o0J0R0g0o0y0J0J0C010e0d0s010406050J0!0E0E0y0I0n040N0k0o0!0_0k0Z050D101214160~0s04051m1f1p0D1m0~0Q0d0i0.0:0=0@0:0Z0B0!0y0B0K0l0s0n0e0#1d0R0#0d0B0#0o1R0#0e0|050)0q0o0K1y0;0?011Q1S1U1S0e1!1$1Y0e0I1n1M0.190J0s0y0Z0@0U011(1A010O0+0K0Z0y0E0K1Y1}1 241*271$2a2c0|0a0R0v0I0k0s0k0J0d1c0Z0R0%1{0I0I0K0g2x1f2f0Z1n0D1M2K1@1_1^1Z0Q2h1B0d0Z292u1Y1v1x0/1)2U2W0Z0k2!1Y0s2D1n2I2K2;0 1~2y2$252*0I130o1Y0y1P2D0O0@030t0t0g2+0K1U2)0k0l0T3f0|0R0T1f0y2=2^0}2@2g2`1*2|2~30320K340136383a3c2X3f0l22040R0U3l3n1 3p2I2T013u0y2 1n310#333537390%3E2*3G0w3i0w3M2H3o0~3Q3s0@3T3V053X3Z3A3#3D2V3F3g0H3i0H3.1g3:3q2_1z3t0k2}3U3w3Y3y3!3C3%403)3g0Y3i0Y462;3;2^3R3^4g3|3B3$3b4m3e3g0S3i0S4s483=4b3@4d3v3W3x3z4A3 3d3G0M3i0M4J3O4u3r4M3S4O4f4Q4h4S3~4l4V3g0j3i0j4!2J4$4a2%4)4e3_3{4i3}4k4C4;0l0L3i0L4_3P4v3?4~4P3`4R4j4B3(4E3f0p0|0T0p5b4{4w4*505i535k4D3G0T0T5p3k0D3m3/3O1q2/1f2!2N0Q1_2S5e4B2Z1w1n2.0K2:3o5I2J054B5Z2g0d0Q0@372I5B3w5+5-545l5:0R2l0K5?5z565D2K5H4L4}0f0|0%0O5#5)4|250b3i69494w0O0|2D0g0#0K0I6l0K6f63250{040x6r5d4(0Z0|0,0e6x4%4}6u0P690R6g5e6A042*0E0q2D6E6b1*6H6J6L6z666T3R6W473O6K6s3t0|686(5$6+0@6u0m0V690~6/6a0R5=015.2^3G3I5h6~4/55413H235{5}4U78735G6|5e6d3J0R7l6#5e0J0Q0|020r0!0k0e0z7s7u7w7y7v0z6_6#750t5/3g3+4Q7G5~783+5`2b5|6 5@5A7J1Y7g6Y4}7p3i7l2p0I0X390Z1v2x0R0V0R6C0R0K0J0e0R0!2W7;0d7^1%0F0R2.0d4d0d5`1O1@0d0X0K0P876Q2D7?7^7`2y0X0o0X2c0Z7_6p6o0#0X2z1 0-0:7}7 6K6{6`2?3Q7G7I0l437L5,7T7N4n8I7a7R7c4:788J3.6;017#7k7l2S7@7_1$0R0I1 0B2z0!2z0X0q1b2z1%8y6k6m8s8c7?7_0O7;1%8+1D8@7;31272y2A8_2E8{6p8v0Z8x7^7E6{6g8G714o5;8L765^9o7Q2c8S778O4p617h4(8Z7%822u0e7+7-842y7:8y0O1d2F9K8*290i0k0d1%0Q8/0q0k198b9L8B4t7F9q7H9n0l4G8K9w9s9/8Q9v8M7d8O9:8W6y7!7q8!0R0G0I0!1%2v8e6R1%8%9f8x311U7 8d0(0R0W3U0Ja72V1d0u9j8E4v9m1 4W9p9=7V0l4X9u7S9raA4X9A7Z259D7%7B7A7t7CaN7D8C9+5?8H4?9;9`8T8O4?aDaz56aX3M9EaJ1*65040d6.2;6*9 2{6!6{a@6F250k0|0C0C6X8X6Na=5!8X6u6^aT9k8F9,8H58aYaF5658a%aZ9x5mbga+9E7%a-0@a/2D0e0!0I1ea{bt3S6B9ibca^6V0|0h7n6Z040QbL6G0|0cb3bH0@a 04b1bTa}6,6O0k8f6qbbat5*be9.5qaybm9?b/blbi78b/9Aa,b40|0EbZ6UbVb0c06$0|6wbGb!3@a`a?bCbW0Ac46M6-bP6t0|0mcg4(bW0D0Dcn4}0E0d0|3Lb*b7aub-aw3g5Cb:b^8OcEb@7U5 60bq7m8Xbv0(bybAccb}048`6n6pcjbI6vc!ca046Cc%016%cUbUbDb$b(c+c-3oa|c1c:bOc8c`c@6)bC6Nb c}c504cmbB8X0k7j4dcsa_cW9ccY6mc?c6c+6Nc*d45ec 2Jc_4w0|6Paadj046Id8c/d2dd1*cedD0@cu5pdxdzc.c9c:b65Jb8clas5!0D5(5K5Y5M5V1f0e5Pd#2Q2L0y1#dY0D5N6`0%0)0+0J04.
Comparaison avec la méthode de parcours séquentiel

On donne ici une méthode "naïve" par parcours de liste séquentiel.

Nous allons comparer ces deux méthodes dans le pire des cas (nous cherchons un élément x qui ne se trouve pas dans la liste):

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(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

Votre figure

Votre tracé sera ici

À lire

Ici, le parcours séquentiel est plus efficace. Une explication est que les appels de fonction (récursivement) ont un coût.
Utiliser la méthode diviser pour régner dans ce cas-là s'apparente à "écraser une mouche avec un marteau-pilon."

2. Recherche du maximum dans une liste non triée⚓︎

Avec le paradigme diviser pour régner

Le problème est de rechercher le maximum d’une liste de nombres.

En adoptant le paradigme "diviser pour régner", l’idée pour résoudre cette question est de rechercher récursivement le maximum de la première moitié de la liste et celui de la seconde, puis de les comparer. Le plus grand des deux sera le maximum de toute la liste.

La condition d’arrêt à la récursivité sera l’obtention d’une liste à un seul élément, son maximum étant bien sûr la valeur de cet élément.

Voici donc les trois étapes de la résolution de ce problème via la méthode "diviser pourrégner":

• Diviser la liste en deux sous-listes en la “coupant” par la moitié.

• Rechercher récursivement le maximum de chacune de ces sous-listes. Arrêter la récursion lorsque les listes n’ont plus qu’un seul élément.

• Combiner : Renvoyer le plus grand des deux maximums précédents.

Observons le schéma suivant :

maxis

À vous de jouer 2 :

Compléter le script ci-dessous :

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(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
Évaluations restantes : 5/5

.128013w]itkc[v8o-)yl0bxpq_P3(a;+g=/m4rse97Sf,d 612:é5nuCh050O0I0e0y0d0o0H0P0g0o0y0H0H0C010e0d0s010406050H0X0E0E0y0G0n040L0k0o0X0@0k0W050D0~1012140|0s04051k1d1n0D1k0|0O0d0i0,0.0:0=0.0W0B0X0y0B0I0l0s0n0e0Z1b0P0Z0d0B0Z0o1P0Z0e0`050%0q0o0I1w0/0;011O1Q1S1Q0e1Y1!1W0e0G1l1K0,170H0s0y0W0=0S011$1y010M0)0I0W0y0E0I1W1{1}221(251!282a0`0a0P0v0G0k0s0k0H0d1a0W0P0#1_0G0G0I0g2v1d2d0W1l0D1K2I1=1@1?1X0O2f1z0d0W272s1W1t1v0-1%2S2U0W0k2Y1W0s2B1l2G2I2/0}1|2w2!232(0G110o1W0y1N2B0M0=030u0u0g2)0I1S2%0k0l0S0l0R0`0P0R1d0y2:2?0{2=2e2^1(2`2|2~300I32013436383a2V3d3d3h0S3k3m1}3o2G2R013t0y2}1l2 0Z313335370#3D2(3F0w3h0w3J2F3n0|3N3r0=3Q3S053U3W3z3Y3C2T3E3e0F3h0F3+1e3-3p2@1x3s0k2{3R3v3V3x3X3B3!3}3$3e0V3h0V432/3.2?3O3=4d3_3A3Z394j3c3e0Q3h0Q4p453/483;4a3u3T3w3y4x3|3b3F0K3h0K4G3L4r3q4J3P4L4c4N4e4P3{4i4S3e0j3h0j4X2H4Z472#4$4b3?3^4f3`4h4z4.0l0J3h0J4?3M4s3:4{4M3@4O4g4y3#4B3f0p0`0R0p584^4t4%4}5f505h4A3F0R3g045z5p465r4|4v4 4Q4-3~3f205B3I0D3l3,4Y5E5b4u4)4w4,525L0R3(5B3*5Q3K4@5U4#5W5e4*5g4R5#405B425*5S5,4I4`5/4~4+515i5y4m5B4o5{445T5~2_5s5H625w530R4D5B4F692;1q2-1d2Y2L0O1@2Q5b4y2X1u1l2,0I2.3n5|1l4y6E2e0d0O0=352G5y3v6L6N635x3e3g0P2j0I6T6h5#1W5{6c1(0f0`0#0M6G5-4`0b3h6:6*3;0M0`110r0d0E0 0u2B0g0X0G2t6/6a2H6;230_040x6^5a5.0`1Y7g4!4`7d0N6G0P7b3s6-0I0q197l4_7c0`7p79047r6_3P0`251c7D7s0=7d0m0T6G0|7L3N6S016O2?3F5N5e7V5Z643e206Y296!7W6U537!6)7h6=3h0P7_7y3O0H0O0`020t0X0k0e0z80828486830z7R7{7$0u6P3e5%7#6M7.6$4k0l3(7+2a6#5?8n8i7=7m237}7^7_2o0U370W1t2v0+0T0P1Y0P0I0H0e0P0X2U0P1S8O0I0N2x7v198M8O8T02030w0J0z2T1t0g1#0O0X2x0U7w8P2y0.0P730Z0I0G0g8~8X8c7T4s8e8g0l5^8j8s5K8n408q7-7%6V996(5R7G8z7E7_8M8P7J8%8)8+8-0d8/8Y8T2 9t8`2 8}8 910I942;7U8k7X1}3F669b8l8t5j4m9g9c5!8n9R8w7z1(9o9q2n2s0e8E8G0d1M8J8{0M1b2D9:2w2B0W0i0k0d1#1!0P6}6 0 9A8{8U0e1#7k7D7S9L969N8f7Y4C6Rah8m5j4D9X9T9dao9l6J9%0=9)9q8988818aaA8bad8dah984U4N8ean4T216Z9Y7(0laK3J9*7M016,040d782/7F7?2_7u8^7qaX0k0`0C0Ca-7G0W7I2Ta?a)1(7d7Q7Da(8x1(0g5A030P0Y0/9A0q0/1#8R0P0H0I0X0o0P0U0o0U2a0W0e9K6F9M6T984:aLam9U3F4:aq9i53bwaV9*9qaXaZ2B0e757Ka%aXa^04acafb27N0`0h7{5Va+7x95bV017d0cbr3L5E97aj54alaR9j55bC7/5L552I3laW7GaZ39bgbZ4#a~b,7abt7.985nb=ar9Z5jccb_aN6W5lb}9pbHb1aw7H040E0)a00Xa{b(a/04a=b0aX7d7fb%cqbR0#a,cC7Gcz0AcxcHa_bObsa|bW040mcP3Ocz0D0DcY5bct0`5P4qaHbub:5zcdbD5#6XaQceaSc:cmco7`a@0`0rc%4#czcBbPc cs0y6~700E722C7577c47n0`cFbUcQbS0y0qdh7A047Cd6cUcrcJb$dl3O7od25 6|cubhdqa}0`cXaGcG0Pb/9P6W7!2 aMbzdQaP7,b?6i7;b~c}bQ0`0ndC23d4d*7td8da7173dfa#dHcVdkcTb(bRbTd{cqdBcLdvbRct1SdGe2cy0`cOe8cqc)5Bd^b)7Bd-3;cReg7Oc7avdNaIc/8idSbyas5y8pc^c=8n5$auc}cp3OaZd@ec4td0ej01cz020o84d53neFb!04d)dM5bc6dLdzdO0W5y9aeudY5@dW8rc_9j0R9a5*eEb dvbK0$bNeMbReXc,dMe%65c;b`eB9Wezf6cg9#d#cobJ0`c29JeYc50`a f1e$erdP3f6k9SeAcgapf9cjfreDe^c~e`0`bLe}eJeVd1e#6F0D6I1o6q0D6s1d0e6ufS2O2Jdo1!2I6s7S0#0%0)0H04.
À vous de jouer 3 :

Compléter le script ci-dessous :

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(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
Évaluations restantes : 5/5

.128013w]itkc[vN8o-)yl0bxpq_P3(a;+g=/m4rse97Sf,d 612:é5nuh050P0J0e0z0d0p0I0Q0g0p0z0I0I0D010e0d0t010406050I0Y0F0F0z0H0o040M0l0p0Y0@0l0X050E0~1012140|0t04051k1d1n0E1k0|0P0d0i0,0.0:0=0.0X0C0Y0z0C0J0m0t0o0e0Z1b0Q0Z0d0C0Z0p1P0Z0e0`050%0r0p0J1w0/0;011O1Q1S1Q0e1Y1!1W0e0H1l1K0,170I0t0z0X0=0T011$1y010N0)0J0X0z0F0J1W1{1}221(251!282a0`0a0Q0w0H0l0t0l0I0d1a0X0Q0#1_0H0H0J0g2v1d2d0X1l0E1K2I1=1@1?1X0P2f1z0d0X272s1W1t1v0-1%2S2U0X0l2Y1W0t2B1l2G2I2/0}1|2w2!232(0H110p1W0z1N2B0N0=030v0v0g2)0J1S2%0l0m0x0m0S0`0Q0S1d0z2:2?0{2=2e2^1(2`2|2~300J32013436383a2V3d0m20040Q0T3k3m1}3o2G2R013t0z2}1l2 0Z313335370#3D2(3F0x3h0x3L2F3n0|3P3r0=3S3U053W3Y3z3!3C2T3E3e0G3h0G3-1e3/3p2@1x3s0l2{3T3v3X3x3Z3B3$3 3(3e0W3h0W452/3:2?3Q3@4f3{3A3#394l3c3e0R3h0R4r473;4a3?4c3u3V3w3y4z3~3b3F0L3h0L4I3N4t3q4L3R4N4e4P4g4R3}4k4U3e0k3h0k4Z2H4#492#4(4d3^3`4h3|4j4B4:0m0K3h0K4^3O4u3=4}4O3_4Q4i4A3%4D3f0q0`0S0q5a4`4v4)4 5h525j4C3F0S3g045B5r485t4~4x514S4/403f3H0S3K0E3l3.4!5G5d4w4+4y4.545N0S3*5D3,5S3M4_5W4%5Y5g4,5i4T5%425D445,5U5.4K4|5;504-535k5A4o5D4q5}465V602_5u5J645y550S4F5D4H6b4s5/616g5Z5K5#663e0S4W5D4Y6p4J5c5:6t5=5!655z6y4=5D4@6D6d6F6s5I6u6i5^4m3f575D596Q5 6S6f6U6I6v6K550T5n046:5a1o2-1d2Y2L0P1@2Q5d4A2X1u1l2,0J2.3n5~1l4A772e0d0P0=352G5A3v7e7g6.5%212j0J7m6j7o2I5T6e1(0f0`0#0N796r230b3h7D7x3?0N0`110s0d0F0 0v2B0g0Y0H2t0N0v0i5R2;7J010_040y7I6)3s0`1Y7,4$4|7)0O790Q7E7.040#0r197_7{0=0l0`0D817%0f0g0`0j1b0J7;4{237@877-3?0`251c6c2H7`7%8404868p3I8201898b8d8f3Q7)0n0U790|8w5G7l017h2?3F3H5g8M6w6L3G7p297r8N7n6Y8R5}7%7G3I0Q8,8D5d0I0P0`020u0Y0l0e0A8?8^8`8|8_0A8I8D8T0v7i3e5)8S7f8!7t6Y3*0Q7q7s6X5l988(8k018:3h8,2n0H0V370X1t2v0+0U0Q1Y0Q0J0I0e0Q0Y2U0Q1S9E0J0O2x0J7 9F9D9F0p02030x0K0A2T1t0g1#0P0Y2x0V9Q9O9J2 7T0Z0J0H0g9;9N928K3P94960m5`999h5M6Y429f8Ya25$a41W9l7=239o8+8,0$0Q8n9J9V9X9Z9v0d9$9-0.aj2Tas9/2C9;9?9;9`7$4u9}8P4n7k9a8U554oa62aa86x0m683-7%af9q2n2s0e9u9w0d1M9zat0N1b2Da$2w2B0X0i0l0d1#1!0Q7N7P0 aw9J0d9L9A0z0raC789|aJ95aG0m6ma19b9i3F4FaN8ZaK5Nbbac8g1(aV9q8 8~8@90br918w8JaD7db79~6Abcbj6Y4WbhaP8VbD5,aW8y7z040d7C8w8r9m0X7A9P80bT8y8t0D8v2/bUad7y8a048c2U8.4%7)8Hbx93bBb96NbE8#5l4=bIbda3b ab3laWbN7%bW7}bY0e8jb+8385cebn0=0F0d0`5qb^9{aEb`1}3F6!b}9c5l57c1bFcyc5agb*cj8z0`bRci4v8m2TcK5db$b(3ncF3Q8Ab.8Ccqcf7(0`b@6qcY2waFct6y6;cwbec,8XaOc2a95l5pcDc79q8yca8ncO4%b$d0610r0`2ib;7?0`7+c(cL047:dc5d8Fd8238t0mdj1(cl5ob43N8Lcs0X5A5Cc.c3dwc;bib~dA7vcEbOcIbSb)c}bX9Qd3dk85cR3NcT5XcM8odK7%b?dr2Hdt7m9~5QaIbJ6k20cAdD6y8%c6c{dT4%bP2B0e7VdWcSdLdeb2dn0=7)0he23RdMbZbzcG7)0cd!7cc)du5A982 94cxeidBd+5%9kd=8-880`390I8edgb=c#eed$8!d(a0ekb7em6ya59gc?aQ0Sa0bMd?d cl1S0J0YdO1(d2b!dYdae6ca7~e9d~8s0`0BeY8l04c ezd9040ne:018t0E0Ee{dp6=eCb6d%b90SaSeHep6Yf7eoeN8VfcdFd?d@610`0se{e!dXbV7M0z7O7Q0F7S2C7V7X7Z7#b59m7)dbeadddffGdh0`7^e#fqcbdNe@8hfLe{caeUa?eXfR1(dicpfGc*dv6ybbf9fe6kbgeMcB5Ablesc7d 0ofnchfNcZfVfsa{fv7TfybRfAe6fEe(7/e1fZe3fTf}cGfV0)fXf{04e/gf3Qf13jgcc!04fMfpf~dVg70`e`f$fCbAf5c+3fbDf,f;6ybHf:d/gGc`eSeubQdJe,fOfmgncP8=0p8`dR8qf_gy04c$47dcf(5Ab|gIgN0Sc0gMeJ3fb|eRfiet9md_0$d|fU0`f`gBdsf4eEf6cvg;g_0Sczg^c/6ZgPc{dH04eweyfJeAg*f3crgEf)3Gc-hchh6:fdgJhwhjg}hld`h2gX5:fleC0E7b6^766`731d0e6}hT2O2Jb21!2I6{8J0#0%0)0I04.
Comparaison avec la méthode de parcours séquentiel

On donne ici une méthode "naïve" par parcours de liste séquentiel.

Nous allons comparer ces deux méthodes :

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(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

Votre figure

Votre tracé sera ici

À lire

Ici, le parcours séquentiel est plus efficace. Une explication est que les appels de fonction (récursivement) ont un coût.
Utiliser la méthode diviser pour régner dans ce cas-là s'apparente à "écraser une mouche avec un marteau-pilon."

Remarque

😨 Mais pourquoi utiliser "diviser pour régner?"

3. Exponentiation récursive classique⚓︎

On peut définir \(x^n\) de façon récursive

  • \(x^0\) = 1
  • \(x^n\) = \(x\) * \(x^{n-1}\)
À vous de jouer 4 :

🤣 Le but étant de programmer la puissance "à la main", il est intedit d'utiliser ** ou pow.

1. Compléter le script ci-dessous :

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(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
Évaluations restantes : 5/5

.128013witkcv8o-)ylxbqp0_P3(a;g=/m4r*se97Sf,d 612:é5nuh050M0G0d0w0c0m0F0N0f0m0w0F0F0z010d0c0q010406050F0V0B0B0w0D0l040J0i0m0V0;0i0U050A0{0}0 110_0q04051h1a1k0A1h0_0M0c0g0)0+0-0/0+0U0y0V0w0y0G0j0q0l0d0W180N0W0c0y0W0m1M0W0d0@050!0o0m0G1t0,0.011L1N1P1N0d1V1X1T0d0D1i1H0)140F0q0w0U0/0Q011Z1v010K0$0G0U0w0B0G1T1^1`1 1#221X25270@0a0N0t0D0i0q0i0F0c170U0N0Y1?0D0D0G0f2s1a2a0U1i0A1H2F1/1;1:1U0M2c1w0c0U242p1T1q1s0*1!2P2R0U0i2V1T0q2y1i2D2F2,0`1_2t2X202#0D0~0m1T0w1K2y0K0/030s0s0f2$0G1P2!0i0j0C0j0P0@0P1a0w2-2:0^2/2b2=1#2@2_2{2}0G2 01313335372S3a0j1}040Q3g3i1`3k2D2O013p0w2`1i2|0W2~3032340Y3z2#3B0u0@0u3G2C3j0_3K3n0/3N3P053R3T3v3V3y2Q3A3b0C0@0C3(1b3*3l2;1u3o0i2^3O3r3S3t3U3x3X3`3Z3b0T0@0T402,3+2:3L3/4a3?3w3W364g393b0O0@0O4m423,453.473q3Q3s3u4u3_383B0I0@0I4D3I4o3m4G3M4I494K4b4M3^4f4P3b0h0@0h4U2E4W442Y4Z483:3=4c3@4e4w4+0j0H0@0H4:2F2)0G2F2V2I0M1;2N3-014v2U1r1i572+3j3)3I054v5m2b0c0M0/322D3B3d4K5u5w4~3Y4y3c1~2g0G5D4v5F5z1T0A3h433L0e0@0Y0K5o2E5S5f0b0@0N5Y5s4?2?0K0@0G0n2o0s2y0f5)5!4Y0?040v5^4F4@0U0@0n5~4p5f5{0L5)5(5 2?0@19415p6b1#5{0k0R5)0_6f5Z3K5C015x2:3B3D3;0N6r4)4 3{3C5I265K6s5E4x6v5P5R6h0/5$040N6R5(6o5*3L0F0M0@020p0V0i0d0x6!6$6(6*6%0x6m645t5v6H5y3b3#5B6?6A5N6_6E275L4O6C6`3(6N016X5%6S2l0S340U1q2s0N0R0N0n0N0Z0N2t0F180d2u0G0(240;0G0D0F6:6U5S6z0s6^3a3r7E5M6J3|706G6}7L7H2F6M654Y796Q7b2p0d7e7g0c1J7j0+0N0K182A7%2t2y0U0g0i0c1Y0n0E0E6e4n6;2t7E7G4j6{724*6C4j7o6F856B4h0j83767U4@7W6S0N6-6,6#6.8m6/6U6n2.6q6|7F6u4z7I8w7K504A89716H8C6C4A7S7X6R5_4@5U040c5X6U6a8h6c047}3j8V4X4@0i0@0z0z698O200B0c0@0r7 3L5{6l8s8?818y0j4R848H738d4R8F7O6I508 3G8k8k8-1#8Q2y0d0V0D8Z3I8#5+1#8/3e7B8u4p8|1`3B4-907P504-958b6~0j9x9a6S9d0/8Q360F0G8,778^9r5n8v5D7G529y976C529C91868d9X9H9b9m5T0@9g9i9k2E9-5f6104638U9J018(040E9P8W3o5.5:0i5=2z8?660@5}7C779_9{9s8$2067a2aja48Yam9n0/9 0jaq3L9p043faea30/6j9S5p0A5r1l2*1a5a1a0d5caM2L2G0w1W58aK5j6n0Y0!0$0F04.

2. Utilisons la fonction précédente pour calculer \(2^{1000}\)

Que se passe-t-il?

Solution

Nous avons un message d'erreur expliquant qu'il y a eu un trop grand nombre d'appels de fonctions récursifs. Nous verrons plus tard que nous pouvons modifier cette limite dans Python.

😥 Il faudra faire 100 multiplications pour calculer \(x^{100}\) .
On dit que la complexité (en regardant le nombre de multiplications) de cet algorithme est en \(O(n)\),

Temps de calcul avec l'exponentiation récursive classique

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(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

Votre figure

Votre tracé sera ici

Solution

La complexité semble encore linéaire.

Quelques exemples d'utilisation de "diviser pour régner" :

Diviser pour régner : exemples

La correction est arrivée 😊

Diviser pour régner : exemples - correction

III. Une approche de la complexité⚓︎

Vidéo de Cédric Gerland

https://youtube.com/watch?v=UcT_4cWfnAs&si=EnSIkaIECMiOmarE

IV. Le tri fusion⚓︎

🤔 Comment fusionner deux listes triées pour obtenir une liste triée ?⚓︎

Nous donnons l1 = [2, 3, 5, 8] et l2 = [1, 4]

✏️ A vos crayons 1 :⚓︎

Voici un script Python :

Python
def mystere(l1, l2):
    n1 = len(l1)
    n2 = len(l2)
    lst = [] # initialisation de la fusion de l1 et l2 
    i1 = 0 # indice qui sert à parcourir l1
    i2 = 0 # indice qui sert à parcourir l2
    while i1 < n1 and i2 < n2 :
        if l1[i1] < l2[i2]:
            lst.append(l1[i1])
            i1 = i1 + 1
        else :
            lst.append(l2[i2])
            i2 = i2 + 1
    return lst

mystere([2, 3, 5, 8], [1, 4])

Recopier sur votre cahier le tableau suivant qui décrit le déroulement de l'exécution de :
mystere([2, 3, 5, 8],[1, 4]) et le compléter.

  • Il y a une ligne par tour de boucle.
  • Pour vous aider, nous avons rajouté une colonne pour l1 et une pour l2. Vous pourrez entourer à chaque étape, dans une de ces colonnes, l'élément qui sera ajouté à lst (en gras ici)
i1 i2 l1 l2 lst
0 0 [2, 3, 5, 8] [1, 4] [1]
0 1 [2, 3, 5, 8] [1, 4] [1, 2]
... ... ... ... ...
...
Solution
i1 i2 l1 l2 lst
0 0 [2, 3, 5, 8] [1, 4] [1]
0 1 [2, 3, 5, 8] [1, 4] [1, 2]
1 1 [2, 3, 5, 8] [1, 4] [1, 2, 3]
2 1 [2, 3, 5, 8] [1, 4] [1, 2, 3, 4]
2 2

😥 Nous observons que les deux listes n'ont pas été complètement fusionnées, car nous avons "épuisé" tous les éléments de l2.
👉 Par contre, il est certain que les éléments restants de l1 qui n'ont pas été fusionnés, sont triés, et plus grands que tous les éléments déjà présents dans lst.
🤗 Pour obtenir la liste complètement fusionnée, il suffit donc d'exécuter :
lst + [5, 8] c'est à dire lst + l1[i1:]

💻 A vous de jouer 1

Compléter le script suivant :

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(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
Évaluations restantes : 5/5

.128013w]itkc[v8o-)yl0bqpx_.P3(a;+gE=/mà4rse97Sf,d 612:é5nuh050R0L0e0z0d0o0K0S0g0o0z0K0K0E010e0d0s010406050K0!0G0G0z0J0n040O0k0o0!0_0k0Z050F101214160~0s04051m1f1p0F1m0~0R0d0i0.0:0=0@0:0Z0C0!0z0C0L0l0s0n0e0#1d0S0#0d0C0#0o1R0#0e0|050)0q0o0L1y0;0?011Q1S1U1S0e1!1$1Y0e0J1n1M0.190K0s0z0Z0@0V011(1A010P0+0L0Z0z0G0L1Y1}1 241*271$2a2c0|0a0S0w0J0k0s0k0K0d1c0Z0S0%1{0J0J0L0g2x1f2f0Z1n0F1M2K1@1_1^1Z0R2h1B0d0Z292u1Y1v1x0/1)2U2W0Z0k2!1Y0s2D1n2I2K2;0 1~2y2$252*0J130o1Y0z1P2D0P0@030u0u0g2+0L1U2)0k0l0T0l0U0|0S0U1f0z2=2^0}2@2g2`1*2|2~30320L340136383a3c2X3f0l22040S0V3m3o1 3q2I2T013v0z2 1n310#333537390%3F2*3H0x3j0x3N2H3p0~3R3t0@3U3W053Y3!3B3$3E2V3G3g0I3j0I3/1g3;3r2_1z3u0k2}3V3x3Z3z3#3D3(413*3g0Y3j0Y472;3=2^3S3_4h3}3C3%3b4n3e3g0T3j0T4t493?4c3^4e3w3X3y3A4B403d3H0N3j0N4K3P4v3s4N3T4P4g4R4i4T3 4m4W3g0j3j0j4#2J4%4b2%4*4f3`3|4j3~4l4D4=0l0M3j0M4`3Q4w3@4 4Q3{4S4k4C3)4F3h0p0|0U0p5c4|4x4+515j545l4E3H0U3i045D5t4a5v504z534U4;423h3J0U3M0F3n3:4$5I5f4y4-4A4:565P0U3,5F3.5U3O4{5Y4)5!5i4.5k4V5)445F465.5W5:4M4~5?524/555m5C4q5F4s5 485X622{5w5L665A570U4H5F4J6d4u5;636i5#5M5%683g0U4Y5F4!6r4L5e5=6v5@5$675B6A4@5F4_6F6f6H6u5K6w6k5`4o3h595F5b6S616U6h6W6K6x6M570V5p046=5H6g4d6-655_5O6!0V5E716_6+6{5h6}5z6Z5n0V3J7c744(6V775y5N5(705+0V5-5V6e6*7g6,7i5^796 7b5|0V5~7q6s6`4O6|7j6y6N3I6a0V6c7D3p1q2/1f2!2N0R1_2S5f4C2Z1w1n2.0L2:7Q7r1n4C7*2g0d0R0@372I5C3x7;7?6:5)232l0L7|6l7~2K5V7F010f0|0%0P607/4}250b3j8d6t2{0P0|0P0!2v1d8j870{040y8s753^0|0o3l7,8k1*8u0Q8d0S8E8z040o5T2?8t0|0m0W8d0~8D3R7{017@2^3H3J5i8Y7J6;7 2b818Z7}701Y5 878h3K0S8`8x7t1*0K0R0|020r0!0k0e0A92949698950A8U8|2y8)0u7^3g5+8(7=8/836!3,0S80827a3+8=868y018 3j8`2p0J0X390Z1v2x0S0W0S8B0S0(9N0V0S0K1d0e2z0L0!0t9N0d0K0e0L0-1@0d0X9)9e8W4w9h9j0l5|9m9u7y3H449s8-9`7l5n9^8?9z9B8_8`0w2u0e9H9J0d1O9M0:0S0P1d2Fae2y2D0Z0i0k0d1%0!2W9#9%1%9+9-1{0Z9%2w0!aA2Aah8o8q2y9/8P9;9n8!1 3H6a9_9o9v4p8,2ca06z0laTa48}0@a69D9X9N0U9P9W8NaM7Q8XaP9i8#4G7`a_9p5n4H9~aZaV9{a|858e3Sa+9D0D0t0L0G0s1$9La?3P5I9=a{0l6CaU8*5P4Yb28.br6!bpa(8f8~90a7ai8pam0y0h0V0Q0S0xbK0YbK0j0c0Q0h0UbK0I0c0m0Saoaqas0SbTbKbJbLbNbP0cbj2Jbla_9?6Pbq8:5n4@bua!7Kb@bzb9bCa,9b9a939cc49d7,8VaN7:b=bn6$b^a 3H59b|b4a1cj9x3q9:cd7|9?5ra}b}6m5pclbw5ncvb7a,8K3T0|0Z8C2;8J870k0|0E8IcG0Z0q8A299f3S8u8wcrbA8L8BcX5f8u0mb/b8bmaR6A5EchaW3h3icAb_5Cc=5.cF870ZcI8O3pcM9zcO04cQ7,d5a)3TcU8McWc#cY0|c!ccc$cH8Md3bk8Q04c,cacXc/0Z5C8%319hci6A22c`dC5Qcpc 9zd18M9%cRcNcPdO9z8u0hb.dacG0g5E030S2V2w0d3V9$0z9KaH31aJama-9O9Q8N8Jdudhdw5C9ldAa~c@5*aYbvc{6A9lc~9DcS0|0dcKd4cGd7d9cLcG0G0d0|5sdW87dY0|d!2V1v0g1%930d9T0L0J9W0H0S1~0J390!0J0d0Ja.c-b;ctbn0U9^d~cx5{e2eT6!eQdIe8d0eadp2JdbdmefdRdcejele,dmep04er9I0deu0SeweyeA0SeCeEeGeIeKa=d_dld#cec:3haTeScma#0U4qdFe0a%3ndJdc89040b1Q1$e:4xeaec3Pe)3Sd7020o96ft5ZcIfwe(ee8^1 0RfE5=e$fN4~fAfCc9ehe#040Ze%3KcG8u8Tf6a@aOeOfa6ncwfe7Kf-fib53h6o3Na,fmdmfo0d8cendK8AfHb8c*0|0hc)fO04ebg84~8udVfVd691fTfQ2{8AfZf#g6gcglgagndr0cf%6sd`f9dx6AbpfdcB5Cbt9tf/6mbyflf`gMe9dM0egq1*d70vgR8L0z0s0s29fMdhg58vgVdnc(g$4)dTg)dLgbg,gd0|bXeMa^f+gA3hb@gDe4g}eVgI5)b gLgMf{fugag3fy5fe+g0dcg:hbee0|0Bgk1*e.5Fg_f*8/cucgg dG0UckgHgE6Acge7gN87fo3b0K0Lhm0@f$hqcshsbn6=f.hA3Iczhzh0hRcEh7h8fFgPg)gTg/0|gXgZ9Ig)cZh*doh/gpg=gr0dgtdSg@dtgxf7d{3g71hShXc_hWdGi3hZh!8{fWh`hK01hegghgfPhfe*hkifhog3cbf)hOaQg|7ci4i8dEi7c@iwiahc4)f}f iidmhhifefegedfWcJh?04gw49gyg{8$d}f8eW7b9riAf?7oeZhE9zfo2D0eeH1eilh90,gQi=hdini_g9f5f7g%g7h^3uiki g-0|0WgfiUi0gz8$eRiZh3709}i%cni2a3h6iE4~iGifg:fZjo25iMjrd2iRiT5XiVhPfa7NixiBfhjja#jFiDh#iF0|i.i:jxh%i|fRi{iIi?g3go04j1j563fvjzj9jB2?0F7.7R7)7T7$1f0e7Wj@2Q2L0z1#j;0F7U8V0%0)0+0K04.

😥 Le problème, c'est que les "slices" ne sont pas vraiment au programme de NSI, et que leur utilisation n'est pas toujours efficace. Essayons une version qui n'utilise pas de "slices".

💻 A vous de jouer 2

Compléter le script suivant :

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(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
Évaluations restantes : 5/5

.128013w]itkc[v8o-)yl0bqpx_.P3(a;+gE=/mà4rse97Sf,d 612:é5nuh050R0L0e0z0d0o0K0S0g0o0z0K0K0E010e0d0s010406050K0!0G0G0z0J0n040O0k0o0!0_0k0Z050F101214160~0s04051m1f1p0F1m0~0R0d0i0.0:0=0@0:0Z0C0!0z0C0L0l0s0n0e0#1d0S0#0d0C0#0o1R0#0e0|050)0q0o0L1y0;0?011Q1S1U1S0e1!1$1Y0e0J1n1M0.190K0s0z0Z0@0V011(1A010P0+0L0Z0z0G0L1Y1}1 241*271$2a2c0|0a0S0w0J0k0s0k0K0d1c0Z0S0%1{0J0J0L0g2x1f2f0Z1n0F1M2K1@1_1^1Z0R2h1B0d0Z292u1Y1v1x0/1)2U2W0Z0k2!1Y0s2D1n2I2K2;0 1~2y2$252*0J130o1Y0z1P2D0P0@030u0u0g2+0L1U2)0k0l0N0l0U0|0S0U1f0z2=2^0}2@2g2`1*2|2~30320L340136383a3c2X3f0l22040S0V3m3o1 3q2I2T013v0z2 1n310#333537390%3F2*3H0x3j0x3N2H3p0~3R3t0@3U3W053Y3!3B3$3E2V3G3g0I3j0I3/1g3;3r2_1z3u0k2}3V3x3Z3z3#3D3(413*3g0Y3j0Y472;3=2^3S3_4h3}3C3%3b4n3e3g0T3j0T4t493?4c3^4e3w3X3y3A4B403d3H0N3j0N4K3P4v3s4N3T4P4g4R4i4T3 4m4W3g0j3j0j4#2J4%4b2%4*4f3`3|4j3~4l4D4=0l0M3j0M4`3Q4w3@4 4Q3{4S4k4C3)4F3h0p0|0U0p5c4|4x4+515j545l4E3H0U3i045D5t4a5v504z534U4;423h3J0U3M0F3n3:4$5I5f4y4-4A4:565P0U3,5F3.5U3O4{5Y4)5!5i4.5k4V5)445F465.5W5:4M4~5?524/555m5C4q5F4s5 485X622{5w5L665A570U4H5F4J6d4u5;636i5#5M5%683g0U4Y5F4!6r4L5e5=6v5@5$675B6A4@5F4_6F6f6H6u5K6w6k5`4o3h595F5b6S616U6h6W6K6x6M570V5p046=5H6g4d6-655_5O6!0V5E716_6+6{5h6}5z6Z5n0V3J7c744(6V775y5N5(705+0V5-5V6e6*7g6,7i5^796 7b5|0V5~7q6s6`4O6|7j6y6N3I6a0V6c7D6G7t764,6.6Y7y3H0V6o7Y7f4}7u7T787k6z3I6C0V6E7P6T7R7G7v6L6l5P0V6P7{5c1q2/1f2!2N0R1_2S5f4C2Z1w1n2.0L2:3p601n4C8e2g0d0R0@372I5C3x8l8n6:5)232l0L8t7_6!5E3/7F010f0|0%0P8g6t250b3j8K8E0Z0P0|0P0!2v1d5T2?8E0{040y8P753^0|0o3l7r8j7$1*8#0Q8(7=3T8+8Y8f8!0|0m0W8g0~8.5I8s018o2^7X8r8m968u708w2b8y9c8A7b1Y5 8E8N3K0S9q8@8:0@0K0R0|020r0!0k0e0A9y9A9C9E9B0A919s0S95971 3+9a8z7a9Q0S8x9S7W3g5+8D8)019v3j9q2p0J0X390Z1v2x0S0W0S8,0S0(9@0V0S0K1d0e2z0L0!0t9@0d0K0e0L0-1@0d0Xa99K933R9N0u8p439R9i9Tal9V9g9X7l5n5|9#8^9(9p9q0w2u0e9.9:0d1O9?0:0S0P1d2FaG2y2D0Z0i0k0d1%0!2Wa5a71%abad1{0Za72w0!a$2AaJ8U8W2yaf8Z4waiak0l6a5iai9j3H4qaq2cas7+a{9m9$ay9*a19@0U9_a00o8{5Xaga@9b9O0Z3H6oa|bk9d5n4Hb19h7J57bob6ax9waz0S0D0t0L0G0s1$9=a=8|bj8ta_6Cbpb37K4YbubS57bQbz9t9%bBb9a/aO0y0h0V0Q0S0xb-0Yb-0j0cb-0h0Ub-0I0c0m0SaQaSaU0Sb_b-b,b.b:b=0cbL3P94bqa_6PbRan9Y0l4@bVciat3HcgbZ3Sb89*9H9G9z9Icv9J8.92a?8kce983g6$chbw5P59cmcK6!cI5.b98L3u0|0Z8-2;0ScT0@0k0|0E8gcZ8Q0q8+299L5f8#8%bi8^0Z8+cXbM8^8#0mcb2JcdbOcG5oamcO5n5r9fb2cn7+d82K3ncS8QcVbg2Jc*9$c$04c(8.dlc@c,042kc/4)c;dw638`dz25c}c 8/9McF9P6A8C31a}ao3h3icNbr5C8CcR9*c!8_dua7c)dXdndpcYdX8#0hcadqdX0g5E039M0Z2w0d3Va60z9;a-31b(1Oa-bc9`bfcZcB9La^d35Sd5dS6A22dRa~ee9ldfdWdh040dc`3Pdrb!d%d#8E0G0d0|5sd.8Ed:0|d=2V1v0g1%9z0d9}0L0Ja00H0S1~0J390!0J0d0JbbdFd19ca_5*eceh3h3,egdOe%debCdXc^endj3Kd$c%eu9$eweye{8^eC04eE9/0deH0SeJeLeN0SePeReTeVeXbfeZahdIbm6AavdMbqe)0U44e,cjfreje:8E8G040b1Q1$e b!e=eofE3Sdn020o9CfI5ZcVepdkd$9o1 0RfO5=0|0de@erfJ9xfMcAd)em0Zf#d*0|90e7c?2ye9dJ3ha{fobW5)b09Wdb7K0Ub5ekb99rfyfZ8JeA9$e=8,dC8;0|0hgf8*enfRdGc:0|d-f+dmf(fNgbc@dBf?3Sd+gjdYf!gB8#0cf;6sgyf^fl3hbof|g16mbtg0d65Cbyg5g6dggc8+d!gy5fdn0vgBe=0z0s0s29fWg$dx0|c=cDfFc_gEghg*fZgmf/04b}fibNe#eabQgOgT6AbUgSed3hbYgWgXg7gZglfX4~etgvg_hkhof%040Bhl25e}5Fh3cEd2f_0Ucgh8hdhDd9bvhGcqhgel9$fz3b0K0Lhvgg04gH49gJfk5CcIhFfqcMhch%fwhhg6e;g!0egBg(g}04g,g.9/g{8$h?fhg;4~gAh 2{fZe@h0h2f=g^dHhBgL6=e(dOidftco3gide/h,gYgwe?hTc#e`hrfPipit4)dnhuiw4~hxgmcCc{f@hZijdLiagP7`dQh)ifdUgWdXfz0dgagriofHiA25d%d(3pf$iucWh{hWbhi9gK7X3JcJhd7chIf}70i;dVgXiS8T4eiqgCj10k9o2Vj10Zdt0J1 1Hh{g@iF4xi4h{8?iZcU04f-h{8 hziGib7X9!h$ife+iOcj7oh+imhiio0,h:i21*h=jHgkh^g/jdh}i58}04gijKj2jUgFc~i8jfi/ijfniKh93Ifsjyiij*jBi}g8042D0eeU1ejkgkjFc)iEccfjjsijf{j(i?f ariL70g4fxhOg9j7jhj`01i#kejmjQ9$8#i,5:hYk13IgNk4e)7Yi^k87bgVbCinb!fzaL0Jkj0dj3j5j_iWfFj9jbhSjWg?h?iYi9go04jjkMjgjmg jRjpjZj h4bl7Xh7kuifhbk7j)7.j/imh.dZjGkVix0|g)jUg+g-jNkRh|l1g`l5jTk}dAenh{i7gIi.iH3IhEk/jzclj,7+7{k^kC3Sfzj?j^kjj|k)d00F8i7 8d818a1f0e84lH2Q2L0z1#lE0F82920%0)0+0K04.

Cours détaillé⚓︎

Cours de Nicolas Revéret

Dans ce cours les tableaux sont des tableaux de taille fixe. La syntaxe .append n'est donc jamais utilisée.

⏳ Nous étudierons une autre présentation de ce tri avec le type list Python dans un second temps

Cours de Nicolas Revéret

➗ Diviser Pour Régner : le tri fusion 🤴⚓︎

😊 Nous allons maintenant implémenter une méthode de tri basée sur "diviser pour régner" : le tri fusion.

Observons cette animation :

Illustration animée (source wikipédia)

Nous disposons d'un tableau (type list de Python) de taille n.
Son premier rang est donc 0 et son dernier rang n-1.
On notera t[a -> b] la liste constituée des éléments de rang compris entre a et b (compris) de la liste t.
La fonction tri_fusion fait appel à la fonction fusion qui permet de fusionner deux listes triées en une liste triée. 


fonction tri_fusion(t)
      """
      entrée ː un tableau t
      sortie ː renvoie un autre tableau qui correspond au tableau t trié
      """
      n = longueur(t)
      si n ≤ 1
              renvoyer t
      sinon 
              m = n//2
              renvoyer fusion(tri_fusion(t[0 -> m-1]), tri_fusion(t[m -> n-1]))

La terminaison est justifiée par la décroissance stricte de n à chaque appel récursif.

💻 A vous de jouer 3

Compléter le script suivant :

La fonction fusion est écrite dans le code caché.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(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
Évaluations restantes : 5/5

.128013w]itkc[v8o-)yl0bqp_P3(a;g=/m4rse97Sf,d 612:é5nuh050M0G0e0x0d0o0F0N0g0o0x0F0F0A010e0d0s010406050F0V0C0C0x0E0n040J0k0o0V0;0k0U050B0{0}0 110_0s04051h1a1k0B1h0_0M0d0i0)0+0-0/0+0U0z0V0x0z0G0l0s0n0e0W180N0W0d0z0W0o1M0W0e0@050!0q0o0G1t0,0.011L1N1P1N0e1V1X1T0e0E1i1H0)140F0s0x0U0/0Q011Z1v010K0$0G0U0x0C0G1T1^1`1 1#221X25270@0a0N0u0E0k0s0k0F0d170U0N0Y1?0E0E0G0g2s1a2a0U1i0B1H2F1/1;1:1U0M2c1w0d0U242p1T1q1s0*1!2P2R0U0k2V1T0s2y1i2D2F2,0`1_2t2X202#0E0~0o1T0x1K2y0K0/030t0t0g2$0G1P2!0k0l0j0l0P0@0N0P1a0x2-2:0^2/2b2=1#2@2_2{2}0G2 01313335372S3a0l1}040N0Q3h3j1`3l2D2O013q0x2`1i2|0W2~3032340Y3A2#3C0v3e0v3I2C3k0_3M3o0/3P3R053T3V3w3X3z2Q3B3b0D3e0D3*1b3,3m2;1u3p0k2^3Q3s3U3u3W3y3Z3|3#3b0T3e0T422,3-2:3N3;4c3^3x3Y364i393b0O3e0O4o443.473:493r3S3t3v4w3{383C0I3e0I4F3K4q3n4I3O4K4b4M4d4O3`4h4R3b0j3e0j4W2E4Y462Y4#4a3=3@4e3_4g4y4-0l0H3e0H4=3L4r3/4`4L3?4N4f4x3!4A3c0p0@0P0p574@4s4$4|5e4 5g4z3C0P3d045y5o455q4{4u4~4P4,3}3c3E0P3H0B3i3+3K1l2*1a2V2I0M1;2N5a4x2U1r1i2)0G2+3k5R2E054x5,2b0d0M0/322D5x3s5@5_505h5|0N2g0G5 5v525z3*4H4_0f0@0Y0K5.5=4^200b3e6h5D5a0U0K0@1/0d0t0K0V2q186n6b200?040w6A594!0U0@0%0e6G4Z4_6D0m0R6h0_435S3M5~015`2:3C3E5d6Y4+515K1}6326656Z605w3b6%5P6i3N6l3F0N6~6N6j1#0F0M0@020r0V0k0e0y76787a7c790y6T700N6)0t5{3b3%4M7l675K3%6.27664Q7t1T6_6o4!733e6~2k0E0S340U1q2s0N0R0N6L0N0G0F0e0N0V2R7Q0d7U0G7i6V5/6X5^6;7n0l3 7q7+6*613~1~647x5J4j7.7A5Q6B72746}6~0u2p0e7K7M0d1J7P0+0N0K182A8a2t2y0U0i0k0d1Y7X1Y1P7#0N770d7S7U7Q2|8s0e1Y6t0S7$7(3l8H5D7l7-4l7:7`6+7|4l7v6:7=6?0l8N3I6U2.7*5 7-4C8O6;7s7|4C8T8P7?0l8)6a6H4_7E830N7f7e777g8}7h8H8!5-8$7,6#3b4T8*8V524T8/8+7y7|9a3I7G0N7C4_6J04198H9m800/0k0@0A6h9t8^2?0q6K247j5a6D6F8J9u3O6K7U9G4!6Q7%8#4r8L983a5}7;6=524/9f9c5K4/2F3i9l9n206d040d6g9s9.3p0@9r2,9A6O209w04020o7a9y9@9L0C0d5l9P6P0@6S937j9V1`3C549b9!5K549%am7|ak9k9l7G9^0/9:2y0e0V0E9{3k9}713:9N6Maf9K9U9Z7-5m9Y8:8WaPap8,5iaP9+8{aw019:360F8G9|a!6Dae4pagaN9W5yaQ9g7{aW3daU9ha_7~8{9-9L9p0C9za!a0a5a*b19`b49La00B0Bbb9B1#a80@5Oa.aL5?a:ai3b5Na?9(7|bsa{a^5x6^9,au6 9Lay0ZaBaD3KaF4s0@6w6ybI7)bh0/9Iab2?6s0E6ubN8ibU1#bTbnaG9M046Lb#bS0@0ha-95bRb*b3b(3N6D0c0m0Lbg9~9_046t6v6xb!b_9H0@9J9Tc0aHb+9Oc79Qb/b-b@cja,b|0m9z945S0B5;5T5+5V5(1a0e5Ycy2L2G0x1Wcv0B5W6U0Y0!0$0F04.

Une approche de la complexité du tri fusion⚓︎

Fonction tri_fusion

On redonne :

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(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

💻 A vous de jouer 4

Compléter le script suivant :

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(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
Évaluations restantes : 5/5

.128013w]itkc[v8o-)yl0bqp_.!PL3(a;j+gE=/mà4rse97Sf,d 612:C5nuh050T0N0e0A0d0o0M0U0g0o0A0M0M0G010e0d0s010406050M0$0I0I0A0L0n040Q0k0o0$0{0k0#050H12141618100s04051o1h1r0H1o100T0d0i0:0=0@0_0=0#0E0$0A0E0N0l0s0n0e0%1f0U0%0d0E0%0o1T0%0e0~050+0q0o0N1A0?0^011S1U1W1U0e1$1(1!0e0L1p1O0:1b0M0s0A0#0_0X011*1C010R0-0N0#0A0I0N1!1 21261,291(2c2e0~0a0U0w0L0k0s0k0M0d1e0#0U0)1}0L0L0N0g2z1h2h0#1p0H1O2M1_1{1`1#0T2j1D0d0#2b2w1!1x1z0;1+2W2Y0#0k2$1!0s2F1p2K2M2?11202A2(272,0L150o1!0A1R2F0R0_030t0t0g2-0N1W2+0k0l0O0l0W0~0U0W1h0A2@2`0 2_2i2|1,2~3032340N3601383a3c3e2Z3h0l24040U0X3o3q213s2K2V013x0A311p330%3537393b0)3H2,3J0y3l0y3P2J3r103T3v0_3W3Y053!3$3D3(3G2X3I3i0K3l0K3;1i3?3t2{1B3w0k2 3X3z3#3B3%3F3*433,3i0!3l0!492?3@2`3U3{4j3 3E3)3d4p3g3i0V3l0V4v4b3^4e3`4g3y3Z3A3C4D423f3J0P3l0P4M3R4x3u4P3V4R4i4T4k4V414o4Y3i0j3l0j4%2L4)4d2)4,4h3|3~4l404n4F4@3h3l0O4|3S4y3_514S3}4U4m4E3+4H3j0p0~0W0p5d4~4z4-535k565m4G3J0W3k045E5u4c5w524B554W4?443j3L0W3O0H3p3=4(5J5g4A4/4C4=585Q0W3.5G3:5V3Q4}5Z4+5#5j4:5l4X5*465G485/5X5;4O505@544;575n5D4s5G4u604a3R1s2;1h2$2P0T1{2U5g4E2#1y1p2:0N2=3r611p4E6w2i0d0T0_392K5D3z6D6F685C3i3k0U2n0N6L5B595F3;63270f0~0)0R6y5=500b3l6(6Y3w0R0~1_0d0t0M3d2G2I6f2L6)270}040z6-5f5?0~1W0M0e0N734*50700m0Y6y106|6B2A6K016G2`3J3L5j7m5(693i246Q2d6S7n6M597r606.0_6+3M0U7K7b4 270M0T0~020r0$0k0e0B7S7U7W7Y7V0B7h7M0U7t6@7p3i5,7s6E7B6U5Q3.7y2e6T5{4q0l7/7F74507P3l7K0U77790U0N782B1)0e0n0s1)877a7j7i2^3T7+6H456J7;7u6N0l467_7A8t595}6X817O7Q7J7K0x330R1f2H0d1Q2F0#0i0k0d8h338i0U6=0N1)200L0U4g0T2F0:2t0d0@210e0u7(7j5J8o7-0l6b7:7{5P7}4s8x8}5)8 1!807c8E847K0F0o1(0U1d0-8-8h02030y0O0B3X0E4g2y0%2e8c8X0L0d0U8#0U6^1(8M1f0u0U0Z9j9l0B8a0e9e2A6=0U7#7W2b9y0=0g0N9R7%8k7)8^213J4J4T7+7?7}4J917=7|5o9)8C971,838G9Q7T7$9Y9Y8=8m4y9$0#4Z8r927v0l4!9/8z5Q4!2M3p850U6~1,6!048K0L6yaj7G3V0~0daqak0_0k7I2Xawas0#0q0~0L211J7)5g70728?aDaF042maK4+aMaT64768-79aW6 0~0maC8D1,0k0~0la)9^0_0I0d5ra#1,7e7g9!aOa38s7,9%4^a79:8~5o4_ac7C5Q4_ag9{aiaxat042X1x9W0ta=1g7jara*ay0~0Ga/7N3waua16x8na 8p5a9*a 9,5o0O256Ra88ubIbcaibeasamaobu4z0~0CbU5gazaubn2?bpa:3VaQaH1F8ja2b)aVa}b)0#bxbobfa,040DbY4+a=a@b=bv0_700Sb~64aQaSc23Ub;b/c3bg8ia^c4a%7fc7270g5F030U2F0g0%0N0Lct1)2C0o9I9mbi0d9W2B0$0Ubm0d0I13by6gbA6LbC5sb3ad7}cSb8bG5D5qbObPc$c%c(c)bQbq01co0~cq0T210/9d2F78cy8U86aZ0N0z0J2B8,79a(a|ce7*bB8_5EcTb9cV6PbKb4935odac#c*bfam0d6%b_aDaYc_ci01700hdub@04bXcbaL0~0ccma+7R0o7WdG3`dsa!dCaU0~dxdPaXbh0#bj0NblaBdTa$040ca{4w9#d8b15RdbcY6O7xdfcUdi7Eahc*bPbfdzcDbkbmdL01b{btdqc,dzdBd*cba45D7/339+9;edbJ7zbL6V7 d`c$dmaudpb%d}b#dXdZb$3rb(cfb{0ve5etdrbhdu70d)ezbfc.04cq2G0%aI1)0McB0B0-0U0n0U330$2Y9U0$0/8g0{880i3X0N0$8$c;0#0McN6}cP7BcR8BefbFeh6O8wd?dcdi8B5/d{f985eMcp86338#0{cyd2c`fec|dtd5bza~cQd98{e el5*90f4d:3j8{f8d{euaRc}eIdRdyb^d6dDd%c6e6b?dNb.fpb:fId#bwdVewe1fWcjd%e2e4e2dzchf#dvfVfL75fYcEdYf!f:7ddEfOeFe7fRfH04dSf_2}fKfTcf70dFfo6g0H6A6h6v6j6s1h0e6mgi2S2N0A1%gf0H6k7i0)0+0-0M04.
Temps de calcul pour le tri fusion et le tri par sélection

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(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

Votre figure

Votre tracé sera ici

Solution

Le tri fusion est bien plus efficace

💻 A vous de jouer 5

Compléter le script suivant :

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(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
Évaluations restantes : 5/5

.128013w]itkc[v8o-)yl0bqp_.PL3(a;gE=/m4rse97Sf,d 612:é5nuCh050P0J0e0z0d0o0I0Q0g0o0z0I0I0D010e0d0s010406050I0Y0F0F0z0H0n040M0k0o0Y0^0k0X050E0 1113150}0s04051l1e1o0E1l0}0P0d0i0-0/0;0?0/0X0B0Y0z0B0J0l0s0n0e0!1c0Q0!0d0B0!0o1Q0!0e0{050(0q0o0J1x0:0=011P1R1T1R0e1Z1#1X0e0H1m1L0-180I0s0z0X0?0T011%1z010N0*0J0X0z0F0J1X1|1~231)261#292b0{0a0Q0v0H0k0s0k0I0d1b0X0Q0$1`0H0H0J0g2w1e2e0X1m0E1L2J1?1^1@1Y0P2g1A0d0X282t1X1u1w0.1(2T2V0X0k2Z1X0s2C1m2H2J2:0~1}2x2#242)0H120o1X0z1O2C0N0?030t0t0g2*0J1T2(0k0l0S0p3e0{0Q0S1e0z2;2@0|2?2f2_1)2{2}2 310J33013537393b2W3e3g21040Q0T3l3n1~3p2H2S013u0z2~1m300!323436380$3E2)3G0l0x3i0x3M2G3o0}3Q3s0?3T3V053X3Z3A3#3D2U3F3f0l0G3i0G3/1f3;3q2^1y3t0k2|3U3w3Y3y3!3C3%413)430W3i0W482:3=2@3R3_4i3}3B3$3a4o3d430R3i0R4u4a3?4d3^4f3v3W3x3z4C403c3*0L3i0L4L3O4w3r4O3S4Q4h4S4j4U3 4n4X430j3i0j4$2I4(4c2$4+4g3`3|4k3~4m4E4?3g0K3i0K4{3P4x3@504R3{4T4l4D3(4G3g3f0{3f5d4}4y4,525k555m4F3*0S0S5r3k0E3m3:4%4b5v514A544V4=425p3I0S3L5H3N4|5L5g4z4.4B4;575S3e3,040S3.5X5J2I1p2.1e2Z2M0P1^2R5g4D2Y1v1m2-0J2/3o5=1m4D662f0d0P0?362H5C3w6d6f565n6i0Q2k0J6l5A583h2J5I4N4 0f0{0$0N685!4*0b3i6E6y2`0N0{1?0d0t2U0I0J0H2F493O6F4 0`040y6J5f4*0X6N0z0q6%4)6Z0{0U680Q6Y2`0q0{1T0I0e6.4~246!0m6?6^1)0k0{0l020B0e0A746K3t6`046|6~6W5?7f0?6!6=7l3p7r5L6k016g2@3*3I5j7v5)6n43216p2a6r7w6m5B7F1X5;7n016H3J0Q7U6 3R0I0P0{020r0Y0k7c7#7%7)7$7(7d7r0}7t3Q7C0t6h435-7B6e7K6t5+3,7H2b6s4W807O6x6(4 7Y3i7U0Q1Z0Q0J6}2y1$0e0n0s1$7j0J687;2=7?7}7x1~3*454S7@7 4p3g45827J7D7M8E876b701)8b7T7U0w300N1c2E0d1N2C0X0i0k0d8o308p8e0H0d0V1$1}0H0Q4f0P2C0-2q0d0;1~0e0u8r7W7@7_3g4r8A8v7L6u4r8G845R8D0l953/7Q8P8d0Q0C0o1#0Q1a0*8{8o02030x0K0A3U0B4f2v0!2b8j8+0d0Q8:0Q6R6T2w0u0Q0Z9u9w0A8h0e9p2x6O8g2x0s0/0g0J8 7:9197930l4I969c5*9e4I9b7~859?8L750?9j8d7*7.a17,7+7/4v9+6l9-4Z9:9_9d5o0l4Z9^8I6uab3M9k9}016A048U0H7e892`0{2U1u9%au6/240k7S2UaB8N3^7h0H1~1G7W5g6!6$7=av1)0F0d5raO4*6!0OaH4y7h2jaY6:6#a*aw041Za-1)720m7qa7aS6c9,7y4@6j978Caf4^ai985+4^6w8Q9k6@7Q6*043a0J2b0X7k2:bbaT0?77040Da$5#6+6-a`aI016!0ha;3^ax0Xaz8qbv3R6!0c90bG92a}59a 9;7EbOb4b13*5ab8ba8daobd0dbr4*bobq7rblaC3tbCbEbK8t4xbM8x435qacaj5+5qbT9`afb`ambYb,bwaq0b1P1#b%4 b#cbaD7!7ba63oc53RaV0{0pce767S1~0PcpbBa/6,bAbx0{bzbGbs04b$b+aobo0lcu01cm5.cybIcKbo7a7ccKbdbfbhbj677Q7pb;cZb?a|b^5p5Eb{b59e5D226qbQ8J3ec,c3c4bZbcbtcOcAcycdcCaZ0{bJcG7Qb)cUc~d3a+cBb=b-cvcFbkcH78cKcM5GdfbwcP9*bLc)0X5C7A308Bc0dwc;7Ic?6u5V8Lc{anc}cEcQ0{b*djdKdicjdk04cJd7bmcLaWcNdsdp9Kdu5C7{dyb0dAb_81c=ad9=c17{5Xc{b!dbd$aPd0dca.dR6Xc!d5dMbpdabe1#cXc$6X0E6a5@655_621e0e5|ej2P2K6,1#2J5`7;0$0(0*0I04.
Temps de calcul pour le tri fusion et le tri par insertion

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(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

Votre figure

Votre tracé sera ici

Solution

Le tri fusion est bien plus efficace

Une vidéo de Cédric Gerland sur le tri fusion et sa complexité⚓︎

Complexité

Le tri fusion a un coût en \(n \log_2 n\)

Bilan⚓︎

Le tri fusion en entier

Python
def fusion(l1, l2):
    """
    Précondition : l1 et l2 sont deux listes triées
    Postcondition : la fonction renvoie une liste triée constituée de la fusion 
    de l1 et l2
    Exemple :
    fusion([2, 3, 5, 8],[1, 4]) renvoie [1, 2, 3, 4, 5, 8]
    """
    n1 = len(l1)
    n2 = len(l2)
    lst = [] # initialisation de la fusion de l1 et l2 
    i1 = 0 # indice qui sert à parcourir l1
    i2 = 0 # indice qui sert à parcourir l2
    while i1 < n1 and i2 < n2 :
        if l1[i1] < l2[i2]:
            lst.append(l1[i1])
            i1 = i1 + 1
        else :
            lst.append(l2[i2])
            i2 = i2 + 1
    if i1 == n1:
        return lst + l2[i2:]
    if i2 == n2:
        return lst + l1[i1:]

def tri_fusion(lst):
    """
    Précondition : lst est une liste
    Postcondition : la fonction renvoie une liste qui est la liste triée
    """
    n = len(lst)
    if n <= 1:
        return lst
    else :
        m = n // 2
        return fusion(tri_fusion(lst[:m]), tri_fusion(lst[m:]))