PROGETTO
PROGRAMMA PRINCIPALE Program
uses xxxx, yyyy;
…………………...…..
end.
MODULO 1 -
unit xxxx
………………...
end.
………………………………………….
MODULO n -
unit yyyy
………………...
end.
DATA ABSTRACTION
Qualunque tipo di dati può essere descritto sulla base dei valori
che esso può prendere e delle operazioni che ad esso si possono
applicare.
ESEMPIO
Tipo
integer
real
boolean
Valori
- maxint ÷ + maxint
10-38 ÷ 10+38
TRUE, FALSE
Operazioni
+, -, *, DIV
+, -, *, /
AND, OR, NOT
Un abstract data type (ADT) e’ un Type
definito in termini del nome logico che gli si
attribuisce e delle operazioni che possono
essere applicate ad esso.
DATA ABSTRACTION
Separazione del significato logico delle operazioni in
un ADT dai dettagli implementativi.
X=5
X-5=0
Numeri Naturali {gli interi da 0 a infinito}
X+5=0
X = -5
Numeri Interi {gli interi da - infinito a infinito}
2X - 3 = 0
X = 3/2
Numeri Razionali {i numeri che si ottengono come rapporto di due interi}
X2 - 2 = 0
X = 2
Numeri Reali {i numeri decimali periodici e non periodici }
X2 + 1 = 0
X = -1
Numeri Complessi {i numeri definiti nello spazio a due dimensioni R,i }
Nel 1572 tale Raffaele Bombelli, colui che per primo introdusse le
parentesi, propose di trattare la  1 come una entità a parte e di
applicare ad essa tutte le regole che valevano per i numeri normali.
Cartesio chiamò i numeri che prevedevano la presenza della  1
numeri “immaginari” mentre Gauss li chiamò “complessi”.
Solo nel 1777 Eulero propose di sostituire  1 con la lettera “i”.
I numeri complessi sono usati in elettrotecnica, dinamica dei fluidi,
aerodinamica etc.
Notizie sui numeri complessi si trovano in
IL TEOREMA DEL PAPPAGALLO di Denis Guedj, ed. Longanesi, pag.326
IL LINGUAGGIO DELLA MATEMATICA di Keith Devlin ed. Bollati Boringhieri, pag. 159
NUMERI COMPLESSI
Un numero complesso in genere è scritto come
a + bi
dove a e b sono dei numeri reali e i, detta parte immaginaria, è tale
che
i2=-1
i
3
2
2+1i
1
0
-3
-2
-1
r
1
2
3
-1
-2-2i
-2
-3
Rappresentazione grafica dei numeri complessi
TEOREMA FONDAMENTALE DELL’ALGEBRA
Gauss 1799
Qualsiasi equazione polinomiale
an x  an1 x
n
n1
 .......  a1 x  a0  0
1
I cui coefficienti siano numeri complessi ha soluzioni all’interno
dei numeri complessi
Progettare una ADT per i numeri complessi significa realizzare un
software che permetta di definire un Type Complesso e che
implementi tutta una serie di operazioni tipiche dei numeri
complessi. Es. addizione, sottrazione, moltiplicazione, divisione,
valore assoluto, ……………………………..
Una ADT, una volta implementata viene memorizzata su un file e
richiamata da un programma solo quando richiesta. Ognuno di
questi file è definito come unit e come tale è riconosciuto dal
programma principale quando viene richiamato.
UNIT
(pag. 906 testo Meyers)
E’ un insieme di costanti, tipi, dati, variabili funzioni e procedure
che può essere memorizzato su un file e compilato separatamente
dal programma principale che lo chiama.
Nel Turbo Pascal per compilare una unit si deve scegliere sotto la
voce COMPILE l’option DISK (per i programmi generali si usa
invece MEMORY).
Per richiamare una unit in un programma si usa la parola chiave
uses nome_unit, ….;
UNIT
interfaccia
Contiene le dichiarazioni globali a tutta la unit e le definizioni di
procedure e funzioni da esportare
implementazione
Contiene i corpi delle procedure e funzioni sopra dichiarate insieme
alle dichiarazioni di costanti, tipo, variabili e procedure locali
all’unità.
unit xxxxxxxx;
interface
……….
implementation
………………
end.
NUMERI COMPLESSI
X + Yi
TYPE
ComplexNo=RECORD
XRe, YIm: real
END;
ComplexNo
XRe
YIm
UNIT ADTComplexNo;
{documentazione}
INTERFACE
{definizioni dell’ADT}
{sezione interfaccia}
TYPE
ComplexNo=RECORD
XRe, YIm: real
END;
{
le operazioni
PROCEDURE ……………………..
FUNCTION ………………………….
}
IMPLEMENTATION
{sezione implementazioni}
PROCEDURE ……………………..
FUNCTION ………………………….
NUMERI COMPLESSI
a + bi
Le operazioni con i numeri complessi:
Parte Reale: a
Parte Immaginaria: b
Modulo: a 2  b 2
Somma : (a + bi) + (c + di) = (a + c) + (b + d) i
Sottrazione: (a + bi) - (c + di) = (a - c) + (b - d) i
Moltiplicazione: (a + bi) * (c + di) = (ac - bd) +(ad + bc) i
Divisione:
a  bi a  bi c  di ac  bd  bc  ad 

*
 2
 2
i
2
2 
c  di c  di c  di c  d
c d 
UNIT ADTComplexNo;
{documentazione}
INTERFACE
{inizio della sezione INTERFACE }
{
definizioni dell’ADT
}
TYPE
ComplexNo=RECORD
Xre, Yim: real
END;
{
le operazioni
}
PROCEDURE MakeComp(Xpart, Ypart:real;
VAR Cnumber: ComplexNo);
{
costruisci il numero complesso
}
FUNCTION RealPart(Cnumber: ComplexNo):real;
{
identifica la parte reale del numero complesso }
FUNCTION ImaginaryPart(Cnumber: ComplexNo):real;
{
identifica la parte immaginaria del numero complesso
FUNCTION Magnitude(Cnumber: ComplexNo):real;
{
identifica il modulo del numero complesso }
}
PROCEDURE AddComp(Term1, Term2:ComplexNo;
VAR Sum: ComplexNo);
{
addiziona i numeri complessi Term1 e Term2
}
PROCEDURE SubtrComp(Term1, Term2: ComplexNo;
VAR Difference: ComplexNo);
{
sottrae i numeri complessi Term1 e Term2 }
PROCEDURE MultComp(Factor1, Factor2: ComplexNo;
VAR Product: ComplexNo);
{
moltiplica i numeri complessi Factor1 e Factor2 }
PROCEDURE DivComp(Factor1, Factor2: ComplexNo;
VAR Quotient: ComplexNo);
{
divide i numeri complessi Factor1 e Factor2 }
{
fine della sezione INTERFACE
}
IMPLEMENTATION {inizio della sezione IMPLEMENTATION }
PROCEDURE MakeComp(Xpart, Ypart:real;
VAR Cnumber: ComplexNo);
{
costruisci il numero complesso
}
BEGIN
Cnumber.Xre:=Xpart;
Cnumber.Yim:=Ypart
END;
FUNCTION RealPart(Cnumber: ComplexNo):real;
{
identifica la parte reale del numero complesso }
BEGIN
RealPart:= Cnumber.Xre
END;
FUNCTION ImaginaryPart(Cnumber: ComplexNo):real;
{
identifica la parte immaginaria del numero complesso
BEGIN
ImaginaryPart:= Cnumber.Yim
END;
}
FUNCTION Magnitude(Cnumber: ComplexNo):real;
{
identifica il modulo del numero complesso
a2  b2
}
BEGIN
Magnitude:= sqrt(sqr(Cnumber.Xre)+sqr(Cnumber.Yim))
END;
PROCEDURE AddComp(Term1, Term2:ComplexNo;
VAR Sum: ComplexNo);
{
addiziona i numeri complessi Term1 e Term2
(a + bi) + (c + di) = (a + c) + (b + d) i }
BEGIN
WITH Sum DO
BEGIN
Xre:=Term1.Xre+Term2.Xre;
Yim:=Term1.Yim+Term2.Yim
END
END;
PROCEDURE SubtrComp(Term1, Term2:ComplexNo;
VAR Difference: ComplexNo);
{
addiziona i numeri complessi Term1 e Term2
(a + bi) - (c + di) = (a - c) + (b - d) i }
BEGIN
WITH Difference DO
BEGIN
Xre:=Term1.Xre - Term2.Xre;
Yim:=Term1.Yim - Term2.Yim
END;
END;
PROCEDURE MultComp(Factor1, Factor2:ComplexNo;
VAR Product: ComplexNo);
{
addiziona i numeri complessi Term1 e Term2
(a + bi) * (c + di) = (ac - bd) +(ad + bc) i }
BEGIN
WITH Product DO
BEGIN
Xre:=Factor1.Xre * Factor2.Xre - Factor1.Yim * Factor2.Yim;
Yim:=Factor1.Xre * Factor2.Yim + Factor2.Xre * Factor1.Yim
END
END;
PROCEDURE DivComp(Factor1, Factor2:ComplexNo;
VAR Quotient: ComplexNo);
{
addiziona i numeri complessi Term1 e Term2
a  bi ac  bd  bc  ad 
 2
 2
i
2
2 
c  di c  d
c d 
}
VAR
Divisor: real;
{divisore del quoziente}
BEGIN
Divisor:=sqr(Factor2.Xre) + sqr(Factor2.Yim);
WITH Quotient DO
BEGIN
Xre:=(Factor1.Xre * Factor2.Xre + Factor1.Yim * Factor2.Yim)/Divisor;
Yim:= (Factor1.Yim *Factor2.Xre - Factor1.Xre * Factor2.Yim)/Divisor
END
END;
ESEMPIO
Risolvere l’equazione di primo grado AX+B=C con A, B, C
numeri complessi. Supponiamo A 0.
Soluzione: X=(C-B)/A
Input: Introdurre i coefficienti nell’ordine: A, B, C
Per ogni coefficiente introdurre prima la parte reale e poi
la parte immaginaria.
Ouput: Mostrare la soluzione X sotto forma di numero complesso
Pseudo codice
Richiama la unit per i numeri complessi;
Mostra le istruzioni per l’introduzione dei dati;
Leggi i coefficienti;
Calcola la soluzione;
Mostra la soluzione.
Equazione
A
B
C
Mostra Istr.
Leggi
ADTComplexNo
A
B
C
X
Calcola
ADTComplexNo
X
Mostra Ris.
ADTComplexNo
PROGRAM Equazione(input,output);
USES
Compl;
VAR
A,B,C,
{coefficienti}
X: ComplexNo;
{soluzione}
PROCEDURE MostraIstruzioni;
BEGIN
writeln('L'' equazione e'' immaginata sotto la forma
AX+B=C. ' );
writeln('I coefficienti A,B,C vanno introdotti come coppie di
numeri:');
writeln('prima la parte reale e poi quella immaginaria')
END;
PROCEDURE MC(Z:ComplexNo);
{mostra il numero complesso Z}
VAR
Segno:STRING[3];
BEGIN
Segno:=’ - ';
IF ImaginaryPart(Z)<>0 THEN
BEGIN
IF ImaginaryPart(Z)>0 THEN Segno:=' + ';
writeln(RealPart(Z):3:1,Segno,ImaginaryPart(Z):3:1,'i')
END
ELSE
writeln(RealPart(Z):3:1)
writeln
END;
PROCEDURE LeggiCoefficienti(VAR A,B,C:ComplexNo);
VAR
ARe,BRe,CRe,AIm,BIm,CIm:real;
BEGIN
write('Coefficiente A= ');
readln(ARe,AIm);
write('Coefficiente B= ');
readln(BRe,BIm);
write('Coefficiente C= ');
readln(CRe,CIm);
MakeComp(ARe,AIm,A);
MakeComp(BRe,BIm,B);
MakeComp(CRe,CIm,C)
END;
PROCEDURE Soluzione(A,B,C:ComplexNo; VAR X:ComplexNo);
{documentazione}
VAR
CmenoB:ComplexNo;
BEGIN
SubtrComp(C,B,CmenoB);
DivComp(CmenoB,A,X)
END;
PROCEDURE MostraRisultato(X:ComplexNo);
BEGIN
writeln('La radice dell''equazione assegnata e'': ');
MC(X)
END;
{
BODY
}
BEGIN
MostraIstruzioni;
LeggiCoefficienti(A,B,C);
Soluzione(A,B,C,X);
MostraRisultato(X)
END.
OUTPUT
L' equazione e' immaginata sotto la forma AX+B=C.
I coefficienti A,B,C vanno introdotti come coppie di numeri:
prima la parte reale e poi quella immaginaria
Coefficiente A= 5 66
Coefficiente B= 77 55
Coefficiente C= 4 2
La radice dell'equazione assegnata e':
-0.9 + 1.0i
ESERCIZIO 1-B
Progettare e realizzare una Unit che permetta il calcolo delle aree e
dei perimetri delle seguenti figure geometriche:
Triangolo rettangolo – assegnata la base e l’altezza
Rettangolo – assegnata la base e l’altezza
Pentagono e esagono - assegnato il raggio e il lato
Utilizzando la Unit di cui sopra trovare l’area dell’appartamento la cui
planimetria è data in figura assegnando alle dimensioni a,b,c,d,e,f
valori a piacere (da tastiera) e per ogni vano calcolare la superficie
complessiva dei muri sapendo che l’altezza di ogni vano vale k.
c
b
g
a
d
h
f
e
REGOLE GENERALI PER LA PROGETTAZIONE DI
UNIT ADT
Completezza: non necessita di operazioni addizionali per essere usata
Ogni operazione deve appartenere ad una delle seguenti categorie:
Constructor - cambia o inizializza i valori di una variabile astratta
Primitive constructor - assegna un valore ad una variabile astratta
senza fare uso di altre variabili astratte dello stesso tipo. Ha una sola
variabile di output e quelle di input servono per costruire l’output.
Es.
MakeComp(Xpart, Ypart:real; VAR Cnumber: ComplexNo);
{
costruisci il numero complesso
}
Ogni ADT richiede almeno un Primitive constructor così che l'può
assegnare un valore iniziale alla variabile astratta.
Non-primitive constructor -. Ha almeno una variabile di input il cui
tipo è uguale a quello dell’output.
Es.
AddComp(Term1, Term2:ComplexNo; VAR Sum: ComplexNo);
{
addiziona i numeri complessi Term1 e Term2 }
SELECTOR - fornisce informazioni su una variabile di input ADT
ad un parametro di uscita. Spesso è una funzione (il parametro di uscita
in tal caso è la funzione stessa).
Primitive selector - ritorna il valore di uno dei componenti della
variabile astratta. Es.
RealPart(Cnumber: ComplexNo):real;
{
identifica la parte reale del numero complesso }
Ogni unit necessita di un Primitive selector altrimenti il client non
può mostrare i valori della variabile.
Non-primitive selector - ritorna il valore che non è relativo ad uno
dei componenti della variabile astratta ma ciò nonostante è utile al
client.
Es.
Magnitude(Cnumber: ComplexNo):real;
{
identifica il modulo del numero complesso }
PREDICATE - è una funzione booleana che ritorna informazioni
sul valore o lo stato di una variabile astratta.
Un ADT è completa se il client :
• fa riferimento solo al type dell’ADT (es. ComplexNo)
• non deve mai cambiare la logica delle operazioni della unit
• non deve mai aver bisogno di altre operazioni
Ogni unit ADT deve avere :
• un primitive constructor
• i valori devono poter essere letti e scritti
• tutte le operazioni prevedibili per il tipo di ADT
Le Code
• Una coda è una successione lineare di elementi,
eventualmente anche vuota
• Se gli elementi che compongono una coda sono tutti dello
stesso tipo la coda è detta omogenea.
• Le operazioni elementari che possono esser effettuate su di
esse sono: aggiungere un elemento, cancellare e/o estrarre
un elemento.
1
LE CODE (QUEUE)
Head
Head
Tail
LE CODE (QUEUE)
Le operazioni fondamentali che si fanno sulle code sono:
riempimento e svuotamento.
Questo implica che durante lo svolgimento del programma il
numero di oggetti in coda può cambiare.
Dynamic data type: il numero di componenti nel Data Type
cambia nel corso del programma.
Dobbiamo descrivere una queue in funzione della sua head
(testa), della sua tail (coda), degli oggetti in coda e del loro
numero in ogni istante della computazione.
OPERAZIONI SULLE CODE
In una coda l’elemento inserito per primo viene anche estratto per
primo (FIFO).
In una coda occorrerà allora distinguere tra un inizio o TESTA della
coda (punto di estrazione e/o cancellazione di un elemento) ed una
fine o CODA della coda (punto di inserimento di un nuovo elemento).
Aggiungere ed eliminare oggetti.
Se Items[ ] è un array in cui si collocano gli oggetti. Head l’indice
dell’array corrispondente alla Testa, Tail l’indice corrispondente
alla coda e Item l’oggetto da aggiungere potremmo usare i
seguenti algoritmi:
OPERAZIONI SULLE CODE
AGGIUNGERE
Tail  Tail+1
Items[Tail]  Item
InUse  InUse + 1
ELIMINARE
Head  Head+1
InUse  InUse - 1
SOLUZIONE IMPROPONIBILE !!!!!!!!!!!!
Ogni volta che esce un oggetto bisogna spostare in avanti di un
posto tutti quelli in coda altrimenti lo spazio disponibile si esaurisce
rapidamente pur essendoci posti vuoti.
Testa
1
N°=6
2
3
Coda
4
5
6
7
8
9
Escono due oggetti e ne entrano due
N°=6
Testa
1
1
Coda
2
3
4
5
6
Escono due oggetti e ne entrano tre
Coda
Testa
2
3
4
5
6
7
8
9
8
9
N°=7
7
Possiamo descrivere una queue in funzione della sua head (testa), della
sua tail (coda), degli oggetti in coda e del loro numero in ogni istante
della computazione utilizzando l’espressione
Tail:=Tail MOD MaxQueue + 1
Head:=Head MOD MaxQueue + 1
è infatti facile mostrare che con queste espressioni Tail e Head
assumeranno giusto i valori indicati nella tabella precedente nel caso
dell’esempio mostrato.
LE CODE (QUEUE)
Le queue si riempiono aggiungendo oggetti in coda e si svuotano
a partire dalla testa.
Supponiamo di voler gestire con un meccanismo a coda 100 oggetti
di tipo stringa.
UNIT Code;
{documentazione}
INTERFACE
{definizioni dell’ADT}
{sezione interfaccia}
CONST
QueueType
MaxQueue=100;
Tail
InUse
Head
Items
NullItem=‘’;
TYPE
ItemType=STRING[20] massima lunghezza delle stringhe
QueueType=RECORD
Head,
primo oggetto nella coda
Tail : 1..MaxQueue; ultimo oggetto nella coda
InUse :0..MaxQueue; numero di oggetti in coda
Items: ARRAY[1..MaxQueue] OF ItemType contiene gli
oggetti in coda
END;
{
le operazioni
PROCEDURE MakeQueue(VAR Queue:QueueType);
{
inizializza la coda vuota
}
}
PROCEDURE AddQueue(Item:ItemType; VAR Queue:QueueType);
{ se la coda non è piena aggiungi oggetti altrimenti segnala errore }
PROCEDURE DeleteQueue(VAR Queue:QueueType);
{se la coda non è vuota elimina il primo oggetto altrimenti segnala
errore}
PROCEDURE FirstOnQueue(VAR Queue:QueueType;
VAR Item:ItemType);
{assegna a Item il valore del primo oggetto in coda, in mancanza assegna
valore nullo}
FUNCTION QCount(VAR Queue:QueueType; ):integer;
{
identifica quanti oggetti sono in coda }
FUNCTION QEmpty(VAR Queue:QueueType; ):boolean;
{
vera se non ci sono oggetti in coda }
FUNCTION QFull(VAR Queue:QueueType; ):boolean;
{
vera se la coda è piena }
{
fine della sezione INTERFACE
}
IMPLEMENTATION {inizio della sezione IMPLEMENTATION }
PROCEDURE MakeQueue(VAR Queue:QueueType);
{
inizializza la coda vuota
}
BEGIN
WITH Queue DO
BEGIN
Head:=1;
Tail:=MaxQueue;
InUse:=0
END
END;
QueueType
Head
Tail
InUse
Items
PROCEDURE AddQueue(Item:ItemType; VAR Queue:QueueType);
{ se la coda non è piena aggiungi oggetti altrimenti segnala errore }
BEGIN
WITH Queue DO
IF InUse<>MaxQueue THEN
BEGIN
Tail:=Tail MOD MaxQueue+1
Items[Tail]:=Item;
InUse:=InUse+1
END
ELSE
writeln(‘Errore: la coda è piena’)
END;
QueueType
Head
Tail
InUse
Items
PROCEDURE DeleteQueue(VAR Queue:QueueType);
{se la coda non è vuota elimina il primo oggetto altrimenti segnala
errore}
BEGIN
WITH Queue DO
IF InUse<>0 THEN
BEGIN
Head:=Head MOD MaxQueue+1
InUse:=InUse-1
END
ELSE
writeln(‘Errore: la coda è vuota)
END;
QueueType
Head
Tail
InUse
Items
PROCEDURE FirstOnQueue(VAR Queue:QueueType;
VAR Item:ItemType);
{assegna a Item il valore del primo oggetto in coda, in mancanza
assegna valore nullo}
BEGIN
WITH Queue DO
IF InUse<>0 THEN
Item:=Items[Head]
ELSE
Item:=NullItem
END;
QueueType
Head
Tail
InUse
Items
FUNCTION QCount(VAR Queue:QueueType; ):integer;
{
identifica quanti oggetti sono in coda }
BEGIN
QCount:=Queue.InUse
END;
FUNCTION QEmpty(VAR Queue:QueueType; ):boolean;
{
vera se non ci sono oggetti in coda }
BEGIN
QEmpty:=(Queue.InUse=0)
END;
QueueType
Head
Tail
InUse
Items
FUNCTION QFull(VAR Queue:QueueType; ):boolean;
{
vera se la coda è piena }
BEGIN
QFull:=(Queue.InUse=MaxQueue)
END;
{
fine della sezione IMPLEMENTATION
}
QueueType
Head
Tail
InUse
Items
Alcune considerazioni sulla complessità.
Si noti che abbiamo sempre usato la chiamata VAR per la
variabile Queue perché in questa maniera in un solo passo di
computazione O(1) abbiamo a disposizione l’array Queue mentre
in caso contrario ogni volta avremmo usato la copia dell’array
che ci costa O(N) passi.
Constructor - cambia o inizializza i valori di una variabile astratta
Primitive constructor - assegna un valore ad una variabile astratta
senza fare uso di altre variabile astratte dello stesso tipo. Ha una sola
variabile di output e quelle di input servono per costruire l’output.
PROCEDURE MakeQueue(VAR Queue:QueueType);
{
inizializza la coda vuota
}
Ogni ADT richiede almeno un Primitive constructor così che il
client può assegnare un valore iniziale alla variabile astratta.
Non-primitive constructor -. Ha almeno una variabile di input e il cui
tipo è uguale a quello dell’output.
Es.
PROCEDURE AddQueue(Item:ItemType; VAR Queue:QueueType);
{ se la coda non è piena aggiungi oggetti altrimenti segnala errore }
SELECTOR - fornisce informazioni su una variabile di input ADT
ad un parametro di uscita. Spesso è una funzione (il parametro di uscita
in tal caso è la funzione stessa).
Primitive selector - ritorna il valore di uno dei componenti della
variabile astratta. Es.
PROCEDURE FirstOnQueue(VAR Queue:QueueType;
VAR Item:ItemType);
{assegna a Item il valore del primo oggetto in coda, in mancanza
assegna valore nullo}
Ogni unit necessita di una Primitive selector altrimenti il client non
può mostrare i valori della variabile.
Non-primitive selector - ritorna il valore che non è relativo ad uno
dei componenti della variabile astratta ma ciò nonostante è utile al
client.
Es.
FUNCTION QCount(VAR Queue:QueueType; ):integer;
{
identifica quanti oggetti sono in coda }
PREDICATE - è una funzione booleana che ritorna informazioni
sul valore o lo stato di una variabile astratta.
FUNCTION QEmpty(VAR Queue:QueueType; ):boolean;
{
vera se non ci sono oggetti in coda }
BEGIN
QEmpty:=(Queue.InUse=0)
END;
CONSIGLI PER UNA CORRETTA PROGRAMMAZIONE
Per un corretto funzionamento delle Unit è necessario che ogni
operatore esegua una e una sola operazione e che solo i parametri
necessari e sufficienti siano passati alla procedura. Se una
operazione soddisfa questi criteri è detta pura.
PROCEDURE DeleteQueue(VAR Queue:QueueType);
BEGIN
WITH Queue DO
IF InUse<>0 THEN
BEGIN
Head:=Head MOD MaxQueue+1
InUse:=InUse-1
END
ELSE
writeln(‘Errore: la coda è vuota)
END;
PROCEDURE DeleteQueue(VAR
Queue:QueueType;VAR Item:ItemType);
BEGIN
WITH Queue DO
IF InUse<>0 THEN
BEGIN
Head:=Head MOD MaxQueue+1
InUse:=InUse-1
END
ELSE
writeln(‘Errore: la coda è vuota)
END;
Questo parametro è inutile e fuorviante
CONSIGLI PER UNA CORRETTA PROGRAMMAZIONE
Ogni UNIT deve avere solo operazioni pure.
Ogni operazione deve essere assolutamente necessaria altrimenti non
va inserita nella UNIT.
Ogni operazione deve fare una sola cosa altrimenti si corrono
rischi di errori che possono, in maniera nascosta riversarsi su tutto
il programma.
La logica utilizzata all’interno della UNIT deve essere del tutto
trasparente per il client.
GESTIONE ERRORI
Ogni operazione deve essere dotata di sistemi di controllo per
evitare errori.
PROCEDURE DeleteQueue(VAR Queue:QueueType);
{se la coda non è vuota elimina il primo oggetto altrimenti segnala errore}
BEGIN
WITH Queue DO
IF InUse<>0 THEN
BEGIN
Head:=Head MOD MaxQueue+1
InUse:=InUse-1
END
ELSE
writeln(‘Errore: la coda è vuota’)
END;
GESTIONE ERRORI
Ogni operazione di una unit deve possedere messaggi di errore che
arrestino la computazione e consentano all’utente di fare le
opportune correzioni senza mandare in crash il sistema.
Una adeguata illustrazione delle segnalazioni di errore, delle cause
che li possono produrre e dei provvedimenti da prendere va fatta
nell’ambito del manuale di accompagnamento del software.
ESERCIZIO 2 B
Vogliamo simulare l’attività di un bistrot parigino che vende solo caffè a coppie
di giovani. Il numero di tavolini è limitato e il numero di caffè da vendere è
stabilito all’inizio. Useremo una coda fatta di stringhe, ognuna delle quali è il
nome dei clienti ai tavoli che attendono il caffè.
Il barman si comporta così.
Inizialmente stabilisce quanti caffè deve vendere (un numero pari).
Successivamente si predispone ad accettare uno dei seguenti comandi e quindi li
esegue.
- A (fai accomodare): se in coda ci sono meno di tre clienti il barman accetta la nuova
coppia e la fa accomodare altrimenti rifiuta il posto.
- S (porta il caffè) se almeno un tavolino è occupato porta il caffè al primo
arrivato, se non c’è nessuno si arrabbia. Se sono terminati i caffè si mandano
via quelli che sono rimasti al tavolo. Si presume che preso il caffè il tavolo si
libera subito.
- R (riassunto): comunica il numero di caffè venduti, il numero di caffè rimasti e
la lunghezza della coda.
ALGORITMO del Bistrot
Inizializza(VAR Queue: QueueType; VAR TotaleDaVendere:integer);
TotaleVenduto  0;
ChiedereNumeroCaffè DaVendere
WHILE DaVendere>0
Azione
IF Azione IN [‘a’,’A’,‘V’,’v’,’r’,’R’] THEN
CASE Azione OF
‘a’,’A’: IncrementaCoda(Queue);
‘s’,’S’: Vendita(Queue,TotaleVenduto,TotaleDaVendere)
‘r’,’R’: Riassunto(TotaleVenduto,TotaleDaVendere,ContaCoda)
MostraMessaggioPerFineCaffè.
PROGRAM Bistrot(input,output);
{Simula una coda per servire il caffè a coppie di giovani }
{La coda finisce quando tutti i tavolini sono occupati}
USES Coda;
CONST
MaxSize=3; {dimensione massima della coda}
VAR
Queue:QueueType;
TotaleVenduto,
{totale caffè venduti }
TotaleDaVendere: integer; {caffè da vendere }
Azione: char;
{lettera del menu per fare le scelte }
PROCEDURE Inizializza(VAR Queue:QueueType; VAR TotaleDaVendere:integer);
{fa partire la coda e legge un numero pari di caffè da vendere }
BEGIN
MakeQueue(Queue);
write('Quanti caffè dobbiamo preparare oggi? ');
readln(TotaleDaVendere);
TotaleDaVendere:=abs(TotaleDaVendere); {garanzia contro I numeri negativi }
IF TotaleDaVendere MOD 2 <>0 THEN
TotaleDaVendere:=TotaleDaVendere-1
END;
PROCEDURE IncrementaCoda(VAR Queue:QueueType);
{}
VAR
Name:ItemType;
{Nome da aggiungere alla coda }
BEGIN
IF Qcount(Queue)<MaxSize THEN
BEGIN
write('Nome: ');
readln(Name);
writeln(Name, ' accomodatevi al tavolo, prego.'.');writeln;
AddQueue(Name,Queue)
END
ELSE
writeln('Mi dispiace i tavoli sono tutti occupati. ‘);
writeln;
END;
PROCEDURE Vendita(VAR Queue:QueueType; VAR TotaleVenduto, TotaleDaVendere:integer);
{}
VAR
Name:ItemType;
{nome del cliente }
BEGIN
IF NOT Qempty(Queue) THEN
BEGIN
FirstOnQueue(Queue,Name);
TotaleVenduto:=TotaleVenduto+2;
TotaleDaVendere:=TotaleDaVendere-2;
write(Name);
writeln(' Prego accomodatevi');
DeleteQueue(Queue)
END
ELSE
writeln(Urlo2)
END;
PROCEDURE Riassunto(TotaleVenduto, TotaleDaVendere, OnQueue:integer);
{ mostra la situazione dei biglietti e della coda}
BEGIN
write(TotaleVenduto:1,' biglietti venduti, e ');
writeln(' la lunghezza della coda e'' ',OnQueue,'.');
writeln(' Sono rimasti ancora ',TotaleDaVendere:1,' biglietti da vendere.')
END;
PROCEDURE MostraRifiuto(Queue:QueueType);
{}
VAR
Name:ItemType; {nome della persona a cui chiede scusa }
BEGIN
WHILE NOT Qempty(Queue) DO
BEGIN
FirstOnQueue(Queue,Name);
writeln('Scusate don ',Name,', i bigliette sono finiti.');
DeleteQueue(Queue)
END
END;
{
BEGIN
BODY
}
Inizializza(Queue,TotaleDaVendere);
TotaleVenduto:=0;
writeln(Urlo);
WHILE TotaleDaVendere>0 DO
BEGIN
write('Azione: ');
readln(Azione);
IF Azione IN ['A','a', 'S','s','R','r'] THEN
CASE Azione OF
'A','a': IncrementaCoda(Queue);
'S','s': Vendita(Queue,TotaleVenduto,TotaleDaVendere);
'R','r': Riassunto(TotaleVenduto,TotaleDaVendere,QCount(Queue))
END
END;
MostraRifiuto(Queue);
readln
END.
A:bistrot
ESERCIZIO
Siano date tre code Q1, Q2, Q3 di lunghezza differente. Costruire,
usando la UNIT Queue, una coda Q4 prendendo di volta in volta gli
elementi appartenenti alla coda più lunga fra le tre iniziali.
PROGRAM code (input,output);
uses code,crt;
VAR
c1,c2,c3,c4:queuetype
PROCEDURE inizializza (VAR q1,q2,q3,q4:QueueType);
{inizializza i valori delle dei quattro record che contengono code}
BEGIN
{****MAIN BLOCK**********}
MakeQueue(Q1);
BEGIN
MakeQueue(Q2);
clrscr;
inizializza(c1,c2,c3,c4);
MakeQueue(Q3);
chiedivalori(c1);
MakeQueue(Q4);
chiedivalori(c2);
END;
chiedivalori(c3);
PROCEDURE chiedivalori (VAR qx:QueueType);
creaq4(c1,c2,c3,c4);
{chiede i valori da inserire nelle tre code }
readln;
VAR
END.
stringa:ItemType;
i,n:integer;
BEGIN
write('quanti elementi vuoi inserire nella coda (max30) ? ');
readln(n);
for i:=1 to n do
begin
writeln('dammi il ',i,'° elemento');
readln(stringa);
AddQueue(stringa,qx);
end;
END;
PROCEDURE Aggiungi(VAR qi,q4i:QueueType);{aggiunge}
BEGIN
AddQueue(FirstOnQueue(qi),q4i);
DeleteQueue(qi);
END
PROCEDURE Creaq4 (VAR q1,q2,q3,q4:QueueType);
{crea la quarta coda svuotando le tre iniziali}
BEGIN
WHILE NOT(QEmpty(q1) AND QEmpty(q2) AND QEmpty(q3)) DO
{finchè le tre code non sono tutte vuote}
BEGIN
IF ((QCount(q1) > QCount(q2)) AND > (QCount(q2)>QCount(q3)))
OR ((QCount(q1) > QCount(q3)) AND > (QCount(q3)>QCount(q2))) THEN
Aggiungi(q1,q4)
{se la prima coda è più lunga della terza}
ELSE
IF ((QCount(q2) > QCount(q1)) AND > (QCount(q1)>QCount(q3)))
OR ((QCount(q2) > QCount(q3)) AND > (QCount(q3)>QCount(q1))) THEN
Aggiungi(q2,q4); {prendi l'elemento dalla terza coda}
ELSE
IF ((QCount(q3) > QCount(q1)) AND > (QCount(q1)>QCount(q2)))
OR ((QCount(q3) > QCount(q2)) AND > (QCount(q2)>QCount(q1))) THEN
Aggiungi(q3,q4)
ELSE
Aggiungi(q1,q4)
END;
ESERCIZIO
Siano date due linee di montaggio e una serie di lavori da fare su ciascuna linea.
Ogni lavoro dura un tempo diverso. Allocare i diversi lavori sulle due linee in
maniera tale da minimizzare il tempo di lavoro complessivo.
NB I lavori vengono eseguiti con la strategia FIFO.
Es. Lista lavori e tempi di esecuzione
Risolvere il problema utilizzando
L1-> 3
due strutture a coda opportunamente
L2 -> 1
progettate.
L3 -> 2
L4 -> 6
L5 -> 2
L6 -> 2
Strategie possibili:
L7 -> 2
1- la prima metà in una coda la seconda nell’altra
L8 -> 4
2- un elemento in una coda il successivo nell’altra
3- aggiungere l’elemento nella coda al momento più corta
Le Cataste o Stack
• Uno stack è una successione lineare di elementi,
eventualmente anche vuota
• Se gli elementi che compongono uno stack sono tutti dello
stesso tipo lo stack è detto omogeneo.
• Le operazioni elementari che possono esser effettuate su di
essi sono: aggiungere un elemento, cancellare e/o estrarre
un elemento.
1
STACK
Top
Top
STACK
Le operazioni fondamentali che si fanno sugli stack sono:
riempimento e svuotamento.
Questo implica che durante lo svolgimento del programma il
numero di oggetti nello stack può cambiare.
Per descrivere uno stack è sufficiente sapere quali sono gli
oggetti (Items) nello stack e il loro numero (Top).
OPERAZIONI SUGLI STACK
In uno stack l’elemento inserito per ultimo viene estratto per primo
(LIFO - Last In First Out).
In uno stack occorrerrà solo conoscere il numero di oggetti (Top).
Aggiungere ed eliminare oggetti.
Items[ ] è un array in cui si collocano gli oggetti, Top il numero
di oggetti, l’operazione di aggiungere oggetti si chiama push e
quella di eliminare oggetti pop.
Quando Top=0 allora lo stack è vuoto.
OPERAZIONI SUGLI STACK
AGGIUNGERE
Top  Top + 1
Items[Top]  Item
ELIMINARE
Top  Top - 1
STACK
Supponiamo di voler gestire 100 caratteri con un meccanismo a
STACK
UNIT Stack;
{documentazione}
INTERFACE
{definizioni dell’ADT}
{sezione interfaccia}
CONST
MaxStack=100; massimo numero di caratteri che si possono trattare
TYPE
ItemType=char;
StackType=RECORD
Top : 0..MaxStack; numero di oggetti presenti
Items: ARRAY[1..MaxStack] OF ItemType contiene gli
oggetti 
END;
StackType
Top
Items
{
le operazioni
PROCEDURE MakeStack(VAR Stack:StackType);
{
inizializza lo stack vuoto
}
}
PROCEDURE Push(Item:ItemType; VAR Stack:StackType);
{ se lo stack non è pieno aggiungi oggetti altrimenti segnala errore }
PROCEDURE Pop(VAR Stack:StackType);
{se lo stack non è vuoto elimina il primo oggetto altrimenti segnala
errore}
FUNCTION StackTop(VAR Stack:StackType): ItemType;
{se lo stack non è vuoto la funzione assume il valore dell’oggetto al top
dello stack , in mancanza assume valore nullo chr(0)}
FUNCTION StackEmpty(VAR Stack:StackType; ):boolean;
{
vera se non ci sono oggetti nello stack }
FUNCTION StackFull(VAR Stack:StackType; ):boolean;
{
vera se lo stack è pieno }
{
fine della sezione INTERFACE
}
IMPLEMENTATION {inizio della sezione IMPLEMENTATION }
PROCEDURE MakeStack(VAR Stack:StackType);
{
inizializza lo stack vuoto
}
BEGIN
Stack.Top:=0;
END;
StackType
Top
Items
FUNCTION StackEmpty(VAR Stack:StackType; ):boolean;
{
vera se non ci sono oggetti nello stack }
BEGIN
StackEmpty:=(Stack.Top=0)
END;
FUNCTION StackFull(VAR Stack:StackType; ):boolean;
{
vera se lo stack è pieno }
BEGIN
StackFull:=(Stack.Top=MaxStack)
END;
StackType
Top
Items
FUNCTION StackTop(VAR Stack:StackType): ItemType;
{se lo stack non è vuoto la funzione assume il valore dell’oggetto al
top dello stack , in mancanza assume valore nullo chr(0)}
BEGIN
WITH Stack DO
IF Top=0 THEN
StackTop:=chr(0)
ELSE
StackTop :=Items[Top]
END;
StackType
Top
Items
PROCEDURE Push(Item:ItemType; VAR Stack:StackType);
{ se lo stack non è pieno aggiungi oggetti altrimenti segnala errore }
WITH Stack DO
IF Top<>MaxStack THEN
BEGIN
Top:=Top+1;
Items[Top]:=Item;
END
ELSE
writeln(‘Errore: lo stack è pieno’)
END;
StackType
Top
Items
PROCEDURE Pop(VAR Stack:StackType);
{se lo stack non è vuoto elimina il primo oggetto altrimenti segnala
errore}
StackType
BEGIN
Top
WITH Stack DO
IF Top<>0 THEN
Top:=Top-1
ELSE
writeln(‘Errore: lo stack è vuoto)
END;
{
Items
fine della sezione IMPLEMENTATION }
Constructor
Primitive constructor - assegna un valore ad una variabile astratta
senza fare uso di altre variabile astratte dello stesso tipo. Ha una sola
variabile di output e quelle di input servono per costruire l’output.
PROCEDURE MakeStack(VAR Stack:StackType);
{
inizializza lo stack vuoto
}
Ogni ADT richiede almeno un Primitive constructor così che il
client può assegnare un valore iniziale alla variabile astratta.
Non-primitive constructor -. Ha almeno una variabile di input e il cui
tipo è uguale a quello dell’output.
Es.
PROCEDURE Push(Item:ItemType; VAR Stack:StackType);
{ se lo stack non è pieno aggiungi oggetti altrimenti segnala errore }
SELECTOR - fornisce informazioni su una variabile di input ADT
ad un parametro di uscita. Spesso è una funzione (il parametro di uscita
in tal caso è la funzione stessa).
Primitive selector - ritorna il valore di uno dei componenti della
variabile astratta. Es.
FUNCTION StackTop(VAR Stack:StackType): ItemType;
{se lo stack non è vuoto la funzione assume il valore dell’oggetto al
top dello stack , in mancanza assume valore nullo chr(0)}
Ogni unit necessita di una Primitive selector altrimenti il client non
può mostrare i valori della variabile.
Non-primitive selector - ritorna il valore che non è relativo ad uno
dei componenti della variabile astratta ma ciò nonostante è utile al
client.
NESSUNA
(Ricorda nelle code Qcount)
PREDICATE - è una funzione booleana che ritorna informazioni
sul valore o lo stato di una variabile astratta.
FUNCTION StackEmpty(VAR Stack:StackType; ):boolean;
{
vera se non ci sono oggetti nello stack }
FUNCTION StackFull(VAR Stack:StackType; ):boolean;
{
vera se lo stack è pieno }
Alcuni commenti
Si noti che sia nella unit della QUEUE che in quella degli STACK
abbiamo adoperato una variabile ItemType per indicare il tipo di
oggetti che volevamo trattare con le nostre strutture.
Questo sistema ci permette di modificare in maniera molto semplice
le due Unit nel momento in cui volessi trattare integer invece che
stringhe o real invece che caratteri. Non è però sufficiente la
modifica del solo ItemType in alcune funzioni o procedure, ad
esempio quelle di controllo dell’errore.
ESEMPIO N.1
Assegnato un file contenente stringhe di caratteri riscrivere, rigo per
rigo, il file con i caratteri in ordine inverso.
Esempio:
Oggi è una bella giornata
che diventa
atanroig alleb anu è iggo
Soluzione
Leggere il file carattere per carattere e introdurre i singoli caratteri,
nell’ordine in cui appaiono in uno stack.
Il contenuto dello stack a partire dal Top andando verso sinistra sarà la
risposta al nostro problema.
Pseudo Codice
MakeStack(ChStack)
{inizializza uno stack vuoto}
WHILE NOT eoln DO
read(Ch)
push Ch in ChStack
readln
WHILE ChStack non è vuoto DO
mostra il valore di Ch nel Top
pop il valore di Ch dal Top dello Stack
writeln
PROGRAM InvertiRigo(input,output);
{documentazione}
USES Stack;
VAR
ChStack:StackType
Ch:char
{carattere da inserire o eliminare dallo stack}
BEGIN
MakeStack(ChStack);
WHILE NOT eoln DO
BEGIN
read(Ch);
Push(Ch,ChStack);
END;
readln;
WHILE NOT StackEmpty(ChStack) DO
BEGIN
Ch:=StackTop(ChStack);
Pop(ChStack);
write(Ch)
END;
writeln;
END.
ESEMPIO N. 2
Assegnata una espressione contenente parentesi controllare che
l’apertura e chiusura di queste sia bilanciata.
Supponiamo che le parentesi siano del tipo:
Aperta
{
[
(
Esempio
{a+[ b*c - (d-a) ]+d}
Re:=sqrt(sqr(A[3,5]+33)
Chiusa
}
]
)
Soluzione
Si legge la stringa contenente le parentesi. Quando appare una parentesi
aperta si inserisce in uno stack.
Non appena appare la prima parentesi chiusa si confronta questa con la
parentesi contenuta nel Top dello Stack. Se le parentesi sono uguali si
prosegue altrimenti si dichiara che le parentesi non sono ben bilanciate.
Pseudo Codice
MakeStack(ChStack)
Bilanciato  TRUE
FOR Posizione  1 TO lenght(Linea) DO
Ch  Linea[Posizione]
IF Ch è una parentesi aperta THEN
Push(Ch,ChStack)
ELSE IF Ch è una parentesi chiusa THEN
IF NOT Matched(StackTop(ChStack),Ch) THEN
Bilanciato  FALSE
Pop(ChStack)
Linea Bilanciata  Bilanciato AND StackEmpty(ChStack)
FUNCTION Matched(LeftCh, RightCh:char):boolean;
{ritorna vero se la parentesi aperta e
quella chiusa sono dello stesso tipo}
BEGIN
Matched:= (LeftCh=‘{‘) AND (RightCh=‘}’) OR
(LeftCh=‘[‘) AND (RightCh=‘]’) OR
(LeftCh=‘(‘) AND (RightCh=‘)’)
END;
FUNCTION LineaBilanciata (Linea:LineString):boolean;
{ritorna vero se la parentesi aperte e chiuse sono bilanciate}
VAR
Posizione:1..80;
Ch:char;
Bilanciato : boolean;
ChStack: StackType;
BEGIN
MakeStack(ChStack);
Bilanciato :=TRUE;
FOR Posizione:=1 TO lenght(Linea) DO
BEGIN
Ch:=Linea[Posizione];
IF Ch IN [‘{‘,’[‘,’(‘] THEN
Push(Ch,ChStack)
ELSE IF Ch IN [‘}’, ’], ‘,’)‘] THEN
BEGIN
IF NOT Matched(StackTop(ChStack),Ch) THEN
Bilanciato :=FALSE;
Pop(ChStack)
END;
END;
LineaBilanciata:= Bilanciato AND StackEmpty(ChStack)
END;
ESERCIZI SULLE LISTE ASTRATTE
Si hanno a disposizione le seguenti funzioni base per il dato astratto lista (di interi):
procedure cancella(var L:lista, i:integer)
precondizioni: 0<=i<=n ed L=(al,a2,. . . aj,. . . an)
postcondizioni: L=(al,a2,... ai-l,ai+l ... an)
function estrai(L:lista, i:integer): integer
precondizioni: 0<=i<=n ed L=(al,a2, . . ai,. .. an)
postcondizioni estrai = ai
function ultimo(L:lista,i:integer):boolean
precondizioni: 0<=i<=n ed L=(al,a2, . . ai,. .. an)
postcondizioni ultimo = TRUE se an è l’ultimo elemento della lista
Scrivere un algoritmo per la procedura che trasforma la lista L in una lista priva di
zeri e conta il numero di elementi cancellati.
Si hanno a disposizione le seguenti procedure per il dato astratto lista di interi:
Crealista(var L:tipolista)
(*crea una lista vuota*)
Function lung(L.tipolista):integer (*dà il numero di elementi nella lista L*)
Function seleziona(L.tipolista;i:integer):integer
(* Se L = (c1, ci-1, ci, , cn) e 0<i<=n allora seleziona = ci altrimenti
seleziona =maxint *)
Function pos(L:tipolista;m:integer):integer
(* pos = k se ck è il primo elemento di L uguale a m altrimenti pos = 0. *)
Procedure cancella(var L:tipolista;i:integer)
(* Se L=( c1,.. ci-1, ci, , cn)e 0<i<=n allora L diventa (c1, ci-1, ci+1,.., cn )
altrimenti L resta inalterata. *)
Procedure accoda(var L:tipolista;m.integer)
(* Se L =(c1,… ci, …, cn) L diventa (c1,… ci,.. , cn , m) *)
Utilizzando tali processi trasformare una lista L disordinata e contenente ripetizioni
nella lista ordinata senza ripetizioni che contiene soltanto gli elementi di L che si
ripetono esattamente k volte.
Dato il tipo astratto lista utilizzare le routine elencate per sviluppare il seguente
algoritmo:
date tre liste di interi L1, L2, L3, aggiungere in L1 solo gli elementi di L2 presenti
in L3 e non in L1, eliminando tutti gli altri.
Function Lung(L:tipolista): integer;
(*valuta la lunghezza della lista*)
Function estrai(L:tipolista, n:integer): integer;
(* fornisce il valore dell’ennesimo intero della lista, se esiste, maxint
altrimenti*)
Procedure aggiungi(L:tipolista, n:integer; k:integer): integer;
(* aggiunge nella posizione n della lista, l’elemento k*)
Procedure cancella(var L:tipolista; n: integer);
(*cancella l’ennesimo elemento della lista, se esiste*)
Es.
L1
8
4
2
5
6
L2
2
1
7
4
3
6
L3
2
5
7
1
3
Risultato
L1
1
7
3
Utilizzare le seguenti routine per il tipo astratto lista per sviluppare il seguente
algoritmo:
date tre liste L1, L2, L3, contenenti lettere dell’alfabeto, lasciare in L1 tutte le vocali
presenti in L1, L2 e L3, senza ripetizioni, ordinate in maniera crescente, in L2 tutte
le consonanti presenti in L1, L2 e L3, senza ripetizioni, ordinate in maniera
decrescente in L3, tutti caratteri, presenti in L1, L2 e L3, senza ripetizioni, ordinate
in maniera crescente.
Function Lung(L:tipolista): integer;
(*valuta la lunghezza della lista*)
Function estrai(L:tipolista, n:integer): char;
(* fornisce il valore dell’ennesimo carattere della lista, se esiste, ‘?’ altrimenti*)
Procedure cancella(var L:tipolista; n: integer);
(*cancella l’ennesimo elemento della lista, se esiste*)
Procedure aggiungi(var L:tipolista; n: integer; lettera:char);
(*aggiunge dopo l’ennesimo elemento della lista il carattere lettera*)
Es.
L1
b a z e f o  a e i o
L2
i q w e a z  z w q f b
L3
f b o a  a b e f i o q w z