Relazione ricerca

Ci è stato posto il problema di ricercare all’interno di un vettore un valore, attraverso la ricerca binaria. La differenza della ricerca binaria da quella sequenziale è il fatto che, quella binaria non controlla tutti i valori contenuti all’interno del vettore, ma:

inizialmente controlla gli estremi dell’intervallo e il valore intermedio. Se il valore non è uguale a nessuno dei tre, allora controlla se il valore cercato è maggiore o minore di quello centrale all’intervallo del vettore; se è minore, il programma reimposta l’estremo destro al valore centrale. Se invece è maggiore, reimposta l’estremo sinistro al valore centrale.  Al termine, il programma fornisce il risultato della ricerca: se il valore è stato trovato scrive: “il valore è stato trovato”, altrimenti scrive: “Il valore non è stato trovato”.Il vantaggio che se i numeri sono n, non esegue n controlli ma solo log n.

Abbiamo creato due diversi programmi: uno chiede all’utente i numeri da inserire nel vettore, l’altro, invece, li crea casualmente.

Pseudocodice

Procedura caricavet;

Inizio

Ripeti

Scrivi('Da quanti valori vuoi che il vettore sia composto?');

Leggi(max);

Finchè (max>0) e (max<100);

Fine;

Procedura acqui;

var i:interi;

Inizio

Per i:=1 a max esegui

Inizio

Scrivi('inserisci il',i,'valore');

Leggi(v[i]);

fine;

fine;

Procedura scambia(var a,b:interi);

Var supporto:interi;

Inizio

supporto:=a;

a:=b;

b:=supporto;

Fine;

Procedura Ordina;

var i,j:interi;

Inizio

Per i:=1 a max-1 esegui

Per j:=i+1 a max esegui

se v[i]>v[j] allora

scambia(v[i],v[j])

fine;

Procedure chiedivet;

Inizio

Scrivi('quale numero vuoi cercare');

Leggi(n);

fine;

Procedure ricercavet;

Var

sx,dx,md:interi;

Inizio

trov:=false;

sx:=1;

dx:=max;

Mentre (trov=false) e (dx>=sx) esegui

Inizio

md:=(sx+dx) div 2;

Se (n=v[sx]) o (n=v[dx]) o (n=v[md]) allora

trov:=true

altrimenti

se md<n allora

sx:=md+1 altrimenti

dx:=md-1;

fine;

fine;

Procedure visua;

Inizio

Se trov=true allora

Scrivi('il numero è stato trovato')

altrimenti Scrivi('il numero non è stato trovato');

fine;

{Programma principale}

Inizio

caricavet;

acqui;

ordina;

chiedivet;

ricercavet;

visua;

fine.

Flow Chart

Procedura caricavet;

O

I

Procedura acqui;

O

I

Procedura scambia(var a,b:interi);

Procedura Ordina;

Procedure chiedivet;

O

I

Procedure ricercavet;

Procedure visua;

O O

{Programma principale}

Programma in formato pascal

Pseudocodice

Function mt$random( var b:integre ):real;external;

Procedura acqui;

var i:interi;

Inizio

Per i:=1 a max esegui

Inizio

a=mth$random(b);

v[i]:=trunc(a*300+1);

fine;

fine;

Procedura scambia(var a,b:interi);

Var supporto:interi;

Inizio

supporto:=a;

a:=b;

b:=supporto;

Fine;

Procedura Ordina;

var i,j:interi;

Inizio

Per i:=1 a max-1 esegui

Per j:=i+1 a max esegui

se v[i]>v[j] allora

scambia(v[i],v[j])

fine;

Procedure chiedivet;

Inizio

Scrivi('quale numero vuoi cercare?(un valore compreso tra 1 e 300');

Leggi(n);

fine;

Procedure ricercavet;

Var

sx,dx,md:interi;

Inizio

trov:=false;

sx:=1;

dx:=max;

Mentre (trov=false) e (dx>=sx) esegui

Inizio

md:=(sx+dx) div 2;

Se (n=v[sx]) o (n=v[dx]) o (n=v[md]) allora

trov:=true

altrimenti

se md<n allora

sx:=md+1 altrimenti

dx:=md-1;

fine;

fine;

Procedure visua;

Inizio

Se trov=true allora

Scrivi('il numero è stato trovato')

altrimenti Scrivi('il numero non è stato trovato');

fine;

{Programma principale}

Inizio

Max:=100;

caricavet;

acqui;

ordina;

chiedivet;

ricercavet;

visua;

Scrivi(‘ ‘);

Scrivi(‘ ‘);

Scrivi(‘ Il programma è stato realizzato da Teodoro Montanaro e Alessio Massaro ‘);

fine.

Flow Chart

Procedura acqui;

Procedura scambia(var a,b:interi);

Procedura Ordina;

Procedure chiedivet;

O

I

Procedure ricercavet;

Procedure visua;

O O

{Programma principale}

O

O

O

Programma in formato pascal