lundi 26 février 2001

Recherche


LES RECHERCHES

Nous utilisons différents types de recherche pour trouver des données spécifiques. Nous verrons qu'il y a divers types de recherche qui peuvent être faites.

Type de recherche

La recherche séquentielle

La recherche séquentielle consiste à vérifier du début  du tableau, liste... jusqu'à ce qu'on trouve ce qu'on désire ou parcoure totalement le tableau liste... C'est évidemment pas la recherche la plus efficace. Ce type de recherche est doit être utilisé si le tableau n'est pas trié.
//on définit les variables utilisées
Const
  Max=15;
  type
    tabType = array [1..Max] of integer;
function SequentialSearch(tab:tabType; item:integer):integer;
var
  i : integer;
  found : boolean;
begin
  SequentialSearch := 0;
  i := low(tab);
  found := false;
  while( i <= high(tab)) and (not found) do
  begin
    if tab[i] = item then
    begin
      SequentialSearch := i;
      found := true;
    end;
    inc(i);
  end;
end;

La recherche binaire

La recherche séquentielle consiste à comparer la valeur recherché par le milieu du vecteur.Si cet élément est plus grand que l'élément recherché, ce dernier est à gauche sinon à droite. On répète l'opération sur les sous-vecteurs. Le tableau doit évidemment être trié pour tirer parti de ce type de recherche

function BinarySearch(tab:tabType; item:integer):integer;
var
  Milieu:integer;
  Found:boolean;
  bas:integer;
  haut:integer;
begin
  bas := low(tab);
  haut := high(tab);
  Found := False;
  BinarySearch := 1;
  while(bas <= haut) and (not Found) do
  begin
    Milieu := (bas + haut) div 2;
    if tab[Milieu] = item then
    begin
      Found := True;
      BinarySearch := Milieu;
    end
    else
      if tab[Milieu] < item then
        bas := Milieu + 1
      else
        haut := Milieu - 1;
  end;
end;

jeudi 22 février 2001

Matrice

MATRICE

Une matrice est un genre de tableau
2 44 69
15 71 8
562 3 9
128 67 564
L'exemple précédent est une matrice 4 * 3 (4 lignes, 3 colonnes). Il est bien sûr possible de mettre des chiffres à virgule flottante dans une matrice. Diverses opérations peuvent être effectuées sur les matrices, c'est ce qu'on verra.

Opérations sur les matrices

Produit

Pour effectuer cette opération, il faut que le nombre de colonnes de la matrice A soit supérieur ou étal au nombre de ligne de la matrice B.

Matrice A

1 2 3
4 5 6

Matrice B

1 2
3 4
5 6
La multiplication de A et B donnera

Matrice A*B

1 2
22 28
49 64

Pour parvenir à ce résultat, il faut faire faire multiplier la ligne de la matrice A * la colonne de la matrice B.
Donc on a (1*1) + (2*3) + (3*5) , (1*2)+(2*4)+(3*6) , (4*1)+(5*3)+(6*5),(4*2)+(5*4)+(6*6).

Type
  matrice1=array[1..2,1..3]of integer;
  matrice2=array[1..3,1..2]of integer;
  matrice=array[1..high(matrice1),1..high(matrice2)]of integer;

function Produit(Mat1:matrice1;Mat2:Matrice2):matrice;
var
  i,j,k:integer;
  Mat3:matrice;
begin
for i:=1 to high(Mat1) do
  for j:=1 to high(Mat1) do
    begin
    Mat3[i,j]:=0;
    for k:=1 to high(Mat2) do
      Mat3[i,j] := Mat3[i,j]+Mat1[i,k]*Mat2[k,j];
    end;
    result := Mat3;
end;

Addition de matrice

L'addition de matrice est simple, il suffit d'additionner les valeurs des deux matrices qui sont situées au même endroit. Les matrices doivent être de même dimensions

Matrice A

1 2
3 4

Matrice B

5 6
7 8
On addition 1 avec 5, 2 avec 6 , 3 avec 7 et 4 avec 8 pour obtenir
6 8
10 12
Voici le code de la fonction
type
  matrice=array[1..2,1..2]of integer;

function Addition(Mat1:,Mat2:matrice):matrice;
var
  i,j:integer;
  Mat3:matrice;
begin
  for i:=1 to high(Mat1) do
    for j:=1 to high(Mat1) do
      Mat3[i,j] := Mat1[i,j]+ Mat2[i,j];
    result:=matc;
end;
Le principe de la soustraction est le même. Il suffit de remplacer le + par un - dans l'algo ci-dessus.

Produit boolean

Cette opération ressemble au calcul de matrice.Pour effectuer cette opération, il faut que le nombre de colonnes de la matrice A soit supérieur ou étal au nombre de ligne de la matrice B. Puisque c'est boolean, les éléments des matrices que peuvent avoir que des 0 ou des 1 comme valeur.

Matrice A

1 0 1
1 0 0
0 0 0

Matrice B

1 0 0
0 1 0
1 0 0

Le principe ressemble à la multiplication de deux matrices. On remplace les plus par des ou logiques. L'utilisation des ou logique implique qu'aussitôt qu'on retrouve 1*1, ça donnera 1.

Donc on a (1*1 ou 0*0 ou 1*1) ça donne 1. Puisqu'on a 1*1 et que c'est ou, on aurait pu arrêter à 1*1. Le résultat final donnera

1 0 0
1 0 0
0 0 0

Voici le code de la fonction pour calculer le produit boolean

type
  matrice=array [1..3,1..3] of integer;

function ProduitBoolean(matrice1,matrice2:matrice):matrice;
var
  i,j,k:integer;
  ok:boolean;
  matrice_result:matrice;
begin
  ok := false;
  for i:=1 to high(matrice1) do begin
    for j:=1 to high (matrice1) do
    begin
      for k:=1 to high(matrice1) do
        if (matrice1[i][k] = 1 ) and (matrice2[k][j]=1) and not(ok)then
          ok := true;
      if ok then
        matrice_result[i][j]:=1
      else
        matrice_result[i][j]:=0;
      ok := false;
    end;
  end;
  result := matrice_result;
end;