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

Voir le sujet précédent Voir le sujet suivant 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



Samy.C

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

Voir le profil de l'utilisateur http://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é?

GrlSidious (Vince)
Admin

Messages : 58
Karma Karma : 53
Date d'inscription Date d'inscription : 23/05/2016
Age Age : 27
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.

Samy.C

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

Voir le profil de l'utilisateur http://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... ^^

GrlSidious (Vince)
Admin

Messages : 58
Karma Karma : 53
Date d'inscription Date d'inscription : 23/05/2016
Age Age : 27
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

Samy.C

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

Voir le profil de l'utilisateur http://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

Voir le sujet précédent Voir le sujet suivant Revenir en haut

- Sujets similaires

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