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

Aller en bas

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

Message par Samy.C le Ven 27 Mai - 11:31

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


avatar
Samy.C

Messages : 42
Karma Karma : 55
Date d'inscription Date d'inscription : 24/05/2016
Age Age : 22
Localisation Localisation : Cellule AFPA
Humeur Humeur : Gone

Voir le profil de l'utilisateur https://www.youtube.com/sonicdbzfan07

Revenir en haut Aller en bas

Indices?

Message par GrlSidious (Vince) le Ven 27 Mai - 11:35

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é?
avatar
GrlSidious (Vince)
Admin

Messages : 58
Karma Karma : 53
Date d'inscription Date d'inscription : 23/05/2016
Age Age : 29
Localisation Localisation : Grenoble
Humeur Humeur : Fiora top 4 ever

Voir le profil de l'utilisateur https://fr.wiktionary.org/wiki/connard

Revenir en haut Aller en bas

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

Message par Samy.C le Ven 27 Mai - 11:40

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.
avatar
Samy.C

Messages : 42
Karma Karma : 55
Date d'inscription Date d'inscription : 24/05/2016
Age Age : 22
Localisation Localisation : Cellule AFPA
Humeur Humeur : Gone

Voir le profil de l'utilisateur https://www.youtube.com/sonicdbzfan07

Revenir en haut Aller en bas

télépathe?

Message par GrlSidious (Vince) le Ven 27 Mai - 11:42

C'était ma deuxième question... ^^
avatar
GrlSidious (Vince)
Admin

Messages : 58
Karma Karma : 53
Date d'inscription Date d'inscription : 23/05/2016
Age Age : 29
Localisation Localisation : Grenoble
Humeur Humeur : Fiora top 4 ever

Voir le profil de l'utilisateur https://fr.wiktionary.org/wiki/connard

Revenir en haut Aller en bas

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

Message par Samy.C le Ven 27 Mai - 11:49

Cool
avatar
Samy.C

Messages : 42
Karma Karma : 55
Date d'inscription Date d'inscription : 24/05/2016
Age Age : 22
Localisation Localisation : Cellule AFPA
Humeur Humeur : Gone

Voir le profil de l'utilisateur https://www.youtube.com/sonicdbzfan07

Revenir en haut Aller en bas

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

Message par Contenu sponsorisé


Contenu sponsorisé


Revenir en haut Aller en bas

Revenir en haut

- Sujets similaires

 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum