Fichier PDF

Partagez, hébergez et archivez facilement vos documents au format PDF

Partager un fichier Mes fichiers Boite à outils PDF Recherche Aide Contact



Les methodes de recherche .pdf



Nom original: Les methodes de recherche.pdf
Titre: Les methodes de recherche
Auteur: hp

Ce document au format PDF 1.4 a été généré par PDFCreator Version 1.5.0 / GPL Ghostscript 9.05, et a été envoyé sur fichier-pdf.fr le 07/04/2018 à 15:38, depuis l'adresse IP 41.224.x.x. La présente page de téléchargement du fichier a été vue 223 fois.
Taille du document: 254 Ko (5 pages).
Confidentialité: fichier public




Télécharger le fichier (PDF)









Aperçu du document


Les méthodes de recherche

Sommaire
1)

Recherche séquentielle ................................................................................................................................................ 2
Analyse du module de recherche ( Recherche d'un entier dans un tableau ) ................................................................. 2
Algorithme du module de recherche ( Recherche d'un entier dans un tableau ) ........................................................... 2
Programme Pascal du module de recherche et son appel dans un programme permettant m'affichage du résultat de
la recherche ( Recherche d'un entier dans un tableau ) .................................................................................................. 2

2)

Recherche dichotomique ............................................................................................................................................. 3
Analyse du module de recherche dichotomique ( Recherche d'un entier dans un tableau Trié) .................................. 3
Algorithme du module de recherche dichotomique ( Recherche d'un entier dans un tableau Trié).............................. 4
Programme Pascal du module de recherche dichotomique et son appel dans un programme permettant m'affichage
du résultat de la recherche ( Recherche d'un entier dans un tableau Trié) .................................................................... 4

1

Niveau Scolaire : 4ème Sciences Expérimentales

préparé par Khaoula ABAIDI

Les modules de recherche permettent la recherche d'une valeur parmi celles existantes dans un tableau, Il
existe différentes méthodes de recherche ; parmi celles-ci , nous allons voir la méthode de recherche
séquentielle puis la méthode de recherche dichotomique.
1) Recherche séquentielle
Le principe est simple, on va parcourir les éléments du tableau dans l'ordre croissant des indices jusqu'à ce qu'on
trouve l'élément x, ou bien jusqu'à ce qu'on arrive à la fin du tableau , sans avoir trouver l'élément x.

Analyse du module de recherche ( Recherche d'un entier dans un tableau )
DEF FN rechercheSequentielle(x, n : entier ; T : Tab) : booleen
rechercheSequentielle = b
b = [ ] si (T[i] = x) alors
b← vrai
sinon
b ← faux
finSi
i = [ i ← 0 ] Répéter
i←i+1
Jusqu'à (T[i] = x) ou (i = n)
Fin rechercheSequentielle

T.D.O .L
Objet

Type/Nature

i

Var/entier

b

Var/booléen

Algorithme du module de recherche ( Recherche d'un entier dans un tableau )
0) DEF FN rechercheSequentielle(x, n : entier ; T : Tab) : booleen
1) i = [ i ← 0 ] Répéter
i←i+1
Jusqu'à ( T[i] = x ) ou (i = n)
2) b = [ ] si T[i] = x alors
b← vrai
sinon
b ← faux
finSi
3) rechercheSequentielle ← b
4) Fin rechercheSequentielle
Programme Pascal du module de recherche et son appel dans un programme permettant m'affichage du
résultat de la recherche ( Recherche d'un entier dans un tableau )
program applicationRechercheSequentielle; Uses wincrt ;
type tab = array[1..50] of integer ;
Var p , taille : integer ; tr : tab ; res : boolean ;
procedure saisieTaille(var n : integer);
begin
repeat begin write('N =') ; readln(n); end; until (n > 0) and (n <20) ;
end ;
procedure remplissageTableau(var t : tab ; n : integer);
var i : integer ;
begin for i:= 1 to n do begin write('Tr[ ',i,' ] = '); readln(t[i]); end;
end;
Les méthodes de recherche

2

Niveau Scolaire : 4ème Sciences Expérimentales

préparé par Khaoula ABAIDI

procedure affichageTableau(var t : tab ; n : integer);
var i : integer ;
begin for i:= 1 to n do write(t[i],' '); writeln('');
end;
function rechercheSequentielle(x,n:integer ; t : tab) : boolean ;
var i : integer ; b : boolean;
begin
i := 0 ;
repeat
i := i + 1 ;
until ( t[i] = x ) or (i = n) ;
if t[i] = x then b := true
else b := false ;
rechercheSequentielle := b ;
end;
begin
saisieTaille(taille); remplissageTableau(tr,taille); affichageTableau(tr,taille);
write('Element a chercher '); readln (p);
res := rechercheSequentielle(p,taille,tr) ;
write('Est-ce que l''element ',p,' est existant dans le tableau Tr? ', res);
end.
2) Recherche dichotomique
La recherche dichotomique est une manière efficace et rapide de rechercher un élément dans une
structure de données triée.
Le principe de la recherche dichotomique est le suivant :
a) Trouver la position la plus centrale du tableau (si le tableau est vide, sortir).
b) Comparer la valeur de cette case à l'élément recherché.
c) Si la valeur est égale à l'élément, alors retourner la position, sinon reprendre la procédure dans la
moitié de tableau pertinente.
On peut toujours se ramener à une moitié de tableau sur un tableau trié en ordre croissant. Si la valeur de la
case est plus petite que l'élément, on continuera sur la moitié droite, c'est-à-dire sur la partie du tableau qui
contient des nombres plus grands que la valeur de la case. Sinon, on continuera sur la moitié gauche.
Analyse du module de recherche dichotomique ( Recherche d'un entier dans un tableau Trié)
DEF FN rechercheDichotomique(x : entier ; T : Tab) : booleen
rechercheDichotomique = b
b = [ debut ← 1 , fin ← n , b ← faux ]
Répéter
moitier ← (debut + fin) div 2
si (x = T[moitier]) alors b ← vrai
sinon
si x < T[moitier] alors
fin ← moitier - 1
sinon debut ← moitier + 1
finSi
Jusqu'à (b) ou (debut > fin)
Fin rechercheDichotomique

Les méthodes de recherche

T.D.O
Objet

Type/Nature

debut

Var/entier

fin

Var/entier

moitier

Var/entier

b

Var/booléen

3

Niveau Scolaire : 4ème Sciences Expérimentales

préparé par Khaoula ABAIDI

Algorithme du module de recherche dichotomique ( Recherche d'un entier dans un tableau Trié)
0) DEF FN rechercheDichotomique(x : entier ; T : Tab) : booleen
1) b = [ debut ← 1 , fin ← n , b ← faux ]
Répéter
moitier ← (debut + fin) div 2
si (x = T[moitier]) alors b ← vrai
sinon
si x < T[moitier] alors
fin ← moitier - 1
sinon debut ← moitier + 1
finSi
Jusqu'à (b) ou (debut > fin)
2) rechercheDichotomique ← b
3) fin rechercheDichotomique
Programme Pascal du module de recherche dichotomique et son appel dans un programme permettant
m'affichage du résultat de la recherche ( Recherche d'un entier dans un tableau Trié)
program applicationRechercheDichotomique;
uses wincrt ;
type tab = array[1..50] of integer ;
Var p , taille : integer ; tr : tab ; res : boolean ;
procedure saisieTaille(var n : integer);
begin
repeat
begin
write('N =') ;
readln(n);
end;
until (n > 0) and (n <20) ;
end ;
procedure remplissageTableau(var t : tab ; n : integer);
var i : integer ;
begin
for i:= 1 to n do
begin
write('Tr[ ',i,' ] = ');
readln(t[i]);
end;
end;
procedure affichageTableau(var t : tab ; n : integer);
var i : integer ;
begin
for i:= 1 to n do
write(t[i],' ');
writeln('');
end;

Les méthodes de recherche

4

Niveau Scolaire : 4ème Sciences Expérimentales

préparé par Khaoula ABAIDI

procedure tri(var t : tab ; n : integer);
var ppm, i : integer ;
procedure permut(var x , y : integer);
var aux : integer ;
begin
aux := x ; x := y ; y := aux ;
end ;
function premposmin(t : tab ; n , m : integer) : integer ;
var posmin, j : integer ;
begin
posmin := m ;
for j:= m+1 to n do
if t[posmin]>t[j] then posmin := j;
premposmin := posmin ;
end ;
begin
for i := 1 to n-1 do
begin
ppm := premposmin(t,n,i);
if t[ppm] <> t[i]) then permut(t[ppm],t[i]);
end;
end;
function rechercheDichotomique(x,n:integer ; t : tab) : boolean ;
var debut, fin , moitier : integer ; b : boolean;
begin
debut := 1 ; fin := n ; b := false ;
repeat
begin
moitier := (debut + fin) div 2 ;
if (x = T[moitier]) then b := true
else if x < T[moitier] then fin := moitier - 1
else debut := moitier + 1 ;
end ;
until (b) or (debut > fin) ;
rechercheDichotomique := b ;
end;
begin
saisieTaille(taille); remplissageTableau(tr,taille); affichageTableau(tr,taille);
tri(tr,n); {La recherche dichotomique est appliquée sur un tableau trié}
affichageTableau(tr,taille); write('Element a chercher '); readln (p);
res := rechercheDichotomique(p,taille,tr) ;
write('Est-ce que l''element ',p,' est existant dans le tableau Tr? ', res);
end.

Les méthodes de recherche

5


Documents similaires


Fichier PDF les methodes de recherche
Fichier PDF proposition correction bac2013 09h30
Fichier PDF proposition correction bac2011 14h30
Fichier PDF sousprogrammes utiles
Fichier PDF sousprogrammes utiles
Fichier PDF tri bulle activite


Sur le même sujet..