Initiation à l'algorithmique

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
Exemple :
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 Mostafa Sedoki
Computer science teacher and the founder of the e-learning platform "developpement-informatique.com", my mission is to provide high-quality courses for free to all computer science students and teachers

Cours Similaires :