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
