Lezione del 18 Dicembre 2001

Gli array - ricerca sequenziale

COSA E' STATO FATTO A LEZIONE

Questo documento contiene un RIASSUNTO degli argomenti presentati a lezione. Per eventuali chiarimenti rivolgersi al docente.

Ricerca sequenziale

Supponiamo di essere in un contesto di programma in cui sono disponibili le seguenti dichiarazioni.

const

   vettLenght = 1000; {Capacita' del tipo-array vett}


type

   vett = array [0..vettLenght-1] of integer;


var

   v1 : vett;
   v1Size : integer; {Numero di elementi utilizzati nell'array v1}

Prima versione (PASCAL STANDARD)

{
  AI: 0 <= vSize <= vettLength-1 AND
      v[0..vSize-1] e' inizializzato 
  AF: ristituice il minimo i tale che v[i]=x, -1 se un tale i non esiste
}
function ricercaSequenziale (x:integer;
                              v:vett; 
                              vSize:integer)

var
   i:integer;
   trovato:boolean;

begin
   i:=0;
   trovato:=false;

   { 
     IC: 0 <= i <= vSize AND 
         x non occorre in v[0..i-2] AND
         trovato = (x = v[i-1])
   }
   while (i < vSize) and (not trovato) do
      begin
         trovato:=(x=v[i]);
         i:i+1; 
      end;
  
  if trovato then ricercaSequenziale:=i-1
             else ricercaSequenziale:=-1;
end;

Seconda versione (TURBO PASCAL)

{
  AI: 0 <= vSize <= vettLength-1 AND
      v[0..vSize-1] e' inizializzato 
  AF: ristituice il minimo i tale che v[i]=x, -1 se un tale i non esiste
}
function ricercaSequenziale (x:integer;
                              v:vett; 
                              vSize:integer)

var
   i:integer;

begin
   i:=0;

   { 
     IC: 0 <= i <= vSize AND 
         x non occorre in v[0..i-i] 
   }
   while i < vSize do
      begin
         if x=v[i] then begin
                           ricercaSequenziale:=i;
                           exit;
                        end;
         i:i+1; 
      end;
  
  ricercaSequenziale:=-1;
end;

Complessita` computazionale concreta in tempo e in spazio della function "ricercaSequenziale"

Complessita' in spazio: entambe le versioni della function ricercaSequenziale hanno complessita' in spazio lineare in vettLength.
NOTA: passando il vettore v per referenza (var) la complessita' in spazio diventa costante.

Complessita' in tempo: entambe le versioni della function ricercaSequenziale hanno complessita' in tempo che e':

NEL CASO PESSIMO (x non occorre in v): lineare in vSize.
NEL CASO MEDIO (consideriamo come insiemi dei casi possibili i casi in cui v contiene una permutazione degli interi 0..vSize-1 e x occorre in v[0..vSize-1]): lineare in vSize.

ESERCIZI DA SVOLGERE

Per eventuali chiarimenti rivolgersi ai docenti.

Scrivere, compilare, ed eseguire un programma Pascal che legge un array V di N interi (N stabilito dall'utente), un intero X, e stampa il risultato della chiamata: "ricercaSequenziale(X,V,N)".
ATTENZIONE: PROVARE ENTRAMBE LE VERSIONI DELLA function, CON ENTRAMBE LE MODALITA' DI PASSAGGIO DEL PARAMETRO v.