EXAMEN_Difficile_Vallée

Considérons une liste d’entiers de taille quelconque.

Nous vous demandons d’implémenter un programme permettant de déterminer la plus grande vallée (voir définition ci-dessous) au sein de cette liste d’entiers. Pour résoudre le problème, vous allez devoir écrire trois méthodes.

Exemple : Considérons par exemple la liste d’entiers suivant : tab = {3, 6, 7, 10, 13, 11, 11, 12, 10, 9, 7, 5, 4, 3, 3, 4, 3, 4, 2, 1, 2} et la représentation de cette liste dans le plan cartésien, les indices du tableau étant représentés sur l’axe X et les valeurs correspondantes (éléments de la liste) étant représentées sur l’axe Y (Figure 1).

Définition d’une vallée : Un intervalle d’indices \([i,j]\) de cette liste, est considéré comme une vallée si les valeurs de la liste pour les indices allant de \(i\) à \(j\) (\(i\) et \(j\) compris) sont toutes inférieures ou égales aux valeurs de la droite reliant les points \(i\) et \(j\), pour leur indice respectif (notion proche de la notion de concavité d’une fonction). Autrement dit, un intervalle d’indices \([i, j]\) est considéré comme une vallée si les points du graphe (tel que représenté en Figure 1) compris entre les indices \(i\) et \(j\) se trouvent toujours sur ou sous la droite reliant les deux points \((i, tab[i])\) et \((j, tab[j])\). La taille d’une vallée est donnée par la valeur absolue de la différence entre les deux positions \(i\) et \(j\). Afin d’illustrer cette définition, considérons la même liste d’entiers que ci-dessus, cette fois représenté en Figure 2.

La liste contient plusieurs vallées, dont certaines sont représentées sur la Figure 2. Par exemple, l’intervalle d’indices \([4, 7]\) est une vallée car les points \(4\), \(5\), \(6\) et \(7\) se trouvent sous la droite reliant les points \(4\) et \(7\), ou sur elle pour les points frontière. Il en est de même pour les intervalles \([7, 17]\) et \([10, 15]\) qui sont également des vallées. A l’inverse, l’intervalle \([4, 15]\) n’est pas une vallée car on peut observer sur la Figure 2 que certains points compris dans cet intervalle sont strictement au-dessus de la droite reliant les points \(4\) et \(15\) (en pointillé sur la Figure 2).

Dans cet exemple, la plus grande vallée de la liste est celle déterminée par l’intervalle \([7, 17]\) et a une longueur de \(10\). Afin de simplifier le problème, nous n’allons considérer l’existence de vallées qu’entre les différents maxima locaux de la liste. Il ne faut donc tester que ces points de début et fin d’intervalle « candidats vallée ». Dans l’exemple ci-dessus, \([10, 15]\) n’est donc plus considéré comme une vallée.

Définition d’un maximum local : Un élément d’une liste est considéré comme un maximum local s’il est strictement plus grand que ses éléments voisins (de gauche et de droite). Notons que nous considérons que les extrémités du tableau (premier et dernier indice) ne peuvent pas être un maximum local.

A partir de ces informations, vous allez devoir écrire trois méthodes, au cours des quatre étapes suivantes.

עליך להדביק את הפקודה הזאת במסוף שלך:

הסיסמה להתחברות אל

שאלה 1: Maxima locaux

Dans un premier temps, nous vous demandons donc d’implémenter une fonction maximaLocaux qui prend en argument une liste d’entiers et qui renvoie une liste d’entiers contenant les indices de tous les maxima locaux de la liste passé en argument, conformément à la définition de maxima local donnée ci-dessus. Signature de la fonction (n'oubliez pas de la réécrire) :

def maximaLocaux(tab)

שאלה 2: Vallée

Pour cette question vous pouvez considérer que vous disposez d’une fonction valeurDroite (déjà écrite) qui prend en argument les coordonnées de deux points \((x_A, y_A)\) et \((x_B, y_B)\) ainsi qu’un nombre et qui renvoie la valeur (hauteur y) au point de la droite passant par les deux points \((x_A, y_A)\) et \((x_B, y_B)\). Rappelons que l’équation de la droite passant par les deux points \((x_A, y_A)\) et \((x_B, y_B)\) est définie par :

\begin{equation*} \frac{y-y_A}{x-x_A}=\frac{y_A-y_B}{x_A-x_B} \end{equation*}

En isolant le y dans cette équation, on obtient la hauteur de la droite au point d’abscisse x. Vous devez donc utiliser la fonction suivante :

def valeurDroite(xA, yA, xB, yB, x)

Ici, nous vous demandons d’écrire une fonction estVallee prenant en argument une liste d’entiers tab ainsi que deux nombres entiers a et b et renvoyant un booléen indiquant si l’intervalle d’indices [a,b] dans la liste tab est une vallée (true) ou non (false).

La fonction estVallee doit utiliser la fonction valeurDroite, et n’oubliez pas de vous référer à la définition de vallée donnée précédemment.

Signature de la fonction (n'oubliez pas de la réécrire) :

def estVallee(tab, a, b)

שאלה 3: Plus grande vallée

Enfin, nous vous demandons d’implémenter la fonction principale plusGrandeVallee prenant en argument une liste d’entiers tab et renvoyant une liste d’entiers contenant les indices de début et de fin de la plus grande vallée identifiée au sein de cette liste tab. Pour le cas où il n'y a pas de vallée, la fonction plusGrandeVallee doit retourner la liste [0,0] La fonction plusGrandeVallee doit utiliser les fonctions maximaLocaux et estVallee décrites ci-dessus. Les sous-questions étant indépendantes, vous pouvez utiliser les fonctions maximaLocaux et estVallee grâce à leurs signatures données ci-dessus, même si vous n’avez pas réussi à répondre à ces sous-questions.

Signature de la fonction (n'oubliez pas de la réécrire) :

def plusGrandeVallee(tab)

יוצרים	Maxime Postaire, Jean-François Sambon
מועד הגשה	אין מועד הגשה
מגבלת הגשות	אין הגבלה

מידע

כניסה