ARRAY CON SUB-RANGE
DIVERSI DAGLI INTERI
ARRAY
Indice 
1
2
3
.
.
.
.
.
.
100
In Pascal si può usare come sub-range un qualunque ordinal type
Un ordinal type, cioè un tipo per il quale è noto il successore e il
predecessore di ogni valore escluso il primo e l’ultimo.
Problema
Contare il numero di volte che ciascuna lettera dell’alfabeto
compare in un preassegnato testo e calcolare la percentuale della
ricorrenza di ciascuna lettera rispetto al totale.
Sia C:\TP\ESEMPI\TESTO.TXT il file di testo da analizzare.
Output
Introduci il Nome del file: C:\TP\ESEMPI\TESTO.TXT
Lettera
A
B
----------------Z
Occorrenze
32
18
2
Percentuale
15
11
1
ContaLettere
Indice 
a
b
c
.
.
.
.
.
.
z
TYPE
ArrayContatore = ARRAY[‘a’..’z’] OF integer;
VAR
ContaLettere: ArrayContatore;
N.B. Il programma deve contare sia le lettere minuscole che le
maiuscole. Poiché di solito le minuscole sono più frequenti
abbiamo definito il sub-range in termini di minuscole mentre
opereremo la conversione maiuscola-minuscola nel caso che
appaiano lettere maiuscole.
Pseudo-codice
LeggiNomeFile(UnFile)
reset(UnFile)
AzzeraContatori(ContaLettere)
ContaOccorrenze(UnFile,ContaLettere)
close(UnFile)
MostraOccorrenze(NomeFile,ContaLettere)
Cerchiamo solo i caratteri IN[‘a’..’z’] o IN[‘A’..’Z’] quindi
se leggiamo eoln, non appartenendo esso ai sub-range indicati
non viene preso in esame, per cui non è necessario il controllo
sull’eoln. E’ invece obbligatorio il controllo sull’eof.
ContaOccorrenze(UnFile,ContaLettere)
Pseudo-codice
WHILE NOT eof(UnFile) DO
read(UnFile,Carattere)
IF Carattere è una lettera THEN
aggiungi 1 all’elemento corrispondente in ContaLettere
PROGRAM ContaLeLettere(input,output, UnFile);
{conta e mostra le occorrenze di tutte le
lettere presenti in un file testo}
CONST
LunMass=30;
TYPE
ArrayContatore=ARRAY['a'..'z'] OF integer;
StringaNome=STRING[LunMass];
LeggiNomeFile(UnFile)
reset(UnFile)
AzzeraContatori(ContaLettere)
ContaOccorrenze(UnFile,ContaLettere)
close(UnFile)
MostraOccorrenze(NomeFile,ContaLettere)
VAR
Unfile : text; {variabile di file da cui sono contate le lettere}
ContaLettere: ArrayContatore; {memorizza le occorrenze}
NomeFile: StringaNome;
{directory e nome file testo}
PROCEDURE AzzeraContatori(VAR
LeggiNomeFile(VAR NomeFile:
ContaLettere:
StringaNome;
ArrayContatore);
VAR UnFile: text);
PROCEDURE LeggiNomeFile(VAR NomeFile: StringaNome; VAR UnFile: text);
VAR
BEGIN
IndiceLettera: ‘a’..’z’;
BEGIN write(' Dammi il nome del file da elaborare: ');
readln(NomeFile);
FOR IndiceLettera:=‘a’
TO ‘z’ DO
assign(UnFile, NomeFile)
ContaLettere[IndiceLettera]:=0;
END;
END;
LeggiNomeFile(UnFile)
reset(UnFile)
AzzeraContatori(ContaLettere)
ContaOccorrenze(UnFile,ContaLettere)
close(UnFile)
MostraOccorrenze(NomeFile,ContaLettere)
PROCEDURE ContaOccorrenze(VAR ContaLettere : ArrayContatore;
VAR UnFile: text);
VAR
Scambio: integer;
Carattere: char;
BEGIN
Scambio:= ord('a')-ord('A');
WHILE NOT eof(UnFile) DO
BEGIN
read(UnFile,Carattere);
IF Carattere IN['A'..'Z'] THEN
Carattere:=chr(ord(Carattere)+Scambio);
IF Carattere IN['a'..'z'] THEN
ContaLettere[Carattere]:=ContaLettere[Carattere]+1
END
END;
PROCEDURE MostraOccorrenze(NomeFile: StringaNome;
ContaLettere : ArrayContatore);
VAR
IndiceLettera: 'a'..'z';
MostraLettera: 'A'..'Z';
Scambio, SommaLettere: integer;
LeggiNomeFile(UnFile)
reset(UnFile)
AzzeraContatori(ContaLettere)
ContaOccorrenze(UnFile,ContaLettere)
close(UnFile)
MostraOccorrenze(NomeFile,ContaLettere)
BEGIN
Scambio:=ord('A')-ord('a');
write('Le occorrenze delle lettere nel file ');
writeln(NomeFile, ' sono: ');
writeln;
SommaLettere:=0; {serve per il calcolo delle frequenze }
FOR IndiceLettera:= 'a' TO 'z' DO
BEGIN
SommaLettere:=SommaLettere+ContaLettere[IndiceLettera];
END;
FOR IndiceLettera:= 'a' TO 'z' DO
BEGIN
MostraLettera:=chr(ord(IndiceLettera) + Scambio); {cambio min/maiusc}
write(' ':24,MostraLettera,'''s -- ');
writeln(ContaLettere[IndiceLettera]:1,' % ',
(ContaLettere[IndiceLettera] / SommaLettere)*100:10:2);
END;
END;
{ ******************** BODY ******************}
BEGIN
LeggiNomeFile(NomeFile,UnFile);
reset(UnFile);
AzzeraContatori(ContaLettere);
ContaOccorrenze(ContaLettere, UnFile);
close(UnFile);
MostraOccorrenze(NomeFile, ContaLettere);
readln
END.
ESERCIZIO
Gioco della TOMBOLA
Dati i 90 numeri della Tombola effettuare una estrazione completa
di tutti i numeri con un generatore random.
Impedire che venga estratto due volte lo stesso numero.
LA TOMBOLA
[0]
[1]
[..]
[..]
[30]
[..]
[..]
[90]
1
2
...
...
30
...
...
90
NumeroRandom 1..90  30
NumeroEstratto Interi[30]  30
[0]
[1]
[..]
[..]
[30]
[..]
[89]
[90]
1
2
...
...
90
...
89
90
NumeroRandom 1..89  2
NumeroEstratto Interi[2]  2
[0]
[1]
[..]
[..]
[30]
[..]
[89]
[90]
1
89
...
...
90
...
89
90
NumeroRandom 1..88  30
NumeroEstratto Interi[2]  90
[0]
[1]
[..]
[..]
[30]
[..]
[89]
[90]
1
89
...
...
88
...
89
90
ESEMPIO 10.2
Si vuole simulare l’attività del cambio di monete.
A partire dal valore giornaliero dei valori di cambio, data una
certa cifra in una moneta corrente si chiede l’equivalente in
un’altra moneta.
Supponiamo che le monete trattate siano: Lire, Dollaro,
Rublo,Yen, Sterlina, Franco Svizzero.
Il dialogo che vogliamo si svolga tra utente e macchina è del tipo:
Buongiorno. Dammi i cambi della Lira di oggi:
Dollaro: 1909
Rublo: 989.99
Sterlina: 3097
Yen: 18.64
Franco Svizzero: 1210
Grazie.
Abbiamo finito per oggi? (S/N) N
Moneta da convertire: Yen
Moneta in cui convertire: Sterlina
Cambio da Yen a Sterlina.
Valore da cambiare: 1000
1000 Yen si convertono in 43.76
Sterline
……………………….
Batti un tasto per effettuare cambi.
Abbiamo finito per oggi? (S/N) S
Pseudo-codice
DammiCambi(DaLireA)
REPEAT
DammiMonete(DaMoneta, NuovaMoneta)
Cambia(DalireA, AmmontareDaCamb, AmmontareCambiato);
MostraQuadroRiepilogativo(DaMoneta, NuovaMoneta,
AmmontareDaCamb,AmmontareCambiato, Risposta)
UNTIL Risposta IN ['S','s']
RAPPRESENTAZIONE GRAFICA
DaLireA
DaLireA
Istruzioni
DammiCambi
Ripeti finchè la Risposta è NO
DaMoneta DaLireA
NuovaMoneta
DammiMonete
Moneta
Moneta
Valido
Nome
AmmontareDaCamb
AmmontareCambiato
Cambia
DaMoneta
NuovaMoneta
AmmontareDaCamb
AmmontareCambiato
MostraQuadroRiepilogativo
STRUTTURA DATI
Indice 
ArrayConversione
Lira
1000
Dollaro
1909
Rublo
989.99
Sterlina
3097
Franco Svizzero
1210
Yen
18.64
Rapporto di conversione = valore moneta richiesta
valore moneta offerta
Usiamo il TYPE enumerativo
TYPE
TipoMoneta=(Nessuno, Lira, Dollaro, Rublo, Sterlina,
FrancoSvizzero, Yen)
ArrayConversione=ARRAY[Lira..Yen] of REAL;
VAR DaLireA: ArrayConversione
DaMoneta, AMoneta: TipoMoneta
PROGRAM SimulazioneCambiBancari(input,output);
{
}
TYPE
TipoMoneta=(Nessuno, Lira, Dollaro, Rublo, Sterlina, FrancoSvizzero, Yen)
ArrayConversione=ARRAY[Lira..Yen] of real;
VAR
DaLireA: ArrayConversione;
DaMoneta, NuovaMoneta: TipoMoneta;
AmmontareDaCamb, AmmontareCambiato : real;
Risposta: char;
………………………………………………………………………………………...
{ ******************* BODY *********************** }
BEGIN
Istruzioni;
DammiCambi(DaLireA);
REPEAT
DammiMonete(DaMoneta, NuovaMoneta);
Cambia(DalireA, AmmontareDaCamb,AmmontareCambiato);
MostraQuadroRiepilogativo(DaMoneta,NuovaMoneta,AmmontareDaCamb,
AmmontareCambiato, Risposta)
UNTIL Risposta IN ['S','s']
END.
DammiCambi Pseudo-codice
DaLireA[Lire]  1.000
FOR Moneta  Dollaro TO Yen DO
MostraCambi
readln(DaLireA [Moneta] )
BEGIN
Istruzioni;
DammiCambi(DaLireA);
REPEAT
DammiMonete(DaMoneta, NuovaMoneta);
Cambia(DalireA,AmmontareDaCamb,AmmontareCambiato);
MostraQuadroRiepilogativo(DaMoneta,NuovaMoneta,
AmmontareDaCamb,AmmontareCambiato, Risposta)
UNTIL Risposta IN ['S','s']
END.
PROCEDURE DammiCambi(VAR DaLireA1: Tipo ArrayConversione);
{
}
VAR
Moneta: TipoMoneta;
BEGIN
DaLireA1[Lire]:=1000;
writeln(‘ Salve! Dammi i rapporti di cambio di oggi: ‘);
FOR Moneta:=Dollaro TO Yen DO
BEGIN
write (‘Lire / ‘);MostraCambio(Moneta);
write(‘: ‘);
readln(DaLireA1[Moneta])
END;
writeln(‘ Grazie! Ciao ‘);
END;
DammiMonete
Pseudo-codice
REPEAT
introduci SiglaMoneta
UNTIL Valido(SiglaMoneta)
DaMoneta  Nome(SiglaMoneta)
REPEAT
introduci SiglaMoneta
UNTIL Valido(SiglaMoneta)
NuovaMoneta  Nome(SiglaMoneta)
mostra i valori delle monete
FUNCTION Valido(SiglaMoneta1: char): boolean;
BEGIN
Valido:=SiglaMoneta1 IN [‘L’,’D’,’R’,’S’,’Y’]
END;
FUNCTION Nome(SiglaMoneta1: char): TipoMoneta;
{ }
BEGIN
CASE SiglaMoneta1 OF
‘E’: Nome:=Lira;
’D’: Nome:= Dollaro;
’R’: Nome:= Rublo;
’S’: Nome:= FrancoSvizzero;
’Y’: Nome:= Yen
END
{CASE}
END;
PROCEDURE DammiMonete(VAR DaMon, NuovaMon: TipoMoneta);
VAR
Moneta: char;
BEGIN
REPEAT
write('Cambio da: ');
readln(Moneta);
UNTIL Valido(Moneta);
DaMon:=Nome(Moneta);
REPEAT
write('A: ');
readln(Moneta);
UNTIL Valido(Moneta);
NuovaMon:=Nome(Moneta)
BEGIN
END;
Istruzioni;
DammiCambi(DaLireA);
REPEAT
DammiMonete(DaMoneta, NuovaMoneta);
Cambia(DalireA,AmmontareDaCamb,AmmontareCambiato);
MostraQuadroRiepilogativo(DaMoneta,NuovaMoneta,
AmmontareDaCamb,AmmontareCambiato, Risposta)
UNTIL Risposta IN ['S','s']
END.
BEGIN
Istruzioni;
DammiCambi(DaLireA);
REPEAT
DammiMonete(DaMoneta, NuovaMoneta);
Cambia(DalireA,AmmontareDaCamb,AmmontareCambiato);
MostraQuadroRiepilogativo(DaMoneta,NuovaMoneta,
AmmontareDaCamb,AmmontareCambiato, Risposta)
UNTIL Risposta IN ['S','s']
END.
PROCEDURE Cambia(DaLirA:ArrayConversione;VAR
AmmDaCamb, AmmCambiato:real);
BEGIN
write(' Introduci ammontare da cambiare: ');
readln(AmmDaCamb);
AmmCambiato:= AmmDaCamb*DaLirA[NuovaMoneta]/DaLirA[DaMoneta];
END;
BEGIN
Istruzioni;
DammiCambi(DaLireA);
REPEAT
DammiMonete(DaMoneta, NuovaMoneta);
Cambia(DalireA,AmmontareDaCamb,AmmontareCambiato);
MostraQuadroRiepilogativo(DaMoneta,NuovaMoneta,
AmmontareDaCamb,AmmontareCambiato, Risposta)
UNTIL Risposta IN ['S','s']
END.
PROCEDURE MostraQuadroRiepilogativo(DaMon, NuovaMon :
TipoMoneta; AmmDaCamb, AmmCambiato: real;VAR Risp:char);
BEGIN
write('Converti ');
write(AmmDaCamb:4:2,' ');
MostraCambio(DaMon);
write(' in ');
write(AmmCambiato :4:2,' ');
MostraCambio(NuovaMon);
writeln;
write('Mi posso riposare? ');
readln(Risp)
END;
{ ******************* BODY *********************** }
BEGIN
Istruzioni;
DammiCambi(DaLireA);
REPEAT
DammiMonete(DaMoneta, NuovaMoneta);
Cambia(DalireA, AmmontareDaCamb,
AmmontareCambiato);
MostraQuadroRiepilogativo(DaMoneta,NuovaMoneta,
AmmontareDaCamb,AmmontareCambiato, Risposta)
UNTIL Risposta IN ['S','s']
END.
ALGORITMI DI RICERCA LINEARE
Problema: Cercare tra i valori contenuti in un Array un preassegnato
valore.
Es.: Data una lista di N numeri verificare se esiste un preassegnato
Valore.
Indice 
Data la lista
1
10
2
19
3
98
4
30
5
29
6
12
7
18
Cerca se in essa è contenuto il numero 12
Algoritmo 10.1
Controlla se abbiamo esaminato
tutti gli elementi dell’array
Indice  valore iniziale dell’indice
Trovato  false
WHILE NOT finito AND NOT Trovato DO
IF UnArray[Indice]=ValoreCercato THEN
Trovato  true
ELSE
Indice  nuovo valore dell’indice
IF NOT Trovato THEN
Indice  0
Condizioni di uscita:
- la ricerca è finita se nessun elemento uguale a quello cercato esiste
- la ricerca è finita se almeno un elemento uguale a quello cercato è
stato trovato
I criteri per stabilire il nuovo valore da attribuire all’indice possono
essere i più diversi.
E’ però importante che una volta stabilito che un elemento
individuato da un certo indice non è quello cercato questo elemento
non venga più esaminato.
Una maniera ovvia è quella di partire dall’ultimo elemento della
lista e risalire fino in cima nella ricerca dell’elemento.
Algoritmo 10.2
Indice  NumeroTotaleElementi
Trovato  false
WHILE NOT (Indice=0) AND NOT Trovato DO
IF UnArray[Indice]= ValoreCercato
Trovato  true
ELSE
Indice  Indice-1
Se Indice=0 significa che non abbiamo
trovato l’elemento cercato.
Poiché ad ogni passo della ricerca eliminiamo un elemento il
massimo numero di passi è pari al numero di elementi, di qui
anche il nome di Algoritmo di Ricerca Lineare.
Array di nomi
Stringa
Indice:=CercaIndice(Nome, NumeroElementi,ValoreCercato);
IF Indice<>0 THEN
BEGIN
write(ValoreCercato,’ è stato trovato nella posizione ‘,Indice:2);
END
ELSE
write(ValoreCercato,’ non è stato trovato ‘);
FUNCTION CercaIndice(VAR Nome: NomeArray; NumeroElementi:integer;
ValoreCercato:NomeStringa):integer;
VAR
Indice:integer;
Trovato: boolean;
BEGIN
WHILE NOT (Indice=0) AND NOT Trovato DO
IF Nome[Indice]=ValoreCercato THEN
Trovato:= true
ELSE
Indice:= Indice-1;
CercaIndice:= Indice
END.
FUNCTION CercaIndice(VAR Nome: NomeArray;
NumeroElementi:integer;
ValoreCercato:NomeStringa):integer;
VAR
Indice:integer;
BEGIN
Nome[0]: =ValoreCercato;
Indice:=NumeroElementi;
WHILE Nome[Indice]<>ValoreCercato DO
Indice:= Indice-1;
Nome[0]=‘’;
CercaIndice:= Indice
END;
Uso di una sentinella per
eliminare la variabile
booleana
sentinella
ORDINAMENTO = SORTING
1
10
9
2
19
10
3
9
12
4
30
18
5
29
19
6
12
29
7
18
30
PROCEDURE OrdinaInteri(VAR Interi: ArrayInteri);
CONST
UltimoElemento=7;
TYPE
ArrayInteri=ARRAY[1.. UltimoElemento] OF integer;
VAR
Interi:= ArrayInteri;
BEGIN
……………
END;
I° Approccio
FOR Ordine  1 TO UltimoElemento-1 DO
scambia gli elementi nel sub-range Ordinati..UltimoElemento
Ipotesi di lavoro:
Per ogni algoritmo che progetteremo, una volta ordinata una parte
della lista, ad esempio da 1 a Ordine, i rimanenti elementi presenti
nella parte da Ordine+1 fino a UltimoElemento sono tutti
maggiori in valore di qualunque elemento appartenente alla parte
della lista già ordinata.
Tutti ordinati
1
Tutti di valore maggiore agli ordinati
Ordine Ordine +1
UltimoElemento
BUBBLE SORT
Pseudo-codice
FOR Indice  UltimoElemento-1 DOWNTO Ordinato DO
IF Interi[Indice]> Interi[Indice+1] THEN
Scambia(Interi[Indice], Interi[Indice+1] )
Ordinato=1
10
19
9
30
29
12
18
10
19
9
12
30
29
18
10
19
9
30
29
12
18
10
19
9
12
30
29
18
10
19
9
30
12
29
18
10
9
19
12
30
29
18
Ordinato=2
9
10
19
12
30
29
18
Ordinato=3
9
10
19
12
30
29
18
9
10
19
12
18
30
29
9
10
12
19
18
30
29
9
10
19
12
30
18
29
9
10
12
19
18
30
29
9
10
12
19
18
29
30
9
10
19
12
18
30
29
9
10
12
19
18
30
29
9
10
12
19
18
29
30
Ordinato=4
9
10
12
18
19
29
30
9
10
12
19
18
29
30
9
10
12
19
18
29
30
9
10
12
19
18
29
30
9
10
12
19
18
29
30
9
10
12
18
19
29
30
Ordinato=6
Ordinato=5
9
10
12
18
19
29
30
9
10
12
18
19
29
30
9
10
12
18
19
29
30
9
10
12
18
19
29
30
Ordinato=7
9
10
12
18
19
29
30
9
10
12
18
19
29
30
N° confronti: (n-1)+(n-2)+…+1=(n-1)*n/2
PROCEDURE BubbleSort(Var Interi:ArrayInteri);
VAR
Ordina, Indice :1..UltimoElemento;
BEGIN
FOR Ordinato:=1 TO UltimoElemento-1 DO
BEGIN
FOR Indice:=UltimoElemento-1 DOWNTO Ordinato DO
IF Interi[Indice]> Interi[Indice+1] THEN
Scambia(Interi[Indice],Interi[Indice+1] )
END;
END;
PROCEDURE Scambia(Var Int1,Int2:integer);
VAR
Temp:integer;
BEGIN
Temp:= Int1;
Int1:= Int2;
Int2:= Temp;
END;
SELECTION SORT
Ordinamento per selezione
E’ un poco più efficiente del Bubble perché effettua solo una
sostituzione ad ogni giro del loop.
Pseudo-codice
FOR Ordina  1 TO UltimoElemento-1
IndiceMinimo  valore dell’indice dell’elemento più piccolo nel
sub-range Ordina..UltimoElemento-1
Scambia(Interi(Ordina),Interi(IndiceMinimo))
1
10
19
9
30
29
12
18
9
19
10
30
29
12
18
9
10
19
30
29
12
18
1
2
3
3
3
1
10
19
9
30
29
12
18
9
19
10
30
29
12
18
9
10
19
30
29
12
18
3
2
3
3
3
1
10
19
9
30
29
12
18
3
9
19
10
30
29
12
18
9
10
19
30
29
12
18
2
3
3
6
1
10
19
9
30
29
12
18
9
19
10
30
29
12
18
9
10
18
30
29
19
12
3
2
3
1
10
19
9
30
29
12
18
9
19
10
30
29
12
18
3
1
10
19
9
30
29
12
18
Ordina=1
3
2
Ordina=2
3
3
Ordina=3
6
SELECTION SORT
9
10
12
30
29
19
18
9
10
12
18
30
29
19
9
10
12
18
19
30
29
4
5
5
6
9
10
12
30
29
19
18
9
10
12
18
29
30
19
4
6
9
10
12
30
29
19
18
7
Ordina=4
7
Ordina=5
5
7
Ordina=6
6
4
N° confronti: (n-1)+(n-2)+…+1=(n-1)*n/2
9
10
12
18
19
29
30
SELECTION SORT
7
SELECTION SORT
PROCEDURE SelectionSort(Var Interi:ArrayInteri);
VAR
Ordina, Indice, IndiceMinimo :1..UltimoElemento;
BEGIN
FOR Ordina:=1 TO UltimoElemento-1 DO
BEGIN
IndiceMinimo:=Ordina;
FOR Indice:= Ordina+1 TO UltimoElemento DO
IF Interi[Indice]< Interi[IndiceMinimo] THEN
IndiceMinimo:=Indice;
Scambia(Interi[IndiceMinimo],Interi[Ordina] )
END
END;
INSERTION SORT
Ordinamento per inserimento
E’ l’algoritmo più intuitivo. Se ad esempio si ha un mazzo di carte
non ordinato possiamo ordinarlo scorrendo le carte una alla volta
e inserendo ogni carta immediatamente dopo la carta più piccola
tra quelle che la precedono.
Supponiamo che il primo elemento sia già ordinato.
Pseudo-codice
FOR PostoSuccessivo  2 TO UltimoElemento DO
sposta tutti gli elementi maggiori di Interi[PostoSuccessivo ] di un
posto in avanti e metti Interi[PostoSuccessivo ] nella sua giusta
posizione
Tutti ordinati
11
Interi[1]
61 65
Non ancora ordinati
63
Interi[PostoSuccessivo]
33
UltimoElemento
Inserisci tra questi due elementi
Algoritmo
Supponiamo di essere al passo j. Confrontiamo il valore
dell’elemento di Interi[j] con i suoi predecessori. Se chi lo precede ha
un valore più elevato lo spostiamo di un posto in avanti. Se
incontriamo nella posizione i un valore più basso allora poniamo in
Interi[i+1]  Interi[j].
Pseudo-codice
Temp  Interi[PostoSuccessivo]
Posizione  PostoSuccessivo-1
WHILE Interi[Posizione ] > Temp DO
Interi[Posizione+1]  Interi[Posizione]
Posizione  Posizione -1
Potrebbe succedere che uno degli elementi sia più piccolo di tutti e
che quindi noi, risalendo la lista cerchiamo di confrontarlo con
l’elemento posto in Interi[0] provocando così un crash.
Per evitare questo definiamo il range dell’array Interi variabile tra
0..UltimoElemento e ogni volta che scegliamo un valore per eseguire
i confronti lo memorizziamo temporaneamente in Interi[0], così che
se esso fosse il più piccolo di tutti comunque verrebbe posto in
Interi[0+1]
PostoSuccessivo
2
3
4
5
[0]
[1]
[2]
10
10
19
9
30
29
12
18
[0]
[1]
[2]
[3]
[4]
[5]
[6]
[7]
10
10
19
9
30
29
12
18
9
10
9
19
30
29
12
18
9
9
10
19
30
29
12
18
[0]
[1]
9
9
[0]
[1]
30
9
10
19
30
29
12
18
29
9
10
19
29
30
12
18
[2]
10
[2]
[3]
[3]
19
[3]
[4]
[4]
30
[4]
[5]
[5]
29
[5]
[6]
[6]
12
[6]
[7]
[7]
18
[7]
6
7
[0]
[1]
[2]
29
9
10
19
29
30
12
18
12
9
10
19
29
12
30
18
12
9
10
19
12
29
30
18
12
9
10
12
19
29
30
18
[0]
[1]
12
9
10
12
19
29
30
18
18
9
10
12
19
29
18
30
18
9
10
12
19
18
29
30
18
9
10
12
18
19
29
30
[2]
[3]
[3]
[4]
[4]
[5]
[5]
[6]
[6]
[7]
[7]
N° confronti: (n-1)+(n-2)+…+1=(n-1)*n/2
PROCEDURE InsertionSort(VAR Interi: ArrayInteri);
VAR
PostoSuccessivo,
Posizione: 0..UltimoElemento;
BEGIN
FOR PostoSuccessivo:=2 TO UltimoElemento DO
BEGIN
Interi[0]:=Interi[PostoSuccessivo];
Posizione:= PostoSuccessivo-1;
WHILE Interi[Posizione]>Interi[0] DO
BEGIN
Interi[Posizione+1]:= Interi[Posizione];
Posizione:=Posizione-1
END;
Interi[Posizione+1]:=Interi[0]
END
END;
IL CORSO TERMINA IL 17 GENNAIO
PRIMA PROVA SCRITTA IL 22 GENNAIO
PER SOSTENERE L’ESAME BISOGNA AVERE
CONSEGUITO
UNA VOTAZIONE TRA A-D
SIA PER LA
PROVA SCRITTA
SIA PER
IL PROGETTO CHE VA CONSEGNATO ALLEGANDO UNA
RELAZIONE E IL FLOPPY DISK
AL PIU’ TARDI 10 GIORNI PRIMA DELL’ESAME ORALE
REQUISITI MINIMALI PER IL PROGETTO
• Pseudo Codice
• Rappresentazione grafica
• Relazione
• Programma Pascal
ALGORITMO DI RICERCA BINARIA
Data una lista di N elementi ordinati cercare se tra essi esiste un
determinato elemento.
Dividiamo gli elementi ordinati in due parti. Quello che cerchiamo
può appartenere o alla prima o alla seconda parte, essendo tutti gli
elementi ordinati. Dividiamo la parte scelta ancora in due e
applichiamo ancora il ragionamento precedente. L’algoritmo
termina o quando l’ultimo elemento rimasto dalle successive
suddivisioni è uguale a quello cercato, oppure quando l’intervallo
rimasto non è più suddivisibile il che implica che il nostro elemento
non appartiene alla lista.
Supponiamo di vedere se 19 appartiene alla seguente lista
1
2
3
4
[1]
[2]
[3]
[4]
[5]
[6]
[7]
9
10
12
19
20
29
30
[4]
[5]
[6]
[7]
19
20
29
30
[4]
[5]
19
20
[4]
19
Condizioni di uscita
A - il valore cercato è stato trovato (Flag booleano = TRUE)
B - il valore cercato non è stato trovato (espressione che indichi
questa condizione)
Quando riducendo i sub-range Basso>Alto e il valore cercato non
è stato trovato allora esci
NOT Basso>Alto
oppure Basso<=Alto
Basso  1
Pseudo-codice
Alto  ElementiTotali
Uso di un flag booleano
Trovato  false
WHILE (Basso<=Alto) AND NOT Trovato DO
BEGIN
Metà  (Basso+Alto) DIV 2
IF Interi[Metà ] = ValoreCercato THEN
Trovato = true
ELSE
IF Interi[Metà ] < ValoreCercato THEN
Basso  Metà+1
[2 4 8 11 12 21 30]
ELSE
Alto  Metà-1
ValoreCercato=30
END
Indice=7
IF Trovato THEN
Metà
Basso
Alto
Indice  Metà
4
1
7
ELSE
6
5
7
Indice  0
7
7
7
ValoreCercato=11
Indice=4
Metà
Basso
Alto
4
1
7
Senza flag booleano
Condizioni di uscita
Si cerca l’intervallo entro il quale il valore cercato potrebbe
trovarsi.
Questa ricerca termina quando modificando di volta in volta gli
indici Basso e Alto non si verifica una inversione dei valori.
A questo punto si esce dal ciclo e si verifica se l’elemento che si trova
nella posizione Basso è quello cercato. Nel caso di risposta positiva
l’indice sarà Basso altrimenti sarà 0.
Basso:=1;
Alto:=ElementiTotali
WHILE Basso <= Alto DO
BEGIN
Meta:=(Basso+Alto) DIV 2;
IF Interi[Meta]< ValoreCercato THEN
Basso:=Meta+1;
ELSE
Alto:=Meta-1;
IF Basso <= ElementiTotali THEN
IF Interi[Basso]= ValoreCercato THEN
Indice:=Basso
ELSE
[2 4 8 10 30 40 50]
Indice:=0;
END;
Basso
1
5
5
6
Alto
7
7
5
Meta
4
6
5
Interi[Meta]
10
40
30
NOTAZIONE ASINTOTICA
g(n)
Upper bound
f(n)
f ( n) = O (g (n ))  f ( n)  c * g ( n) "n
n
O(n log n)
Lower bound
f ( n) = W(g (n ))  f ( n)  c * g ( n) "n
W (n log n)
f(n)
g(n)
n
Definiamo complessità di un algoritmo il numero di passi massimo
previsto perché esso termini.
La valutazione di complessità di un algoritmo va fatta sul caso
peggiore che detto algoritmo si potrebbe trovare ad affrontare.
Ad esempio nel caso dell’algoritmo di ricerca lineare il caso
peggiore si presenta quando il valore cercato si trova all’ultimo
posto della lista. Quindi la complessità di tale algoritmo è O(N) se
N sono gli oggetti della lista.
g(N)
100
f(N)
100
N
Ogni volta che si introduce un loop su N elementi avremo una
complessità pari a O(N). Ovviamente due loop annidati uno dentro
l’altro avranno complessità O(N2) e così via.
Gli algoritmi di sort proposti: Bubble, Selection e Insertion hanno
tutti complessità pari a O(N2) avendo ognuno due loop annidate.
L’algoritmo per LA TOMBOLA ha complessità pari a O(N)
L’algoritmo di Ricerca Binaria ha una complessità pari a O(log2N).
Infatti ad ogni passo noi dividiamo il numero N totale di elementi
su cui cercare il valore richiesto per 2 e facciamo un solo confronto
per passo.
Se N è il numero totale di elementi quante volte dobbiamo dividere
N per due affinchè diventi uguale o minore di 1?
N
N/2
N= 2k
……
N/4

N/ 2k
k= log2N
60
50
40
O(N)
32
30
O(log(N))
20
10
0
5
1 6 11 16 21 26 31 36 41 46
N=10.000.000
log2(N)=23,25
LINEARE
1000*10=10.000sec=2,7 h
Ciclo = 10-6 sec T= 10-6 * 107=10 sec
Ciclo = 10-6 sec T= 10-6 * 23 sec
BINARIA
1000*23* 10-6 = 23* 10-3 sec=23 ms
Le chiamate degli array per valore e per variabile sottostanno agli
stessi criteri validi per le variabili classiche:
la chiamata per valore non modifica il contenuto dell’array dopo il
suo utilizzo nell’ambito della procedura mentre quella per variabile
lo modifica.
Nel caso della chiamata di un array per valore un FOR interno
trasferisce elemento per elemento l’array nell’area dati prendendo
quindi tempo di computazione e occupando, anche se
IN
GENERE PER GLI ARRAY SI USA LA
temporaneamente spazio di memoria.
PER
Nel caso CHIAMATA
della chiamata di un array
perVARIABILE
variabile nell’area dati viene
memorizzato solo l’indirizzo del primo elemento dell’array e per gli
altri elementi se richiesti gli indirizzi vengono calcolati di volta in
volta. Quindi minore tempo di calcolo, in media, e minore spazio
occupato in area dati.
Supponiamo di avere un Programma che chiama la procedura di
Ricerca Binaria. Se tra programma e procedura passiamo l’array
con i dati mediante una chiamata per valore allora noi avremo
un numero di chiamate pari a O(N), più il numero di passi necessari
per la ricerca, pari a O(log2N).
La complessità totale sarà quindi data da
O(N+log2N)O(N)
Se invece tra programma e procedura passiamo l’array con i dati
mediante una chiamata per variabile (passiamo solo l’indirizzo)
allora noi avremo un numero di chiamate pari a O(1) più sempre
il numero di passi necessari alla ricerca pari a O(log2N).
La complessità totale sarà quindi data da
O(1+log2N)= O(log2N)
Quando si hanno due algoritmi che risolvono lo stesso problema
ma hanno diverse complessità, ovviamente si deve scegliere quello
con complessità più piccola.
A parità di complessità vanno considerati diversi altri fattori sia
legati all’uomo che alla macchina.
Ad esempio un programma un poco più lento di un altro ma con
una codifica semplice può essere preferito perché se suscettibile di
modifiche o manutenzioni frequenti il costo per modificarlo è più
basso.
SUGGERIMENTI
Controllare che i dati digitati siano coerenti con quelli che il
programma si aspetta.
Usando gli array controllare sempre che gli indici attraverso cui si
gestisce l’array non assumano valori esterni al sub-range di
definizione.
Quando si progettano algoritmi di sorting fare test sui casi estremi
(es. array già ordinato, array ordinato in ordine inverso, etc.)
ricordando che le possibili disposizioni degli oggetti in un array
sono n! dove n è il numero di elementi dell’array .
Per la ricerca binaria fare i seguenti test:
•Cercare l’elemento in prima posizione
•Cercare l’elemento in ultima posizione
•Cercare un elemento tra la prima e l’ultima posizione
•Controllare il caso in cui si è in presenza di elementi duplicati.
ESERCIZIO
Scrivere un algoritmo di ricerca binaria su un array ordinato che
indichi se l’elemento cercato appartiene all’array e se è presente
più volte.
Es. INPUT ArrayOrdinato [2 4 5 6 6 6 8 8 9]
ValoreCercato: 6
OUTPUT Il valore cercato 6 appartiene all’array e ricorre 3
volte.