TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F....

117
TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA’ M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill

Transcript of TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F....

Page 1: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

TESTI UFFICIALI

MEYERS R.A. PASCAL

Prentice Hall

FIORENTINO G., LAGANA’ M.R., ROMANI F., TURINI F.PASCAL

LABORATORIO DI PROGRAMMAZIONEMcGraw-Hill

Page 2: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

1a sess 2a sess Tot FebbPresenti scritto 37,00 55,00 92,00% su 259 14,29 21,24 35,52Superato scritto 27,00 40,00 67,00% su presenti 72,97 72,73 35,52% su 259 10,42 15,44 25,87Superato orale 20,00 33,00 53,00% su sup scritto 74,07 82,50 79,10% su 259 7,72 12,74 20,46% su presentati 92 57,61

media 27,00 24,76 25,60

ESAMI FEBBRAIO 2001 - MOD. A

Page 3: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

1. Sia dato un file di testo riguardante un insieme di soggetti di cui è fornito il cognome seguito dalla nazionalità e dalla data di nascita, giorno mese anno. Nel primo rigo sono indicati e nome e cognome dell’autore della registrazione e il numero di soggetti registrati.

Il file sarà perciò così composto: tipo dato esempio rigostringa, integer <eoln> carlo bruni^ 76 1stringa stringa^ integer integer integer <eoln> rossi italiano^22 12 1930 2stringa stringa^ integer integer integer <eoln> smith inglese^ 28 9 1990 3…………………………………………………………………………………………………………………………………………………………………………………………

.……………………………………………………………………………………………

.<eof>Leggere il file mostrando a video i nomi ordinati per nazionalità e con la data di

nascita.

ESAMI MOD. A

Page 4: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

PROGRAM Esercizio1(output,Client);CONSTLunMax=40;MassimoCli=100;TYPEStringaNome=STRING[LunMax];AnagraficaRecord=RECORD Cognome, Nome:StringaNome; END;DataRecord=RECORD Giorno, Mese, Anno:integer; END;ClienteRecord=RECORD CognCli:StringaNome; Nazione:StringaNome; Nascita:DataRecord; END;RappresentanteRecord=RECORD Anagrafe:AnagraficaRecord; NumeroCli:integer; END;IndiceTipo=0.. MassimoCli;CliArray=ARRAY[IndiceTipo] OF ClienteRecord;VAR

Clienti:CliArray;IndiceCli:IndiceTipo;ClientiFile:text;UnCliente: ClienteRecord;UnRappresentante: RappresentanteRecord; 

DataRecord

Giorno Mese Anno

AnagraficaRecord

Cognome Nome

RappresentanteRecord

Anagrafe Numero

ClienteRecord

CognCli Nazione Nascita

BEGIN

assign(ClientiFile,'C:\Modapr\test1.TXT');

reset(ClientiFile);

LeggiRappresentante(ClientiFile, IndiceCli);

readln;

OrdinaClienti(IndiceCli,Clienti, ClientiFile);

MostraRisultati(Clienti,IndiceCli);

readln

END.

Page 5: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

ApriFile

ClientiFile ClientiFile

LeggiRappresentante

IndiceCli

LeggiParola

CognomeSentinella

LeggiParola

NomeSentinella

ClientiFile ClientiFile

LeggiParola

GiornoSent

ClientiFile

LeggiParola

CognCliSent

ClientiFile

MostraRisultati

IndiceCliClienti

OrdinaClienti

IndiceCli Clienti

ClientiFile

CostruisciRecordCliente

IndiceCliClientiFile Clienti[I]

LeggiParola

Sent

ClientiFile

Nazione

LeggiParola

Sent

ClientiFile

Mese

LeggiParola

Sent

ClientiFile

Anno

BEGINassign(ClientiFile,'C:\Modapr\test1.TXT');reset(ClientiFile);LeggiRappresentante(ClientiFile, IndiceCli);readln;OrdinaClienti(IndiceCli,Clienti, ClientiFile);MostraRisultati(Clienti,IndiceCli);readlnEND.

Page 6: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

PROCEDURE LeggiParola(Sentinella:char;VAR Parola:StringaNome;VAR Clienti:text);VARCarattere:char;BEGIN

Parola:='';read(Clienti,Carattere);WHILE (Carattere<>Sentinella) DO

BEGIN Parola:=Parola+Carattere; read( Clienti,Carattere)END;

END;

Page 7: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

PROCEDURE CostruisciRecordCliente(UnCliente:ClienteRecord;VAR ClientiFile:text);BEGIN WITH UnCliente, Nascita DO BEGIN LeggiParola(' ',CognCli, ClientiFile); LeggiParola('^',Nazione, ClientiFile); read(ClientiFile,Giorno); read(ClientiFile,Mese); read(ClientiFile,Anno); readln(ClientiFile); writeln(' Cliente ',CognCli,' ',' Nazionalita'' ',Nazione); writeln(' Nato il ',Giorno,'/',Mese,'/',Anno); writeln END END;PROCEDURE LeggiRappresentante (VAR ClientiFile:text; VAR IndiceCli1:IndiceTipo);VAR

UnRappresentante: RappresentanteRecord;BEGIN WITH UnRappresentante, Anagrafe DO BEGIN LeggiParola(' ',Cognome, ClientiFile); LeggiParola('^',Nome, ClientiFile); read(ClientiFile,IndiceCli1); readln(ClientiFile); writeln('Rappresentante ',Cognome,' ',Nome,'N. Clienti',IndiceCli); ENDEND;

Page 8: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

PROCEDURE Scambia(VAR Ch1,Ch2: StringaNome);VARTemp: StringaNome;BEGINTemp:=Ch1;Ch1:=Ch2;Ch2:=TempEND;

PROCEDURE Ordina(VAR Clienti:CliArray; IndiceCli:IndiceTipo);VAROrdinato,Indice: IndiceTipo;BEGIN WITH UnCliente DO FOR Ordinato:=1 TO IndiceCli DO

FOR Indice:= IndiceCli DOWNTO Ordinato DO IF Clienti[Indice].Nazione > Clienti[Indice+1].Nazione THEN Scambia(Clienti[Indice].Nazione,Clienti[Indice+1].Nazione);

END; 

Page 9: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

PROCEDURE OrdinaClienti(VAR IndiceCli:IndiceTipo;VAR Clienti:CliArray;

VAR ClientiFile:text);

VAR

Indice:IndiceTipo;

BEGIN

FOR Indice:=1 TO IndiceCli DO

  BEGIN

CostruisciRecordCliente(Clienti[Indice],ClientiFile);

END;

Ordina(Clienti,IndiceCli)

END;

PROCEDURE MostraRisultati(VAR Clienti:CliArray;IndiceCli:IndiceTipo);

VAR I:integer;

BEGIN

WITH UnCLiente DO

FOR I:=1 TO IndiceCli DO

writeln(Clienti[I].CognCli,' ',Clienti[I].Nazione,' ',Clienti[I].Nascita.Giorno,'/', Clienti[I].Nascita.Mese,'/',Clienti[I].Nascita.Anno);

END;

Page 10: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

BEGIN

assign(ClientiFile,'C:\Modapr\test1.TXT');

reset(ClientiFile);

LeggiRappresentante(ClientiFile, UnRappresentante, IndiceCli);

readln;

OrdinaClienti(IndiceCli,Clienti, ClientiFile);

MostraRisultati(Clienti,IndiceCli);

readln

END.

TP\ESEMPI|MODA

Page 11: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

Esercizio n° 5

Scrivere un programma che, dato un file testo prova.txt estragga dal testo tutti i

caratteri di tipo numerico sostituendoli con spazi vuoti. Memorizzare il file così

corretto con il nome di prova1.txt.

Fare la somma dei numeri estratti.

Es. DATI

Ab73cqSw1yt

Ab cqSw yt

A video deve comparire

73

1

Somma = 74

Page 12: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

ApriFile(ProInput,ProOut);

CercaNumero(ProInput,ProOut,Somma);

ChiudiEStampa(ProInput,ProOut,Somma);

readln

ProOut

ApriFile

ProInput

CercaNumero

ProOutProInput Somma

ChiudiEStampa

Somma

Potenza

Pot

CostruisciNumero

PotCh Numero

Page 13: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

PROGRAM Esercizio5(output,ProInput,ProOut);VARProInput,ProOut: text;Somma:integer;FUNCTION Potenza(P:integer):integer;VARI,Pote:integer;

BEGINPote:=1;

FOR I:=1 TO P DOPote:=Pote*10;Potenza:=Pote

END;

PROCEDURE CostruisciNumero(VAR Numero,Pot:integer;Ch:char);VAR CharNum:integer;

BEGINCharNum:=ord(Ch)-ord('0');Numero:= CharNum +Numero*potenza(Pot);END;

PROCEDURE ApriFile(VAR PrIn,Prout:text);BEGIN assign(PrIn,'C:\TP\ESEMPI\TEST5.TXT'); assign(Prout,'C:\TP\ESEMPI\COPIA5.TXT'); reset(PrIn); rewrite(Prout);END;

Page 14: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

PROCEDURE CercaNumero(VAR ProInp,ProOu:text; VAR Somm:integer);VARNumero, Pot:integer; Ch: Char;BEGIN WHILE NOT eof(ProInp) DO BEGIN WHILE NOT eoln(ProInp) DO BEGIN Numero:=0; Pot:=0; read(ProInp,Ch);

IF (ord(Ch)<58) AND (ord(Ch)>47) THENBEGIN

WHILE (ord(Ch)<58) AND (ord(Ch)>47) DOBEGIN

write(ProOu,' '); CostruisciNumero(Numero,Pot,Ch);

Pot:=Pot+1; read(ProInp,Ch);

END; writeln(Numero);

Somm:=Somm+Numero; write(ProOu,Ch);

ENDELSE

write(ProOut,Ch); END; END;END;

Page 15: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

 

PROCEDURE ChiudiEStampa(VAR ProInpu,ProOu:text;Som:integer);BEGINclose(ProInpu);close(ProOu);writeln('File Duplicato -- La somma vale: ',Som);END;

{*************MAIN**************}BEGIN

ApriFile(ProInput,ProOut);CercaNumero(ProInput,ProOut,Somma);ChiudiEStampa(ProInput,ProOut,Somma);readln END.

TP\ESEMPI|MODA

Page 16: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

Esercizio 3

Sia data la successione:

an=an-3+3*an-2 -2*an-1+c

Calcolare la somma dei valori della successione per n che va da 3 a un

valore prefissato K sapendo che:

a0=-1 a1=2 a2=-5

e che c è una costante prefissata a priori.

Page 17: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

PROGRAM Esercizio3(input,output);VARC,K,I:integer;An,An1,An2,An3:real;PROCEDURE AssegnaValori(VAR C1,K1:integer); BEGIN

Write(' Dammi C ');Readln(C1);Write(' Dammi K ');Readln(K1);

END;PROCEDURE CalcolaSuccessione(an11,an22,an33:real;C1,K1:integer);VAR An:real;BEGIN writeln('Valori della successione da 1 a ',K); writeln('1 = ',an11:5:0); writeln('2 = ',an22:5:0); writeln('3 = ',an33:5:0);

FOR I:=3 TO K1 DOBEGIN

An:=an3+3*an2*an1+C1;An3:=an2;An2:=an1;An1:=an;writeln(I:1,' = ',An:5:0);

END;END;

Page 18: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

{****************** MAIN ****************}

BEGIN

An3:=-1;An2:=2;An1:=-5;AssegnaValori(C,K);CalcolaSuccessione(an1,an2,an3,C,K);writeln(' FINE COMPUTAZIONE ');readln

END.

TP\ESEMPI|MODA

Page 19: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.
Page 20: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

PROGETTO

MODULO 1 -

MODULO n -

PROGRAMMA PRINCIPALE -

Program

…………………...…..

end.

unit xxxx………………...end.

unit yyyy………………...end.

………………………………………….

uses xxxx, yyyy;

Page 21: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

DATA ABSTRACTION

Qualunque tipo di dati può essere descritto sulla base dei valoriche esso può prendere e delle operazioni che ad esso si possonoapplicare.

ESEMPIO

Tipo Valori Operazioniinteger - maxint ÷ + maxint +, -, *, DIVreal 10-38 ÷ 10+38 +, -, *, /boolean TRUE, FALSE AND, OR, NOT

Page 22: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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.

Page 23: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

ESEMPIO

NUMERI COMPLESSI

Un numero complesso in genere è scritto comea + bi

dove a e b sono dei numeri reali e i, detta parte immaginaria, ed è tale che

i2=-1

Page 24: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

Nel 1572 tale Raffaele Bombelli, colui che per primo introdusse le parentesi, propose di trattare la 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 dellanumeri “immaginari” mentre Gauss li chiamò “complessi”.Solo nel 1777 Eulero propose di sostituire con la lettera “i”.

1

1

1

Notizie sui numeri complessi si trovano in il TEOREMA DEL PAPPAGALLO di Denis Guedj, ed. Longanesi, pag.326

I numeri complessi sono usati in elettrotecnica, dinamica dei fluidi, aerodinamica etc.

Page 25: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

Rappresentazione grafica dei numeri complessi

i3

22+1i

10 r

-3 -2 -1 1 2 3-1

-2-i2 -2

-3

Page 26: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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.

Progettare una ADT per i numeri complessi significa realizzare un software che permette di definire un Type Complesso e implementi tutta una serie di operazioni tipiche dei numeri complessi. Es. addizione, sottrazione, moltiplicazione, divisione, valore assoluto, ……………………………..

Page 27: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

UNIT (pag. 906 testo)

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, ….;

Page 28: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

interfacciaContiene le dichiarazioni globali a tutta la unit e le definizioni di procedure e funzioni da esportare

implementazioneContiene 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.

UNIT

Page 29: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

NUMERI COMPLESSI

X + Yi

TYPEComplexNo=RECORD

XRe, YIm: realEND;

ComplexNo

XRe YIm

Page 30: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

UNIT ADTComplexNo;{documentazione}

INTERFACE {sezione interfaccia}{definizioni dell’ADT}

TYPEComplexNo=RECORD

XRe, YIm: realEND;{ le operazioni }PROCEDURE ……………………..FUNCTION ………………………….

IMPLEMENTATION {sezione implementazioni}PROCEDURE ……………………..FUNCTION ………………………….

Page 31: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

NUMERI COMPLESSI

a + bi

Le operazioni con i numeri complessi:

Parte Reale: aParte Immaginaria: bModulo:

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:

22 ba

idc

adbc

dc

bdac

dic

dic

dic

bia

dic

bia

2222*

Page 32: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

UNIT ADTComplexNo;{documentazione}INTERFACE {inizio della sezione INTERFACE }{ definizioni dell’ADT }

TYPEComplexNo=RECORD

Xre, Yim: realEND;

{ 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 }

Page 33: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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 }

Page 34: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

IMPLEMENTATION {inizio della sezione IMPLEMENTATION }PROCEDURE MakeComp(Xpart, Ypart:real;

VAR Cnumber: ComplexNo);{ costruisci il numero complesso }BEGINCnumber.Xre:=Xpart;Cnumber.Yim:=YpartEND;FUNCTION RealPart(Cnumber: ComplexNo):real;{ identifica la parte reale del numero complesso }BEGINRealPart:= Cnumber.XreEND;

FUNCTION ImaginaryPart(Cnumber: ComplexNo):real;{ identifica la parte immaginaria del numero complesso }BEGINImaginaryPart:= Cnumber.YimEND;

Page 35: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

FUNCTION Magnitude(Cnumber: ComplexNo):real;{ identifica il modulo del numero complesso

}BEGINMagnitude:= sqrt(sqr(Cnumber.Xre)+sqr(Cnumber.Yim))END;

22 ba

PROCEDURE AddComp(Term1, Term2:ComplexNo; VAR Sum: ComplexNo);

{ addiziona i numeri complessi Term1 e Term2 (a + bi) + (c + di) = (a + c) + (b + d) i }

BEGINWITH Sum DOBEGIN

Xre:=Term1.Xre+Term2.Xre;Yim:=Term1.Yim+Term2.Yim

ENDEND;

Page 36: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

PROCEDURE SubtrComp(Term1, Term2:ComplexNo; VAR Difference: ComplexNo);

{ addiziona i numeri complessi Term1 e Term2 (a + bi) - (c + di) = (a - c) + (b - d) i }

BEGINWITH Difference DO

BEGINXre:=Term1.Xre - Term2.Xre;Yim:=Term1.Yim - Term2.Yim

END;END;

Page 37: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

PROCEDURE MultComp(Factor1, Factor2:ComplexNo; VAR Product: ComplexNo);

{ addiziona i numeri complessi Term1 e Term2 (a + bi) * (c + di) = (ac - bd) -(ad + bc) i }

BEGINWITH Product DO

BEGINXre:=Factor1.Xre * Factor2.Xre - Factor1.Yim * Factor2.Yim;Yim:=Factor1.Xre * Factor2.Yim + Factor2.Xre * Factor1.Yim

END

END;

Page 38: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

PROCEDURE DivComp(Factor1, Factor2:ComplexNo; VAR Quotient: ComplexNo);

{ addiziona i numeri complessi Term1 e Term2

}

VARDivisor: real; {divisore del quoziente}

BEGINDivisor:=sqr(Factor2.Xre) + sqr(Factor2.Yim);

WITH Quotient DOBEGIN

Xre:=(Factor1.Xre * Factor2.Xre + Factor1.Yim * Factor2.Yim)/Divisor;

Yim:= (Factor1.Yim *Factor2.Xre - Factor1.Xre * Factor2.Yim)/Divisor

ENDEND;

idc

adbc

dc

bdac

dic

bia

2222

Page 39: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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, CPer ogni coefficiente introdurre prima la parte reale e poi la parte immaginaria.

Ouput: Mostrare la soluzione X sotto forma di numero complesso

Page 40: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

Pseudo codiceRichiama la unit per i numeri complessi;Mostra le istruzioni per l’introduzione dei dati;Leggi i coefficienti;Calcola la soluzione;Mostra la soluzione.

ABC

X

Mostra Istr. Leggi Calcola Mostra Ris.

ADTComplexNo ADTComplexNoADTComplexNo

ABC

X

Equazione

Page 41: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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;

Page 42: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

PROCEDURE MC(Z:ComplexNo);{mostra il numero complesso Z}VARSegno:STRING[3];BEGIN

Segno:=' ';IF ImaginaryPart(Z)>=0 THEN Segno:=' + ';writeln(RealPart(Z):3:1,Segno,ImaginaryPart(Z):3:1,'i');writeln

END;

Page 43: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

PROCEDURE LeggiCoefficienti(VAR A,B,C:ComplexNo);VARARe,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;

Page 44: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

PROCEDURE Soluzione(A,B,C:ComplexNo; VAR X:ComplexNo);{documentazione}VARCmenoB:ComplexNo;BEGIN SubtrComp(C,B,CmenoB);

DivComp(CmenoB,A,X)END;

PROCEDURE MostraRisultato(X:ComplexNo);

BEGINwriteln('La radice dell''equazione assegnata e'': ');MC(X)

END;

Page 45: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

{ BODY }BEGIN

MostraIstruzioni;LeggiCoefficienti(A,B,C);Soluzione(A,B,C,X);MostraRisultato(X)

END.

Page 46: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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 66Coefficiente B= 77 55Coefficiente C= 4 2

La radice dell'equazione assegnata e':-0.9 + 1.0i

OUTPUT

Page 47: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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’altezzaRettangolo – assegnata la base e l’altezza

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.

ea

b

c

d

f

Page 48: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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 il client può assegnare un valore iniziale alla variabile astratta.

Page 49: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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 }

Page 50: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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 }

Page 51: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

PREDICATE - è una funzione booleana che ritorna informazioni sul valore o lo stato di una variabile astratta.

Page 52: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

Un ADT è completa se il client :• fa riferimento solo al type dell’ADT (es. ComplexNo)• non deve mai cambiare la logica delle operazioni dell’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

Page 53: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

1

Le Code• Una coda è una successione lineare di elementi,

eventualmente anche vuota

• Se gli elementi che compongono una coda sono tutti dellostesso tipo la coda è detta omogenea.

• Le operazioni elementari che possono esser effettuate su diesse sono: aggiungere un elemento, cancellare e/o estrarreun elemento.

Page 54: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

Head

LE CODE (QUEUE)

Tail

Head

Page 55: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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.

Page 56: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

OPERAZIONI SULLE CODE

In una coda l’elemento inserito per primo viene anche estratto per primo (FIFO).

In una coda occorerrà 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:

Page 57: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

OPERAZIONI SULLE CODE

AGGIUNGERE

Tail Tail+1Items[Tail] ItemInUse InUse + 1

ELIMINARE

Head Head+1InUse 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.

Page 58: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

Escono due oggetti e ne entrano tre

Escono due oggetti e ne entrano due

Testa Coda

1 2 3 4 5 6 7 8 9

N°=6

Testa Coda

1 2 3 4 5 6 7 8 9

N°=6

TestaCoda

1 2 3 4 5 6 7 8 9

N°=7

Page 59: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

Gli indici che caratterizzano Head e Tail devono variare tra 1 e 9. Se si supera 9 e nelle posizioni da 1 a indice di Head c’è ancora posto allora gli indici di Head e Tail devono adeguatamente modificarsi per sfruttare sempre tutti gli spazi disponibili.

entra esce head tail in use

0 0 1 6 60 1 2 6 50 1 3 6 41 0 3 7 51 0 3 8 60 1 4 8 50 1 5 8 41 0 5 9 51 0 5 1 61 0 5 2 7

Page 60: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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.

Page 61: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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.

Page 62: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

UNIT Code;{documentazione}

INTERFACE {sezione interfaccia}{definizioni dell’ADT}

CONSTMaxQueue=100;NullItem=‘’;TYPEItemType=STRING[20] massima lunghezza delle stringheQueueType=RECORD

Head, primo oggetto nella codaTail : 1..MaxQueue; ultimo oggetto nella codaInUse :0..MaxQueue; numero di oggetti in codaItems: ARRAY[1..MaxQueue] OF ItemType contiene gli

oggetti in codaEND;

Tail InUse Items

QueueType

Head

Page 63: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

{ 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}

Page 64: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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 }

Page 65: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

IMPLEMENTATION {inizio della sezione IMPLEMENTATION }

PROCEDURE MakeQueue(VAR Queue:QueueType);{ inizializza la coda vuota }BEGIN

WITH Queue DO BEGIN

Head:=1; Tail:=MaxQueue; InUse:=0END

END;

Tail InUse Items

QueueType

Head

Page 66: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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+1END

ELSE writeln(‘Errore: la coda è piena’)

END;

Tail InUse Items

QueueType

Head

Page 67: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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-1END

ELSE writeln(‘Errore: la coda è vuota)

END;

Tail InUse Items

QueueType

Head

Page 68: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

PROCEDURE FirstOnQueue(VAR Queue:QueueType; VAR Item:ItemType);

{assegna a Item il valore del primo oggetto in coda, in mancanza assegna valore nullo}

BEGINWITH Queue DO IF InUse<>0 THEN

Item:=Items[Head] ELSE Item:=NullItem

END;

Tail InUse Items

QueueType

Head

Page 69: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

FUNCTION QCount(VAR Queue:QueueType; ):integer;{ identifica quanti oggetti sono in coda }BEGIN

QCount:=Queue.InUseEND;

FUNCTION QEmpty(VAR Queue:QueueType; ):boolean;{ vera se non ci sono oggetti in coda }BEGIN

QEmpty:=(Queue.InUse=0)END;

Tail InUse Items

QueueType

Head

Page 70: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

FUNCTION QFull(VAR Queue:QueueType; ):boolean;{ vera se la coda è piena }BEGIN

QFull:=(Queue.InUse=MaxQueue)END;

{ fine della sezione IMPLEMENTATION }

Tail InUse Items

QueueType

Head

Page 71: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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.

Page 72: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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 }

Page 73: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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.

Page 74: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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 }

Page 75: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

FUNCTION QEmpty(VAR Queue:QueueType; ):boolean;{ vera se non ci sono oggetti in coda }BEGIN

QEmpty:=(Queue.InUse=0)END;

PREDICATE - è una funzione booleana che ritorna informazioni sul valore o lo stato di una variabile astratta.

Page 76: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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-1END

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

ELSEwriteln(‘Errore: la coda è vuota)END;

Questo parametro è inutile e fuorviante

CONSIGLI PER UNA CORRETTA PROGRAMMAZIONE

Page 77: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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.

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.

Page 78: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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-1END

ELSE writeln(‘Errore: la coda è vuota’)

END;

Page 79: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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.

Page 80: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

NORME PER FARE GLI ESERCIZI

Nome file: cognome+iniziale nome

In testa ad ogni programma devono essere scritti i dati dellostudente.

Es.nome file -> BianchiG

{programma sviluppato da Bianchi Giulio mat. 050/888}PROGRAM …….

Page 81: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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.

Page 82: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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è.

Page 83: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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;

CONSTMaxSize=3; {dimensione massima della coda}Urlo=’xxxxxxxxxxxxxx’;Urlo2=’ssssssssssssss';

VARQueue:QueueType;TotaleVenduto, {totale caffè venduti }TotaleDaVendere: integer;{caffè da vendere }Azione: char; {lettera del menu per fare le scelte }

Page 84: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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-1END;

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)

ENDELSE

writeln('Mi dispiace i tavoli sono tutti occupati. ‘); writeln;END;

Page 85: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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)

ENDELSE writeln(Urlo2)

END;

Page 86: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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)

ENDEND;

Page 87: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

{ BODY }BEGIN

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); readlnEND.

Page 88: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

1

Le Cataste o Stack• Uno stack è una successione lineare di elementi,

eventualmente anche vuota

• Se gli elementi che compongono uno stack sono tutti dellostesso tipo lo stack è detto omogeneo.

• Le operazioni elementari che possono esser effettuate su diessi sono: aggiungere un elemento, cancellare e/o estrarreun elemento.

Page 89: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

Top

Top

STACK

Page 90: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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.

Anche lo stack come la queue è un Dynamic data type (il numero di componenti nel Data Type cambia nel corso del programma).

Per descrivere uno stack è sufficiente sapere quali sono gli oggetti (Items) nello stack e il loro numero (Top).

STACK

Page 91: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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.

Page 92: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

OPERAZIONI SUGLI STACK

AGGIUNGERE

Top Top + 1Items[Top] Item

ELIMINARE

Top Top - 1

Page 93: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

STACK

Supponiamo di voler gestire con un meccanismo a STACK 100 caratteri.

Page 94: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

UNIT Stack;{documentazione}

INTERFACE {sezione interfaccia}{definizioni dell’ADT}

CONSTMaxStack=100; massimo numero di caratteri che si possono trattareTYPEItemType=char; StackType=RECORD

Top : 0..MaxStack; numero di oggetti presentiItems: ARRAY[1..MaxStack] OF ItemType contiene gli

oggetti END;

Items

StackType

Top

Page 95: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

{ 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)}

Page 96: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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 }

Page 97: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

IMPLEMENTATION {inizio della sezione IMPLEMENTATION }

PROCEDURE MakeStack(VAR Stack:StackType);{ inizializza lo stack vuoto }BEGIN

Stack.Top:=0;END;

Items

StackType

Top

Page 98: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

FUNCTION StackEmpty(VAR Stack:StackType; ):boolean;{ vera se non ci sono oggetti nello stack }BEGIN

StackEmpty:=(Stack.Top=0)END;

Items

StackType

Top

FUNCTION StackFull(VAR Stack:StackType; ):boolean;{ vera se lo stack è pieno }BEGIN

StackFull:=(Stack.Top=MaxStack)END;

Page 99: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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)}

BEGINWITH Stack DO IF Top=0 THEN

StackTop:=chr(0) ELSE StackTop :=Items[Top]

END;

Items

StackType

Top

Page 100: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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;

Items

StackType

Top

Page 101: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

PROCEDURE Pop(VAR Stack:StackType);{se lo stack non è vuoto elimina il primo oggetto altrimenti segnala

errore}

BEGINWITH Stack DO IF Top<>0 THEN

Top:=Top-1 ELSE writeln(‘Errore: lo stack è vuoto)

END;

{ fine della sezione IMPLEMENTATION }

Items

StackType

Top

Page 102: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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 }

Page 103: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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.

Page 104: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

Non-primitive selector - ritorna il valore che non è relativo ad uno dei componenti della variabile astratta ma ciò nonostante è utile al client. NESSUNA

Page 105: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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 }

Page 106: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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.

La scelta di usare nelle FUNCTION la call per VAR invece che per valore pur se questa scelta impegna più memoria però in compenso la chiamata avviene in un tempo di complessità pari a O(1) invece che O(N).

Page 107: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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

SoluzioneLeggere 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.

Page 108: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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

Page 109: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

PROGRAM InvertiRigo(input,output);{documentazione}USES Stack;VARChStack:StackTypeCh: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.

Page 110: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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 Chiusa{ }[ ]( )

Esempio

{a+[ b*c - (d-a) ]+d}Re:=sqrt(sqr(A[3,5]+33)

Page 111: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

SoluzioneSi 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 CodiceMakeStack(ChStack)Bilanciato TRUEFOR 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 FALSEPop(ChStack)

Linea Bilanciata Bilanciato AND StackEmpty(ChStack)

Page 112: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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;

Page 113: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

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 [‘}’, ’], ‘,’)‘] THENBEGIN

IF NOT Matched(StackTop(ChStack),Ch) THEN Bilanciato :=FALSE;Pop(ChStack)

END;END;

BalancedLine:= Bilanciato AND StackEmpty(ChStack)END;

Page 114: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

ESEMPIO PROCEDURE ANNIDATE

Proc AProc B

Proc C

…………….Proc B

Proc A

Page 115: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

EsercizioDato un numero verificare se esso è palindromo.

Si definisce palindromo un numero (o stringa) che può essere letto indifferentemente da sinistra verso destra e da destra verso sinistra. Es. 1232442321 7659567Un numero (o stringa) palindromo si dice pari se il numero delle cifre (caratteri) che lo compongono è pari, dispari altrimenti.

EsercizioAddizionare due numeri interi di grandezza superiore a 215 .

Page 116: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

Un suggerimento

Quando si scrivono delle ADT invece di inserire scritte che ne controllino la correttezza di funzionamento è opportuno inserire in esse funzioni o procedure aventi lo stesso scopo così da poterle utilizzare anche dopo che la Unit è stata compilata per ulteriori controlli.

Page 117: TESTI UFFICIALI MEYERS R.A. PASCAL Prentice Hall FIORENTINO G., LAGANA M.R., ROMANI F., TURINI F. PASCAL LABORATORIO DI PROGRAMMAZIONE McGraw-Hill.

Primo progetto intercorso

Simulare l’attività di un distributore automatico di generi alimentari in cui sono in vendita prodotti con data di scadenza. Siano tre le linee di prodotti: A, B, C.I prodotti A possono rimanere nel distributore 3 giorniI prodotti B possono rimanere nel distributore 5 giorni I prodotti C possono rimanere nel distributore 4 giorniI prodotti vengono dati al pubblico in funzione della data di scadenza, prima quelli più antichi.Simulare il caricamento di ogni prodotto con un massimo numero di pezzi (maxA, maxB, maxC).Simulare la vendita dei tre prodotti con segnalazione di fine prodotto.Simulare la raccolta a fine settimana dei prodotti scaduti tenendo presente che essi vanno riconsegnati a diversi distributori. Poiché i distributori sono in luoghi diversi verranno caricati sui camion prima i prodotti di tipo B, poi quelli C e infine quelli A.Simulare infine la consegna dei prodotti ai distributori.