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 :

🐍 Script 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
🐍 Console Python
>>> 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

###
# testsbksl-nlbksl-nldef max(py-strargs, py-strpy-strkwargs):bksl-nl assert False, "Interdit d'utiliser max."bksl-nlbksl-nlbksl-nlbksl-nlassert sommet([4, 5, 7, 5, 3]) == 7bksl-nlassert sommet([1, 10, 9, 8, 7, 6, 5, 4]) == 10bksl-nlassert sommet([10, 100, 10, 9, 8, 7, 6]) == 100bksl-nlassert sommet([1, 2, 4, 8, 4]) == 8bksl-nlassert sommet([3, 4, 3, 2, 1, 0, -1, -2]) == 4bksl-nlbksl-nlbksl-nlfor i in range(1, 10):bksl-nl for j in range(1, 10):bksl-nl l = list(range(i)) + list(range(i + j, i - 1, -1))bksl-nl assert sommet(l) == i + jbksl-nlbksl-nlbksl-nlbksl-nlclass IntSurcharge():bksl-nl py-undpy-undcompteurpy-undcomparaison = 0bksl-nlbksl-nlbksl-nl def py-undpy-undinitpy-undpy-und(self, x):bksl-nl self.py-undpy-undvaleur = xbksl-nlbksl-nl def py-undpy-undltpy-undpy-und(self, autre):bksl-nl IntSurcharge.py-undpy-undcompteurpy-undcomparaison += 1bksl-nl return self.py-undpy-undvaleur < autre.py-undpy-undvaleurbksl-nlbksl-nl def py-undpy-undgtpy-undpy-und(self, autre):bksl-nl IntSurcharge.py-undpy-undcompteurpy-undcomparaison += 1bksl-nl return self.py-undpy-undvaleur > autre.py-undpy-undvaleurbksl-nlbksl-nl def py-undpy-undnepy-undpy-und(self, autre):bksl-nl IntSurcharge.py-undpy-undcompteurpy-undcomparaison += 1bksl-nl return self.py-undpy-undvaleur != autre.py-undpy-undvaleurbksl-nlbksl-nl def py-undpy-undeqpy-undpy-und(self, autre):bksl-nl IntSurcharge.py-undpy-undcompteurpy-undcomparaison += 1bksl-nl return self.py-undpy-undvaleur == autre.py-undpy-undvaleurbksl-nlbksl-nl def py-undpy-undlepy-undpy-und(self, autre):bksl-nl IntSurcharge.py-undpy-undcompteurpy-undcomparaison += 1bksl-nl return self.py-undpy-undvaleur <= autre.py-undpy-undvaleurbksl-nlbksl-nl def py-undpy-undgepy-undpy-und(self, autre):bksl-nl IntSurcharge.py-undpy-undcompteurpy-undcomparaison += 1bksl-nl return self.py-undpy-undvaleur >= autre.py-undpy-undvaleurbksl-nlbksl-nl @propertybksl-nl def compteur(self):bksl-nl return IntSurcharge.py-undpy-undcompteurpy-undcomparaisonbksl-nlbksl-nl @propertybksl-nl def valeur(self):bksl-nl return self.py-undpy-undvaleurbksl-nlbksl-nlunimodal = [IntSurcharge(i) for i in range(10000)]bksl-nlunimodal.extend([IntSurcharge(i) for i in range(10000, 543, -1)])bksl-nlbksl-nlresultat = sommet(unimodal)bksl-nlbksl-nlvaleur = resultat.valeurbksl-nlcompteur = resultat.compteurbksl-nlassert valeur == 10000bksl-nlassert compteur < 200, "Vous avez utilisé une méthode interdite"bksl-nlbksl-nldel maxbksl-nlbksl-nl 5/5
def sommet(tableau):bksl-nl gauche = 0bksl-nl droite = len(tableau) - 1bksl-nl while droite - gauche > 1:bksl-nl milieu = (...) // 2bksl-nl if tableau[milieu-1] < tableau[milieu] < tableau[milieu+1]:bksl-nl gauche = ...bksl-nl elif tableau[milieu - 1] > ... > ...:bksl-nl droite = ...bksl-nl else:bksl-nl return tableau[...]bksl-nlbksl-nlbksl-nl# testsbksl-nlassert sommet([1, 9, 8, 7]) == 9bksl-nlassert sommet([1, 3, 5, 2]) == 5bksl-nlassert sommet([1, 2, 3, 4, 5, 4, 3, 2, 1]) == 5bksl-nlassert sommet([1, 2, 3, 4, 3, 2, 1, 0, -1, -2]) == 4bksl-nlbksl-nldef sommet(tableau):bksl-nl gauche = 0bksl-nl droite = len(tableau) - 1bksl-nl while droite - gauche > 1:bksl-nl milieu = (gauche + droite) // 2bksl-nl if tableau[milieu-1] < tableau[milieu] < tableau[milieu+1]:bksl-nl gauche = milieubksl-nl elif tableau[milieu-1] > tableau[milieu] > tableau[milieu+1]:bksl-nl droite = milieubksl-nl else:bksl-nl return tableau[milieu]bksl-nlbksl-nlbksl-nl# testsbksl-nlassert sommet([1, 9, 8, 7]) == 9bksl-nlassert sommet([1, 3, 5, 2]) == 5bksl-nlassert sommet([1, 2, 3, 4, 5, 4, 3, 2, 1]) == 5bksl-nlassert sommet([1, 2, 3, 4, 3, 2, 1, 0, -1, -2]) == 4bksl-nlbksl-nl