Échauffement

Pour l'écriture des fonctions des deux questions suivantes, on n'utilisera pas les fonctions déjà existantes, la seule opération autorisée sur les listes est la construction de la forme :

for element in liste:
    ...

Question 1 Réécrire, en utilisant la forme précédent et sans utiliser les fonctions prédéfinies de Python, les fonctions usuelles suivantes sur les listes :

• maximum qui retourne le plus grand élément d'une liste,
• somme qui retourne la somme de tous les éléments d'une liste d'entiers,
• contient qui, étant donné une liste l et une donnée e, retourne True si e est présent dans l, et False sinon.

Question 2 Écrire une fonction moyenne_olympique qui, étant donné une liste l de nombres de longueur au moins 3, retourne la moyenne des valeurs de l calculée après en avoir retiré la plus grande et la plus petite valeurs.

>>> moyenne_olympique([13, 12, 1, 12, 19, 11])
12.0

Vous avez maintenant le droit, à nouveau, d'utiliser toutes les fonctions Python que vous voulez.

Sur la route

Le long d'une route se trouvent ${`n`}$ maisons dont les positions sont données par des réels ${`x_0`}$ à ${`x_{n - 1}`}$ (pas forcément dans l'ordre). Elles sont représentées en Python par un tableau positions.

Question 3 Écrire une fonction plus_proches (resp. plus_eloignees) qui, étant donné un tableau de positions de maisons, renvoie la distance des deux maisons les plus proches (resp. éloignées). Quelle est sa complexité ? Est-elle optimale ?

>>> pos = [42, 35, 85, 4, 18, 73, 58]
>>> plus_proches(pos)
7
>>> plus_eloignees(pos)
81

Question 4 Définir une fonction distances qui, étant donné un tableau pos, renvoie un tableau à double entrée dont la case d'indices ${`(i, j)`}$ contient la distance ${`\\bigl|x_i - x_j\\bigr|`}$.

>>> distances([42, 35, 18, 49])
[[0, 7, 24, 7], [7, 0, 17, 14], [24, 17, 0, 31], [7, 14, 31, 0]]

Question 5 Écrire une fonction plus_eloignees2 qui, étant donné un tableau de distances comme obtenu dans la question précédente, renvoie la distance maximale entre deux maisons.

Question 6 Pouvez-vous faire cela en temps linéaire ? Prouvez la correction du programme proposé.

Des hauts et des bas

Dans les exercices suivants, nous allons travailler avec une liste d'entiers que l'on pourra voir comme un profil topographique (autrement dit, une coupe d'un relief).

Plateaux

Étant donné une liste d'entiers, un plateau est un succession de valeurs égales. La largeur du plateau est alors le nombre de valeurs successives égales (un plateau peut être de largeur 1).

Question 7 Écrire une fonction plateau qui, étant donné une liste d'entiers donnée en argument, retourne la valeur du plateau le plus large (on prendra la première valeur si plusieurs plateaux sont une largeur maximale).

Ainsi, dans l'exemple suivant, les plateaux les plus larges sont de largeur 3, de valeurs 2 puis 8.

Sommets

Étant donné une liste d'entiers l, le i-ème élément de la liste est un sommet si l[i] est strictement supérieur à l[i - 1] et à l[i + 1] (ces deux valeurs devant nécessairement être définies).

Ainsi, dans l'exemple suivant, la liste a 3 sommets :

Question 8 Écrire une fonction sommets qui renvoie le nombre de sommets de la liste donnée en argument.

Ainsi, pour l'exemple précédent,

>>> sommets([1, 2, 3, 2, 1, 2, 3, 4, 3, 4, 5, 2])
3

Creux

Nous allons à nouveau considérer une liste d'entiers positifs que l'on voit comme la forme d'un relief. On y trouve des sommets et des creux. Si l'on verse de l'eau, les creux se remplissent, comme dans l'exemple suivant :

Le nombre de carrés remplis d'eau est égal à ${`5`}$.

Question 9 Écrire une fonction remplissage qui, étant donné une liste d'entier, retourne le nombre de carrés remplis d'eau avec cette procédure.

Pour reprendre l'exemple précédent, on veut :

>>> remplissage([1, 2, 3, 2, 1, 2, 3, 4, 3, 4, 5, 2])
5

Question 10 Pouvez-vous faire cela en temps linéaire ?