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

.128013(og)5wrh36a [;v,c8lS/ekm=4p9nib1:y-2+]ut_dPf7s0050Q0w0O0l0E0t0U0m0r0t0l0U0U0z010O0E0B010406050U0N0y0y0l0h0I040u0c0t0N0:0c0D050v0`0|0~100^0B04051g191j0v1g0^0Q0E0p0(0*0,0.0*0D0d0N0l0d0w0J0B0I0O0i170m0i0E0d0i0t1L0i0O0?050Z0F0t0w1s0+0-011K1M1O1M0O1U1W1S0O0h1h1G0(130U0B0l0D0.0K011Y1u010S0#0w0D0l0y0w1S1@1_1~1!211W24260?0a0m0R0h0c0B0c0U0E160D0m0X1=0h0h0w0r2r19290D1h0v1G2E1.1:1/1T0Q2b1v0E0D232o1S1p1r0)1Z2O2Q0D0c2U1S0B2x1h2C2E2+0_1^2s2W1 2!0h0}0t1S0l1J2x0S0.030P0P0r2#0w1O2Z0c0J0K0J0G0?0m0G190l2,2/0@2.2a2;1!2?2^2`2|0w2~01303234362R39393d0K3g3i1_3k2C2N013p0l2_1h2{0i2}2 31330X3z2!3B0j3d0j3F2B3j0^3J3n0.3M3O053Q3S3v3U3y2P3A3a0A3d0A3%1a3)3l2:1t3o0c2@3N3r3R3t3T3x3W3_3Y3a0f3d0f3 2+3*2/3K3.493=3w3V354f383a0k3d0k4l413+443-463q3P3s3u4t3^373B0T3d0T4C3H4n3m4F3L4H484J4a4L3@4e4O3a0s3d0s4T2D4V432X4Y473/3;4b3?4d4v4*0J0C3d0C4/3I4o3,4@4I3:4K4c4u3X4x3b0V0?0G0V544;4p4Z4_5b4|5d4w3B0G3c045v5l425n4^4r4{4M4)3`3b1|5x3E0v3h3(4U5A574q4#4s4(4~5H0G3!5x3$5M3G4:5Q4X5S5a4$5c4N5X3|5x3~5$5O5(4E4?5+4`4%4}5e5u4i5x4k5@405P5`2=5o5D5~5s4 0G4z5x4B654m5)5{6a5T5E5V603a0G4Q5x4S6j4D565*6n5,5U5 5t6s4,5x4.6x3H1k2)192U2H0Q1:2M574u2T1q1h2(0w2*3j5^1h4u6#2a0E0Q0.312C5u3r6,6.6E6e1}2f0w6@6d5X1S5@681!0x0?0X0S6%0m6l2=0S0?0U0c0|0Y6%7a1!0=040b7i723-0?1+0w0l0N7o6z4?7l0e0H6%0^662D5A6?016/2/3B5J5a7H6q6F3C0m6{6}5/4g3C2E3h0m7!797p3L0?0d7u0r0i0w787j0.0c0?0z7/7%0y0E0?5k7E3k7~7G6-7I0P6:3a5Z7N827P4 3!7S256|836~7W875$7#7$7x2=752l2q7.7~8m4W4?7=047@8t7:3L0F0?2e7w8v1 7l7n807%0D7r0l1V7t7v8L8n7k0?0e7^8U7;0?0J8Y8H1!7`5i7C8G2s7O847K3{6=896^5H3|8d267U5G7W5;3F8l8B74040g1K1W8%4=8o040Q8q0O8s2+8u9a1!8x8$8A8M7)7+7-993K8x020d0O0o9s578*5x8-3K7l7B7~7D2-3J8/850J62888}5W7W4i8{8f8a5H9O8k8l7#8B8N047`1O0w8S9h8B8x8z9-7%8J9D5R9p0N7,9g3j9i9t0?0L9z5*8p0c8r9@4X7za28w0?0v0vaa1 9B5L6k8T6+8@9M6g9P8g7V5f4z9U9Q6r0Jao9Z9!9~57940E779n8Z7(047s7ua77y0?0naM9b9)0E9+aQ9k8#aV0.9B3fak9j0.7l0MafaW04020t9xa+7qaJ8P1WaLa$9EaOaYaIaSaUa`57a)a;019ua/9yaG8(a=aK9,6$9=a|b1a39(0#aTbd6L7%8xa1bh4?a!a}a)9Gaj9J4o9L8;0J6uap9W7W4Qauaq8~5fbDazaA9#9o047*9`9rb9a%b57?b49%a bm5(a`bA1_3B6HbE8^7W4,bIbF5fb,bN927%944vaF9;aH9%bcbubgbybaa~bkb0c4bW9la}btbr8I0?a*bV9 a-9wb8b~c5c0a@8Rc204aPce3o0?b#cschcnca0?9va:ci9^a?8Qa_c9a{cta}b!c7b$6*cC04bqcL9A7{9Ccva(cgbw41b(ambB514J8/8h5f51b;b.c:707ZbOb_b a4a6cG4X9/bZcxcQ8,c)6@9M5j8?av7Qd9c=c/5u5h7Y04c`930?350U9|bnaH9Fd5cLb)0D5u5wb-df6s3cdeardxc^djc`bPaH942x0O0N0h18c 5{8OcJcR8B7lcucWbicyc!01b39H9Ddv5u7M2{c.dE6s1|dDbKd,dG9Ibebzc*b*6s87d.8@dA3b8c7TbJ9R5f5Yd_d*d}dw6s90e1db6e8`e6b=5u9071aH0r5w030m9f0U0O0Udtd{ald7bB0G9Oehe7aweE6`8eei5X9Y5Nb`0?1Z0w0h0Od2047e7geVd$8JdYeAbWcddZaN040qb49B53e#0?e.dRagcY6Je+cfe-e/cY6we|8V040M8Xe^a,0z9:9}8Be:ezdqeB83d8aoeGem6satelc?5uayePdKeR0,eTe!cB4p7d7f26fxe(cM0be%ffe)cYa#f2c#e~f7aZcY5#fMd%e?e 0?64fT7le@fycX0?aifEb2cgf6f$d07?fa3HaB4X9BfYc(dued5ubDfkfp6sbHfoe36tdGdl04eSeUeWeYfCcsfGccfKcsf#fb7_cYf)fIcMgjf=fcfRgifW045?fZfVfP01f^gugA9Bgxf*a8gzf.bsgte=fOgKe_f(gDgP8)ghgNf5b49/f;2Df?gLfXfe7F9Kf|6GdaeHdcb:g3d:3bb@fsc594g9fDgrbQgc7hgNgfd$e*gHe,gqg#gsgRgNh8djha04fSh6e}hdg$gQgwgSgkaH9Bhhgof+gOhpc5ahhog~hqgVgyhvhAhxcY7}hDhk9.aXh4hChif3hKbohMfThygWf-hwcTf9gvgG5P800v6)6M6!6O6X190O6Rh/2K2Fcq2E6P7D0X0Z0#0U04.