Initiation à l'algorithmique

Notification de cookies

Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies. Plus d'informations

Elément majoritaire d'un tableau

Ecrivez un algorithme qui prend un tableau et affiche l’élément majoritaire (s’il existe), sinon retourner NIL. Un élément majoritaire dans un tableau A de taille n est un élément qui apparaît plus de n/2 fois (et il existe donc au plus un de ces éléments). Exemple : A= [2, 6, 2, 2, 6, 2, 2, 8, 2, 1] (n=10) L’élément 2 apparait plus que 5 fois
Solution 1 : Naive

Utiliser deux boucles

            dans la boucle intérieure calculer le nombre d'occurences de chaque élément
            dans la boucle extérieure verifier si le nombre d'occurence est supérieur à taille/2, et retourner cet élément

            pour i=1 à n
              cpt=0
              pour j=1 à n
                SI tab[j]=tab[i] alors 
                  cpt=cpt+1
              SI cpt>=(n/2) alors
                retourner tab[i]
            retourner NIL
        

Complexité O(n2)

          def majoritaire(tab):
            n=len(tab)
            for i in range(n):
              cpt=0
              for j in range(n):
                if tab[i]==tab[j]:
                  cpt+=1
              if cpt>(n//2):
                return tab[i]
            return None
      
Solution 2 : Tableau trié

Utiliser un tableau trié

            1 - Trier le tableau
            2 - Parcourir le tableau et compter le nombre d'occurences
              3 - si le nombre d'occurences d'un élément est supérieur à taille/2, retourner cet élément
            4 - Retourner NIL Sinon.
        

Complexité de tri est O(nlogn) avec le tri rapide

Complexité de la boucle est O(n)

Donc complexité de cet algorithme est O(nlogn)

            def majoritaire(tab):
              n=len(tab)
              cpt=1
              indice=0
              for i in range(1,n):
                if cpt>(n//2):
                  return tab[indice]
                if tab[i]==tab[indice]:
                  cpt+=1
                else: # si tab[i] est différent de tab[indice] 
                  indice=i;
                  cpt=1
              return None
        
Solution 3 : Algorithme de Boyer–Moore

Cette méthode ne fonctionne que lorsque cet élément majoritaire existe dans le tableau. Sinon, cette méthode ne fonctionnera pas

l'algorithme est décomposé en deux étapes :
  • La première étape donne l'élément qui peut être un élément majoritaire dans le tableau. S'il y a un élément majoritaire dans un tableau, cette étape renverra définitivement l'élément majoritaire, sinon elle retournera un candidat pour l'élément majoritaire.
  • Vérifiez si l'élément obtenu à partir de l'étape 1 est un élément majoritaire. Cette étape est nécessaire car nous ne sommes pas toujours sûrs que l'élément renvoyé par la première étape est un élément majoritaire.

Etape 1 :

              1 - Initialiser le compteur pour le candidat à 0
              2 - Parcourir le Tableau
                2-1 - SI compteur=0 alors candidat=tab[i]; compteur+=1
                2-2 - SINON 
                  2-2-1 - SI candidat=tab[i] ALORS compteur+=1
                  2-2-1 SINON compteur-=1
      

cette étape consiste à parcourir le tableau et maintient le compteur pour le candidat.

  • Si l'élément suivant est identique, incrémentez le compteur,
  • si l'élément suivant n'est pas identique, décrémentez-le et
  • si le nombre atteint 0, modifiez le candidat en élément actuel et réinitialiser le compteur

Etape 2 :

          1 - SI compteur=0 ALORS pas d'element majoritaire
          2 - SINON
            2-1 - parcourir le tableau et compteur le nombre d'occurences pour le candidat
            2-2 - SI compteur > n/2 ALORS retourner candidat
            2-3 - ELSE retourner NIL
      

Complexité : O(n)

      # ETAPE 1
      def TrouverCandidat(A): 
          n=len(A)
          cand_indice = 0
          compteur = 1
          for i in range(n): 
              if A[cand_indice] == A[i]: 
                  compteur += 1
              else: 
                  compteur -= 1
              if count == 0: 
                  cand_indice = i 
                  compteur = 1
          return A[cand_indice] 
        
      # ETAPE 2 
      def estMajoritaire(A, cand): 
          n=len(A)
          compteur = 0
          for i in range(n): 
              if A[i] == cand: 
                  compteur += 1
          if compteur > len(A)/2: 
              return True
          else: 
              return False
        
      # TEST
      def Majoritaire(A): 
          # Trouver un candidat
          cand = TrouverCandidat(A) 
            
          # Afficher l'élément majoritaire s'il exist
          if estMajoritaire(A, cand) == True: 
              print(cand) 
          else: 
              print("Pas d'élément majoritaire") 
      
      A = [1, 3, 3, 1, 2] 
      Majoritaire(A)
      

Partager ce cours avec tes amis :

Rédigé par M. ESSADDOUKI

Learning a new programming language is an easy thing, but the most difficult thing is how to design efficient algorithms for real-world problems, so don't be a programmer, be a problems solver.

Cours Similaires :