Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Algorithmes de recherche Quelques algorithmes de recherche La recherche En informatique on est généralement amener à stocker un ensemble de données présentant des caractéristiques communes L ? une des opérations les plus usuelles est la recherche de ces e

Quelques algorithmes de recherche La recherche En informatique on est généralement amener à stocker un ensemble de données présentant des caractéristiques communes L ? une des opérations les plus usuelles est la recherche de ces ensembles d ? éléments selon certains critères La recherche peut intervenir dans l ? un des cas suivant - Cas d ? un annuaire téléphonique informatisé Un annuaire téléphonique est destiné à fournir le numéro de téléphone d ? un abonné étant donné son nom et éventuellement les caractéristiques complémentaires comme le prénom ou l ? adresse - Un autre exemple assez di ?érent est celui d ? un dictionnaire o? l ? on cherche la dé ?nition des mots en faisant d ? abord la recherche du mot que l ? on veut dé ?nir a La recherche séquentielle La façon de procéder la plus na? ve consiste à comparer l ? élément recherché X successivement à tous les éléments de la liste l selon le schéma séquentiel suivant - Le compteur i est compris entre et la longueur de la liste - Comparer X et le ième élément On va s ? intéresser dans un premier temps à la recherche d ? une solution quelconque On arrête donc la progression dans la liste lorsqu ? on trouve un élément qui est égal à X Dans le cas o? la liste est remplacée par un tableau T T i désignera le ième élément de la liste tableau et l ? algorithme suivant nous dira si l ? élément X se trouve dans le tableau T ou pas Algorithme recherche Const N type T tableau N- de entier Var X i entier Début Ecrire lecture des éléments du tableau Pour i ? à N- Faire Lire T i Finpour Ecrire élément à rechercher Lire X Tantque i N- et X T i faire i ? i ?ntantque si i N- alors Ecrire élément X inexistant Sinon Ecrire X existe en position i Finsi Fin Remarque Dans cet algorithme la condition d ? arrêt de la boucle tantque est double On e ?ectue donc à chaque itération un test de ?n de la liste i N- en plus de la comparaison entre les éléments X T i Tant que ces conditions ne sont pas réunies on itère avance dans la case suivante Dès que l ? une des conditions est véri ?ée on sort de la boucle tantque b La recherche dans une liste triée Supposons à présent qu ? il existe un ordre total sur les éléments et que la liste est triée par ordre croissant Pour rechercher encore un élément X on peut encore évidemment parcourir séquentiellement la liste jusqu ? à ce qu ? on trouve soit X soit un élément strictement supérieur à X auquel cas X n ? est pas dans la liste puisque les éléments sont rangés dans l ? ordre croissant Ici la recherche est encore séquentielle et elle tient très peu compte du fait que les éléments de