Elément de pic d'un tableau
Étant donné un tableau d'entiers. Ecrivez un algorithme qui perment de retourner un élément de pic.
Un élément de tableau est un pic s'il est supérieur à ces voisins gauche et droite
- Si le tableau est trié dans l'ordre croissant, l'élément de pic est le dernier élément du tableau
- Si le tableau est trié dans l'ordre décroissant, l'élement de pic est le premier élément du tableau
T= [1,4,3,6,7,5]
4 et 7 sont des éléments de pic dans le tableau
Solution 1 : Naive
Parcourir le tableau Trouver un élément supérieur a ces voisins, retourner cet élément
Complexité O(n)
def pic(tab): pt=0 for i in range(1,len(tab)-1): if tab[i]>tab[i-1] and tab[i]>tab[i+1]: return tab[i] # si on a pas trouvé un tel élément à l'interieur du tableau # retourner le premier ou le dernier élément if tab[0]>tab[-1]: return tab[0] else: return tab[-1] tab=[9,2,7,12,2] print(pointe_recursive(tab,0,len(tab))) ==> 12
Solution 2 : Dichotomie
sélectionner un élément de manière aléatoire retourner cet élément si il est supérieur à ces voisins sinon si cet élément est inférieur à son voisin gauche, rechercher dans la partie gauche sinon, rechercher dans la partie droite // Utiliser la recherche dichotomique Initialiser debut=0, fin = taille-1 répéter jusqu'à trouver l'élément de pic milieu=(debut+fin)/2 si tab[milieu] est un élément de pic retourner tab[milieu] sinon si tab[milieu]> tab[milieu-1] debut=milieu+1 sinon fin=milieu-1 fin si
def pic_recursive(tab,debut,fin): if debut==fin: return tab[debut] else: milieu=(debut+fin)//2 if tab[milieu]>tab[milieu-1] and tab[milieu]>tab[milieu+1]: return tab[milieu] else: if tab[milieu]>tab[milieu-1]: return pointe_recursive(tab,milieu+1,fin) else: return pointe_recursive(tab,debut,milieu-1) tab=[9,2,7,12,2] print(pointe_recursive(tab,0,len(tab))) ==> 12 def pic_iterative(tab): debut=0 fin=len(tab) while (debuttab[milieu-1] and tab[milieu]>tab[milieu+1]: return tab[milieu] else: if tab[milieu]>tab[milieu-1]: debut=milieu+1 else: fin=milieu-1 return tab[debut] print(pic_iterative(tab,0,len(tab))) ==> 12
Partager ce cours avec tes amis :
Rédigé par
ESSADDOUKI
Mostafa