Aller au contenu

Sommet d'un tableau unimodal

Sommet d'un tableau unimodal⚓︎

Un tableau unimodal est un tableau :

  • comportant au moins trois éléments
  • dont les premiers sont strictement croissants, jusqu'à un indice i,
  • dont les éléments, à partir de i, sont strictement décroissants.

Le sommet d'un tableau unimodal est sa plus grande valeur.

Ainsi :

  • [1, 2, 3, 2, 1, 0] est un tableau unimodal, son sommet est 3.
  • [1, 2, 3, 5, 10, 9] est un tableau unimodal, son sommet est 10.
  • [1, 2, 3] n'est pas un tableau unimodal, il n'y a pas de descente à la fin,
  • [1, 2] non plus, il n'y a pas assez d'éléments (au moins trois),
  • [5, 3, 0] non plus, il n'y a pas de montée au début.

Remarquons bien que le sommet n'est jamais la première valeur ni la dernière valeur.

Objectif⚓︎

Écrire une fonction efficace afin de déterminer le sommet du tableau unimodal.

La fonction reçoit en paramètre un tableau intitulé valeurs, qu'on supposera unimodal, sous la forme d'une liste Python et renvoie son sommet.

L'emploi de la fonction max ou de tri est interdit dans ce sujet.

Ci-dessous une animation de la recherche du sommet avec les valeurs :

Python
valeurs = [1, 2, 3, 4, 5, 6, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3]

Recherche du sommet

Principe de l'algorithme :

On cherche à déterminer l'indice de la valeur maximale.

C'est l'indice i tel que valeurs[i] > valeurs[i - 1] et valeurs[i] > valeurs[i + 1]. Pour cela on débute avec des indices gauche = 0 et droite = len(tableau) - 1 permettant de couvrir tout le tableau. À chaque étape, les variables gauche ou droite vont être modifiées. On appelle l'indice milieu, l'indice central entre les indices gauche et droite. On examine l'ordre dans lequel sont rangés les éléments respectivement d'indice gauche, milieu et droite.

  • Si ces éléments sont rangés par ordre croissant cela signifie que le sommet est situé à droite de milieu.
  • Si ces éléments sont rangés par ordre décroissant cela signifie que le sommet est situé à gauche de milieu
  • Sinon, on a trouvé le sommet !

Algorithme naïf ?

Il est très simple de déterminer le sommet en parcourant de gauche à droite le tableau.

Notre objectif est de le faire avec un bien meilleur coût.

On rappelle que le tableau donné sera unimodal.

Exemples
Python Console Session
>>> sommet([1, 2, 0])
2
>>> sommet([1, 9, 8, 7])
9
>>> sommet([1, 3, 5, 2])
5
>>> sommet([1, 2, 3, 4, 5, 4, 3, 2, 1])
5
>>> sommet([1, 2, 3, 4, 3, 2, 1, 0, -1, -2])
4
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

.128013uev6pr_Shf;nkly,t-wm375b)sc]1 9d/(oa+P08[=2gi4:050G0c0r0K0T0o0A0E0B0o0K0A0A0Q010r0T0f010406050A0b0u0u0K0g0p040i0J0o0b0:0J0m050H0`0|0~100^0f04051g191j0H1g0^0G0T0d0(0*0,0.0*0m0S0b0K0S0c0s0f0p0r0j170E0j0T0S0j0o1L0j0r0?050Z0y0o0c1s0+0-011K1M1O1M0r1U1W1S0r0g1h1G0(130A0f0K0m0.0R011Y1u010k0#0c0m0K0u0c1S1@1_1~1!211W24260?0a0E0M0g0J0f0J0A0T160m0E0X1=0g0g0c0B2r19290m1h0H1G2E1.1:1/1T0G2b1v0T0m232o1S1p1r0)1Z2O2Q0m0J2U1S0f2x1h2C2E2+0_1^2s2W1 2!0g0}0o1S0K1J2x0k0.030h0h0B2#0c1O2Z0J0s0R0s0D0?0E0D190K2,2/0@2.2a2;1!2?2^2`2|0c2~01303234362R39393d0R3g3i1_3k2C2N013p0K2_1h2{0j2}2 31330X3z2!3B0v3d0v3F2B3j0^3J3n0.3M3O053Q3S3v3U3y2P3A3a0U3d0U3%1a3)3l2:1t3o0J2@3N3r3R3t3T3x3W3_3Y3a0x3d0x3 2+3*2/3K3.493=3w3V354f383a0e3d0e4l413+443-463q3P3s3u4t3^373B0w3d0w4C3H4n3m4F3L4H484J4a4L3@4e4O3a0O3d0O4T2D4V432X4Y473/3;4b3?4d4v4*0s0F3d0F4/3I4o3,4@4I3:4K4c4u3X4x3b0N0?0D0N544;4p4Z4_5b4|5d4w3B0D3c045v5l425n4^4r4{4M4)3`3b1|5x3E0H3h3(4U5A574q4#4s4(4~5H0D3!5x3$5M3G4:5Q4X5S5a4$5c4N5X3|5x3~5$5O5(4E4?5+4`4%4}5e5u4i5x4k5@405P5`2=5o5D5~5s4 0D4z5x4B654m5)5{6a5T5E5V603a0D4Q5x4S6j4D565*6n5,5U5 5t6s4,5x4.6x3H1k2)192U2H0G1:2M574u2T1q1h2(0c2*3j5^1h4u6#2a0T0G0.312C5u3r6,6.6E6e1}2f0c6@6d5X1S5@681!0n0?0X0k6%6l1 0t3d78723-0k0?0A0J0|0Y7d6z4?0=040I7m4W5{0?1+0c0K0b7s4=1 7p0z0V6%0^662D5A6?016/2/3B5J5a7L6q6F3C0E6{6}5/4g3C2E3h0E7(0E793o0?0S7y0B0j0c6%7*7e010J0?0Q7?7+0.0u0T0?5k7I3k847K6-7M0h6:3a5Z7R887T4 3!7W256|896~7!8d5$7)7@7n2=752l2q7=848s7t1 7`047|8z7~3L0y0?2e7A3K7p7r867^0m7v0K1V7x7z8Q8t1!7D7}7^8D0s8$8Z7 815x7G8M7S8a7O3{6=8f6^5H3|8j267Y5G7!5;3F8r8H74040t1K1W8*8B7,040G8w0r8y2+8A7B1!8(9b9l3-7-7/7;9o3K8D020S0r0l9u57805i8M577p7F847H2-3J8;8b0s628e8 5W7!4i8}8l8g5H9Q8q8r7)8H8S04801O0c8X9j8H8D8F9/7^8O9F5*9r0b7:9i3j9k9v0?0L9B9`9e9g9~6L9@0?0za44?8D0H0Had1 9D045L6k8Y6+8_9O6g9R8m7Z5f4z9W9S6r0sas9#9$a057960T778G8R8T8V7y9_7o0?0PaP8u9*0#0T9-aT9m0?8)ao9p01ak3fa%8N0?0Caia!04020o9za:9q047waOa,9GaRaZa`9+aX9.6$aa04a/aK8+7_0?a?a^ba9ca`a|b5a9bb7paSa~a5b3aYbpaea2b1a)8-a+9Lbma.9IanbAap6@9O6uat9Y7!4Qayau905fbJaDaE9%aL047.9|9tbga(9;a_3L0?brbk5(a,9N8?0s6HbK8`7!4,bObL5fb=bT947^964vaJ9?bb9)bjbwbnbw9)b+bw9nbtajbyc8a.b(9w9y9Ab#4paM1Wa}bFa(c9cf9dcccw0.7pb9c4bhbca=cmb(c68Ucrb,6*cub0czb)aV9,cM9:bvcQa*cib8bD41b.aqb:514J8;8n5f51b`b@c.707%bUb c58v0J8xck7{cIb*aWbsbEb64ob/1_5u5hc+8_c-d96`8kaz7U5jc?04c^950?350Aa87Jb7c#5Pc%bHb:5v8^dh6e3cc:dd6s5w93c^bVbb962x0r0b0g18co5Rcq8WcZboctcpcSb4cZcCc$dYd70m5u7Q2{c,avd,df8~bP9T5f0D7Q5$9Kd5bG899O5YdAd@aAe2dEd:6s8p3hd}bld 7Nd86s92d.dce83b8|7Xe4di9271bb0B5w030E9h0A0r0A8/dwe0dy9QejdB5X9Veob{61dkdn041Z0c0g0rd0047i7keUcQ8OdXd~a(cYe!0?0qb(ak53e*04e,dS4Xak6JdYa e;e-8-6we`4XcBace?bu8E9=9 8He.eCd)c(eg3baseHep6eaxeLc;5uaC5Nc00?eReTeVeX26eZf0aQ7qe$ede(che:e=cDfD0?5#fy7Ce+e}0?64fL8!fNf4cg0?ame%a-b8f3fHa1f6fO04fQd(fYd*5ubJfheM6sbNfldF3bbSfpdLfr0,eSfxf8bWfv7le:0IfBdsbbe)fRcAfTf$9C8-fXfCfZfGg2ga8-fKfYe{gl3HaFe@8-5?gc017pgs2Dgu4?akf+gjgrf)gxgqf1gegmcEakgpgHgMe|fU1!akgig9cEgAf)bzgLfz0Cf#gOb$7{f7gtf98-gGb-fcdxfe0Db=f;fm6Gd=9Xg~3bb}f|cE96fsg1g:g37jfwcZg7bwgbg(fMgUgfgvfWcZgBdlg;fJhogJhtgV8,hsfFf)gYcNgkg$hvhlgE8-83gyg#hwcFa$gyhhgSfzhpgD8Ca#hgghd$g+habb9;g/gChr04gKdv2-0H6)6M6!6O6X190r6Rh^2K2FcKh=0H6P7H0X0Z0#0A04.