PROGRAMME 7

PROGRAMME 7 : Recherche dichotomique dans un vecteur

Ecrire un programme qui remplit un vecteur à partir d'un fichier TEXT et recherche dichotomiquement un ensemble de données également lues sur le fichier d'entrée.

On utilisera le module Remplir et Recherche défini comme suit :

- Remplir : remplissage d'un vecteur à partir d'un fichier de données
- Recherche : recherche dichotomique d'une donnée dans un vecteur

Le programme

PROGRAM Dicho;
VAR I :INTEGER;
      Tab : ARRAY(.1..10.) OF INTEGER;
      Fs : TEXT; { Fichier De Sortie }
      Fe : TEXT; { Fichier D'Entrée }
      N, D : INTEGER;

{ remplissage du tableau }
PROCEDURE Remplir;
    VAR
      Nombre, I : INTEGER;
    BEGIN
      READLN(Fe, Nombre);
      FOR I:=1 TO Nombre DO
        READLN(Fe, Tab[I] );
    END;

{ Recherche dichotomique }
FUNCTION Recherche ( Cle : INTEGER ) : BOOLEAN;
    VAR
      M, Bi, Bs : INTEGER;
      Trouv : BOOLEAN;
    BEGIN
      Bi := 1;
      Bs := 10;
      Trouv := FALSE;
      WHILE (Bi <= Bs) AND NOT Trouv DO
        BEGIN
          M := (Bi + Bs) DIV 2;
          IF Tab(.M.) = Cle
          THEN Trouv := TRUE
          ELSE IF Tab(.M.) > Cle
               THEN Bs := M -1
               ELSE Bi := M + 1
        END;
      Recherche := Trouv
    END;

BEGIN
    ASSIGN( Fe,'D_dicho.Pas');
    ASSIGN( Fs,'R_dicho.Pas');
    RESET(Fe);
    REWRITE(Fs);
    Remplir;
    READLN(Fe, N ); {nombre De Données à Rechercher}
    FOR I:= 1 TO N DO
      BEGIN
        READLN(Fe, D);
        IF Recherche(D)
        THEN WRITELN(Fs, 'L''élément ', D, ' existe')
        ELSE WRITELN(Fs,'L''élément ', D, ' n''existe pas');
      END;
    CLOSE(Fs)
END.

Les données

Contenu du fichier D_Dicho.Pas

10 Nombre d'éléments
23
32
34
45
54
72
76
76
78
89
12 Nombre de données à rechercher
34
76
23
89
5
99
74
32
45
54
34
72

Les résultats

Contenu du fichier R_Dicho.Pas

L'élément 34 existe
L'élément 76 existe
L'élément 23 existe
L'élément 89 existe
L'élément 5 n'existe pas
L'élément 99 n'existe pas
L'élément 74 n'existe pas
L'élément 32 existe
L'élément 45 existe
L'élément 54 existe
L'élément 34 existe
L'élément 72 existe