(Spoiler) Recherche par dichotomie d'un élément d'une table classée

Sauf petit détails, voila l'algo de la recherche par dichotomie :

Code:


1-
Entrée                                  Sortie

Table----------------->RechercheDichotomie---->NuméroPrénom
Prénom------------------>

2-
Définir Type Chaine
N=80
Chaine = Tableau[N] Caractères

3-

/       Tableau  /  Prénom    /   NuméroPrénom   /
/  agathe berthe cellulite cenegonde  /  agathe    /        1         /
/ bertrand damien florent  /  adrien    /        0         /
/ bertrand damien florent  /  batman    / 0         /
/ bertrand damien florent  /  cyril     /        0         /
/ bertrand damien florent  /  dean      /        0         /
/ bertrand damien florent  /  damien    /        2         /
/ bertrand damien florent  /  elena     /        0         /
/ bertrand damien florent  /  florent   /        3         /
/ bertrand damien florent  /  gerard    /        0         /

4-
Outils
procédure RechercheDichotomie(entrée Table:chaine,entrée Prénomcherche:prénom, sortie NuméroPrénom:entier)
// Cette procédure permet d'effectuer une recherche par dichotomie dans une table classé
// Table est le tableau contenant les noms
// Prénom correspond au prénom dont on cherche le numéro
// NuméroPrénom est le numéro correspondant a un prénom

procédure RemplirTableau(sortie NombreElementsTableau, sortie Table)
// Cette procédure permet de remplir un tableau
// NombreElementsTableau représente le nombre de valeurs contenues dans le tableau
// Table est le tableau rempli

5-
Programme

Constantes
N=80             //Longeur max du tableau
LongeurPrenom = 7 // Taille max d'un prénom

Type
prénom = tableau[LongeurPrenom] caractères
chaine=tableau[N]prénom // Type des caractères traités

Variables
Table : chaine // Tableau d'entier à trier
PrénomCherche : prénom // PrénomRechercher
NuméroPrénom : entier // Numéro du prénom recherché

Outils
procédure RechercheDichotomie(entrée Table:chaine,entrée Prénom:caractères, sortie NuméroPrénom:entier)
// Cette procédure permet d'effectuer une recherche par dichotomie dans une table classé
// Table est le tableau contenant les noms
// Prénom correspond au prénom dont on cherche le numéro
// NuméroPrénom est le numéro correspondant a un prénom

procédure RemplirTableau(sortie NombreElementsTableau, sortie Table)
// Cette procédure permet de remplir un tableau
// NombreElementsTableau représente le nombre de valeurs contenues dans le tableau
// Table est le tableau rempli

Debut

 RemplirTableau(LongeurPrenom,Table)
 ecrire("Nom recherché ?")
 lire(Prénom)
 RechercheDichotomie(Table,PrénomCherche,NuméroPrénom)
 Si NuméroPrénom<>0 alors
 ecrire("Le numéro correspondant à ",prénomCherche," est : ",NuméroPrénom)
 Sinon
 ecrire(prénomCherche," est introuvable dans le tableau")
Fin

6-
procédure RemplirTableau(sortie NombreElementsTableau, sortie Table)

Variables

ValeursDejaEntrées : entier // Nombre de valeurs déja entrées dans le tableau

Debut

 ValeursDejaEntrées=0

 Repeter
 ecrire("Nombre de valeurs : ")
 lire(NombreElementsTableau)
 Jusqu'a 0<=NombreElementsTableau et NombreElementsTableau<=N
 
 Repeter
 ecrire("Valeurs du tableau : ")
 lire(Table[ValeursDejaEntrées])
 ValeursDejaEntrées:=ValeursDejaEntrées+1
 Jusqu'a NombreElementsTableau=ValeursDejaEntrées
Fin

procédure RechercheDichotomie(entrée Table:chaine,entrée Prénomcherche:prénom, sortie NuméroPrénom:entier)

Variables

DebutZone entier //Delimite le début de la zone de recherche
FinZone : entier //Delimite la fin de la zone de recherche

Debut
 
 DebutZone:=1
 FinZone:=LongeurPrenom
 NuméroPrénom:=((DebutZone+FinZone)/2)
 
 Tantque DebutZone>=FinZone et Table[NuméroPrénom]<>Prénom faire
 
 Si Prénom > Table[NuméroPrénom] alors

 FinZone:=NuméroPrénom-1
 
 Else
 
 DebutZone:=NuméroPrénom+1
 
 FinSi
 
 NuméroPrénom:=((DebutZone+FinZone)/2)
 
 FinTantque

 Si DebutZone>FinZone alors
 NuméroPrénom := 0 // non trouvé dans la table
 finsi
Fin




Pourquoi tu ne mets pas des indices au lieu de variables?
pourquoi pas tableau[i] au lieu de DebutZone???

choix du développeur ou simplicité du programme ou "indice" pas conseillé?

Choix perso, les deux sont possible d'après JCC, sinon, petit détail, il vaut mieux utiliser un Tantque qu'un répéter dans la procédure RemplirTableau.

C'était ma deuxième question... ^^