Algo Séquentielle

Identification

Infoforall

Animation de la recherche séquentielle


Cette page présente une animation permettant de comprendre le principe de la recherche sequentielle.

L'algorithme de recherche est sous l'animation.

1 - Animation

On notera que le tableau n'a pas besoin d'être trié.

Recherche séquentielle d'une valeur

Valeur cherchée :

Index 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
Elément 60 89 15 56 82 1 86 97 24 86 75 6 14 69 98 31 37 89 91 56

Recherche séquentielle de la valeur maximale

Index 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
Elément 60 89 15 56 82 1 86 97 24 86 75 6 14 69 98 31 37 89 91 56

2 - Algorithmes

On y présente l'algorithme de recherche de valeur puis l'algorithme de recherche du maximum.

Algorithme de recherche séquentielle

But : trouver si un élément recherché existe bien dans un tableau. S'il existe, on fournit l'index de la première occurence trouvée. Sinon, il renvoie une réponse vide.

Principe : lecture séquentielle et progressive des différents éléments. On renvoie l'index du premier élément qui correspond. VIDE si aucun des éléments n'a correspondu à la recherche.

Description des entrées / sortie

  • ENTREES :
    • tableau : un tableau contenant un ensemble d'éléments.
    • x : un élément voulu qu'on tente de rechercher dans le tableau
    • (optionnelle selon les langages d'implémentation): longueur, le nombre d'éléments dans le tableau
  • SORTIE : une réponse vide (à définir) ou un nombre correspondant à l'index trouvé.

Exemple :

Prenons tableau = [13, 18, 89, 1024, 45, -12, 18]

Index 0 1 2 3 4 5 6
Elément 13 18 89 1024 45 -12 18

L'application de l'algorithme de recherche

  • sur l'élément 89 doit renvoyer 2 (présence à l'index 2).
  • sur l'élément 18 doit renvoyer 1 (présence sur l'index 1 et 6)
  • sur l'élement 105 doit renvoyer une valeur signifiant vide (prenons None comme en Python par exemple, ou -1 pour indiquer qu'il s'agit d'une absence d'index).

La valeur exacte de VIDE doit être gérée au moment de l'implémentation dans un langage.

Description de l'algorithme

    index ← 0

    TANT QUE index < longueur et que tableau[index] est différent de x

      indexindex + 1

    Fin TANT QUE

    SI index < longueur

      Renvoyer index

    Fin Si

    Renvoyer VIDE

Algorithme de recherche de maximum

Principe

On place le premier élément du tableau en tant que valeur maximale. Ensuite, on compare chaque élément lu séquentiellememt à ce maximum : on remplace le maximum si l'élément lu est plus grand.

Description des entrées / sortie

  • ENTREES :
    • tableau : un tableau d'au moins un élément.
    • (optionnelle selon les langages d'implémentation): longueur, le nombre d'éléments dans le tableau
  • SORTIE : la valeur maximale.

Description de l'algorithme

    maxitableau[0]

    index ← 1

    TANT QUE index < longueur

      SI tableau[index] > maxi

        maxitableau[index]

        indexindex + 1

      Fin du SI

    Fin du TANT QUE

    Renvoyer maxi

3 - Python

Recherche séquentielle d'une valeur dans un tableau

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
def trouverIndex(tableau, x) : '''Fonction qui renvoie l'index de l'élément x dans le tableau. None en cas d'échec de la recherche :: param tableau(list) :: un tableau contenant le même type d'élément que le paramètre x :: param x(au choix) :: l'élément qu'on cherche à trouver dans le tableau :: exemples :: >>> test = [10,20,30,40,50] >>> trouverIndex(test, 20) 1 >>> trouverIndex(test, 60) ''' index = 0 longueur = len(tableau) while index < longueur and tableau[index] != x : index = index + 1 if index < longueur : return index return None # Inutile en réalité : ce serait fait automatiquement if __name__ == '__main__' : import doctest doctest.testmod()

Recherche d'une valeur dans un dictionnaire (avec la méthode keys)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
def trouverCle(dictionnaire, x) : '''Fonction qui renvoie la première clé associée à la valeur x dans le dictionnaire. None en cas d'échec de la recherche :: param dictionnaire(dict) :: un dictionnaire :: param x(au choix) :: l'élément qu'on cherche à trouver dans le dictionnaire :: return (comme les clés) :: la clé correspondant à la valeur x :: exemples :: >>> test = {'boucle':'loop', 'données':'data', 'tant que':'while'} >>> trouverCle(test, 'data') 'données' >>> trouverCle(test, 'stack') ''' for cle in dictionnaire.keys() : if dictionnaire[cle] == x : return cle return None # Inutile en réalité : ce serait fait automatiquement if __name__ == '__main__' : import doctest doctest.testmod()

Recherche d'une valeur dans un dictionnaire (avec la méthode items)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
def trouverCle(dictionnaire, x) : '''Fonction qui renvoie la première clé associée à la valeur x dans le dictionnaire. None en cas d'échec de la recherche :: param dictionnaire(dict) :: un dictionnaire :: param x(au choix) :: l'élément qu'on cherche à trouver dans le dictionnaire :: return (comme les clés) :: la clé correspondant à la valeur x :: exemples :: >>> test = {'boucle':'loop', 'données':'data', 'tant que':'while'} >>> trouverCle(test, 'data') 'données' >>> trouverCle(test, 'stack') ''' for (cle, valeur) in dictionnaire.items() : if valeur == x : return cle return None # Inutile en réalité : ce serait fait automatiquement if __name__ == '__main__' : import doctest doctest.testmod()

Recherche du maximum dans un tableau

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
def trouverMax(tableau) : '''Fonction qui renvoie la valeur maximale lue dans le tableau :: param tableau(list) :: un tableau d'éléments qu'on peut comparer :: return (type en fonction du tableau) :: la valeur maximale :: exemples :: >>> test = [10,20,60,40,50] >>> trouverMax(test) 60 >>> test = [10,20,60,40,50,100] >>> trouverMax(test) 100 >>> test = [100,20,60,40,50] >>> trouverMax(test) 100 ''' maxi = tableau[0] for index in range( 1, len(tableau) ) : if tableau[index] > maxi : maxi = tableau[index] return maxi if __name__ == '__main__' : import doctest doctest.testmod()

Recherche du minimum dans un tableau

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
def trouverMin(tableau) : '''Fonction qui renvoie la valeur minimale lue dans le tableau :: param tableau(list) :: un tableau d'éléments qu'on peut comparer :: return (type en fonction du tableau) :: la valeur maximale :: exemples :: >>> test = [10,20,60,40,50] >>> trouverMin(test) 10 >>> test = [10,20,60,40,50,100] >>> trouverMin(test) 10 >>> test = [100,20,60,40,50] >>> trouverMin(test) 20 ''' mini = tableau[0] for index in range( 1, len(tableau) ) : if tableau[index] < mini : mini = tableau[index] return mini if __name__ == '__main__' : import doctest doctest.testmod()

Recherche de la moyenne dans un tableau

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
def trouverMoy(tableau) : '''Fonction qui renvoie la valeur moyenne des valeurs du tableau :: param tableau(list) :: un tableau NON VIDE d'entiers ou de flottants :: return (float) :: la valeur moyenne :: exemples :: >>> test = [10,20,60,40,50] >>> trouverMoy(test) 36.0 >>> test = [100,20,60,40,50] >>> trouverMoy(test) 54.0 ''' somme = 0 longueur = len(tableau) for index in range(longueur) : somme = somme + tableau[index] return somme / longueur if __name__ == '__main__' : import doctest doctest.testmod()

Article publié le 11 04 2020
Dernière modification : 13 04 2020
Auteur : ows. h.