Le premier minimum local

Alors qu'elle joue sur un chemin dallé, Élodie laisse rouler une balle. En observant les dalles devant elle, elle se rend compte que certaines dalles sont plus basses que les précédentes, d'autres plus hautes.

Elle se pose la question suivante : "Où va s'arrêter la balle ?"

On donne les hauteurs des dalles dans le chemin sous forme d'une liste de nombres entiers positifs. Cette liste compte au minimum deux valeurs.

On garantit que la hauteur de la dernière dalle est strictement supérieure celles de toutes les autres.

Par exemple :

🐍 Script Python

# indices    0  1  2  3  4  5  6  7  8  9 10  11
hauteurs = [10, 8, 7, 5, 5, 4, 3, 6, 6, 5, 4, 12]

Dans l'exemple précédent, illustré par la figure, la balle s'arrête sur la dalle d'indice 6. En effet, la balle s'arrête sur la première dalle dont la hauteur est strictement inférieure à celle de la suivante.

On signale que lorsque deux dalles consécutives sont à la même hauteur, la balle continue de rouler.

Écrire la fonction indice_arret :

• qui prend en argument la liste des hauteurs des dalles (hauteurs),

• et qui renvoie l'indice de la dalle sur laquelle s'arrête la bille. La balle est initialement sur la dalle d'indice 0.

Exemples

🐍 Console Python

>>> hauteurs = [3, 2, 5]
>>> indice_arret(hauteurs)
1

🐍 Console Python

>>> hauteurs = [3, 5]
>>> indice_arret(hauteurs)
0

🐍 Console Python

>>> hauteurs = [10, 8, 7, 5, 5, 4, 3, 6, 6, 5, 4, 12]
>>> indice_arret(hauteurs)
6

###

Lancer from random import randintbksl-nlbksl-nl# Testsbksl-nlhauteurs = [3, 2, 5]bksl-nlassert indicepy-undarret(hauteurs) == 1bksl-nlbksl-nlhauteurs = [3, 5]bksl-nlassert indicepy-undarret(hauteurs) == 0bksl-nlbksl-nlhauteurs = [10, 8, 7, 5, 5, 4, 3, 6, 6, 5, 4, 12]bksl-nlassert indicepy-undarret(hauteurs) == 6bksl-nlbksl-nl# Tests supplémentairesbksl-nlassert indicepy-undarret([0, 1]) == 0bksl-nlassert indicepy-undarret([0] py-str 10 + [1]) == 9bksl-nlfor py-und in range(100):bksl-nl hauteurs = [randint(1, 100) for py-und in range(randint(1, 100))] + [101]bksl-nl i = [k for k in range(len(hauteurs) - 1) if hauteurs[k] < hauteurs[k + 1]][0]bksl-nl assert indicepy-undarret(hauteurs) == ibksl-nlbksl-nl Valider 5/5 Télécharger Téléverser Recharger Sauvegarder

def indicepy-undarret(hauteurs):bksl-nl ...bksl-nlbksl-nlbksl-nl# Testsbksl-nlhauteurs = [3, 2, 5]bksl-nlassert indicepy-undarret(hauteurs) == 1bksl-nlbksl-nlhauteurs = [3, 5]bksl-nlassert indicepy-undarret(hauteurs) == 0bksl-nlbksl-nlhauteurs = [10, 8, 7, 5, 5, 4, 3, 6, 6, 5, 4, 12]bksl-nlassert indicepy-undarret(hauteurs) == 6bksl-nlbksl-nldef indicepy-undarret(hauteurs):bksl-nl i = 0bksl-nl while hauteurs[i] >= hauteurs[i + 1]:bksl-nl i += 1bksl-nl return ibksl-nlbksl-nl

A

Il s'agit d'une recherche de minimum réalisée avec une approche gloutonne.

Si l'on cherche le minimum de l'ensemble de la liste, l'algorithme utilisé ici n'est pas optimal. Par contre, si l'on cherche comme ici le premier minimum local, l'algorithme donnera à coup sûr la bonne réponse.

La variable i contient l'indice de la dalle sur laquelle se trouve la balle. On l'initialise à 0.

On parcourt ensuite les indices à partir de 0 tant que la hauteur de la dalle suivante est inférieure ou égale à celle de la dalle "actuelle".

La garantie que le dernier élément de la liste est le strictement supérieur aux précédents nous assure que l'on sortira bien de la boucle avant que i ne soit égal à len(hauteurs)-1 (ce qui entrainerait une erreur au moment d'accéder à hauteurs[i+1]).

Une fois sorti de la boucle, on renvoie la valeur de l'indice i.

Z