Algorithme de recherche séquentielle dans un tableau
Plan de tutoriel
1- Principe de l'algorithme de recherche séquentielle dans un tableau
2- Algorithme de recherche séquentielle dans un tableau
3- Programme Python
Principe de l'algorithme de recherche séquentielle dans un tableau
Le programme a pour objectif de rechercher une valeur donnée dans un tableau et de déterminer si cette valeur existe ou non parmi les éléments du tableau. Il utilise une recherche séquentielle, également appelée recherche linéaire.
Tout d’abord, le programme demande à l’utilisateur de saisir la taille du tableau, comprise entre 2 et 14 éléments. Ensuite, les différents éléments du tableau sont saisis par l’utilisateur et enregistrés dans les premières cases du tableau.
Après le remplissage du tableau, le programme demande à l’utilisateur de saisir la valeur à rechercher, notée x. Cette valeur sera comparée successivement avec les éléments du tableau.
La recherche commence à partir de la première case, d’indice 0. Le programme compare t[i] avec x. Si les deux valeurs sont différentes, l’indice i est augmenté de 1 afin de passer à l'élément suivant. Cette opération est répétée jusqu’à ce que la valeur recherchée soit trouvée ou que la dernière case du tableau soit atteinte.
Lorsque t[i] == x, cela signifie que la valeur recherchée existe dans le tableau. La fonction recherche() retourne alors True. Si le parcours du tableau se termine sans trouver x, la fonction retourne False.
Enfin, le programme principal affiche un message indiquant si la valeur recherchée a été trouvée ou non dans le tableau.
Algorithme de recherche séquentielle dans un tableau
Dans cet algorithme, On va utiliser trois fonctions et une procédure :
- la fonction saisie_taille
- la procédure remplir
- la fonction saisie
- la fonction recherche
Algorithme du programme Principal
L’algorithme principal Recherche_TABLEAU assure le déroulement général du programme de recherche d’un élément dans un tableau.
Il commence par appeler la fonction saisie_taille() afin de saisir et valider le nombre d’éléments du tableau. Ensuite, il appelle la procédure remplir(t, n) pour remplir le tableau avec les n éléments saisis par l’utilisateur.
Après le remplissage du tableau, l’algorithme demande à l’utilisateur de saisir la valeur x à rechercher. Il appelle ensuite la fonction recherche(t, n, x) afin de vérifier si cette valeur existe dans le tableau.
Enfin, selon le résultat retourné par la fonction recherche(), l’algorithme affiche un message indiquant que la valeur x a été trouvée ou qu’elle n’a pas été trouvée dans le 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 28 29 30 31 32 33 |
Algorithme Recherche_TABLEAU Debut # Appeler la fonction saisie_taille() # pour obtenir le nombre d'éléments du tableau. n <-- saisie_taille() # Afficher un message avant le remplissage du tableau. Ecrire("***Remplissage du tableau***") # Appeler la fonction remplir() pour saisir # les n éléments du tableau dans l'ordre croissant. remplir(t, n) # Demander à l'utilisateur de saisir # la valeur à insérer dans le tableau. x <-- saisie() # ========================================================== # Recherche de la valeur # ========================================================== # Appeler la fonction recherche() # pour vérifier si la valeur x existe dans le tableau. # # La fonction recherche() retourne : # - True si x est trouvé ; # - False si x n'est pas trouvé. Si recherche(t, n, x) = Vrai alors # Afficher un message indiquant que # la valeur recherchée a été trouvée. Ecrire(x, " est trouvé") Sinon # Afficher un message indiquant que # la valeur recherchée n'a pas été trouvée. Ecrire(x, " n'a pas été trouvé") Fin si Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
| x | entier |
| t | tableau des entiers |
La fonction saisie_taille
La fonction saisie_taille() permet de saisir et de contrôler le nombre d’éléments n du tableau. Elle demande à l’utilisateur de donner une valeur comprise entre 2 et 14.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
Fonction saisie_taille():entier # La variable test permet de contrôler # si la taille saisie est correcte. test <-- Faux # Répéter la saisie tant que la valeur # n'est pas comprise entre 2 et 14. Tant que test = Faux faire # Demander à l'utilisateur de saisir # la taille du tableau. Ecrire("donner n entre 2 et 14: ") Lire(n) # Vérifier que n est comprise entre 2 et 14. Si 2 <= n <= 14 alors # La taille saisie est correcte. test <-- Vrai Fin si Fin tant que # Retourner la taille du tableau. retourner n Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
La procédure remplir
La procédure remplir a pour rôle de remplir les n premières cases du tableau t avec des valeurs saisies par l’utilisateur.
|
1 2 3 4 5 6 7 8 9 |
Procédure remplir(var t:tab; n:entier) # Parcourir les n premières cases du tableau. Pour i de 0 à n-1 faire # Demander à l'utilisateur de saisir # un élément du tableau. Ecrire("donner un element du tableau : ") Lire(t[i]) Fin pour Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
La fonction saisie
La fonction saisie() permet de demander à l'utilisateur de saisir une valeur entière à rechercher dans le tableau, puis de retourner cette valeur.
|
1 2 3 4 5 |
Fonction saisie():entier Ecrire("donner une valeur à rechercher ") Lire(n) retourner n Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
La fonction recherche
La fonction recherche a pour rôle de chercher une valeur x dans les n premiers éléments du tableau t et de déterminer si cette valeur existe ou non.
Elle commence la recherche à partir de la première case du tableau, d’indice 0. Elle compare successivement chaque élément t[i] avec la valeur recherchée x.
Tant que l’élément courant est différent de x et que la dernière case du tableau n’est pas atteinte, la fonction passe à l’élément suivant en augmentant l’indice i de 1. Cette méthode correspond à une recherche séquentielle.
À la fin de la recherche, si t[i] = x, la fonction retourne Vrai, indiquant que la valeur recherchée a été trouvée. Sinon, elle retourne Faux, indiquant que x n’existe pas dans le tableau.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
Fonction recherche(t:tab; n:entier; x:entier) : # Commencer la recherche à partir de la première # case du tableau. i <-- 0 # Parcourir le tableau tant que : # - l'élément courant est différent de x ; # - et que l'on n'a pas atteint la dernière case utilisée. Tant que (t[i] != x) et (i < n - 1) faire # Passer à l'élément suivant du tableau. i <-- i + 1 Fin tant que # Vérifier si l'élément trouvé est égal à x. Si t[i] = x alors # La valeur x existe dans le tableau. # Retourner True pour indiquer qu'elle est trouvée. retourner Vrai Sinon # La valeur x n'existe pas dans le tableau. # Retourner False pour indiquer qu'elle n'est pas trouvée. retourner Faux Fin si Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
Programme en Python
|
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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 |
# ========================================================== # Importation de la bibliothèque NumPy # ========================================================== from numpy import array # Importer la fonction array de NumPy. # Elle permet de créer et de manipuler des tableaux. # ========================================================== # Création du tableau # ========================================================== # Créer un tableau de 100 éléments. # Toutes les cases sont initialisées à 0. # Dans notre programme, seules les n premières cases # seront utilisées pour stocker les éléments du tableau. t = array([int()] * 100) # ========================================================== # Fonction de saisie de la taille du tableau # ========================================================== def saisie_taille(): # La variable test permet de contrôler # si la taille saisie est correcte. test = False # Répéter la saisie tant que la taille # n'est pas comprise entre 2 et 14. while test == False: # Demander à l'utilisateur de saisir # la taille du tableau. n = int(input("donner n entre 2 et 14: ")) # Vérifier que la taille est comprise # entre 2 et 14. if 2 <= n <= 14: # La taille saisie est correcte. test = True # Retourner la taille du tableau. return n # ========================================================== # Fonction de saisie de la valeur à rechercher # ========================================================== def saisie(): # Demander à l'utilisateur de saisir # la valeur qu'il souhaite rechercher # dans le tableau. x = int(input("donner la valeur à rechercher: ")) # Retourner la valeur saisie. return x # ========================================================== # Procédure de remplissage du tableau # ========================================================== def remplir(t, n): # Parcourir les n premières cases du tableau. for i in range(n): # Demander à l'utilisateur de saisir # un élément du tableau. t[i] = int(input("donner un element du tableau : ")) # ========================================================== # Fonction de recherche d'un élément dans un tableau # ========================================================== def recherche(t, n, x): # Commencer la recherche à partir de la première # case du tableau. i = 0 # Parcourir le tableau tant que : # - l'élément courant est différent de x ; # - et que l'on n'a pas atteint la dernière case utilisée. while (t[i] != x) and (i < n - 1): # Passer à l'élément suivant du tableau. i = i + 1 # Vérifier si l'élément trouvé est égal à x. if t[i] == x: # La valeur x existe dans le tableau. # Retourner True pour indiquer qu'elle est trouvée. return True else: # La valeur x n'existe pas dans le tableau. # Retourner False pour indiquer qu'elle n'est pas trouvée. return False # ========================================================== # Programme principal # ========================================================== # Appeler la fonction saisie_taille() # pour obtenir le nombre d'éléments du tableau. n = saisie_taille() # Afficher un message avant le remplissage du tableau. print("***Remplissage du tableau***") # Appeler la fonction remplir() # pour saisir les n éléments du tableau. remplir(t, n) # Demander à l'utilisateur de saisir # la valeur à rechercher dans le tableau. x = saisie() # ========================================================== # Recherche de la valeur # ========================================================== # Appeler la fonction recherche() # pour vérifier si la valeur x existe dans le tableau. # # La fonction recherche() retourne : # - True si x est trouvé ; # - False si x n'est pas trouvé. if recherche(t, n, x) == True: # Afficher un message indiquant que # la valeur recherchée a été trouvée. print(x, " est trouvé") else: # Afficher un message indiquant que # la valeur recherchée n'a pas été trouvée. print(x, " n'a pas été trouvé") |
0 commentaire
laisser un commentaire
Passion de robotique
Tutoriels récents
Atelier robotique
Tutoriels populaires
Construction des robots
Tutoriels plus commentés
Bras robotique
Categories
Maison intelligente
