Le problème d’accès à un élément d’un ensemble, classique en gestion, est formulé habituellement de deux manières:
- Soit on connait la position de l’élément à trouver, on recherche , depuis le début de l’ensemble jusqu’au ixième élément.
- Soit on ne connait pas la position de l’ élément et l’on recherche le premier élément dont la valeur est la valeur donnée.
On distingue donc deux types de recherche dans une file séquentielle:
- Un accès par position
- Un accès par valeur ou associatif
On veut parcourir un ensemble depuis le début pour trouver un élément dont la valeur égale à une valeur donnée. Le schéma de programme est un prédicat délivrant Vrai si la valeur choisie appartient à l’ensemble des valeurs de la file, Faux sinon.
Objectif: Recherche par valeur lors d'un parcours séquentiel d'un ensemble d'éléments. Lecture de tous les éléments de l'ensemble Résultat: l'algorithme retourne Vrai si le valeur est trouvée Faux sinon
Recherche associative dans un ensemble non trié:
rechercheParValeur_1 ensemble Ensemble,valeur Element -> Bool
existe <- Faux
Initialiser ensemble
Enumerer ensemble ET NON existe
element >- Element_Courant
ensemble existe <- valeur = element
Element_Suivant ensemble
Fin
<- existe
Fin
L’élément existe indique que l’on a trouvé une valeur correspondant à la condition de recherche. La cohérence du schéma est assurée par l’initialisation de existe à Faux avant le test d’itération. Ceci permet de ne pas entrer dans la boucle itérative si l’ensemble est vide. Par conséquent l’instruction Element_Courant ne sera exécutée que si la variable existe a la valeur Faux.
Recherche associative dans un ensemble trié:
Si l’on considère une file dont les éléments sont munis d’une relation d’ordre, le schéma ci-dessus peut être optimisé. Les deux principales relation d’ordre couramment utilisées sont représentées par:
- une fonction croissante, l’ensemble est ordonné en ordre croissant
- une fonction décroissante, la file est ordonnée en ordre décroissant
Dans le cas de l’accès associatif la relation d’ordre permet d’éviter un énumération complète des éléments de l’ensemble pour trouver une occurrence de la valeur cherchée.
rechercheParValeur_2 ensemble Ensemble,valeur Element -> Bool
existe <- Faux
Initialiser ensemble
Enumerer ensemble ET NON existe
element >- Element_Courant ensemble
Si valeur < element Sortie
existe <- valeur = element
Element_Suivant ensemble
Fin
<- existe,
Fin
Recherche dans un ensemble itérable non trié
Dans cette version de recherche d’un élément, la boucle de parcours de l’ensemble est une expression itérable. Le type itérable Ensemble est une abstraction de for element In ensemble que l’on retrouve dans le plupart des langages de programmation impératifs. La variable element agit comme une variable d’itération , qui prend successivement la valeur de chacun des éléments de ensemble.
avec ensemble non trié
rechercheParValeur_3 ensemble Ensemble,valeur Element -> Bool
existe <- Faux
ensemble : element
Si valeur = element
existe <- Vrai
Sortie
Fin
Fin
<- existe
Fin
ssss
Recherche dans un ensemble itérable trié
rechercheParValeur_4 ensemble Ensemble,valeur Element -> Bool existe <- Faux ensemble : element Si valeur < element Sortie Si valeur = element existe <- Vrai Sortie Fin Fin <- existe Fin
Recherche avec boucle infinie dans un ensemble trié
rechercheParValeur_5 ensemble Ensemble,valeur Element -> Bool
existe <- Faux
Initialiser ensemble
Vrai
Si AucunElement ensemble Sortie
element >- Element_Courant ensemble
Si valeur < element Sortie
Si valeur = element
existe <- Vrai
Sortie
Fin
Element_Suivant ensemble
Fin
<- existe
Fin
Traduction des algorithmes en : Swift, Julia
copyright A rchitectures A pplicatives A vancées A3-Soft