Maurizio Lenzerini Paolo Atzeni
PROGETTO
DI PROGRAMMI IN PASCAL NUOVA EDIZIONE
La cultura è un bene dell'umanità (
[email protected])
Serie Linguaggi e strumenti di programmazione
IN VEt-!OIT1' f'T"'=~SO li
ARTOl
:!::.~::;-::,.::.
r ~· u .-=:C:i llf''A
O 184 - RCh.».. ·. - '-'i La cultura è un bene dell'umanità (
[email protected])
1
C;:;v-::iur,
239
di ro la IG 1c:Gli :ila cii S. Pietro In 'll11c:oh
La cultura è un bene dell'umanità (
[email protected])
Maurizio Lenzerini Dipartimento di Informatica e Sistemistica Università degli Studi di Roma "La Sapienza"
Paolo Atzeni Istituto di Analisi dei Sistemi e Informatica Consiglio Nazionale delle Ricerche, Roma
l'PleGETT• IN l'ASCAL
clup - milano
La cultura è un bene dell'umanità (
[email protected])
•1 l'PleGPIAMMI
copyright © 1985 clup cooperativa libraria universitaria del politecnico, milano ISBN 88-7005-656-2 seconda edizione: novembre 1985 ristampa IV lii Il I 1986 1987 1988 1989 è vietata la riproduzione, anche parziale, con qualsiasi mezzo effettuata, compresa la fotocopia, anche ad uso didattico, se non autorizzata stampato presso il centro stampa rozzano, via milano 99, rozzano (mi) per conto della clup, piazza leonardo da vinci 32, milano
La cultura è un bene dell'umanità (
[email protected])
ai nostri Genitori Lio e Maria Livio e Rina
La cultura è un bene dell'umanità (
[email protected])
La cultura è un bene dell'umanità (
[email protected])
INDICE
Prefazione
9
Parte prima ELEMENTI FONDAMENTALI 1.
Calcolo della somma di 100 numeri
15
2.
Calcolo del massimo tra 10 numeri
20
3.
Analisi di una sequenza di zeri e uno
26
4.
Divisione con il metodo delle sottrazioni successive
35
5.
Trasformazione di una sequenza di caratteri
42
6.
Conversione in decimale di un numero in base qualunque
53
7.
Calcolo dell'orario di apertura di un ufficio
66
8.
Somma di due vettori
74
9.
Calcolo del valore e della posizione del massimo in una matrice
81
10. Calcolo del punto di sella di una matrice
89
11. Frequenza di caratteri
95
12. Prodotto di matrici
100
13. Elevamento a potenza di interi
108
14. Gestione informazioni voli
118
15. Creazione di una lista
130
16. Trasferimento di dati tra liste
141
17. Inserzione ed eliminazione di elementi da una lista
150
La cultura è un bene dell'umanità (
[email protected])
Parte seconda STRUTTURE DI DATI 18. Garbage collection
159
19. Fusione di liste semplici
163
20. Realizzazione e gestione di pile e code
16 8
21. Visita di una lista doppia
180
22. Visita di un albero binario
186
23. Visita di un albero in preordine
196
24. Eliminazione di un sottoalbero da un albero
208
25. Costruzione di un albero
220
26. Calcolo del numero di sottoalberi di un albero
232
27. Costruzione di un grafo
241
28. Analisi di un grafo
246
29. Gestione di una tavola
259
Parte terza PROGETTI 30. Elaborazione di testi
273
31. Gestione di programmi
282
32. Valutazione di una espressione aritmetica
293
33. Scomposizione in addendi di un numero intero
304
34. Analisi di una linea spezzata
313
35. Controllo di un percorso cittadino
325
36. Un analizzatore di espressioni aritmetiche
339
37. Ricerca di un elemento in un insieme
355
38. Ordinamento di un insieme
364
Appendice PROBLEMI PROPOSTI
383
La cultura è un bene dell'umanità (
[email protected])
PREFAZIONE
Il linguaggio di programmazione Pascal si e' notevolmente mato
negli
esso
e'
ultimi anni,
soprattutto come strumento
didattico:
largamente adottato sia in ambiente accademico
ambiente
industriale nei corsi introduttivi
di
affer-
che
in
programmazione,
proprio come linguaggio attraverso il quale introdurre lo studente ai concetti fondamentali della programmazione. Lo
scopo di questo libro e' quello di guidare lo studente
approfondimento traverso
dei concetti basilari della programmazione,
lo svolgimento di esercizi di
crescente
nell' at-
complessita•.
L'obiettivo principale non e' quello di fornire esempi di utilizzazione di
del calcolatore nella s;_Qluz:i,_9p._!?__ gi problemi pratici, ma -- - --------------------introdurre gradualmente il lettore all'utilizzo di tecniche
sistematiche
per lo sviluppo dei programmi.
Ìdata enfas j allo svolgimento di
A tale scopo
problemi tipici di
si e'
informatica,
1
rivolgendo stesura
l'attenzione non solo al progetto di algoritmi e alla
concreta
strutture di dati,
dei
programmi,
ma anche
allo
studio
alle loro proprieta' e alle diverse
àslle
tecniche
per la loro rappresentazione ed il loro uso. Il
libro
e' costituito da un insieme di esercizi di
zione in Pascal,
programma-
originariamente preparati nell'ambito del corso
La cultura è un bene dell'umanità (
[email protected])
IO
di
Programmazione dei Calcolatori Elettronici della Facolta'
di
Ingegneria dell'Universita' di Roma "La Sapienza". Per ogni problema presentato, la soluzione viene sviluppata passo passo,
motivando
le
varie scelte e confrontando
le
possibili
alternative, proponendo poi problemi di comparabile complessita', che permettano al lettore di esercitarsi essendo
tutti
enfatizzare che
sono
indipendentemente.
i programmi scritti in Pascal,
gli aspetti generali delle spesso
Pur
si e' tentato
problematiche
relativamente indipendenti dal
di
trattate,
linguaggio
di
programmazione utilizzato. Si
vuole sottolineare che il presente testo e'
come
strumento
introducano
didattico
stato
concepito
che affianchi altri testi in
formalmente il linguaggio Pascal,
le
cui
si
strutture
di
dati e le problematiche relative alla correttezza e all'efficienza
dei
programmi.
Per questa ragione le nozioni relative
sintassi e alla semantica delle istruzioni del definizioni
delle
complessita'
dei
programmazione,
diverse
strutture di dati,
programmi e ad altri concetti
alla
linguaggio, alle di
pur essendo discusse ed utilizzate,
alle
misure base
di
della
non vengono
presentate in modo formale ed esauriente. Il libro e' suddiviso in tre parti: - gli
esercizi della prima parte hanno lo scopo
l'utilizzazione
di
mostrare
degli elementi fondamentali del linguaggio,
come le strutture di controllo, i tipi di dati primitivi, le operazioni di ingresso e uscita, le procedure e le funzioni; in particolare,
si riprendono i concetti piu' importanti
si approfondiscono le problematiche connesse al loro uso;
La cultura è un bene dell'umanità (
[email protected])
e
11
- la
seconda parte e' dedicata alla realizzazione
delle
piu'
esercizi
importanti strutture di
su liste semplici,
liste
dati:
in
Pascal
vengono
svolti
multiple,
pile,
code,
alberi, grafi e tavole, presentandone le possibili realizzazioni
in Pascal,
con i relativi algoritmi fondamentali
di
gestione; - nella
terza
parte si affrontano problemi
piu'
complessi,
caratterizzati, in generale, dalla necessita' di organizzare un
vero e proprio progetto che coinvolge la scelta dell'al-
goritmo e delle strutture di dati piu' adatti al problema. Infine,
il
ulteriori
libro comprende un'appendice in cui vengono proposti esercizi,
ancora
una volta per
fornire
al
lettore
spunti per la applicazione dei concetti presentati e possibilita' di verifica della relativa assimilazione. La versione del linguaggio Pascal adottata e' quella presentata Report",
da
K. Jensen e N. Wirth
Springer-Verlag,
con tutte quelle esistenti.
1975,
in
originaria,
"Pascal User Manual and
che e' normalmente compatibile
Si invitano i lettori che utilizzano
particolari versioni del Pascal ad individuare in modo preciso le eventuali
differenze
rispetto
alla
definizione
del
Pascal
presentata nel testo suddetto. Nella
stesura
sottolineare
dei
programmi si e' adottata la
convenzione
le parole chiave del linguaggio e di distinguere
di i
commenti in tre tipi: - commenti
relativi
alla dichiarazione di dati
dal simbolo "CD") ;
La cultura è un bene dell'umanità (
[email protected])
(contrassegnati
12
commenti
che . motivano
parti
di
programmi
o
sequenze
di
istruzioni (contrassegnati dal simbolo "CM"); - commenti
che
specificano una certa condizione
sia sempre vera quando,
che
s'intende
durante l'esecuzione del programma, si
e' eseguita l'istruzione che precede immediatamente il commento stesso (contrassegnati dal simbolo "CA"). Gli
autori
Prof.
ringraziano la Prof.ssa Luigia Carlucci Aiello e
il
Carlo Batini, docenti dell'Universita' di Roma "La Sapien-
za", per la loro completa disponibilita' a consigli e discussioni e il loro costante incoraggiamento. Inoltre, Massimo
Maurizio Lenzerini desidera ringraziare Franco, Fulvio, e
Mike,
indimenticabili
programmazione.
La cultura è un bene dell'umanità (
[email protected])
compagni
di
lunghe
ore
di
Parte prima Elementi fondamentali
La cultura è un bene dell'umanità (
[email protected])
La cultura è un bene dell'umanità (
[email protected])
1 Calcolo della somma di 100 numeri
TESTO Scrivere
un programma che calcoli la somma di 100 numeri
interi
letti da ingresso.
SOLUZIONE La soluzione consiste nel leggere da ingresso uno per uno i cento interi viene
da sommare;
ogni volta che viene letto un
intero,
esso
sommato a una variabile (la chiameremo "somma") che,
ini-
zialmente posta al valore zero,
conterra',
alla fine,
la somma
totale. La sezione istruzioni del programma sara' percio' composta da una prima parte di inizializzazione della variabile "somma", seconda eseguire
parte 100
consistente
in un ciclo con lo
scopo
di
una
di
volte le istruzioni di lettura di un intero
fare e
di
addizione del suo valore alla somma parziale e di una terza parte per la stampa del risultato. Il corrispondente programma e' il seguente:
La cultura è un bene dell'umanità (
[email protected])
16
program somma(input,output); (* CM: calcola la somma di 100 numeri interi letti da ingresso *) var numero: integer; (* CD: variabile in cui si memorizza l'intero di volta in volta letto *) somma: ìnteger; (* CD: variabile che conterra', di volta in volta, la somma parziale degli interi letti e, alla fine, la somma totale *) i: integer; (* CD: variabile contatore: contiene, di volta in volta, il numero di volte che sono state eseguite le istruzioni del ciclo *) begìn (* CM: ìnìzìalìzzazìonì *) somma := O; ì := l; (* CM: ciclo dì calcolo della somma *) whìle ì 1.1 fi\
>:: 'T >I
Iv 2-;{
Dù Q,
810 G, ,.( )'., '-1--J) (K 1
r- -z1J\i'CD0 > ?\= b then repeat r := r - b; until r < b;
q := q + 1
L ' istruzione ife' stata inserita allo scopo di evitare la
La cultura è un bene dell'umanità (
[email protected])
prima
40
esecuzione
delle
istruzioni
del ciclo qualora
dividendo fosse minore del valore del divisore .
il
valore
del
Si noti che cio'
e' invece assicurato dall'uso della istruzione while . Infine,
l'ultima
istruzione del programma
11
div i sionel 11 e'
l'i-
struzione di stampa dei risultati. I valori delle v ariabili "q" e "r"
verranno stampati sulla stessa linea
rispettivamente
dalle
di
stampa ,
preceduti
scritte "quoziente:" e " rest o:",
per
la
maggiore comprensione di chi analizza i risultati dell ' esecuzione del programma. Come
osservazione
richiedeva
notiamo che il
testo
che i due dati di ingresso fossero
condizione, sionel".
finale,
tuttavia,
non
del
problema
positivi.
Questa
e' controllata dal programma
"divi-
Analizziamone, allora, il comportamento nel caso in cu i
i valori forniti in ingresso non siano entrambi positivi. Supponiamo,
in particolare,
che al dividendo (la variabile "a")
sia assegnato un valore positivo e ai divisore (la variabile "b") un
valore
negativo:
in
queste condizioni il
predicato
della
istruzione while, ossia r >= b
non potra' mai assumere il valore
false.
Infatti,
inizialmente
"r" e' maggiore di "b" e successivamente il suo valore non potra' che
aumentare.
La
conseguenza di cio' e' che l'esecuzione
del
programma entra in un ciclo infinito. Analizzando gli altri casi,
e' facile verificare che nel caso in
cui "a" sia negativo e "b" positivo il programma, pur terminando, non fornisce risultati corretti; viceversa, il quoziente e il resto sono calcolati correttamente per valori di "a" e "b" entrambi
La cultura è un bene dell'umanità (
[email protected])
41
negativi. Nel seguente programma "divisione2 11 sono state inserite le istruzioni
adatte
per
controllare
che i
dati
di
ingresso
siano
positivi.
program divisione2(input,output); (* CM: calcola quoziente e resto della divisione tra due interi positivi con il metodo delle sottrazioni successive *) var a,b,q,r : integer; begin read (a,b); if (a
while r >""' b do begin r := r - b; q := q + 1 end; writeln ('quoziente: 1 ,q, 1 resto ',r)
V
/
C>
~
0
end end.
ESERCIZI PROPOSTI
1.
Scrivere
un
programma
che legga da
ingresso
due
interi
qualunque (positivi, nulli o negativi) e calcoli il quoziente e il resto della divisione del primo per il secondo, utilizzando il metodo delle sottrazioni successive. 2.
Scrivere qualunque
un
programma
(positivi,
che legga da
ingresso
due
nulli o negativi) e calcoli
interi il
loro
prodotto, con il vincolo di non utilizzare l'operatore '*'·
La cultura è un bene dell'umanità (
[email protected])
5 Trasformazione di una sequenza di caratteri
TESTO scrivere
un
alfabetici
programma
che legga una sequenza di
maiuscoli o blank
15
e stampi la sequenza
caratteri
ottenuta
essa eliminando i blanks e sostituendo a ogni lettera quella la
segue
nell'ordinamento alfabetico,
considerando
da che
l'alfabeto
come circolare, e quindi il carattere 'A' come successore di 'Z'. Un esempio di dati di ingresso e relativi dati di uscita corretti e' il seguente (il simbolo"/" indica blank): INPUT:
CODICE/SEGRETO///
OUTPUT:
DPEJDFTFHSFUP
SOLUZIONE Una possibile soluzione e' rappresentata dalla seguente struttura di programma: program soluzionel(input,output); begin /1/ lettura della sequenza; /2/ produzione della nuova sequenza; /3/ stampa della sequenza prodotta end.
La cultura è un bene dell'umanità (
[email protected])
43 Il tre
programma "soluzionel", fasi diverse la lettura,
stampa,
ha
pur avendo il pregio di separare
in
le operazioni vere e proprie e
la
pero' lo svantaggio di richiedere la di tutti i caratteri,
contemporanea
il che non e'
necessario.
E'
trattamento
di un carattere alla volta,
memorizzazione strettamente
quindi preferibile una soluzione che preveda con lettura,
il
eventuale
trasformazione ed eventuale stampa. Poiche' il numero di caratte-
ri che formano la sequenza di ingresso e' noto a priori, l'iterazione del trattamento di un carattere va effettuata per un ro di volte prefissato
e quindi puo' essere realizzata
nume-
mediante
l'istruzione far, secondo il seguente schema:
program trasforma(input,output); (* CM: legge una sequenza di 15 caratteri alfabetici o blanks e la trasforma eliminando i blanks e sostituendo ad ogni lettera quella che la segue nell'ordine alfabetico, considerando l'alfabeto come circolare *) var
i integer; eh: char;
(* CD: contatore *) (* CD: carattere da analizzare *)
begin far i := 1 to 15 do begin /1/ lettura dell'i-esimo carattere eh; /2/ esame del carattere eh ed eventuale stampa end end.
La frase /1/ si traduce semplicemente nell'istruzione: read(ch) mentre, per la frase /2/, occorre considerare che il calcolo e la stampa
del successore del carattere letto deve essere effettuata
solo se esso non e' blank.
Se non lo e', la trasformazione viene
La cultura è un bene dell'umanità (
[email protected])
44
fatta
considerando
l'ordinamento riguarda
che
il tipo "char" e• un
tipo
ordinale
definito sui relativi valori coincide,
i caratteri alfabetici,
con l'ordine
e
per quanto
alfabetico;
e•
quindi possibile utilizzare, per il calcolo del carattere richiesto, la funzione predefinita
11
succ 11 , con l'avvertenza di trattare
in modo opportuno il carattere 'Z'.
La frase /2/ puo•,
percio',
essere tradotta nella seguente istruzione:
if Ch I then if eh 'Z' then write( succ(ch) else write( 'A')
La codifica completa del programma e•:
program trasforma(input,output); legge una sequenza di 15 caratteri alfabetici o blanks (* CM: e la trasforma eliminando i blanks e sostituendo ad ogni lettera quella che la segue nell'ordine alfabetico, considerando l'alfabeto come circolare *) var
i integer; (* CD: contatore *) eh: char; (* CD: carattere da analizzare *)
begin for i := l to 15 do begin (* CM: lettura dell'i-esimo carattere *) read(ch); (* CM: esame del carattere ed eventuale stampa *) if Ch I I then if eh •z• then write( succ(ch) ) else (* CM: si considera l'alfabeto circolare *) write( 'A') end end. Nel caso in cui si utilizzi una implementazione
La cultura è un bene dell'umanità (
[email protected])
del Pascal che
45
preveda
il
valore
"eoln(input)",
iniziale "true"
per
la
funzione
standard
c'e' il problema che la prima esecuzione
dell'i-
struzione read(ch) ha
l'effetto
"eh", tra
di assegnare il valore
1
(blank) alla
variabile
anche se tale valore non e' stato effettivamente i
dati di ingresso.
inserito
Per risolvere questo problema si
puo'
aggiungere, come prima istruzione, l'istruzione: read(ch) ignorando cosi' il valore blank suddetto, oppure l'istruzione: readln che
ha
l'effetto di posizionare l'organo di
lettura
al
primo
carattere effettivamente inserito come dato di ingresso, ignorando,
cosi',
rende true
Inoltre,
il
carattere che segnala la fine della linea (e che
"eoln(input)").
qualora
il compilatore utilizzato gestisca i
dati
di
ingresso in modo tale da inserire il carattere di fine linea dopo l'ultimo carattere non blank della linea stessa, si deve trattare con particolare attenzione il caso in cui la sequenza di ingresso termini con uno o piu' blanks: se cosi' e', infatti, si deve fare in
modo che tali blanks non siano ignorati a causa del fatto che
la linea di ingresso e' considerata conclusa dopo l'ultimo carattere non blank. di
inserire
Un modo per risolvere questo problema e'
comunque,
dopo il quindicesimo e ultimo
quello
carattere
della sequenza, un qualunque altro carattere diverso da blank (ad esempio il punto),
che,
pur non venendo mai analizzato,
La cultura è un bene dell'umanità (
[email protected])
fa
in
46
modo che tutti i caratteri significativi della sequenza d'ingresso siano correttamente letti. Si
vuole ora generalizzare il programma in modo che la
d'ingresso
sia trasformata con la regola che ogni
sequenza
lettera
deve
essere sostituita con quella che la segue a distanza d nell'ardine alfabetico.
Il valore di d viene letto da ingresso come primo
dato ed e' compreso tra O e 26.
Ad esempio,
con d pari a
s,
la
sequenza: CODICE/SEGRETO deve essere trasformata in: HTINHJXJLWJYT Un
primo modo per modificare il programma e' quello di iterare d
volte il calcolo del successore, mediante la seguente istruzione:
for j := 1 to d do if eh -, z • then eh := succ(ch) else eh := 'A' (* CA: eh e' pari alla lettera che dista di j posizioni da quella letta*); (* CA: eh e' pari alla lettera che dista di d posizioni da quella letta *) write(ch)
Un
metodo piu' diretto prevede l'uso delle funzioni
"chr" e "ord".
predefinite
La prima si applica ad un intero appartenente
un opportuno intervallo e restituisce il carattere che, dinamento
ad
nell'or-
del tipo "char" compare nella posizione corrispondente
al valore di quell'intero;
la seconda si applica ad un carattere
e restituisce il valore dell'intero corrispondente alla posizione di quel carattere nell'ordinamento.
La cultura è un bene dell'umanità (
[email protected])
Con queste funzioni la
tra-
47
sformazione di un carattere si effettua calcolando dapprima l'intero
corrispondente al carattere che si vuole ottenere,
sformando tale intero nel corrispondente carattere,
e
tra-
con l'avver-
tenza di usare l'alfabeto come circolare:
k := ord(ch) + d; if k > ord('Z') then k := k - 26; write( chr(k) )
Con questa soluzione, il programma completo diventa:
program trasforma(input,output); (* CM: legge una sequenza di 15 caratteri alfabetici o blanks e la trasforma eliminando i blanks e sostituendo ad ogni lettera quella che la segue di d posizioni nell'ordine alfabetico, considerando l'alfabeto come circolare; il valore di d e' letto come primo dato nella prima linea di ingresso; la sequenza inizia a colonna 1 della seconda linea di ingresso *) var
integer; (* CD: contatore *) i eh: char; (* CD: carattere da analizzare *) d : integer; (* CD: distanza tra i caratteri trasformati e gli originari; il valore di d deve essere compreso tra O e 26 *) integer; (* CD: variabile usata per la trasformazione k dei caratteri *)
begin readln(d); for i := l te 15 do begin (* CM: lettura dell'i-esimo carattere *) read(ch); (* CM: esame del carattere ed eventuale stampa *) if Ch I I then begin k := ord(ch) + d; if k > ord('Z') then k := k - 26; write( chr(k) ) end end end.
La cultura è un bene dell'umanità (
[email protected])
48
Un'ulteriore
versione
del programma che presentiamo prevede
di
rilasciare il vincolo che la sequenza di ingresso sia composta di 15 caratteri.
Per fare questo,
si puo' procedere almeno in
due
diversi modi che nel seguito analizziamo. Una
prima
lunghezza
soluzione consiste nel prevedere che il valore della sequenza sia letta da ingresso,
della
secondo il
se-
guente schema:
begin (* CM: lettura di d, distanza della trasformazione *) writeln(' valore di d (distanza della trasformazione) ? read(d); (* CM: lettura di n, lunghezza della sequenza *) writeln(' valore di n (lunghezza della sequenza) ?'); readln(n); far i := 1 to n do begin
1 );
end end.
Si
noti che sono state inserite due istruzioni di scrittura,
modo che, output
prima della lettura dei valori di d e n,
opportuni
messaggi che indicano quale dato
inserito
in ingresso:
eseguito
interattivamente.
in
compaiano in deve
essere
questo e' utile quando il programma viene Nel caso contrario e ' invece
censi-
gliabile una stampa dei valori letti. una seconda soluzione prevede di non fissare a priori la lunghezza della sequenza, esempio conoscere
ma di utilizzare o un carattere speciale
(ad
".") o la condizione di fine del file d'ingresso per riil
termine della sequenza
La cultura è un bene dell'umanità (
[email protected])
stessa.
In
questo
caso,
49
poiche'
il
numero di volte che le istruzioni del
essere eseguite non e' prefissato, istruzione
ciclo
devono
e' necessario fare uso di una
while (o repeat) per realizzare il ciclo
stesso.
Si
puo' quindi scrivere:
(*CA: la fine della sequenza e' segnalata dal simbolo "·" *) read(ch); while eh ' do begin esame del carattere ed eventuale stampa; read(ch) end end.
Oppure:
(* CA: la fine della sequenza e' segnalata dalla condizione di fine file di ingresso *) while not ( eof) do begin read(ch); esame del carattere ed eventuale stampa end end.
Il vantaggio di usare il punto per indicare la fine della sequenza
risiede nel fatto che sarebbe possibile inserire,
programma D'atra di
lo richiedesse,
altri dati dopo la
parte si deve tenere presente che,
inserire
il punto,
sequenza
La cultura è un bene dell'umanità (
[email protected])
stessa.
qualora si dimentichi
si avrebbe un'interruzione
errore della esecuzione del programma,
qualora il
forzata
per
dovuta ad un tentativo di
50
lettura del file di ingresso vuoto.
Tutte le soluzioni finora presentate presuppongono che i dati ingresso siano corretti, di
essi.
di
senza mai effettuare alcun controllo su
Il controllo di correttezza potrebbe essere realizzato
mediante le seguenti istruzioni:
read(ch) ~ (* CM: trattamento di un carattere *) if Ch I I then if (eh< 'A') or (eh> 'Z') then write(' carattere non alfabetico ') else ...... .
In
questo modo si avrebbe la segnalazione
dell'errore
inserita
tra gli altri risultati, senza l'interruzione dell'esecuzione del programma. Ad esempio, con i seguenti dati di ingresso: CODI'CE/SEGRETO si avrebbe, con d
1, la seguente uscita:
DPEJ CARATTERE NON ALFABETICO DFTFHSFUP Volendo, invece, interrompere l'esecuzione del programma a seguito
di
un errore nei dati di ingresso,
variabile
booleana che,
si puo' fare uso di
con il suo valore,
forzi l'uscita
una dal
ciclo di calcolo quando si verifica l'errore. Questa soluzione e' adottata nel seguente prog;ramma "trasforrnal",
che costituisce la
versione finale della soluzione al nostro problema.
La cultura è un bene dell'umanità (
[email protected])
51
program trasformal(input,output); (* CM: legge una sequenza di caratteri alfabetici o blanks e la trasforma eliminando i blanks e sostituendo ad ogni lettera quella che la segue di d posizioni nell'ordine alfabetico, considerando l'alfabeto come circolare; il valore di d e' letto come primo dato nella prima linea di ingresso; la sequenza inizia a colonna l della seconda linea di ingresso. Si assume che il valore di d sia compreso tra o e 26 e che la sequenza di ingresso termini con un punto *) var
eh: char; d : integer;
(* CD: carattere da analizzare *) tra i caratteri trasformati e gli originari; il valore di d deve essere compreso tra o e 2i *) k : integer; (* CB: variabile usata per la trasformazione dei caratteri *) errore: boolean; (* CD: assume il valore true solo a seguito della lettura di un carattere illegale *)
(* CD: distanza
begin (* CM: lettura della distanza d *) readln(d); (*CM: lettura del primo . carattere*) read(ch); (* CM: inizializzazione della variabile "errore" *) errore := false; while (eh 1 • 1 ) and ( not (errore) ) do begin -( * CM: trattamento di un carattere *) if Ch I I then if (eh >= 'A') and (eh n-1) or (c b-1); (* CM: stampa *)~ if (c < O) or (c > b-1) then (* CA:---r•uscita dal ciclo e' dovuta ad un errore *) write(' cifra scorretta: •,c) else (* CA: tutte le cifre erano corrette *) write(' numero in decimale: ',s) end .
Nel
programma
"conversione3" il ciclo di calcolo e' stato
lizzato mediante l'istruzione repeat,
poiche' il numero di volte
che le istruzioni che compongono il ciclo devono essere non e' fisso,
rea-
eseguite
ma dipende dal verificarsi o meno della condizione
La cultura è un bene dell'umanità (
[email protected])
58
di errore. inserire ciclo:
Con l'uso della istruzione repeat, e' stato possibile anche
la
lettura della prima
cifra
all'interno
del
eia' non comporta effetti collaterali rispetto al calcolo
i
di b
poiche', per i=O, le istruzioni del ciclo far che realizza-
no tale calcolo non vengono eseguite (essendo, >
i),
lasciando
in questo caso, j
alla variabile "e" il corretto
valore
1.
La
condizione
di uscita dell'istruzione repeat tiene opportunamente
conto
fatto che una situazione di
del
l'arresto
del
istruzione ciclo
errore
calcolo della conversione,
if
deve
comportare
mentre la
successiva
serve a disciminare il caso in cui
l'uscita
sia dovuta al valore scorretto di una cifra da
quello
dal di
uscita per fine delle cifre da analizzare. Si
vuole sottolineare che la differenza tra i programmi "conver-
sione2" errore
e
"conversione3"
risiede nel fatto che
causa l'interruzione forzata del
secondo
nel
programma,
primo mentre
un nel
causa solo l'interruzione del calcolo della conversione,
e l'esecuzione del programma viene comunque completata con l'esecuzione dell'ultima istruzione (istruzione if). Un'ulteriore
modifica
che proponiamo per il programma
consiste
nel definire b e n come variabili ed introdurre opportune zioni
di
lettura dei loro valori;
anche
di
tenere
minore di 10, programma
questa scelta ci
conto della verifica che il valore
istru-
suggerisce di
b
sia
tralasciata nei precedenti programmi. Nel seguente
"conversione4 11
b e n
variabili.
La cultura è un bene dell'umanità (
[email protected])
sono,
appunto,
definiti
come
59
program conversione4(input,output); var
(* CD:
b,
base in cui e' espresso il numero convertire *) n, (* CD: numero di cifre del numero da convertire *) s, c, e, i, j : integer;
da
begin (* CM: lettura di b e n *) write(' valore della base b? '); read(b); write(' numero di cifre del numero? '); read(n); (* CM: controllò di correttezza del valore di b *) if (b < 2) or (b > 9) then writeli1( 1 valore scorretto per b ') else begin ----- sezione istruzioni del ----- programma "conversione3" ----end end.
Si
noti che in questo caso la scelta sul metodo di
correttezza
delle cifre e' obbligata,
verifica
di
non potendosi definire la
variabile "c" nel seguente modo: c : o •• bmenol; con
bmenol
uguale a b -1,
perche' b non e' piu' definito
come
costante. Possiamo
a questo punto chiederci se il programma
puo'
essere
ulteriormente migliorato; le seguenti 3 osservazioni sul programma
mostrano
"conversione4"
che
sono
auspicabili
diversi
miglioramenti: - Osservazione 1: i
Il calcolo di b ciclo
di analisi delle cifre:
sostituito che,
viene eseguito con un ciclo all'interno del
al
esso puo' essere eliminato e
da una semplice moltiplicazione, se si osserva i passo i-esimo, b puo' essere calcolato come
La cultura è un bene dell'umanità (
[email protected])
60
i-1 prodotto
di
b
per b
valore gia'
calcolato al passo
(i-1)-esimo. - Osservazione 2: Le
cifre
ingresso dei
del
numero da
convertire
devono
comparire
in
nell'ordine inverso rispetto alla usuale scrittura
numeri:
la
significativa,
prima
cifra deve, cioe', essere
la
e cosi' via fino all'ultima cifra,
meno
che deve
essere la piu' significativa. - Osservazione 3: I
dati di ingresso devono essere organizzati in
che
le
cifre del numero da convertire siano
loro da almeno un blank. cuzione
modo
separate
tale tra
In caso contrario, infatti, l'ese-
del~'istruzione
read(c) assegnerebbe dalle
a
cifre
"c" il valore dell'intero decimale contigue
ed
il
programma
comportamento non voluto. L'osservazione 1 ci suggerisce una nuova soluzione:
program conversione5(input,output); var
b, n, s, c, e, i
integer;
begin (* CM: lettura di b e n *) write(' valore della base b? '); read(b); write(' numero di cifre del numero? '); read(n); (* CM: controllo di correttezza del valore di b *) if (b < 2) or (b > 9) then writelil(' valore scorretto per b ') else begin (* CM: lettura della prima cifra *) read(c); (* CM: inizializzazioni *)
La cultura è un bene dell'umanità (
[email protected])
formato
avrebbe
un
61
e := l; i := l; s := c; (* CM: ciclo per la conversione *) while (i < n) and (c >= O) and (c < b) do begin ~-~ (* CM: lettura i-esima cifra *) read(c); (* CM: calcolo di b elevato ad i *) (* CA: e = b elevato ad i-1 *) e := e * b; bi *) (* CA: e s := s + c * e; i := i + 1 end; (* CM: stampa *) if (c < O) or (c > b-1) then (* CA:-Y•uscita dal ciclo e' dovuta ad un errore * ) ~~ write(' cifra scorretta: •,c) else (* CA: tutte le cifre erano corrette *) write(' numero in decimale: ',s) end end.
programma "conversione5", per valori di i da 1 a n-1, i l i (che termine b viene calcolato moltiplicando i l valore di e i-1 i coincide con b ) per b; si noti che per i=O i l valore di b non
Nel
viene calcolato, essendo esso pari a 1. Per questo alla variabile s viene assegnato un valore iniziale pari alla prima cifra letta. Siamo cosi' riusciti ad eliminare il ciclo di .calcolo piu' interno, rispondendo alla esigenza dell'osservazione 1. L'osservazione 2,
ci conduce,
invece, a una soluzione completa-
mente diversa del problema. E' noto che un polinomio 2 n-1 X + X * b + X * b + + X * b o 1 2 n-1 puo' essere scritto nel seguente modo:
X
o
Il
+ b * (X
programma
proprieta',
+ b * (X
1 che che
+ ••• + b *X ) 2 n-1 ora presentiamo tiene conto
. ..
)
della
consente di analizzare le cifre del
convertire nell'ordine di scrittura usuale dei numeri:
La cultura è un bene dell'umanità (
[email protected])
)
suddetta numero
da
62
program conversione6(input,output); var
b, n, s, c, i
: integer;
begin (* CM: lettura di b e n *) write(' valore della base b? '); read(b); write(' numero di cifre del numero? '); read(n); (* CM: controllo di correttezza del valore di b *) if (b < 2) or (b > 9) then writelil{' valore scorretto per b ') else begin (* CM: lettura della prima cifra (la piu' significativa) *) read(c); (* CM: inizializzazioni *) i := l; s := c; (* CM: ciclo per la conversione *) while (i < n) and (c >= O) and (c < b) do begin ~-~ (* CM: lettura della i-esima cifra (da sinistra) *) read(c); s := s * b + c; i := i + 1 end; (* CM: stampa *) if (c < O) or (c > b-1) then (* CA:-r•uscita dal ciclo e' qovuta ad un errore *) write(' cifra scorretta : ',c) else (* CA: tutte le cifre erano corrette *) write(' numero in decimale: ',s) end end.
Con questa soluzione il valore di s al passo i-esimo viene calcolato
come
prodotto tra il suo valore al passo precedente
e
il
valore della base b, sommato al valore della cifra letta. Resta,
ora, il vincolo che ogni cifra deve essere separata dalla
successiva
da
almeno un blank;
per rilassare questo vincolo
e
rispondere cosi' all'esigenza dell'osservazione 3, si puo' mantenere l'impostazione del programma "conversione6 11 , ma con la scelta
di leggere le cifre del numero come caratteri
e
convertirle
ogni volta nella corrispondente cifra intera: in questo modo le
La cultura è un bene dell'umanità (
[email protected])
63
cifre possono essere scritte contigue, seguente programma,
senza spazi intermedi. Il
che e' l'ultimo che presentiamo, adotta tale
soluzione:
program conversione7(input,output); (* CM: converte in decimale un numero intero espresso in base b letto da ingresso; b e' minore di 10 e il numero da convertire e' composto di n cifre *) var
b, (* CD: base del numero da convertire *) n, (* CD: numero di cifre del numero da convertire *) s, (* CD: somma parziale e, poi, totale *) i integer; (* CD: contatore delle cifre *) c : char; (* CD: le cifre del numero vengono lette come caratteri e convertite in interi *)
begin
(* CM: lettura di b e n *) write(' valore della base b? '); read(b); write(' numero di cifre del numero? '); read(n); (* CM: controllo di correttezza del valore di b *) if (b < 2) or (b > 9) then writeli1( 1 valore scorretto per b ') else begin lettura della prima cifra (la piu' significa(* CM: tiva) *) repeat read(c) until c ' '; (* CM: inizializzazioni *) i:= l; s := ord(c) - ord('O'); (* CM: ciclo per la conversione *) while (i< n) and (c >= 'O') and (c < chr(ord('O')+b)) do begin ~-~ (* CM: lettura della i-esima cifra (da sinistra) *) read(c); s := s * b + ord(c) - ord('O'); i := i + l end; (* CM: stampa *) if (c < 1 0 1 ) or (c > chr(ord('O')+b-1)) then (* CA: uscita dal ciclo per errore *) write(' cifra scorretta: ',c) else (* CA: tutte le cifre erano corrette *) write(' numero in decimale: 1 ,s) end end.
La cultura è un bene dell'umanità (
[email protected])
64
Si noti che: per
la lettura della prima cifra,
fuori dal ciclo,
si
e•
comparire
in
utilizzato l'istruzione: repeat read(c) until c per
1
ignorare eventuali blanks che potrebbero
ingresso da'
prima del numero da convertire:
in questo modo si
possibilita• che il numero inizi ad
la
colonna
una
qualsiasi
della linea di ingresso (e anche dopo un
qualunque
numero di linee di ingresso composte di soli blanks). notare
che con questa scelta si risolve
problema dovuto 11
presente
in
al fatto che
eoln(input)
11
e'
11
alcune
anche
implementazioni
Si fa
l'eventuale del
Pascal
all'inizio del programma il valore di
true 11 e quindi il primo carattere che
legge e' il blank,
si
anche se esso non compare effettivamente
in ingresso; per la conversione tra carattere ed intero si e•
utilizzata
la formula: valore intero corrispondente a c
=
ord(c) - ord( 1 0 1 )
che tiene conto del fatto che nell'ordinamento del tipo char i
valori
verifiche fatto
1
01 ,
1
11,
•••
,'9' sono contigui;
della correttezza delle cifre di ingresso
uso della funzione
carattere
inoltre,
che,
11
chr 11 ,
La cultura è un bene dell'umanità (
[email protected])
si
e'
che converte un intero nel
nell'ordinamento,
corrispondente a quell'intero.
per le
occupa
la
posizione
65
ESERCIZI PROPOSTI 1.
Scrivere un programma che legga un numero (intero o frazionario)
espresso in base qualunque (minore di 10) e lo con-
verta in decimale. nella
forma
Il numero deve comparire in ingresso
stabilita
dalle seguenti regole sintattiche
(i simboli terminali sono quelli racchiusi tra"
"):
= / = { } "·" / [ ] " " = 11 0 11 / 11 1 11 / • • • / "9" in cui ogni cifra deve essere minore di b . seguenti dati di ingresso (con b=B): .5467 0.37 24 561.32 5717. sono coerenti con le regole date.
La cultura è un bene dell'umanità (
[email protected])
Ad
esempio,
i
7 Calcolo dell'orario di apertura di un ufficio
TESTO Scrivere un programma che calcoli l'orario d'apertura di un ufficio in un dato giorno (letto da ingresso) di un anno non bisestile, conoscendo il giorno della settimana (lunedi', martedi', ecc. letto
anch'esso da ingresso) del primo gennaio di
sapendo
quell'anno
e
che l'ufficio e' chiuso la domenica e aperto il lunedi',
mercoledi'
e venerdi' dalle 8 alle 13,
il martedi'
e
giovedì'
dalle 9 alle 12 e dalle 14 alle 18 e il sabato dalle 9 alle 11.
SOLUZIONE Il alla
primo aspetto che affrontiamo in questa soluzione e' relativo organizzazione dei dati di ingresso.
Poiche' il testo
problema
non specifica nessun vincolo a tale riguardo,
decidere
che
nella prima linea di ingresso debba
si
comparire
giorno della settimana del primo gennaio dell'anno in
del puo' il
questione,
scritto per esteso, e nella seconda la data di interesse, espressa in termini di due interi (giorno e mese) separati tra loro dal simbolo
11 - 11 •
Ne segue la prima versione del programma:
La cultura è un bene dell'umanità (
[email protected])
67
program orariol(input,output): begin /1/ /2/ /3/ / 4/
lettura del giorno della settimana del 1 gennaio; lettura della data (giorno e mese) di interesse; calcolo del giorno della settimana della data richiesta; calcolo e stampa dell'orario di apertura dell'ufficio in quella data
end.
Per
tradurre le varie frasi in istruzioni Pascal dobbiamo
dere
quali variabili si utilizzeranno e il loro
alla
variabile
che
si utilizzera' per
giorno della data richiesta, invece,
Riguardo
memorizzazione
del
scegliamo il tipo intero. Riguardo,
alle variabili usate per memorizzare il mese della
richiesta e i giorni della settimana, tivo.
la
tipo.
deci-
Questa
codifica favorendo
del programma,
sebbene
scegliamo un tipo enumera-
possa complicare leggermente
ne aumenta senz'altro la
la
leggibilita',
cosi' la modificabilita' e l'individuazione
tuali errori. "orariol",
scelta,
data
di
even-
Presentiamo, quindi, un raffinamento del programma
in
cui si traducono le frasi /1/ e /2/ in istruzioni
Pascal e si dichiarano le necessàrie variabili. program orariol(input,output); (* CM: calcola l'orario di apertura di un ufficio di un giorno qualunque (letto da ingresso) di un anno non bisestile, conoscendo il giorno della settimana del 1 gennaio di quell'anno (letto da ingresso) e l'orario di apertura dell'ufficio nei giorni della settimana *) var c : char; giornolgen :
(* CD: variabile per la lettura *) (* CD: giorno della settimana del 1 gennaio *)
( lun, mar, mer, gio, ven, sab, dom ); giornoin, (* CD: giorno del mese in ingresso *) mesein integer; (* CD: mese in ingresso *) mese : (* CD: codifica del mese della data in ingresso *) ( gen, feb, mar, apr, mag, giu, lug, ago, set, ott, nov, dic ); i integer; (* CD: contatore *)
La cultura è un bene dell'umanità (
[email protected])
68
begin (* CM: lettura del giorno della settimana del 1 gennaio *) write(' giorno della settimana del 1 gennaio?'); (* CM: lettura del primo carattere *) repeat read(c) until c ' '; (* CM : codifica nel tipo enumerativo *) case c of ~~'L' ~giornolgen : = lun; 'M' begin (* CA: non e' sufficiente il primo carattere *) read(c); if c = 'A' then giornolgen := mar else giornolgen := mer end; gIOrnolgen := gio; 'G' giornolgen := ven; 'V' giornolgen := sab; 'S' giornolgen := dom 'D' end; ~CM: posizionamento sulla seconda linea di ingresso *) readln; (* CM: lettura della data (giorno e mese) di interesse *) write(' giorno - mese della data richiesta ? 1 ) ; read(giornoin, c, mesein); (* CM: codifica del mese nel tipo enumerativo *) mese := gen; for i := 2 to mesein do mese :=-Succ(mese); /3/ calcolo del giorno della settimana della data richiesta; /4/ calcolo e stampa dell'orario di ·apertura dell'ufficio in quella data end.
Si noti che,
poiche' non e' possibile leggere da ingresso valori
appartenenti a un tipo enumerativo (i soli valori che si leggere sono interi,
reali e caratteri),
possono
e' stato necessario un
calcolo del valore di "giornolgen", realizzato con una istruzione case
sul valore del primo carattere letto (ed eventualmente
sul
secondo). Per la codifica del mese in termini del tipo enumerativo
si
e' fatto invece uso della funzione "succ",
che
si
basa
sull'ordinamento implicitamente d,efinito all'atto della dichiarazione dei valori del tipo,
che nel nostro caso e' opportunamente
coincidente con l'ordine naturale dei mesi.
La cultura è un bene dell'umanità (
[email protected])
69
consideriamo ora la frase /3/ del programma "orariol", che prevede
di
calcolare il giorno della settimana
corrispondente
alla
data richiesta. Il calcolo puo' essere effettuato in due passi:
/3 .1/ /3. 2/
calcolo del numero d'ordine nell'anno corrispondente alla data richiesta; calcolo del giorno della settimana corrispondente al numero d'ordine
Il passo /3.1/ puo' essere tradotto in istruzioni Pascal considerando che il numero d'ordine della data x - y (giorno - mese ) si ottiene
sommando
precedono y
tra
loro il numero dei giorni
dei
mesi
(se y non e' gennaio) ed aggiungendo al totale
che cosi'
ottenuto il valore x. Si utilizzeranno le seguenti variabili (che si dovranno poi aggiungere nella versione finale del programma):
nord i ne indmese
integer;
(* CD:
numero d'ordine nell'anno della data richiesta *) ( gen, feb, .... ) (* CD: indice per la scansione dei mesi *)
(* CM: calcolo del numero d'ordine nell'anno corrispondente alla data richiesta *) (* CM: inizializzazione *) nordine := O; (* CM: somma dei giorni dei mesi precedenti *) if mese > gen then far indmese := gen to prec(mese) do case indmese of gen, mar, mag, lug, ago, ott nord i ne := nord i ne + 31; apr, giu, set, nov nardi ne := nord i ne + 30; nordine .- nord i ne + 28 feb end; (* CM:-Somma dei giorni nel mese attuale *) nordine := nordine + giornoin
La cultura è un bene dell'umanità (
[email protected])
70
Il dei
passo /3.2/ potrebbe essere realizzato mediante una scansione giorni
dell'anno,
fino al valore
di
"nordine",
con
una
parallela scansione dei giorni della settimana,
con l'avvertenza
di
domenica
far
seguire
al valore corrispondente alla
quello
corrispondente al lunedì':
(* CM:
calcolo del giorno della settimana corrispondente numero d'ordine calcolato *) (* CM: inizializzazione al giorno del 1 gennaio *) risult := giornolgen; (* CM: scansione dei giorni dell'anno *) far i := 2 to nordine do (* CM: determinazione del giorno successivo *) if risult = dom then risult := lun else risult := succ (risult)
Un
metodo piu' efficiente,
calcolo
del
giorno
dell'operatore "giornolgen": valori
di
mod
che non richiede la ripetizione
successivo e
ricordiamo
della
per
"nordine"
funzione
volte,
"ord"
fa
applicata
che la posizione nell'ordinamento
un tipo enumerativo e' determinata
partendo
con
al
del uso a
dei il
valore o per il primo elemento, 1 per il secondo, e cosi' via. Ne risulta la seguente traduzione per il passo /3.2/:
(* CM:
calcolo del giorno della settimana corrispondente numero d'ordine calcolato *) (* CM: si basa a 7: nordine - l + ord(giornolgen) *) nordine := (nordine - l + ord(giornolgen) ) mod 7; (* CM: calcolo del giorno della settimana---;i;"""f (* CA: si deve trovare x tale che: nordine = ord(x) *) risult := lun; far i := 1 to nordine do risult :;;-succ (risult) (* CA: risult e' tale che: ord(risult) = nordine *)
al
Per completare il programma e' sufficiente tradurre la frase /4/,
La cultura è un bene dell'umanità (
[email protected])
71
che
prevede
la stampa dell'orario di apertura del giorno
della
settimana che si e' precedentemente calcolato: per tale stampa si puo'
fare
uso
della istruzione
case,
per
discriminare
tra
diversi giorni della settimana:
(* CM: stampa dell'orario di apertura dell'ufficio *) write(' il giorno 1 ,giornoin, 1 - 1 ,mesein, 1 l''ufficio'); if risult = dom then writeln(' restera'' chiuso l''intera giornata') else begin write(' sara'' aperto dalle'); case risult of --lun, mer,-Ven : writeln('S alle 13 1 ) ; mar, gio : writeln('9 alle 12 e dalle 14 alle 18'); sab : writeln('9 alle 11 1 ) end end--
Il
programma
completo,
con
la
dichiarazione
di
tutte
le
variabili, e' il seguente:
program orariol(input,output); (* CM: calcola l'orario di apertura di un ufficio di un giorno qualunque (letto da ingresso) di un anno non bisestile, conoscendo il giorno della settimana del l gennaio di quell'anno (letto da ingresso) e l'orario di apertura dell'ufficio nei giorni della settimana*) var c : char; giornolgen, risult mese, indmese giornoin, mese in, i, nordine :
(* CD: variabile per la lettura *) (* CD: giorno della settimana del 1 gennaio *) (* CD: giorno della settimana risultante *) ( lun, mar, mer, gio, ven, sab, dom ); (* CD: codifica del mese della data in ingresso *) (* CD: indice per la scansione dei mesi *) ( gen, feb, mar, apr, mag, giu, lug, ago, set, ott, nov, dic ); (* CD: giorno del mese in ingresso *) (* CD: mese in ingresso *) (* CD: contatore *) integer; (* CD: numero d'ordine nell'anno della data richiesta *)
La cultura è un bene dell'umanità (
[email protected])
72
begin (* CM: lettura del giorno della settimana del 1 gennaio *) write(' giorno della settimana del 1 gennaio?'); (* CM: lettura del primo carattere *) repeat read(c) unti1 c 1 1 ; (* CM: codifica nel tipo enumerativo *) case c of --'L' -giornolgen := lun; 'M' begin (* CA: non e' sufficiente il primo carattere *) read(c); if c = 'A' then giornolgen := mar else giornolgen := mer end; giornolgen := gio; 'G' giornolgen .- ven; 'V' giornolgen := sab; 'S' giornolgen := dom 'D' end; ~CM: posizionamento sulla seconda linea di ingresso *) readln; (* CM: lettura della data (giorno e mese) di interesse *) write(' giorno - mese della data richiesta?'); read(giornoin, c, mesein); (* CM: codifica del mese nel tipo enumerativo *) mese := gen; for i := 2 to mesein do mese :=-Succ(mese); CM: calcolo del numero d'ordine nell'anno corrispondente alla data richiesta *) (* CM: inizializzazione *) nordine := O; (* CM: somma dei giorni dei mesi precedenti *) if mese > gen then for indmese := gen to prec(mese) do case indmese -of gen, mar, mag, lug, ago, ott nordine := nord i ne + 31; apr, giu, nordine .- nord i ne + 30; set, nov nordine := nordine + 28 feb end; (* CM:-Somma dei giorni nel mese attuale *) nordine := nordine + giornoin; (* CM: calcolo del giorno della settimana corrispondente al numero d'ordine calcolato *) si basa a 7: nordine - 1 + ord(giornolgen) *) (* CM: nordine := ( nordine - 1 + ord(giornolgen) ) mod 7; (* CM: calcolo del giorno della settimana *) risult := lun; for i := 1 to nordine do risult :;;-succ (risult); CA: risult e' tale che ord(nordine) risult *)
T*
T*
La cultura è un bene dell'umanità (
[email protected])
73
(* CM: stampa dell'orario di apertura dell'ufficio *) write(' il giorno ',giornoin,' - ',mesein,' !''ufficio'); if risult = dom then writeln(' restera'' chiuso l''intera giornata') else begin write(' sara'' aperto dalle'); case risult of --lun, mer,-Ven: writeln('S alle 13 1 ) ; mar, gio : writeln('9 alle 12 e dalle 14 alle 18'); sab writeln('9 alle 11') end end-end.
ESERCIZI PROPOSTI 1.
Scrivere certa decida,
un programma che legga da
codifica
scelta,
seguendo
eventualmente
una
5
carte di un mazzo
strategia
quali carte cambiare.
deve seguire le regole del poker.
La cultura è un bene dell'umanità (
[email protected])
ingresso,
definita,
secondo di
una
poker
quante
Il cambio delle
e ed
carte
8 Somma di due vettori
TESTO Scrivere un programma che legga due vettori di dimensione 5,
con
componenti intere e calcoli e stampi il vettore somma. Si generalizzi
poi il programma rendendolo parametrico rispetto alle
di-
mensioni dei vettori. Un esempio di dati di ingresso e corrispondenti dati di uscita e' il seguente: INPUT:
1
5
11
3
2
(primo vettore)
4
3
10
1
12
(secondo vettore)
OUTPUT: 5
8
21
4
14
(vettore somma)
SOLUZIONE Una
possibile
soluzione
e•
realizzabile
con
questo semplice
programma: program sommavetl(input,output); (* CM: legge due vettori di 5 componenti intere e calcola stampa il vettore somma *) var
vl, v2, vs i
(* CD: vettori da sommare *) (* CD: vettore somma *) array [1 .. 5) of integer; integer; (* CD: contatore *)
La cultura è un bene dell'umanità (
[email protected])
e
75
begin (* CM: lettura del primo vettore *) far i := 1 to 5 do read( vl[I) ); (* CM: lettura del secondo vettore *) far i := 1 to 5 do read( v2[I) ); (* CM: calcolo del vettore somma *) far i := 1 to 5 do vs[i) :=--Vl[i) + v2[i]; (* CM: stampa del vettore somma *) far i := 1 to 5 do write( vSfiJ ) end-.-
Si
vuole ora presentare una versione dello stesso
cui
si tenga in considerazione il problema della
dei dati di ingresso e di uscita del programma. cioe'
programma
in
documentazione Si introdurranno
opportune istruzioni di stampa affinche' la immissione dei
dati di ingresso e la analisi dei dati di uscita siano agevolati:
program sommavet2(input,output); (* CM: legge due vettori di 5 componenti intere e calcola e stampa il vettore somma; si assume il programma non interattivo e si eseguono opportune istruzioni di stampa per facilitare l'analisi dei dati di uscita *) var
vl, v2, vs i
(* CD: vettori da sommare *) (* CD: vettore somma *) array [1 .. 5) of integer; integer; (* CD: contatore *)
begin (* CM: lettura del primo vettore *) writeln(' ----dati di ingresso '); writeln; writeln(' primo vettore:'); for i := 1 to 5 do begin read( vl[i] ) ; write( vl[i) ) end; (* CM: lettura del secondo vettore *) writeln; writeln(' secondo vettore:'); far i : = 1 to 5 do begin read( v2[i) ); write( v2[i) ) end;
La cultura è un bene dell'umanità (
[email protected])
76
(* CM: calcolo del vettore somma *) for i := 1 to 5 do vs[i] :=--Vl[i] + v2[i]; T* CM: stampa del vettore somma *) writeln; writeln(' ----dati di uscita----'); writeln; writeln(' vettore somma'); for i := l to 5 do write( vSfiJ ) end-.-
Come detto nel commento iniziale del programma, si e' assunto che esso
venga eseguito in modalita' non interattiva:
ragione
per la quale vengono stampati anche i dati
questa e' di
la
ingresso
appena vengono letti. Un esempio di uscita del programma "sommavet2" e' il seguente (si fa
l'ipotesi
che il compilatore usato produca la
stampa
degli
interi su 8 colonne):
---- dati di ingresso primo vettore: 1 2 secondo vettore: 6 7
3
4
5
8
9
10
11
13
---- dati di uscita vettore somma: 7
Si
9
vuole notare che il programma "sommavet" richiede piu' spazio
di memoria del necessario: sia
15
il
vettore
11
e' immediato, infatti, verificare che
v2 11 che il vettore "vs" non
necessari, come mostra il seguente programma:
La cultura è un bene dell'umanità (
[email protected])
sono
strettamente
77
program sommavet3(input,output); legge due vettori di 5 componenti intere e calcola e (* CM: stampa il vettore somma; si assume il programma non interattivo e si eseguono opportune istruzioni di stampa per facilitare l'analisi dei dati di uscita *) var
(* CD:
v
primo vettore da sommare e, poi, vettore somma *) array [1 .. 5) of integer; elem, (* CD: usata per la lettura delle componenti del secondo vettore in ingresso *) i : integer; (* CD: contatore *)
begin (* CM: lettura del primo vettore *) writeln(' ----dati di ingresso '); writeln; writeln(' primo vettore:'); for i := 1 to 5 do begin read( v[i] ) ; write( v[i] end; (* CM: lettura del secondo vettore e contemporaneo calcolo del vettore somma, memorizzato in "v" *) writeln; writeln(' secondo vettore:'); for i := 1 to 5 do begin read(elem); write(elem); v[i] := v[i] + elem end; (* CM: stampa del vettore somma *) writeln; writeln(' ----dati di uscita----'); writeln; writeln(' vettore somma'); for i := 1 to 5 do write( v[I] ) end:-
Nel programma "sommavet3" viene utilizzata una sola variabile
di
tipo array,
in cui si leggono le componenti del primo vettore in
ingresso
si memorizzano le componenti del vettore
e
somma.
componenti del secondo vettore in ingresso sono invece lette alla
volta in una variabile intera e subito sommate alla
Le una
corri-
spendente componente del primo vettore letto. Confrontando le due soluzioni
date dai programmi "sommavet2" e "sommavet3",
si puo'
notare che, pur avendo un comportamento ingresso-uscita identico,
La cultura è un bene dell'umanità (
[email protected])
78
differiscono nella struttura; minore occupazione di memoria, meno
pur richiedendo
una
ha una struttura meno leggibile e
aderente all'impostazione naturale della soluzione del pro-
blema (sottolineiamo, leggibilita• In
"sommavet3",
comunque, la soggettivita' del concetto di
di un programma).
casi di questo tipo la scelta e' tra due esigenze contrastan-
ti:
sara' l'analisi approfondita della maggiore o minore
tanza
impor-
di tali esigenze a condurre alla soluzione finale nei casi
reali. Generalizziamo, ora, il programma
11
sommavet2 11 , rendendolo parame-
trico rispetto alle dimensioni dei vettori da sommare. essere
fatto introducendo due livelli di
Cio' puo'
parametrizzazione:
il
primo rispetto alle dimensioni degli array usati nel programma il
secondo
leggono
rispetto al numero di componenti dei vettori che
quando
il programma viene eseguito.
parametrizzazione rappresenti nel
corso
consiste
la dimensione degli array e l'uso di
nel
fatto che,
degli array,
in questo caso
numero
di
la
tale
basterebbe modificare una semplice
11
la didi
puo' essere realizzato facendo in modo che
il
inserito
e'
la corrispondente
sommavet2 11 :
La cultura è un bene dell'umanità (
[email protected])
come
che dovra' anche verifi-
care che esso non superi la dimensione fissata per gli array.
programma
che
Il secondo tipo
dato di ingresso e letto dal programma,
programma
di
parametrizzazione
componenti dei vettori da sommare sia
seguente
si
costante
qualora fosse necessario aumentare
chiarazione e fare ricompilare il programma. parametrizzazione
tipo
richiede la dichiarazione di una costante
del programma:
dimensione
Il primo
e
generalizzazione
Il del
79
program sommavet4(input,output); (* CM: legge due vettori di componenti intere e calcola e stampa il vettore somma; si assume il programma non interattivo e si eseguono opportune istruzioni di stampa per facilitare l'analisi dei dati di uscita. Il numero di componenti dei vettori e' letto come primo dato *) const n var
=
5; (* CD: dimensione degli array *)
vl, v2, vs k, i
(* CD: vettori da sommare *) (* CD: vettore somma *) array (l .. n] of integer; (* CD: numero di componenti dei vettori da deve essere minore o uguale ad n *) integer; (* CD: contatore *)
begin writeln(' ----dati di ingresso---- '); writeln; write(' numero di componenti dei vettori: '); read(k); writeln(k); if k > n then writeln(' numero di componenti troppo grande ') else begin (* CA: k mat[l,colmax] ~ then colmax := i; (* CM: scansione delle altre righe *) for i := 2 to rig do for j :=~ to col do (* CA: liiat[rigrnax,colmax] e' il massimo fino ad ora incontrato *) if mat[i,j] > mat[rigrnax,colmax] then begin rigrnax := i; colmax := j end;
Abbiamo
volutamente
distinto,
La cultura è un bene dell'umanità (
[email protected])
per maggiore
chiarezza del
86
programma,
la
fase
massimo;
sarebbe,
un'unico
doppio
potuto
di lettura da quella del tuttavia,
ciclo
inserire sia la
calcolo
stato sufficiente
all'interno del lettur~
quale
si
sarebbe
provvisorio.
si sarebbe anche potuto evitare la memorizzazione degli
elementi della matrice in un array,
poiche' essa non e' necessa-
ria ne' per il calcolo del valore massimo, zione
utilizzare
dell'elemento della matrice,
sia il suo confronto con il valore del massimo Inoltre,
del
della
sua
ne' per
posizione nella matrice di
l'indiv idua-
ingresso,
che
e'
ricostruibile, qualora si adotti un metodo adeguato. Presentiamo, appunto,
una soluzione che non richiede la memorizzazione
elementi
in un array:
gli
elementi
quindi, rig
*
il
degli
per fare questo dobbiamo considerare
della matrice sono in numero di rig
*
col
e
che che,
problema si riconduce ad una ricerca del massimo tra
col valori, con la complicazione che, una volta individuato
che il massimo e' in posizione z,
i valori dell'indice i di riga
e j di colonna corrispondenti a tale valore possono essere calcolati a partire i
valori
dall~
seguente relazione (valida nell'ipotesi
della matrice siano letti per righe,
come nel
nostro
caso): z
=
(i - 1)
* col
+ j
da cui si ricava che, noto z, si ha: i
(z - 1) div col + 1
j
(z - 1) mod col + 1
Il programma corrispondente a questa soluzione e' il seguente:
La cultura è un bene dell'umanità (
[email protected])
che
87 program maxmatl(input,output); calcola il valore e la posizione del massimo di una (* CM: matrice di reali, gli elementi della quale sono letti da ingresso "per righe" *) var
elem,
(* CD:
max k,
real; (* CD:
kmax
(* CD: integer;
usata per memorizzare gli elementi della matrice *) (* CD: massimo provvisorio e, poi, finale *) usata per scandire i rig * col elementi della matrice *) posizione, nella matrice di ingresso, del massimo provvisorio e, poi, finale *)
begin
(* CM: inizializzazione di max al primo valore in ingresso *) read (max) ; (* CM: corrispondente inizializzazione di kmax *) kmax := l; (* CM: lettura degli elementi e calcolo del massimo *) far k := 2 to rig * col do begin (*-CA: max e' il massimo provvisorio *) (* CM: lettura di un elemento ed eventuale aggiornamento di max e kmax *) read ( elem) ; if elem > max then begin max := elem; kmax .- k end end; (* CA: max e' il valore del massimo e kmax la sua posizione nella sequenza di ingresso *) (* CM: calcolo e stampa della posizione del massimo nella matrice *) write('posizione del massimo: '); writeln('riga = ' (kmax - 1) div col+ 1, ' colonna ', (kmax - 1) mod col + 1); writeln('valore del massimo: ',max) end.
Confrontando i programmi "maxmat" e "maxrnatl", si puo' notare che lo svantaggio di una maggiore occupazione di memoria del primo e' compensato da una maggiore chiarezza delle sue istruzioni, da una piu'
naturale struttura e,
conseguentemente,
leggibilita'.
La cultura è un bene dell'umanità (
[email protected])
da
una
maggiore
88
ESERCIZI PROPOSTI 1.
Scrivere stampi
un il
programma
che legga una matrice di
valore e la posizione dell'elemento
interi massimo
e di
ogni riga e di ogni colonna. 2.
Scrivere stampi
un il
programma
che legga una matrice di
valore e la posizione dell'elemento
ogni diagonale.
La cultura è un bene dell'umanità (
[email protected])
interi massimo
e di
10 Calcolo del punto di sella di una matrice
TESTO Si
dice
"punto di sella" di una matrice di due
dimensioni,
un
elemento della matrice che sia il minimo della riga cui appartiene
e il massimo della colonna cui appartiene.
Scrivere un
pro-
gramma che legga gli elementi (interi e, supponiamo, tutti diversi tra loro) di una matrice a due dimensioni e determini la posizione del punto di sella, ~e esso es-i-st~
SOLUZIONE La
soluzione
della
matrice
che presentiamo consiste nel leggere gli e poi analizzare ordinatamente ognuna
elementi delle
sue
righe; per ogni riga si calcola la posizione dell'elemento minimo e si verifica se esso e' il massimo della colonna cui appartiene, nel qual caso l'elemento e' il punto di sella cercato.
Il prece-
dimento si arresta o quando e' stato trovato il punto di sella
o
quando e' stata analizzata tutta la matrice. Si noti che l'ipatesi che gli elementi della matrice siano tutti diversi tra loro ci assicura che per ogni riga esiste uno e un solo minimo e per ogni
La cultura è un bene dell'umanità (
[email protected])
90
colonna uno e un solo massimo: come conseguenza, se nella matrice esiste un punto di sella,
esso e' unico.
La prima versione del
programma e' la seguente:
program sella(input,output); (* CM: calcola il punto di sella di una matrice, se esiste; gli ~lementi della matrice sono diversi tra loro: se, quindi, esiste un punto di sella, esso e' unico *) const
=
m
5;
n
=
7;
(* CD:
numero di righe e matrice *)
colonne
della
var mat
array [l .. m, l .. n] of integer; (* CD: la matrice *) i, j, (*CD: usate per scandire l'array *) k, h : integer; (* CD : usate per individuare l'eventuale punto di sella della matrice *)
begin (* CM: lettura della matrice per righe *) far i := 1 to m do far j :=~ to n read( mat[i~] ) ; (* CM: ciclo di scansione delle righe di mat *) i
:= 1 i
repeat (* CM: analisi della riga i-esima *) /1/ scandisci la riga i e calcola la colonna k tale che mat[i,k] e' il minimo della riga i; /2/ scandisci la colonna k e calcola la riga h tale che mat[h,k] e' il massimo della colonna k; (* CA: se h = i il punto di sella e' mat[h,k) *) i := i + 1 until ( /3/ fine array ) or ( /4/ punto di sella trovato ) ; if /4/ punto di sella trovato then writeln('posizione del punto di sella: ',h,k) else writeln('non esiste punto di sella') end-.--
Al
fine
righe
di
e
numero
di colonne della matrice sono state di c hiarate
costanti valori
parametrizzare il programma rispetto al
le
"m" e "n" a cui sono state assegnati rispettivamente (puramente ipotetici) 5 e 7.
programma
La sezione
istruzioni
inizia con la lettura della matrice e continua con
La cultura è un bene dell'umanità (
[email protected])
di due i del un
91
ciclo
di scansione delle righe dell'array,
struzione
repeat:
realizzato con
l'i-
il numero di volte che le istruzioni di
tale
ciclo saranno eseguite non e' fisso, ma dipende dal verificarsi o meno
di una certa condizione che deve essere controllata all'in-
terno del ciclo stesso (punto di sella trovato). All'interno del ciclo, la frase /1/ indica la ricerca dell'indice di
colonna
in corrispondenza del quale si ha il
della
i-esima riga.
nella
variabile
"k".
Tale indice di colonna
"h",
verra'
valore
memorizzato
Questa colonna verra' poi analizzata
calcolare l'indice di riga, bile
minimo
che verra' memorizzato nella
per
varia-
in corrispondenza della quale si ha il massimo valore
della colonna k (frase /3/):
se tale indice e' uguale all'indice
di riga i, il punto di sella esiste, ed e' in posizione (h,k). Ne deriva la seguente traduzione delle frasi /1/ e /2/:
scandisci la riga i e calcola la colonna k mat[i,k] e' il minimo della riga i *)
(* CM:
tale
che
tale
che
k := l;
for j := 2 to n do if mat[i-;J"] < mat[i,k] then k := j; (* CM: scandisci la colonna k e calcola la riga h ma t [ h, k] e ' i l massimo della colonna k *) h := l; for j := 2 to m do if mat[j-;k] < mat[h,k] then h := j
La frase /3/ si traduce semplicemente nella condizione i
mentre, duta
> m
per la frase /4/ si deve considerare che, essendo prece-
dall'incremento dell'indice di riga i,
la
verifica
condizione "punto di sella trovato" equivale al predicato:
La cultura è un bene dell'umanità (
[email protected])
della
92
h
=
i
- l
Il programma completo e', quindi:
program sella; (* CM: calcola il punto di sella di una matrice, se esiste; gli elementi della matrice sono diversi tra loro: se, quindi, esiste un punto di sella, esso e' unico *) const
m
= 5;
n = 7;
(* CD:
numero di righe e matrice *)
colonne
della
var mat
array [l .. m, l .. n] of integer; (* CD: la matrice *) i, j, (*CD: usate per scandire l 'array *) k, h : integer; (* CD: usate per individuare l'eventuale punto di sella della matrice *)
begin (* CM: lettura della matrice per righe *) for i := 1 to m do far j :=l to n read( mat[i-;-]] ) ; (* CM: ciclo di scansione delle righe di mat *) i := l; repeat (* CM: analisi della r~ga i-esima *) (* CM: scandisci la riga i e calcola la colonna che mat[i,k] e' il minimo della riga i *) k
k
tale
:= l;
far j := 2 to n do if mat[i-;-]] < mat[i,k] then k := j; (* CM: scandisci la colonna k e calcola la riga h tale che mat[h,k] e' il massimo della colonna k *) h := l; for j : = 2 to m i5' do if mat[j,k] < mat[h,k] then h := j; (* CA: se h = i il punto di sella e' mat[h,k] *) i := i + 1 until (i> m) or (h =i - l); if h = i - 1 then writeln('posizione del punto di sella: ',h,k) else writeln('non esiste punto di sella') end-.--
>
Il
programma "sella" richiede,
sione
delle righe dell'array,
La cultura è un bene dell'umanità (
[email protected])
oltre al ciclo esterno di due cicli interni realizzati
scancon
93
l'istruzione forche, di
ciclo
puo'
come sappiamo, prevede
che
le istruzioni
siano ripetute un numero predeterminato di
volte.
pero' osservare che il calcolo del massimo della colonna
Si k
(il secondo ciclo far) non e' necessario: e', infatti, sufficiente verificare se il minimo della riga i massimo ciclo
della di
colonna k,
(cioe' "mat[i,k]") e'
il
e eia' puo' essere realizzato con
un
scansione della colonna k che puo'
essere
interrotto
appena si trovi un elemento maggiore di "mat[i,k]". Questa osservazione
porta
a una differente specifica
delle
operazioni
da
eseguire nel punto del programma corrispondente alla frase /2/, e conduce alle seguenti istruzioni:
-----(* CM:
(* h
CM:
:= i;
sostituisce la frase /2/ del programma "sella" ------
verifica se l'elemento mat[i,k] e' il colonna k *) inizializzazione di h *)
della
si scandisce la colonna k e si modifica il valore di h se e solo se si trova un valore mat[j,k] maggiore di mat [i, k] *)
(* CM:
j
massimo
:= 1;
repeat if mat[j,k] > mat[i,k] then (* CA: mat[i,k] non e' il massimo della colonna k *) h := j
:= j i
+ 1 until ( j > m) or ( h i); (* CA: mat[h,k] e' punto di sella se e solo se h j
i *)
In questo modo, qualora nella colonna k non esista alcun elemento maggiore
di mat[i,k],
al valore iniziale i; valore
dell'indice
il valore di h rimane inalterato rispetto in caso contrario, ad h viene assegnato il
di
mat[i,k] nella colonna,
riga
del
primo
elemento
maggiore di
valore sicuramente diverso da i. Si noti
La cultura è un bene dell'umanità (
[email protected])
94
che
questa
modifica
non
ha
alcun
effetto
sulle
successive
istruzioni del programma.
ESERCIZI PROPOSTI l.
Si
supponga di modificare il programma "sella"
sostituendo
all'ultima istruzione if la seguente istruzione:
if i > m then writeln('punto di sella non trovato') else writeln('posizione del punto di sella: ',h,k)
Verificare
se il programma cosi' modificato e' corretto
e,
nel caso che non lo sia, individuare una matrice di ingresso per la quale il risultato del programma sia errato. 2.
Risolvere matrice
il
problema
abbia
tutti
considerando,
10
rilassando il
vincolo tra
che
la
loro
e
gli
elementi
diversi
quindi, che
potrebbe
avere diversi punti di
sella, che devono essere tutti individuati.
3.
Scrivere interi
programma
che legga una matrice
e ne costruisca un'altra (di uguali
elementi media
un
reali
in
elementi
dimensioni)
cui ogni elemento ha valore
aritmetica degli elementi contigui
nella riga,
di
(cioe'
pari
di alla
adiacenti
nella colonna o in una diagonale) nella matrice
originaria.
La cultura è un bene dell'umanità (
[email protected])
11 Frequenza di caratteri
TESTO Scrivere caratteri con
un
programma
che legga da ingresso
una
sequenza
di
e calcoli e stampi il carattere alfabetico che ricorre
maggior
frequenza nella sequenza.
Un esempio
di
dati
di
ingresso con i relativi dati di uscita, e': INGRESSO:
UNA//3/S!!EQUENZA9:;/DIPROVA
USCITA
carattere alfabetico piu' frequente: numero di occorrenze
A 3
SOLUZIONE Per
individuare il carattere alfabetico con il maggior numero di
occorrenze
nella
sequenza e' necessario calcolare il numero
di
occorrenze per ciascun carattere e individuare poi il massimo. Possiamo impostare il programma nel seguente modo:
program maxfreq(input,output); begin /1/
/2/
lettura della sequenza e calcolo delle occorrenze ciascun carattere alfabetico; individuazione del carattere con il massimo numero occorrenze e stampa dei risultati
end.
La cultura è un bene dell'umanità (
[email protected])
di di
96
Per
tradurre
occorrenze
la frase /1/ occorre decidere
di ciascun carattere alfabetico:
come
calcolare
il metodo che
le sce-
gliamo prevede di utilizzare 26 contatori (uno per ogni carattere alfabetico) che, crementati ingresso. sono
inizializzati al valore O (zero),
opportunamente
verranno in-
durante la lettura della sequenza
Poiche' i 26 contatori sono tutti dello stesso tipo
in corrispondenza biunivoca con i caratteri alfabetici,
possono
realizzare mediante un array il cui tipo indice
sia
di e si un
intervallo di caratteri, come mostra il seguente raffinamento del programma,
in
cui la frase /1/ e' stata tradotta in
istruzioni
Pascal:
program maxfreq(input,output); calcola il carattere alfabetico che ricorre piu' (* CM: frequentemente in una sequenza di caratteri letta da ingresso *) var cont : array ('A' .. 'Z'] of integer; (* CD: array di contatori per memorizzare il numero di occorrenze di ciascun carattere *) char; c begin (* CM: lettura della sequenza e calcolo delle occorrenze di ciascun carattere alfabetico *) (* CM: azzeramento dei contatori *) for c:= 'A' to 'Z' do cont(c] := o; T* CM: ciclo di lettura della sequenza *) while not (eof) do begin read (c) ; del contatore relativo al aggiornamento (* CM: carattere letto c, se esso e' alfabetico *) i f c in ( 'A' .. 'z • ] then (.-CA: il carattere letto e' alfabetico *) (* CM: aggiornamento del relativo contatore *) cont[c] := cont[c] + 1 end; /2/~- individuazione del carattere con il massimo numero di occorrenze e stampa dei risultati end.
La cultura è un bene dell'umanità (
[email protected])
97
Si noti che la condizione di uscita dal ciclo si e' fatta coincidere
con la fine dei dati di ingresso,
standard "eof" sidera
utilizzando la
(che, senza specifica esplicita del file, si con-
applicata al file "input") che assume il valore "true" se
e solo se e' stata raggiunta la fine del file;
si noti anche che
non ci si e' preoccupati del controllo di fine linea, sul
funzione
confidando
fatto che quando "eoln" assume il valore "true" e si
l'istruzione
read(c),
la
esegue
variabile "c" assume il valore
(blank), ignorato mediante il successivo test. Il controllo sul valore di "c" e' stato eseguito mediante
l'ope-
ratore
in
che si applica a un elemento e a un insieme e
resti-
tuisce
il
valore "true" se e solo se quell'elemento
membro
dell'insieme.
e'
Nel nostro caso l'insieme e' specificato
mediante
una costante di tipo insieme: [I A I .. I
che come
denota
z I]
appunto l'insieme di caratteri alfabetici
nella specifica di tale insieme si sia sfruttato
mento sui valori del tipo base Passando
alla
frase
/2/,
(si
noti
l'ordina-
d~ll'insieme).
essa puo' essere realizzata
con
un
semplice ciclo di scansione di un array per la ricerca del massimo.
Ne deriva il seguente programma completo:
program maxfreq(input,output); (* CM: . calcola il carattere alfabetico che ricorre piu' frequentemente in una sequenza di caratteri letta da ingresso *) var cont: array ['A' .. 'Z'] of integer; (* CD: array di contatori per memorizzare il numero di occorrenze di ciascun carattere *) c, indmax : char;
La cultura è un bene dell'umanità (
[email protected])
98
begin (* CM: lettura della sequenza e calcolo delle occorrenze di ciascun carattere alfabetico *) (* CM: azzeramento dei contatori *) for c:= 'A' to 'Z' do cont[c) := O; (* CM: ciclo di lettura della sequenza *) while not(eof) do begin read(c); (* CM: aggiornamento del contatore relativo al carattere letto c, se esso e' alfabetico *) if c in [ 1 A 1 • • • z' J then (~CA: il carattere letto e' alfabetico *) (* CM: aggiornamento del relativo contatore *) cont[c] := cont[c) + 1 end; ~CM: individuazione del carattere con il massimo numero di occorrenze e stampa dei risultati *) (* CM: inizializzazione dell'indice di cont corrispondente al massimo provvisorio *) indmax : = 'A' ; (* CM: ciclo di scansione di cont *) for c := 'B' to 'Z' do if cont[c)°""> cont[indmax) then indmax := c; ~A: indmax e' il carattere che ricorre piu' frequentemente *) (* CM: stampa dei risultati *) if cont[indmax) = o then writeln('sequenza priva di caratteri alfabetici') else begin writeln('carattere alfabetico piu'' frequente: indmax) ; writeln('numero di occorrenze: ',cont[indmax)) end end.
Si
noti che il programma,
caratteri
con
solo carattere,
nel caso in cui ci siano due
numero di occorrenze pari al massimo, e precisamente quello,
pare per primo nell'ordine alfabetico.
La cultura è un bene dell'umanità (
[email protected])
o
stampa
piu' un
fra i suddetti, che com-
99
ESERCIZI PROPOSTI
1.
Modificare
il
programma precedente in modo che, se ci sono
due o piu' caratteri alfabetici nella sequenza con numero di occorrenze pari al massimo, li stampi tutti. 2.
Modificare i
il programma precedente in modo che stampi tutti
caratteri alfabetici con associato il numero di volte
cui essi compaiono nella sequenza, stampa,
in
con la regola che, nella
ogni carattere deve comparire dopo tutti quelli con
frequenza maggiore nella sequenza. 3.
Scrivere
un programma. che legga due sequenze di caratteri e
calcoli quante volte la prima compare nella seconda. 4.
Scrivere
un programma che legga due sequenze
alfabetici carattere
di
caratteri
e verifichi se esiste un intero k tale che x
in
posizione
i
di
una
e'
ogni
ottenibile
dal
carattere y dell'altra nellà stessa posizione i, mediante la trasformazione: x dove,
con
carattere
succk in
si
quello
=
succk (y)
e' indicato la trasformazione che
da
esso
dista
k
un
posizioni
nell'alfabeto, considerando l'alfabeto come circolare.
La cultura è un bene dell'umanità (
[email protected])
di
12 Prodotto di matrici
TESTO Scrivere
un programma che legga due matrici quadrate di interi e
calcoli il loro prodotto.
SOLUZIONE Date due matrici A(n,n) e B(n,n), il loro prodotto e' una matrice C(n,n) i cui elementi sono calcolati secondo la seguente formula: n
c
Il
calcolo
doppio dei la
I
A
*
B
ij h = 1 ih hj della matrice sara' percio' realizzato
ciclo per il calcolo di tutti i suoi
quali ottenuto mediante
mediante
elementi,
un
ciascuno
un ulteriore ciclo piu' interno per
sommatoria che compare nella formula suesposta.
Ne segue
la
prima versione del programma:
program prodmat(input,output); (* CM: calcola il prodotto di due matrici quadrate ingresso *) ·
lette
const n = 5; ( * CD: numero di righe e colonne delle matrici *) var a,b (* CD: matrici operandi *) c (* CD: matrice prodotto *) array [l .. n,l .. n] of integer; i,j ,h integer; (* CD: indici per le matrici *)
La cultura è un bene dell'umanità (
[email protected])
da
101
begin /1/ lettura della prima matrice e memorizzazione nell'array a; /2/ lettura della seconda matrice e memorizzazione nell'array b; (* CD: ciclo di calcolo del prodotto *) for i := 1 to n do for j :=l to n do (.* CD: calcolo di c [i, j ] *) begin c[i,j] :=O; for h := 1 to n do c[i,j] :;;-c[i,j] + a[i,h] * b[h,j] endT /3/ stampa dell'array c end.
Il
calcolo della matrice prodotto non ha bisogno di
commenti:
esso,
particolari
come detto precedentemente, e' stato realizzato
mediante tre cicli nidificati, quello di scansione delle righe di c,
quello piu' interno di scansione delle sue colonne,
ancora piu' interno per il calcolo del generico elemento Restano
invece da sviluppare le frasi /1/,
/2/ e /3/.
e quello c[i,j]. Riguardo
alle prime due, si puo' notare che, esse richiedono di eseguire la stessa operazione di lettura, applicata a due differenti variabili dello stesso tipo. utile gramma
Questa e' una tipica situazione in cui
definire un sottoprogramma. ha
Nel nostro caso il
sottopro-
lo scopo di leggere gli elementi di una matrice e
memorizzarli in un opportuno array:
essa necessita,
e'
di
percio', di
un parametro formale, che rappresenta appunto tale array. Riguardo al tipo di sottoprogramma, si
si puo' osservare che ad esso
chiede di calcolare e restituire un valore,
l'operazione di lettura e di memorizzazione:
non
ma di effettuare
e' opportuno, quin-
di, definire un sottoprogramma di tipo "procedure", come e' fatto nella
versione
definitiva del programma "prodmat",
specifica anche la frase /3/:
La cultura è un bene dell'umanità (
[email protected])
in
cui
si
102
program prodmat(input,output); (* CM: calcola il prodotto di due matrici quadrate ingresso per righe *) const n
=
a,b c i,j ,h
da
5; (* CD: numero di righe e colonne delle matrici *)
~ tipoar
v ar
lette
array [l. .n, 1. . n] of integer; (* CD: definizioned i tipo per gli array *)
(* CD: matrici operandi *) (* CD: matrice prodotto *) tipoar; integer; (* CD: indici per le matrici *)
procedure leggimat ( var mat : tipoar ) ; ( * CM: legge una matrice n * n per righe e la memorizza nella variabile di tipo tipoar passata come parametro attuale corrispondente al parametro formale mat *) v a r rig, col : integer; (* CD :
variabili locali dell'array *)
per
la
scansione
beg i n far rig := 1 to n do for col := 1 to n do read( mat[rig,col)) end; (*-CM: fine procedura leggimat *)
( * CM : sezione istruzioni programma principale *) begin ( * CM: lettura delle matrici e loro memorizzazione negli array a e b *) leggimat(a); leggimat(b); (* CD: ciclo di calcolo del prodotto *) for i : = 1 to n do far j :=-"l to n do (* CD: calcolo di c[i,j] *) begin c[i,j] :=O; for h := 1 to n do c[i,j] :;;-c[i,j] + a[i,h] * b[h,j] end; (* CM: stampa dell'array c *) far i := 1 to n do (* CM: stampa riga i-es i ma *) begin for j := 1 to n do write( c[I,j)); (* CM: cambio linea di output *) writeln end end.
La cultura è un bene dell'umanità (
[email protected])
103
Commentiamo ora procedura e',
dalla
parola
il
Per il parametro della
si e' scelto il passaggio per referenza (il
"mat"
passato
il programma presentato.
infatti,
un parametro variabile,
chiave var),
parametro
essendo
poiche' alla procedura
preceduto
deve
essere
non un semplice valore (nel qual caso si sarebbe
scelto
passaggio di parametri per valore,
omettendo la parola var),
ma il riferimento di una variabile del programma chiamante: po
della procedura e',
letti
da
come
infatti,
quello di assegnare
i
ingresso alle componenti dell'array che viene
parametro.
scovalori
passato
Si ricorda che la differenza tra i due tipi
di
passaggio di parametri e' che, nel passaggio per referenza, tutte le
operazioni
che le istruzioni della
procedura
(o
funzione)
compiono sul parametro formale vengono eseguite anche sul parametro
attuale,
valore:
ne
eventuali dalla
cosa
che
non avviene nel caso di
consegue che,
passaggio
nel caso di passaggio per
modifiche di valori sul parametro
formale
per
referenza, effettuate
esecuzione della procedura (o funzione) sono subite
dalla
variabile passata come parametro attuale. Nella che
sezione dichiarazione dei tipi e' stato definito "tipoar", rappresenta
il tipo delle variabili "a",
parametro formale della procedura "leggimat". taggio
"b",
"c"
e
Questo ha il
del van-
di localizzare in un unico punto del programma la dichia-
razione di quel tipo: cosi', se ad esempio si volesse cambiare il tipo
base dell'array,
dichiarazione tutti
i
nella
si dovrebbe aggiornare solamente sezione dichiarazione dei tipi,
punti in cui la definizione del tipo compare
e
la non
sua in
associato
alle relative variabili o parametri. Ricordiamo poi che la speci-
La cultura è un bene dell'umanità (
[email protected])
104
fica
del tipo dei parametri deve avvenire obbligatoriamente
diante
la
regola
fa eccezione il caso di particolari parametri formali
tipo
definizione di un identificatore di
array,
tipo
(a
me-
questa
in alcune implementazioni del Pascal) che,
di
quindi,
deve essere stato gia' dichiarato precedentemente alla definizione della procedura (o funzione) cui il parametro appartiene. La per
procedura che e' stata scritta potra' essere utilizzata la
lettura di variabili array definiti
di
tipo
solo
"tipoar" :
ricordiamo, infatti, la regola che impone che i parametri attuali specificati
all'atto
di
una
chiamata
di
una
procedura
(o
funzione) siano compatibili nel tipo con i corrispondenti parametri
formali.
La compatibilita' tra un parametro formale
ed
il
relativo parametro attuale e' basata sull'uguaglianza degli identificatori
dei loro tipi.
Cio' impone,
quindi,
che un sotto-
programma (procedura o funzione) in cui sia definito un parametro formale essere
di
tipo x (dove x e' l'identificatore del
tipo)
possa
utilizzato solo nell'ambito di programmi in cui tale tipo
x sia gia' stato definito. Come conseguenza, non e' possibile, in Pascal,
parametrizzare completamente un sottoprogramma
ai tipi dei parametri: "leggimat"
rispetto
nel nostro caso, ad esempio, la procedura
non puo' essere invocata per la lettura di un qualun-
que array, ma di un array di due dimensioni, i cui indici sono di tipo
[l .. n] ed il cui tipo base (cioe' il tipo delle sue
nenti) e' "integer".
compo-
Come gia' accennato precedentemente, alcune
implementazioni del Pascal permettono un meccanismo di definizione dei parametri formali di tipo array che superano alcune limitazioni
dette,
ma ad esse non faremo qui riferimento.
La cultura è un bene dell'umanità (
[email protected])
delle
105
E'
facile verificare che la procedura "leggimat" ha anche un'al-
tra dipendenza dal programma in cui e' definita, alla costante "n":
quella relativa
tale costante e•, infatti, usata dalla proce-
dura stessa, sfruttando il fatto che essa e' definita nel relativo ambito di visibilita•. Cosi', vale il vincolo che la procedura "leggimat" puo' comparire solo in programmi in cui "n" e "tipoar" siano
gia' stati definiti.
all'identificatore
"n",
Si noti che la
dipendenza
al contrario di quella da
11
rispetto
tipoar 11 ,
si
puo' eliminare definendo un nuovo parametro per la procedura, che rappresenti il numero di righe e colonne dell'array, nel seguente modo:
procedure leggimat ( var mat: tipoar; k: integer ); legge da ingresso, per righe, una matrice quadrata di (* CM: due dimensioni e la memorizza nella variabile di tipo tipoar passata come parametro attuale corrispondente al parametro formale mat; k rappresenta il numero di righe e colonne della matrice *) var rig, col : integer; (* CD:
variabili locali dell'array *)
per
la
scansione
begin for rig := 1 to k do for col :=-i- to k ~do read( mat[rig,col)) end; (-;;;-CM: fine leggimat *)
Con questa scelta,
il valore corrispondente al numero di righe e
colonne dell'array che si vuole di volta in volta leggere verrebbe specificato come parametro attuale in corrispondenza al metro valore
formale
"k" ("k" e' un parametro di
tipo
valore).
dovra' necessariamente essere consistente con la
zione di tipo
11
tipoar 11 ,
paraTale
definì-
in modo che non si abbia una chiamata di
La cultura è un bene dell'umanità (
[email protected])
106
procedura in cui il valore del parametro attuale corrispondente a "k" sia maggiore dei limiti dell'array stabiliti nella definizione
del
tipo "tipoar",
cosa che causerebbe
un
errore
durante
l'esecuzione della procedura stessa. Un'ulteriore osservazione riguarda le due variabili "rig" e "col" definite nell '.ambito della procedura "leggimat": diamo,
si chiamano variabili locali della procedura.
potuto adottare una differente scelta ed usare, le
si sarebbe
nella procedura,
variabili "i" e "j" del programma come variabili globali:
questo caso, ad
esse, lo ricor-
qualunque riferimento, nell'ambito della procedura,
"i" e "j" sarebbe stato considerato relativo
del programma, programma
utilizza
alle
variabili
accessibili da parte della procedura. Sebbene nel
"prodmat" cio' non avrebbe comportato problemi di
terferenza
in
nell'uso di tali variabili, dopo
in-
poiche' il programma
le chiamate della procedura,
si puo' notare
le che
tale scelta creerebbe una ulteriore e inutile dipendenza di "leggimat" dal programma chiamante: essere
infatti,
la procedura
potrebbe
inserita in programmi in cui siano definite due variabili
di nome "i" e "j", di tipo integer ed il cui uso non interferisca con
quello della procedura.
Per questa ed altre
ragioni
viene
consigliato un uso oculato e controllato delle variabili globali. Ricordiamo che alle variabili locali della procedura si sarebbero potuto
assegnare
variabili avrebbe
i nomi "i" e
"j",
ridenominando,
del programma con lo stesso nome. avuto come
~onseguenza
della procedura "leggimat",
che,
La
cosi',
le
ridenominazione
nell'ambito di
visibilita'
qualunque riferimento a variabili di
nome "i" e "j" sarebbe stato considerato relativo alle
La cultura è un bene dell'umanità (
[email protected])
variabili
107
locali della procedura, e non a quelle definite nel programma. Un'ultima osservazione riguarda il modo in cui e' stata realizzata
la stampa dell'array nel programma "prodmat":
modo che,
in uscita,
si e' fatto in
ogni riga dell'array compaia in una diffe-
rente linea di stampa.
Cio' e' stato ottenuto inserendo, dopo il
ciclo interno per la stampa della generica riga, l'istruzione writeln il
cui
effetto
e' quello di abbandonare la corrente
linea
di
interi
e
stampa e posizionarsi sulla successiva.
ESERCIZI PROPOSTI
1.
Scrivere
un
verifichi ogni
programma
che
che legga una matrice di
sia una matrice simmetrica (cioe'
suo elemento in posizione i,j sia uguale
in posizione j,i), elementi
al
di
tale
che
all'elemento
triangolare (cioe' tale che tutti i suoi sopra o tutti quelli
al
di
sotto
della
diagonale principale siano uguali a zero) o diagonale (cioe' tale
che
tutti i suoi elementi che non
appartengono
alla
diagonale principale siano uguali a zero). 2.
un
Scrivere interi
e
programma che legga una calcoli
la
dimensione
matrice della
sottomatrice quadrata con elementi uguali.
La cultura è un bene dell'umanità (
[email protected])
quadrata piu'
di
grande
13 Elevamento a potenza di interi
TESTO Scrivere
un sottoprogramma (procedura o funzione) che,
noti due
____ valori interi l__ /interi a ________ e b .J) calcoli il valore di a elevato a b.
SOLUZIONE La prima scelta da effettuare nella soluzione al problema dato e' relativa
al
tipo
piu'
appropriato
di
sottoprogramma
per
l'operazione richiesta. L'alternativa e' fra il tipo procedura ed il tipo funzione.
Analizziamo le due alternative considerando le
relative intestazioni. Nel primo caso si avrebbe: procedure potenza ( a,b
integer; var c
integer ) ;
nel secondo: function potenza ( a,b : integer ) : integer; Si
puo'
notare
che nel caso si scelga il
tipo
risultato della operazione viene comunicato al te
attraverso un parametro,
La cultura è un bene dell'umanità (
[email protected])
in particolare il
procedura,
programm~
terzo,
il
chiamandefinito
109
come parametro variabile: usare
il programma chiamante dovrebbe
una apposita variabile e passarla come parametro
cioe'
attuale,
assieme agli altri parametri, rappresentanti gli operandi dell'elevemento zione
a
potenza;
il valore di tale variabile dopo l'esecu-
della procedura sarebbe proprio il
puo'
dire
procedura quello
di
che
risultato
voluto.
l'effetto del sottoprogramma "potenza"
non e' solo quello di calcolare un
valore,
assegnare tale valore calcolato a una
programma chiamante.
di
Si tipo
ma
anche
variabile
del
Nel caso, invece, di sottoprogramma di tipo
funzione si ha che l'effetto del sottoprogramma e'
semplicemente
quello
chiamante
di
risultato
calcolare e di restituire al programma della operazione voluta,
il
senza necessita' da parte di
quest'ultimo di usare ulteriori variabili;
d'altra parte,
programma
chiamante
assegnare
calcolato
a una sua variabile,
avesse l'esigenza di
il
potrebbe farlo con una
se il valore
semplice
istruzione di assegnazione, nel seguente modo:
(* CM:
calcolo di alfa elevato a beta valore ottenuto a gamma *) gamma:= potenza (alfa,beta );
Per tipo
queste ragioni,
del
assegnazione
scegliamo di definire un sottoprogramma
"function" per il nostro problema.
l'intestazione
ed
funzione:
Abbiamo
gia'
essa avra' due parametri
di
definito valore,
rappresentanti gli operandi dell'elevamento a potenza e sara' tipo "integer",
del
di
perche' tale e' il tipo del risultato, cioe' dei
La cultura è un bene dell'umanità (
[email protected])
110
valori
che
passaggio
la funzione calcola.
Il fatto che si sia scelto
il
di parametri per valore assicura inoltre l'assenza
di
effetti collaterali non voluti provocati dalla funzione, casi
piu' complessi di quello che stiamo
trattando,
che, in
potrebbero
essere difficilmente controllabili. Riguardo al calcolo del valore della funzione,
si puo' utilizzare un ciclo, basato sul fatto
che il valore di a elevato a b si ottiene moltiplicando a per
se
stesso b volte. Si ottiene la seguente definizione:
function potenza ( a,b : integer ) : integer; (* CM: calcola a elevato a b *) var p, i
(* CD: prodotto parziale e, poi, finale *) (* CD: contatore *)
integer;
begin p
:= l;
(* CM: ciclo delle moltiplicazioni successive *) far i := 1 to b do p := p *a (*CA: p vale a elevato a i*); T* CA: p vale a elevato a b *) (* CM: si associa il valore finale al nome della funzione *) potenza := p end; (* CM: fine potenza *)
Si
noti
sono
che le variabili necessarie al calcolo
state
funzione
definite come
variabili locali.
della
funzione
Il valore che
restituisce e' dato dall'espressione che compare a
stra dell' ultima istruzione di assegnazione:
la de-
tale istruzione di
assegnazione non ha l'effetto usuale di assegnare un valore a una variabile Questo
ma
valore
di
associare un valore al
sara' restituito come
della funzione stessa.
nome
risultato
della della
funzione. chiamata
Cosi', ad esempio, l'effetto della ipate-
tica istruzione del programma chiamante:
La cultura è un bene dell'umanità (
[email protected])
111
gamma:= 5 +potenza( alfa,beta );
sara' quello di assegnare alla variabile "gamma" il valore calcolato
come la somma di 5 e il valore che l'esecuzione della
fun-
zione con i parametri attuali "alfa" e "beta" associera' al
nome
della funzione stessa. Si
noti
che
l'uso della variabile locale "p" e'
motivato
dal
fatto che non e' possibile utilizzare il nome della funzione
per
memorizzare il risultato dei prodotti parziali. Sarebbe, infatti, errato scrivere:
potenza := l; far i := 1 to b do potenza := potenza
perche'
*
a;
l'occorrenza del nome
"potenza"
a
destra del
simbolo
di assegnazione sarebbe interpretata come la richiesta di zione
della funzione stessa
della funzione) che,
esecu-
(cioe' come una chiamata ricorsiva
oltre a non essere voluta nel nostro
caso,
necessiterebbe della specifica dei parametri attuali. Vogliamo della
ora presentare una diversa soluzione,
ricorsione.
basata
sull'uso
L'operazione di elevamento a potenza si
puo'
infatti definire ricorsivamente nel seguente modo:
a elevato a b
1:
se b
*
(a elevato a b-1)
La cultura è un bene dell'umanità (
[email protected])
=
o
se b >= O
112
e in base a questa definizione, si puo' scrivere la seguente versione ricorsiva per la funzione "potenza": function potenza ( a,b : integer ) : integer; (* CM: calcola a elevato a b usando la ricorsione *) begin if b =
o
then potenza := 1 else end_; __ potenza := a
*
potenza(a,b-1)
Si puo' notare che la versione ricorsiva della funzione "potenza" rispecchia
fedelmente la definizione ricorsiva dell'elevamento a
potenza, e non richiede l'uso di variabili locali, come invece la corrispondente versione iterativa.
D'altra parte,
anche la ver-
sione ricorsiva necessita di aree di memoria ausiliarie, sono
rese disponibili ed utilizzate durante
ma esse
l'esecuzione
della
funzione, senza che siano esplicitamente visibili al programmatore. Ricordiamo che, nel caso generale, la necessita' di utilizzare
memoria
funzioni
ausiliaria
per eseguire correttamente
ricorsive nasce dall'esigenza di
procedure
memorizzare,
a
o
ogni
chiamata ricorsiva, diversi dati, come, ad esempio, gli eventuali parametri istruzione
e le eventuali variabili locali,
il riferimento
all'
che bisogna eseguire al ritorno della chiamata ricor-
siva, e cosi' via. Nel caso di sottoprogrammi ricorsivi la situazione e' complicata dal fatto che non puo' essere noto a cioe' in fase di compilazione, una esecuzione:
priori,
il numero di chiamate generate da
tale numero sara' noto solo al momento di effet-
tiva esecuzione. Per
chiarire meglio il significato delle precedenti affermazioni
La cultura è un bene dell'umanità (
[email protected])
113
e per mostrare in dettaglio l'effetto di chiamate ricorsive di un sottoprogamma, funzione
presentiamo
la
ricorsiva "potenza",
traccia dell'
esecuzione
supponendo che essa sia
della
invocata
mediante la seguente istruzione del programma chiamante: alfa:= potenza( 5,2 ); Le
grandezze
che considereremo nel seguire
l'esecuzione
della
funzione, saranno: i parametri "a" e "b" e il valore associato di volta
in volta al nome della funzione.
Al momento dell' invoca-
zione della funzione da parte del programma chiamante,
la situa-
zione puo' essere schematizzata nel seguente modo:
ESECUZIONE 1
----->
a
b
5
2
potenza
Si noti che ai parametri formali e' stato assegnato il valore dei parametri
attuali specificati nella chiamata,
associato
a "potenza" e'
"ESECUZIONE
1 11
esecuzione
indica
indefi~ito
(simbolo
che i valori sono
mentre il "-").
Il
relativi
termine
alla
generata dalla invocazione della funzione.
dalla situazione mostrata,
valore
prima
A partire
vengono eseguite le istruzioni
della
funzione, che, . nel nostro caso, consistono in una semplice istruzione
if.
"false", percio'
poiche'
il valore di "b" non e' uguale a
eseguito il ramo else,
"potenza" prima
Il predicato associato a tale funzione da' il
essere valutata.
La cultura è un bene dell'umanità (
[email protected])
zero;
viene
che prevede di associare al nome
il valore di un'espressione,
cosa,
valore
che
deve,
La valutazione della
quindi,
per
espressione
114
prevede
di moltiplicare il valore di "a" per il valore
ottenuto
dalla esecuzione ricorsiva della funzione "potenza",
con parame-
tri
di
attuali
ESECUZIONE
rispettivamente di valore 5 (il valore 1)
e di valore 1 (il valore di "b" in
"a"
in
ESECUZIONE
l
meno 1). Rappresentiamo la chiamata ricorsiva nel seguente modo:
ESECUZIONE 1 ESECUZIONE
Si
2
-----> ----->
a
b
5
2
5
1
noti che nella situazione attuale
r~~
esistono
differenti copie
di "a", "b" e "potenza", ciascuna corrispondente ad una esecuzione della funzione. Inoltre il valore di "potenza" in ESECUZIONE 1 e'
ancora
indefinito
conoscenza quindi,
perche' la sua
del valore di "potenza" in
valutazione ESECUZIONE
la seconda esecuzione della funzione:
richiede 2.
la
Seguiamo,
poiche' il valore
di "b" durante tale esecuzione non e' pari a zero, viene di nuovo eseguito
il ramo else dell'istruzione if,
che,
analogamente
a
quanto era avvenuto per la prima esecuzione, richiede l'esecuzione
ricorsiva della funzione,
mediante una chiamata della stessa
con parametri attuali di valore 5 ("a" in ESECUZIONE 2) e O
("b"
in ESECUZIONE 2 meno 1). La situazione evolve nel seguente modo:
ESECU ZIONE 2
-----> ----->
ESECUZIONE 3
----->
ESECUZIONE 1
a
b
,5
2
5
1
5
o
La cultura è un bene dell'umanità (
[email protected])
potenza
115
Nella terza esecuzione della funzione, il predicato b
dell'istruzione
if ha valore "true";
relativo ramo then, valore 1.
= o viene percio' eseguito
che prevede l'associazione a
"potenza"
il del
Alla fine di ESECUZIONE 3, quindi, la situazione e' la
seguente:
ESECUZIONE 1 ESECUZIONE 2 ESECUZIONE 3
-----> -----> ----->
potenza
a
b
5
2
5
1
5
o
1
A questo punto la terza esecuzione della funzione termina,
e
il
suo effetto e' quello di restituire il valore 1 a chi tale esecuzione
aveva
invocato,
funzione stessa. zione
cioe'
seconda
esecuzione
della
Il controllo torna, quindi, alla seconda esecul'ist~uzione
che puo' completare
temente
alla
interrotta
per la chiamata
di assegnazione preceden-
ricorsiva,
e
associare
a
"potenza" il valore di "a" (in ESECUZIONE 2, cioe' 5) moltiplicato
1,
il
valore
restituitogli dalla
terza
esecuzione
funzione. Alla fine di ESECUZIONE 2, la situazione e':
ESECUZIONE 1 ESECUZIONE 2
-----> ----->
a
b
5
2
5
1
La cultura è un bene dell'umanità (
[email protected])
potenza
5
della
116
Si
noti che nel disegno i valori relativi alla ESECUZIONE 3
non
vengono pìu' mostrati, in guanto tale l'esecuzione e' terminata. Analogamente prima
al caso precedente,
esecuzione della funzione,
tenza"
il controllo ritorna ora
alla
che riprende associando a "po-
il valore calcolato come prodotto tra il valore
di
"a"
(in ESECUZIONE 1, cioe' ancora 5) e il valore restituitogli dalla ESECUZIONE 2 della funzione,
cioe' 5. La situazione e', a questo
punto:
----->
ESECUZIONE 1
Percio',
l'esecuzione
a
b
5
2
potenza 25
della funzione · termina,
resti tuend.o
il
e al contrario
di
corretto valore 25 al programma chiamante. Per
concludere notiamo come,
guanto
potesse
richieda
una
iterativa, (e,
sembrare a prima vista,
la
versione
ricorsiva
maggiore occupazione di memoria rispetto a
dovuta essenzialmente al fatto che tutti i
in generale,
replicati
nel complesso,
ad
quella
parametri
tutti gli oggetti definiti localmente) vengono
ogni
occupazione
di
compensata
dalla
chiamata.
memoria
e'
maggiore
definizione della funzione·,
D'altra nascosta
parte, al
semplicita'
questa
programmatore e
naturalezza
maggiore ed
e'
della
evidenti soprattutto in quei casi in
cui il problema stesso sia formulabile ricorsivamente in naturale.
La cultura è un bene dell'umanità (
[email protected])
maniera
117
ESERCIZI PROPOSTI
1.
Scrivere calcoli
un
programma
che legga un vettore
di
interi
la somma delle sue componenti mediante la
a una funzione ricorsiva.
e
chiamata
Si segua poi la traccia dell'ese-
cuzione della funzione scritta,
ipotizzando di eseguirla su
un vettore scelto a piacere. 2.
Scrivere una procedura ricorsiva che, una
stringa
stampi
di caratteri,
tali
caratteri
avendo come parametro
rappresentata nell'ordine
mediante inverso
array, rispetto
all'ordine in cui compaiono nella stringa. 3.
Scrivere una procedura ricorsiva che, un
array
elementi
a una dimensione, compaiano
lo modifichi in modo che
in ordine inverso
originario.
La cultura è un bene dell'umanità (
[email protected])
avendo come parametro
rispetto
gli
all'ordine
14 Gestione informazioni voli
TESTO
Si
assuma
partenza cord.
che le informazioni relative ai voli da
Ogni
giornalieri
un aereoporto siano memorizzate in un array di record contiene le seguenti informazioni sul
in
re-
corri-
spendente volo: 1. Numero del volo
2. orario di partenza 3. Numero di posti liberi
4.
Si
Destinazione. vuole
scrivere
una
procedura
per
ognuna
delle
seguenti
operazioni: a) Cambio dell'orario di un volo b) Aggiornamento dei posti liberi in un volo.
SOLUZIONE
Il
del problema specifica che i dati
testo
strutturati relativi
in un array di record;
di
interesse
ciascun record contiene dati
a un certo volo in partenza da un aereoporto.
La cultura è un bene dell'umanità (
[email protected])
sono
Si
puo'
119
pertanto
assumere nota alle procedure che si devono scrivere
la
seguente definizione di tipi:
tiponumvolo = array [ 1.. 5] of char; tiporario = record 23; ora : o 59 minuti : o end; record recvolo tiponumvolo; numvolo tiporario; orario integer; postilib array [l. .30) of char destinaz end; array [l. .n] of recvolo; tabvoli
~
Il
record destinato a contenere informazioni sul singolo volo e'
stato
strutturato in 4 campi,
all'orario
di
partenza,
record composto di 2 campi,
uno dei
quali,
quello
relativo
e' stato definito a sua volta come
un
uno per l'ora, l'altro per i minuti.
Entrambi questi campi sono stati definiti come subrange d'interi. Stabilita la struttura dei record, procedure, bio
passiamo alla scrittura delle
iniziando con quella relativa alla operazione di cam-
dell'orario di partenza di un volo.
Le informazioni che
si devono fornire alla procedura sono:
- il numero del volo di cui si vuole aggiornare l'orario; - il nuovo orario di partenza. A seguit.o di queste informazioni, la procedura dovra' inserire il nuovo
orario
nel campo opportuno del record
volo desiderato. La prima versione della procedura e':
La cultura è un bene dell'umanità (
[email protected])
corrispondente
al
120
procedure nuovorario (var tab : tabvoli; volo : tipounumvolo; ~- nuovor : tiporario); (*CM: modifica l'orario di un volo *) integer;
var i
begin /1/ cerca l'indice i del record relativo al volo di interesse; (* CM: aggiornamento *) tab[i].orario.ora := nuovor.ora; tab[i].orario.minuti := nuovor.minuti end; (* CM: fine procedura nuovorario *)
La procedura ha tre parametri: due di essi rappresentano informazioni d'ingresso alla procedura stessa, il numero del volo di cui si vuole cambiare l'orario ("volo") e il nuovo orario ("nuovor"). Per
essi si e' scelto il passaggio per valore,
proprio
perche'
rappresentano valori che la procedura deve conoscere per compiere le operazioni volute e non variabili che devono essere aggiornate dalla procedura stessa.
Il terzo parametro,
invece, rappresenta
l'array di record contenente le informazioni sui voli, e per esso si
e' scelto il passaggio per referenza,
poiche' rappresenta la
variabile che la procedura deve opportunamente aggiornare. Riguardo
alla sezione istruzioni,
la frase /1/
rappresenta
le
operazioni relative alla ricerca dell'indice dell'array in corrispondenza
del quale si trova il record che contiene,
nel
campo
"numvolo", il numero del volo passato come parametro. Seguono poi le
istruzioni
relative all'aggiornamento del campo ''orario"
di
tale record. Considerando che tale campo e' a sua volta un record e
che
record,
non e' possibile eseguire direttamente si
e'
assegnazioni
separato l'aggiornamento dei due campi
"minuti" che compongono il record stesso.
La cultura è un bene dell'umanità (
[email protected])
"ora"
tra e
121
Tornando alla frase /1/ ed osservando che una analoga di
ricerca
operazione
sara' necessaria anche per la procedura di aggiorna-
mento del numero di posti liberi di un volo, decidiamo di scrivere un nuovo
sottoprogramma
per tale operazione, con l'assunzio-
ne che il risultato che essa deve fornire sia, del record cercato se esso esiste, per
errore,
appunto, l'indice
oppure sia il valore zero se,
si cercasse un numero di volo che
non
esiste.
Il
sottoprogramma sara' percio' di tipo "function".
function indice (mat : tabvoli; volo : tiponumvolo): integer; ricerca in "mat" il record con "numvolo" pari a "volo"; (* CM: fornisce in la posizione di tale record se esso esiste; se il record non esiste, restituisce zero *) var trovato i
boolean; integer;
begin i
:= n;
trovato := false; repeat if mat[i].numvolo =volo then trovato := true else i := i - 1 untTl(i =O) or (trovato); indice := i ~ end; (* CM: fine funzione indice *)
Si
puo'
facilmente
valore corretto: to,
la
valore o, donato.
variabile
osservare che la
funzione
restituisce
il
se, infatti, il record cercato non viene trova"i" verra' decrementata
fino ad assumere
il
valore che fa si' che il ciclo di calcolo venga abbanSi noti l'uso della variabile booleana che,
con il
suo
valore, controlla l'altra condizione di uscita dal ciclo, e cioe' il
caso in cui il record venga trovato.
La cultura è un bene dell'umanità (
[email protected])
122
Tale variabile e• stata usata al fine di evitare che il controllo sul
valore di
predicato problemi
11
mat[i].numvolo 11 fosse inserito
di uscita dell'istruzione repeat.
direttamente
nel
Per comprendere i
che tale scelta avrebbe comportato consideriamo la
se-
guente versione della sezione istruzioni della funzione "indice":
begfn 1
:= n + l;
repeat
i := i - l until (i= O) or (mat[i].numvolo indice := i end; (* CM: fine funzione indice *)
volo);
Supponiamo di eseguire questa funzione per cercare non esiste;
un record che
l' istruzione del ciclo, cioe' il decremento di "i",
verrebbe, in questo caso, eseguito fino a fare assumere ad "i" il valore o. A questo punto verrebbe valutato il predicato di uscita dell'istruzione repeat cuzione,
poiche'
dell'array
11
mat 11 ,
si
e si avrebbe, tenterebbe
percio', un errore in ese-
di accedere alla
posizione
o
di dimensione [l .• n]. Si noti che l'errore non
si verificherebbe se la valutazione delle due sottocondizioni: (i = O)
e
(mat[i].numvolo =volo) in
or tra loro avvenisse nell'ordine in cui si trovano e
verificarsi
della
prima evitasse la valutazione della
Questo metodo di valutazione dei predicati,
se
il
seconda.
pur essendo adottato
in alcune implementazioni del Pascal, non puo' assumersi vero per tutte
ed e' percio' consigliabile,
La cultura è un bene dell'umanità (
[email protected])
specialmente in mancanza
di
123
precise tore,
informazioni sul comportamento del particolare
compila-
evitare situazioni che potrebbero causare errori del
tipo
di quello appena descritto. Una
soluzione
"ricerca",
alternativa
a quella presentata
nella
e che fa uso dell'istruzione goto e non di
funzione variabili
booleane, e' la seguente:
function indicel (mat : tabvoli; volo : tiponumvolo): integer; (* CM: ricerca in "mat" il record con "numvolo" pari a "volo"; fornisce in uscita la posizione di tale record se esso esiste; se il record non esiste, restituisce zero *) label l; var i : integer; begin i := n + l; repeat i := i - l; if i = O then goto 1 until mat[i).numvolo =volo; l: indicel := i end; (* CM: fine funzione indicel *)
Nella funzione
"indicel",
se "i" assume il valore
o,
il ciclo
viene abbandonato mediante un salto incondizionato realizzato con l'istruzione goto. Si evita cosi' di valutare il predicato mat[i].numvolo =volo con i
O. Ricordiamo che l'effetto dell'istruzione goto 1
e'
di
trasferire il controllo alla istruzione che ha come
chetta la label l:
eti-
nel nostro caso tale istruzione e' l'associa-
zione del valore corretto al nome della funzione. L'istruzione goto e' stata usata, in questo caso, per abbandonare
La cultura è un bene dell'umanità (
[email protected])
124
le istruzioni di un ciclo a fronte del verificarsi di una
condi-
zione
uscita
che
puo• definirsi eccezionale rispetto all'altra
dal ciclo, quella causata dall'aver trovato il record cercato. In linea
generale
questo uso dell'istruzione goto
e•
considerato
accettabile anche da chi giudica che tale istruzione puo' mente
degradare la chiarezza ed il livello di strutturazione
un programma. ammettono eseguita
istruzione,
all'interno
la
esattamente
di
Si noti anche che molte implementazioni del Pascal
una
abbandonare guire
facil-
generalmente chiamata exit
di un ciclo
qualunque,
ha
che,
se
l'effetto
di
le istruzioni del ciclo stesso e di passare ad prima istruzione dopo quelle del
ciclo,
ese-
riproducendo
l'uso che abbiamo fatto dell'istruzione
goto
nella
funzione "indicel". Prima
di passare alla seconda procedura richiesta dal
presentiamo
problema,
la versione definitiva della procedura "nuovorario",
opportunamente
modificata
tenendo conto
dell'esistenza
e
comportamento della funzione "indice": procedure nuovorario (var tab : tabvoli; volo : tiponumvolo; ~- nuovor: tiporario); (* CM: modifica l'orario di un volo *) var i
integer;
begin (* CM: ricerca del record *) i:= indice(tab, volo); if i = o then writeln('numero del volo errato') else (* CA: tab[i] e' il record cercato *) begin (* CM: aggiornamento *) tab[i].orario.ora := nuovor.ora; tab[i].orario.minuti := nuovor.minuti end end; (* CM: fine procèdura nuovorario *)
La cultura è un bene dell'umanità (
[email protected])
del
125
La seconda procedura, quella per l'aggiornamento dei posti liberi in
un volo,
ha la stessa struttura di "nuovorario".
che alla procedura venga passato,
Supporremo
mediante il parametro "k",
un
valore corrispondente al numero di posti che non sono piu' disponibili nel volo. La procedura e':
procedure aggiornaposti (var tab : tabvoli; volo k : integer) ; (* CM: aggiorna i posti liberi in un volo *)
tiponumvolo;
integer;
var i
begin (* CM: ricerca del record *) i:= indice(tab, volo); if i
=
o
then writeln('numero del volo errato') else (* CA: tab[i] e' il record cercato *) (* CM: aggiornamento *) tab[i).postilib := tab[i).postilib - k end; (* CM: fine procedura aggiornaposti *)
Per
mostrare
come queste procedure possano
essere
utilizzate,
presentiamo ora un possibile programma completo che lavori rattivamente
con
un ipotetico operatore;
supporremo
inte-
che
tale
operatore abbia la possibilita' di richiedere: a) la modifica di orario di un volo b) l'aggiornamento dei posti liberi di un volo c) la fine delle operazioni. supporremo anche che, i
dati
relativi
all'inizio della esecuzione del programma,
ai voli del giorno siano
letti
da
ingresso,
mediante una procedura, la cui specifica lasceremo al lettore, in modo
da inizializzare opportunamente il corrispondente array
record.
Lasciamo
al lettore anche la scrittura della
La cultura è un bene dell'umanità (
[email protected])
di
procedura
126
"operandi", che acquisisce
le opportune informazioni
della richiesta di una delle operazioni a) e b):
al momento
la struttura di
tale procedura deve essere dedotta dalle chiamate presenti
nelle
istruzioni del programma. Il programma e' il seguente:
program gestvoli; (* CM: gestione informazioni sui voli di un aereoporto *)
=
const n
50;
(* CD: numero di voli del giorno *)
tiponumvolo tiporario =
recvolo
tabvoli
var oper voli V
=
array (1 .• 5) of char; record 23; ora : o minuti : o 59 end; (*co: tipo per le informazioni su un volo *) record tiponumvolo; numvolo orario tiporario; integer; postilib destinaz array ( 1. . 3 O) of char end; -e* CD: tipo per l'array che rappresenta le informazioni sui voli del giorno *) array [l .. n] of recvolo;
char; tabvoli; (* CD: voli del giorno *) tiponumvolo; orario : tiporario;
h
integer;
function indice (mat: tabvoli; volo: tiponumvolo): integer; (*CM: ricerca in "mat" il record con "numvolo" pari a "volo"; fornisce in la posizione di tale record se esso esiste; se il record non esiste, restituisce zero *) var trovato boolean; i : integer; begin i := n; trovato := false; repeat if mat[i].numvolo =volo then trovato := true else i := i - 1 unt~i =O) or (trovato); indice := i end; (* CM: fine procedura indice *)
La cultura è un bene dell'umanità (
[email protected])
127
procedure nuovorario (var tab : tabvoli; volo : tiponumvolo; ~- nuovor: tiporario); (* CM: modifica l'orario di un volo *) var i
integer;
begin (* CM: ricerca del record *) i:= indice(tab, volo); if i = o then writeln('numero del volo errato') else (* CA: tab[i] e' il record cercato *) begin (* CM: aggiornamento *) tab[i).orario.ora := nuovor.ora; tab[i].orario.minuti := nuovor.minuti end end; (* CM: fine procedura nuovorario *)
procedure aggiornaposti (var tab : tabvoli; volo k: integer); (* CM: aggiorna i posti liberi in un volo *) var i
tiponumvolo;
integer;
begin (* CM: ricerca del record *) i:= indice(tab, volo); if i = o then writeln('numero del volo errato') else (* CA: tab[i] e' il record cercato *) (* CM: aggiornamento *) tab[i).postilib := tab[i].postilib - k end; (* CM: fine procedura aggiornaposti *)
procedure leggivoli; (* CM: acquisizione dei dati relativi ai voli del giorno *) ----- si lascia al lettore la specifica ---------di questa procedura ----------
La cultura è un bene dell'umanità (
[email protected])
128
procedure operandi ( •.•... (* CM: acquisizione dati per le operazioni A e B *) ----- si lascia al lettore la specifica ---------di questa procedura ----------
(* CM: istruzioni del programma *) begin (* CM: acquisizione dati relativi ai voli del giorno *) leggidati; (* CM: ciclo di funzionamento: l'operatore chiede una operazione e viene chiamata la corrispondente procedura che la esegue *) readln; repeat writeln( 'A. modifica orario di un volo'); writeln('B. aggiornamento posti liberi in un volo'); writeln ('c. fine operazioni'); read(oper); if oper = 'A' l'operazione richiesta e'la modifica then (* CA: dell'orario di un volo*) begin (* CM: richiesta di dati per l'operazione *) operandi('A', v, orario, h); (* CM: esecuzione dell'operazione *) nuovorario(voli, v, orario) end else if oper = 'B' l'operazione richiesta e' l'aggiornathen (* CA: mento dei numeri di posti in un volo *) begin (* CM: richiesta di dati per l'operazione *) operandi('B', v, orario, h); (* CM: esecuzione dell'operazione *) aggiornaposti(voli, v, h) end else if oper 'C' then writeln('*** operazione sconosciuta***') until oper = ~ end-.--
La cultura è un bene dell'umanità (
[email protected])
129
ESERCIZI PROPOSTI
1.
Un polinomio puo' essere rappresentato mediante un array record
nel
seguente
modo:
ogni
record ha
rappresenta un termine del polinomio; il
coefficiente
ed
il secondo
due
il primo
di
campi
e
rappresenta
l'esponente.
Scrivere
un
programma che legga due polinomi e calcoli la loro somma. 2.
Si
dice
che un vettore A di n componenti e' minore
di
un
vettore B di m componenti se: per:
1. A[i] B[i] 2. A[j] < B[j]
1 A_ r::.x \ : ~ P1"'t'é · Rt f\ D( ?-" D Ai o'\ , P11{17=?; _,
r\
,~
D,
E N I) -
I I
~oci::c v~t-_
L1:Gc , (Pnllir
r;,~~)?
YAR l •. , i'll t. Cr f. 1:VK\; ' 6,...,, E p : :: \-"1''\j
1Xll"\IL1:
BE'G Il'{
11-- ~ P< >1-l1 L
DO
a\
V'I P 11 S (?~ Df\ ì La cultura è un bene dell'umanità (
[email protected])
\'. = P:\
i::x ' :
'
16 Trasferimento di dati tra liste
TESTO Scrivere una procedura che elimini da una lista, un'altra,
inserendoli
in
in qualunque ordine, tutti gli elementi maggiori di un
dato valore.
SOLUZIONE Suppeni•m•
nete
&11•
procedura
che
scriveremo
le
~guenti
definizioni di tip!.:
punt = Aelemente; elemento = record val next end;
Con
tipobase; punt
questa dichiarazione una lista viene rappresentata
mediante
record e puntatori e, quindi, con strutture dinamiche di memorizzazione.
Si
noti che il tipo del campo informazione del
record
(il campo "val") e' stato dichiarato "tipobase": non viene fissa-
La cultura è un bene dell'umanità (
[email protected])
14 2
to,
percio',
procedura
in
definizione stesso
a
priori,
ma si da' la possibilita' di usare
diversi casi, di
0
tipobase 11 •
specificando di volta in L'unico vincolo imposto
volta dal
la la
testo
del problema e' che sui valori di "tipobase" sia definito
un ordinamento.
Le informazioni che si dovranno comunicare
alla
procedura sono: xil
puntatore
iniziale
(di
tipo "punt")
della
lista
da
modificare;
X
il
valore
elementi
(di
tipo "tipobase") con
della
lista
per verificare
cui
confrontare
quali,
tra
gli
questi,
eliminare; X)a
variabile
(di
tipo "punt") in cui la
procedura
possa
comunicare il puntatore iniziale della lista che essa crea; Per eliminare gli elementi richiesti e' necessario che la procedura ed
scandisca la lista esaminando il campo "val" di ogni eseguendo
record
l'operazione di eliminazione nel caso in cui
essa
sia necessaria. Ricordiamo che eliminare . da una lista un elemento
x
che
non sia ne' il primo ne' l'ultimo elemento
della
significa aggiornare il campo puntatore dell'elemento ad x,
in modo che esso non punti piu' ad x,
segue
x nella lista.
lista,
I se,
invece ,
lista,
precede~te
ma all'elemento che
x e' il primo elemento della
la sua eliminazione consiste nell'aggiornare il puntatore
iniziale
della
segue x.
Se, infine, x e' l'ultimo elemento, la sua eliminazione
comporta
l'aggiornamento
precede figura
lista in modo che esso
punti
all'elemento
del campo puntatore dell'elemento
x in modo che esso segnali la fine
della
lista.
che
che Nella
seguente viene schematizzata l'operazione da compiere per
La cultura è un bene dell'umanità (
[email protected])
143
eliminare un elemento (quello con valore 5 nel campo ne) da una lista.
informazio-
Il puntatore tratteggiato e' quello che rimane
dopo la eliminazione:
----
........
/
·I
I
4
i7'
-I
5
'
'
~
-
12
A parte il caso del primo elemento, e' necessario che, al momento in cui s'individua un elemento x da eliminare,
si possa accedere
all'elemento che precede x, per potere effettuare l'aggiornamento del relativo campo puntatore.
In Pascal eia' puo' essere realiz-
zato in almeno due modi: ){"
scandendo la lista con due puntatori,
uno all'elemento
che
si sta analizzando, l'altro all'elemento che lo precede; )("
scandendo
la
lista con un solo puntatore,
volta in volta, analizzando;
che
punti,
all'elemento che precede quello che si
quest'ultimo
e' sempre raggiungibile
di sta
poiche'
nell'elemento che lo precede e' memorizzato il puntatore che punta ad esso. Analizziamo dapprima la soluzione a), sottolineando l'esigenza di porre che mento fare
particolare attenzione al trattamento del primo non ha alcun elemento che lo precede. degli elementi da una lista
elemento,
Riguardo al trasferi-
all'altra,
sara'
necessario
attenzione all'ordine in cui vengono effettuate le assegna-
zioni di valori ai puntatori, in modo da non perdere informazioni significative. Cio' posto,
presentiamo la prima versione
La cultura è un bene dell'umanità (
[email protected])
della procedura.
144
procedure trasfl (var piniz, nuova : punt; n : tipobase); elimina dalla lista il cui puntatore iniziale e' piniz (* CM: tutti gli elementi con valore maggiore di n; gli elementi eliminati vengono posti in una nuova lista, il cui puntatore iniziale e' comunicato nel parametro nuova *) var
p, prec, paux
(* CD: puntatore all'elemento in esame *) (* CD: puntatore all'elemento precedente a quello in esame *) (* CD: puntatore ausiliario *) punt;
begin (* CM: inizializzazione dei puntatori *) p := piniz; prec := nil; (* CA: inizialmente non c'e' elemento precedente *) nuova := nil; (* CM: lista nuova vuota *) (* CM: scansione della lista *) while p nil ero---(* CM: esamina l'elemento puntato da p *) if p".val > n then (* CM: eliminazione dell'elemento *) begin if prec = nil then (* CA:-1 1 elemento da eliminare e' il primo della lista *) aggiornamento del (* CM: puntatore d'accesso alla lista *) piniz := p".next else (* CA: l'elemento da eliminare non e' il primo della lista *) prec".next := p".next; (* CM: inserimento nella nuova lista (in testa) dell'elemento eliminato e aggiornamento del puntatore p *) paux := p".next; (* CM: dovra' essere il nuovo valore di p *) p".next :=nuova; nuova := p; p := paux end else (* CM: avanzamento nella lista: si aggiornano i puntatori p e prec *) begin prec := p; p := p".next end end; (* CM: fine procedura trasfl *)
Si noti che per il parametro "piniz", che rappresenta il puntatore d'accesso alla lista, si e' scelto il passaggio per variabile, ?.
La cultura è un bene dell'umanità (
[email protected])
145
poiche'
e' possibile che la procedura debba modificarne il valo-
re,
particolare
in
nel caso in cui il primo
elemento
sia
da
eliminare. La che
lista "nuova" viene creata aggiungendo in testa gli di volta in volta vi vengono trasferiti,
poiche' in
elementi questo
modo le operazioni sono semplificate; d'altra parte, il testo del problema non richiedeva alcun ordine di memorizzazione particolare per gli elementi di tale lista. Passiamo ora alla soluzione b), che richiede una scansione effettuata memorizzando il puntatore dell'elemento precedente a quello che si sta analizzando.\ Per trattare omogeneamente anche il primo elemento,
possiamo
utilizzare un metodo che ricalca quello pre-
sentato nel problema 15, ratore:
si crea,
che fa uso del concetto di record gene-
cioe', un record che non porta alcuna informa-
zione significativa nel campo "val" e si
inserisce_al_pr.imo_~
della lista. ( Si fanno poi le opportune operazioni sulla lista e, alla
fine,
vantaggio sta
si
elimina e si rilascia il record
generatore:
il
e' che anche il primo·elemento significativo della li-
ha un elemento che lo precede.
La soluzione,
con il metodo
descritto, diventa:
procedure trasf2 (var piniz, nuova : punt; n : tipobase); (* CM: elimina dalla lista il cui puntatore iniziale e' piniz tutti gli elementi con valore maggiore di n; gli elementi eliminati vengono posti in una nuova lista, il cui puntatore iniziale e' comunicato nel parametro nuova *) var
p, paux
(* CD: puntatore all'elemento in esame *) (* CD: puntatore ausiliario *) punt;
La cultura è un bene dell'umanità (
[email protected])
146
begin (* CM: creazione del record generatore *) new(p); pA.next := piniz; (* CM: inizializzazione dei puntatori *) piniz := p; (* CA: piniz punta al record generatore *) nuova := nil; (* CM: lista nuova vuota *) (* CM: scansione della lista *) while pA.next nil ~(* CM: esamina l'elemento che nella lista segue quello puntato da p *) if pA.nextA.val > n then (* CM: eliminazione dell ' elemento e suo inserimento nella nuova lista (in testa) *) begin paux := p A.next; p A.next := paux A.next; pauxA.next : = nuova; nuova := paux end else ~CM: avanzamento nella lista: si aggiornano il punta tor e p *) p := pA.next; (* CM: si elimina il record generatore (puntato da piniz) *) p := piniz; piniz := pinizA.next; dispose(p) end; (* CM: fine procedura trasf2 *)
L'ultima soluzione che presentiamo e' la soluzione ricorsiva.
La
possibilita'
il
nostro
di trovare un semplice algoritmo ricorsivo
problema deriva dal fatto che una lista e' una
per
struttura
ricorsiva, definibile nel seguente modo: Una
lista o e' vuota oppure e' formata da un nodo seguito da una
lista. Nel
caso
della soluzione ricorsiva si dovra' quindi
verificare
che la lista su cui si deve operare non sia vuota {perche' in tal caso la procedura non deve effettuare alcuna operazione) caso
che
non sia vuota,
compiere le operazioni
e,
nel
opportune
sul
primo elemento e richiamare ricorsivamente se' stessa per ripetere le stesse operazioni sulla lista che segue il primo elemento:
La cultura è un bene dell'umanità (
[email protected])
147
procedure trasf3 (var piniz, nuova : punt; n : tipobase); elimina dalla lista il cui puntatore iniziale e' piniz (* CM: tutti gli elementi con valore maggiore di n; gli elementi eliminati vengono posti in una nuova lista, il cui puntatore iniziale e' comunicato nel parametro nuova *) ~
paux
punt; (* CD: puntatore ausiliario *)
begin if /1/ la lista puntata da p non e' vuota then begin if /2/ il primo elemento e' maggiore di n then /3/ eliminalo ed inseriscilo nella lista puntata ~~ da nuova; /4/ esegui ricorsivamente trasf3 sulla lista che rimane end end; (* CM: fine procedura trasf3 *)
La frase /1/ si traduce molto facilmente nel predicato: p nil mentre la frase /2/ nel predicato: p " .val > n Le
istruzioni
relative alla frase /3/ sono
analoghe
a
quelle
viste nella versione iterativa della procedura:
begin paux := p; p := p " .next; paux" .next := nuova; nuova .- paux end
Riguardo,
invece,
alla
frase /4/,
e' necessario decidere,
momento della chiamata della procedura "trasf3",
quale variabile
usare come parametro attuale corrispondente al parametro (parametro
variabile) p,
.che rappresenta il puntatore
della lista. A questo proposito osserviamo che:
La cultura è un bene dell'umanità (
[email protected])
al
formale iniziale
148
- il
valore
passare
del puntatore iniziale della lista che
alla
chiamata ricorsiva e' memorizzato
dobbiamo nel
campo
p".next; - la
variabile
che la chiamata ricorsiva deve
eventualmente
modificare se elimina il primo elemento della lista
su
cui
opera e' ancora p".next. Ne
segue
che la chiamata ricorsiva deve avvenire
nel
seguente
modo: trasf3(p".next, nuova, n)
La versione finale della procedura e':
procedure trasf3 (var piniz, nuova : punt; n : tipobase); elimina dalla lista il èui puntatore iniziale e' piniz (* CM: tutti gli elementi con valore maggiore di n;· gli elementi eliminati vengono posti in una nuova lista, il cui puntatore iniziale e' comunicato nel parametro nuova *) var paux : punt; (* CD: puntatore ausiliario *) begfn if piniz nil then (* CA: la lista puntata da piniz non e' vuota *) begfn if piniz".val > n il primo elemento e' maggiore di n *) then (* CA: - - (*CM: eliminalo ed inseriscilo nella lista puntata da nuova *) begin paux := p; p := p".next; paux".next := nuova; nuova := paux end; · trasf3(piniz".next, nuova, n) end end; (* CM: fine procedura trasf3 *)
La cultura è un bene dell'umanità (
[email protected])
149
ESERCIZI PROPOSTI 1.
Per memorizzare un numero intero di lunghezza qualunque puo' essere utilizzata una lista semplice, scal mediante record e puntatori. legga
rappresentata in
Pa-
Scrivere un programma che
due numeri interi di lunghezza qualunque e calcoli la
loro somma. 2.
Scrivere
un
programma che legga due
interi
di
lunghezza
qualunque e calcoli il loro prodotto. 3.
Scrivere una procedura che, semplice,
la
restituisca
ricevendo in ingresso una lista al programma chiamante
con
gli
elementi che compaiono in ordine inverso rispetto all'ordine originario.
La cultura è un bene dell'umanità (
[email protected])
17 Inserzione ed eliminazione di elementi da una lista
TESTO
Scrivere
una procedura per l'inserzione e la eliminazione di
elemento
da una lista semplice rappresentata con record e punta-
tori.
La lista e' composta di elementi interi tutti diversi
loro,
ordinati
in
ordine crescente;
la procedura deve
un
tra
essere
richiamabile con una istruzione: inselim ( bl, v, p, b2 ) in cui: - bl e b2 siano di tipo booleano: il valore di bl sara' "true" se si richiede un inserimento, una
eliminazione;
sara' "false" se si richiede
in b2 la procedura restituisce il valore
"true" se, nel corso dell'esecuzione dell'operazione richiesta, individua una situazione di errore, "false" altrimenti; - p
sia
di tipo puntatore:
esso
rappresenta
il
puntatore
iniziale della lista; - v
sia di tipo intero:
esso rappresenta il valore che
deve
essere inserito o eliminato dalla lista. La procedura deve: - se bl vale "true", inserire un elemento con valore v, mantenendo
l'ordinamento e controllando che tale elemento non
La cultura è un bene dell'umanità (
[email protected])
esista
151
gia'
nella lista;
essere
effettuato,
nel caso che esista, ma
l'inserimento non
deve
deve essere se.gnalata una situazione
di
errore; - se
bl
vale " false",
controllando
eliminare l'elemento
che tale el e mento esista;
con
valore
v,
nel caso che non esista,
l'eliminazione non deve essere effettuata,
ma deve essere segna-
lata una situazione di errore .
SOLUZIONE
Considerando
le specifiche del problema,
possiamo assumere note
alla procedura le seguenti definizioni: punt elem
"elem; record info su cc end;
integer; punt
Per definire l'intestazione della procedura,
valgono le seguenti
considerazioni: - i
parametri formali corrispondenti a bl e v possono
essere
parametri valore; - il
parametro
formale corrispondente a •2
parametr• varia•ile, risultato
jeve
essere
un
p•iche' viene usato per trasmettere un
al programma chiamante (in particolare per segna-
lare una situazione di errore); - il
parametro
forma l e
parametro variabile, lista
corripondente a
p
deve
essere
un
poiche', a parte il caso di errore, la
deve essere modificata dalla procedura e la
La cultura è un bene dell'umanità (
[email protected])
modifica
152
puo'
riguardare
il primo elemento della
anche il suo puntatore iniziale.
lista,
e
quindi
Si noti che, se fosse noto
a priori che il primo elemento della lista non possa
subire
modifiche, si potrebbe utilizzare il passaggio per valore. Ne deriva la seguente prima versione della procedura:
procedure inselim( insert : boolean; val : integer; var piniz : punt; var errore : boo l ean ) ; (* CM: inserisce~-od elimina l'elemento val dalla lista ordinata piniz, a seconda del valore di insert; la procedura mantiene l'ordinamento della lista e segnala eventuali errori mediante il parametro errore *) begin errore := false; /1/ ricerca l'elemento val nella lista; if insert then if /2/ l'elemento val esiste nella lista then errore := true else /3/ inserisci val else ~/2/ l'elemento val esiste nella lista then /4/ elimina val else errore := true end; (* CM: fine procedura inselim *)
Per
la
prevede
frase /1/,
si utilizzera' una
ricerca
l'analisi degli elementi della lista,
esaustiva,
che
tenendo conto che
essi sono tutti distinti e memorizzati in ordine crescente.
Cio'
implica che la ricerca puo' avere termine o perche' si e' trovato l'elemento cercato o perche' si e' trovato un elemento di maggiore.
valore
Analizziamo, quindi, una prima alternativa per la tra -
duzione della frase /1/:
p := piniz; (* CM: p puntatore per la scansione *) while (p nil) and (pA.info < val) do p := pA.next ~elemento non trovato T* CA: p nil ---> elemento trovato *) p nil --->
La cultura è un bene dell'umanità (
[email protected])
153
Si puo' facilmente vedere che le istruzioni scritte contengono un errore:
se,
infatti, l'elemento non viene trovato, si raggiunge
la condizione p la
=
conseguenza
nil e si valuta il predicato di while;
cio' ha
di generare un errore in esecuzione causato
dal
tentativo di accedere, per la valutazione del termine: p".next < val ad
un
record puntato da un puntatore pari a
evidentemente,
non esiste.
nil,
record
che,
Si ricordi che non si puo', in gene-
rale, confidare sul fatto che il valore "false" per una sottocondizione inibisca la valutazione di eventuali altre sottocondizioni in and con essa. Dobbiamo,
percio' modificare le istruzioni presentate;
nel fare
questo,
terremo presente che la ricerca dell'elemento con valore
pari
"val" nella lista,
a
viene effettuata
per
un
eventuale
inserimento od eliminazione dello stesso. Poiche' entrambe queste operazioni necessitano di accedere al record che precedera' quello
da inserire (nel caso di inserimento) o al record che precede
quello
da
eliminare (nel caso di
eliminazione),
e'
opportuno
effettuare la ricerca: - avendo inserito inizialmente un record generatore all'inizio della lista; - fornendo
come risultato il puntatore al record che
precede
quello con valore "val", se esso esiste, oppure il puntatore al record che precede il primo record nella lista con valore maggiore di "val", ancora esistono
se tale valore maggiore
esiste,
il puntatore all'ultimo record della lista,
oppure se
elementi con valore maggiore o uguale a "val" .
La cultura è un bene dell'umanità (
[email protected])
non La
154
ricerca, insomma, deve tore
all'ultimo
restituire
come risultato il punta-
record della lista con
valore
minore
di
"val" (oppure al record generatore, che, nel seguito, verra' considerato
come
se
avesse
un valore
sempre
minore
di
"val"). Ne deriva la seguente traduzione della frase /1/:
(* CM: creazione del record generatore *) new(paux); pauxA.succ := piniz; piniz := paux; (* CA: piniz punta al record generatore *) (*CM: ricerca dell'elemento val nella lista *) p := piniz; trovato := false; while (pA.succ nil) and ( not trovato ~* CA: p punta al record precedente a quello che si deve analizzare *) if pA.succA.info < val then p := pA.succ else trovato := true; (* CA: trovato vale true se e solo se pA.succ nil e pA.succ A.info >=val *) (* CA: p punta all'ultimo record con valore minore di val *) if trovato then if pA.succA,info > val then trovato := false; ~A:-trovato vale true se-e-solo se esiste nella lista un record con valore val *)
Possiamo
ora presentare tutta la procedura poiche' la traduzione
delle frasi /2/, /3/ e /4/ non presenta alcuna difficolta':
procedure inselim( insert : boolean; val : integer; var piniz : punt; var errore : boolean ) ; (* CM: inserisce~-od elimina l'elemento val dalla lista ordinata piniz, a seconda del valore di insert; la procedura mantiene l'ordinamento della lista e segnala eventuali errori mediante il parametro errore *)
La cultura è un bene dell'umanità (
[email protected])
155
var trovato p, paux
boolean; punt; (*CD: usati per la ricerca dell'elemento *)
begin errore := false; (* CM: creazione del record generatore *) new(paux); pauxA.succ := piniz; piniz := paux; (* CA: piniz punta al record generatore *) (* CM: ricerca dell'elemento val nella lista *) p := piniz; trovato := false; while (pA.succ nil) and ( net trovato ~* CA: p punta al record precedente a quello che si deve analizzare *) if pA.succA.info =val *) (* CA: p punta all'ultimo record con valore minore di val *) if trovato then if pA.succA.info >val then trovato := false; ~A:-trovato vale true se-e-solo se esiste nella lista un record con valore val *) if insert then if trovato then errore := true else begin (* CM: inserimento dopo il record puntato da p *) new(paux); pauxA.info :=val; pauxA.succ := pA.succ; pA.succ := paux end else if trovato . then begin (* CM: eliminazione del record che segue quello puntato da p *) paux := pA.succ; pA.succ := pauxA.succ; dispose(paux) end else errore := true; ~ (*CM: si elimina il record generatore*) paux := piniz1 piniz := pinizA.succ; dispose(paux) end; (* CM: fine procedura inselim *)
. t
La cultura è un bene dell'umanità (
[email protected])
156
ESERCIZI PROPOSTI
1.
Scrivere una procedura ricorsiva per effettuare le operazioni richieste dalla frase /1/ della procedura procedura delle
"inselim''·
La
deve avere un comportamento equivalente a
quello
istruzioni scritte nella procedura suesposta;
quest'
ultime,
percio',
devono
essere sostituite dalla
chiamata
alla nuova procedura e i commenti asserzione presentati
nel
testo devono valere dopo tale chiamata. 2.
Si supponga di rappresentare un insieme di elementi mediante una
lista
semplice.
Scrivere un programma che
legga
due
insiemi e calcoli la loro unione e la loro intersezione. 3.
Scrivere lista
una
funzione che,
semplice,
ricevendo come
parametro
una
verifichi se essa rappresenta un insieme o
un multiinsieme.
La cultura è un bene dell'umanità (
[email protected])
Parte seconda Strutture di dati
La cultura è un bene dell'umanità (
[email protected])
La cultura è un bene dell'umanità (
[email protected])
18 Garbage collection
TESTO
Scrivere
una procedura che,
di memoria gestita a liste,
supposta esistente una zona lineare effettui su di essa l'operazione
di
garbage collection.
SOLUZIONE
Ricordiamo delle
l'operazione di garbage collection
(o
liste) ha lo scopo di raccogliere in una lista
libera)
tutti
utilizzati àati
che
recupero (la
lista
gli elementi di una zona di memoria che non
dalle liste presenti in tale zona.
La
struttura
iàenea a realizzare la zena lineare àa gestirsi a
costituita da un array di record,
con campi puntatore
sonq di
liste e' (intero),
marcatore e informazione. supporremo
che i puntatori di accesso alle varie liste che
"immerse" nella zena di memoria, realizzato
anch'esso
siano riuniti in un direttorio,
per mezzo di array e contenente
nome distintivo di ogni lista j
y-
La cultura è un bene dell'umanità (
[email protected])
sono
anche
un
DtRfi T/
, ___
I ___::-==I
r~~'.· r
!,.
160
I 1-
const
'- .-
dim = 1000; ( * CD: dimensione della zona di memoria *) maxliste = 10; (* CD: numero massimo di liste presenti nell'array "lineare" *) array [l .. 10] of char; indlce = l .. dim; (*CD: tipo indice per l'array *) punt = o .. dim; (*CD: puntatore per le zone di memoria*) base ... , (*CD: tipobase per il campo informazione*) elemento = record info: base; (* CD: campo informazione *) marca: boolean; (* CD: campo marcatore *) next: punt (* CD: campo puntatore *) end;
~nome=
var direttorio:
(* CD: direttorio per l'accesso alle liste *) array [l .. maxliste] of record nomelista: nome; paccesso: punt end; lineare: (* CD: zona lineare di memoria *) array [indice] of elemento; 11: integer; (* CD: puntatore iniziale della lista libera *)
Per quanto riguarda la sezione istruzioni, ricordiamo che l'algoritmo
di garbage collection prevede due
fasi~
sione delle liste attraverso i puntatori,
la prima di scan-
con marcatura di tutti
gli elementi a esse appartenenti; la seconda di scansione sequenziale
della zona di memoria,
con raccolta,
nella lista libera,
degli elementi che durante la prima fase non sono stati marcati e che, quindi, non appartengono ad alcuna delle liste. Si
assume che inizialmente il valore del campo "marca"
record sia "false". in
genere
anche
di
ogni
Poiche' l'algoritmo di garbage collection e'
eseguito ripetutamenete,
e' necessario far
si'
che
alla fine della esecuzione dell'algoritmo stesso il valore
del campo "marca" di ogni record sia "false",
affinche'
ritmo possa essere di nuovo applicato correttamente. di informazioni con il programma chiamante,
La cultura è un bene dell'umanità (
[email protected])
Lo
l'algoscambio
in questo caso, puo'
161
avvenire per mezzo di variabili globali,
e quindi l ' intestazione
della procedura non ha bisogno di contenere alcun parametro. Il testo della procedura,
con le opportune vari a bili locali e
i
commenti, e':
procedure garbage; (* CM : esegue l'operazione di garbage collection sull'array "lineare", variabile globale; nell ' arr ay sono presenti fino ad un numero massimo di liste pari a "maxliste", i cui puntatori iniziali si trovano ~ell'array "direttorio", anch'esso variabile globale *) var i p j
(* CD: indice per la scansione del direttorio *) punt; (* CD : puntatore per la scansione delle liste *) indice; (* CD: indice per la scansione sequenziale *) 1. .maxliste;
begin
(* CA: si assume che il valore del campo marca di ogni record sia false; se questo e' vero prima della chiamata alla procedura, e' vero anche alla fine della sua esecuzione *) (* CM: scansione delle liste attraverso i puntatori *) (* CM: scansione del direttorio *) for i := 1 to maxliste do (* CM: scansione della i-esima lista *) begin (* CM: inizializzazione *) p := direttorio[i).paccesso; while pO • do begin (* CM: marcatura di un elemento *) lineare[p].marca := true; (* CM: avanzamento del puntatore *) p := lineare[p).next end end; (* CM: scansione sequenziale della zona lineare e costruzione della lista libera *) 11 : =
o;
for j:= 1 to dim do (* CM:-esame del j-esimo elemento *) if lineare(j].marca then (* CA: l'elemento e' marcato *) (* CM: modifica del campo marca in modo che , alla fine della esecuzione della procedura, il campo marca di ogni record sia uguale a false *) lineare[j).marca :=false
La cultura è un bene dell'umanità (
[email protected])
162
else
begin lineare(j ]. next := 11; 11 := j end (* fine procedura garbage *)
end;
Si
(* CA: l'elemento non e' marcato *) (* CM: inserimento nella lista libera *)
noti come la creazione della lista libera avveng a molto
sem-
plicemente aggiungendo ogni volta in testa alla l i sta l 'eventuale nuovo
nodo da inserire:
cio' e ' l ec i to poiche' - l'ordine con c u i
si inseriscono i vari elementi non e' significativo.
ESERCIZI PROPOSTI 1.
La
procedura
"garbage" non effettua
verificare che nell'array "lineare" (cioe' lista
tali
controllo
Modificare la procedura affinche' l'operazione di garbage collection
presenza di liste cicliche.
La cultura è un bene dell'umanità (
[email protected])
per
esistano liste cicliche
che il puntatore finale punti a un nodo
stessa).
correttamente
alcun
della
effettui anche
in
19 Fusione di liste semplici
TESTO Si
suppongano
esistenti in memoria due liste ordinate (in
non decrescente) di interi; record e puntatori;
modo
la prima, A, realizzata per mezzo di
la seconda,
B,
realizzata per mezzo di
un
array. Nell'array usato per . realizzare la lista Be' presente una lista libera, una
procedura
l ' ordinamento,
di cui si conosce il puntatore iniziale. che
immerga gli elementi di A in
B
Scrivere
conservando
trasformando cosi' B in una nuova lista
ordinata
formata dagli elementi di A e quelli originari di B.
SOLUZIONE Le struttura di dati da utilizzarsi sono gia' descritte nel testo de l problema. In Pascal possono essere cosi' realizzate:
punt nodo
Anodo; (* CD: tipo puntatore per la lista A *) record val : integer; next : punt end; (* CD: record per gli elementi ~della lista A *)
La cultura è un bene dell'umanità (
[email protected])
164
(* CD: puntatore iniziale alla lista A *) ( * CD: array che realizzano la lista B *) array [l .. n] of integer; pb, (* CD: puntatore iniziale alla lista B *) 11 : integer; (* CD: puntatore iniziale alla lista libera *)
var
pa: punt; info, pun:
La realizzazione piu' semplice dell'operazione richiesta consiste nella scansione parallela delle due liste, elementi
di A in opportune posizioni in B.
con inserimento degli Tenuto
dissimmetria del problema rispetto alle due liste, scandire
la lista A elemento per elemento,
conto e'
della
opportuno
cercando di volta in
volta la posizione corretta nella lista B in cui inserirlo. ovviamente
la
dall'inizio
scansione
di B puo' ogni
volta
riprendere
ma dal punto in cui e' stata interrotta
non
nell'itera-
zione precedente. E'
opportuno utilizzare due puntatori,
delle due liste.
qa e qb per la scansione
Il puntatore qb e' usato in modo tale per
cui,
ogni volta che si individua un elemento della lista A da inserire nella
lista
puntato
B,
esso deve essere inserito dopo l'elemento di
da qb.
Il primo elemento di A va trattato a parte perche', nore
B
del
primo elemento di B,
se fosse mi-
andrebbe inserito in testa
alla
lista B, modificando cosi' il puntatore iniziale di B.
Presentiamo considerando
ora un raffinamento quasi completo della
procedura,
gli array "info" e "pun" che realizzano la lista
come variabili globali.
La cultura è un bene dell'umanità (
[email protected])
B
165
procedure merge ( pa: punt; var pb: integer ); (* CM: immerge gli elementi della lista A, ordinata per valori non decrescenti, nella lista B~ anch'essa ordinata; la lista A (di cui pa e' il puntatore iniziale) e' realizzata mediante records e puntatori; la lista B (di cui pb e' il puntatore iniziale) e' realizzata mediante gli array info e pun, variabili globali *) var
qb : integer;
(* CD: puntatore corrente per la scansione della lista B *)
begin
(* CM: esame
dei primi elementi ( si suppongano le due liste non vuote) e inizializzazione dei puntatori correnti *) if paA.val < info(pb] then begin /1/ inserimento del primo elemento di A in testa a B; pa := paA,next end; qb := pb; (* CM: ciclo di scansione di A, per il quale si utilizza pa, parametro valore *) while pa nil do begin /2/ Sposta il puntatore qb in modo che esso punti all'elemento di B dopo il quale deve essere effettuato l'inserimento dell'elemento corrente di A (cioe' quello puntato da pa); (* CA: l'elemento puntato da pa deve essere inserito subito dopo quello puntato da qb *) /3/ inserimento dell'elemento di A; (* CM: aggiornamento dei puntatori correnti *) pa := paA.next; qb := pun[qb] end end; (* CM: fine procedura merge *)
Proponiamoci ora di tradurre la frase /2/ in istruzioni Pascal; a tale scopo, bisogna spostare il puntatore qb fino a quando: 1. qb punta all'ultimo elemento della lista B, oppure 2. l'elemento
che
segue
quello
puntato da
qb
ha
un
valore
maggiore dell'elemento corrente di A. Useremo percio' un ciclo di
while,
controllato da una variabile
booleana "esci" (che, quindi, va aggiunta tra le variabili locali
La cultura è un bene dell'umanità (
[email protected])
166
della
procedura),
che verra' posta a "true" quando si
verifica
una delle due condizioni suddette.
esci := false; while not (esci) ~if pun[qb] = o then (* CA: qb punta all'ultimo elemento della lista *) ~~ esci:= true else if info[pun[qb]] > paA.val then (* CA: l'elemento che segue quello puntato da ~~ qb e' maggiore di quello puntato da pa, che va quindi inserito subito dopo quello puntato da qb *) esci:= true else qb := pun[qbJ;
Per quanto riguarda le frasi /1/ e /3/, operazione
di inserimento,
esse si riferiscono all'
che e' l'unica lasciata in
poiche' essa viene effettuata in due punti diversi, realizzarla tramite una procedura.
per
raccogliere
scegliamo di
L'inserimento avviene
vando un elemento dalla lista libera che, proprio
sospeso;
lo ricordiamo,
gli elementi dell'array che
non
prelesi usa sono
utilizzati da alcuna lista presente nell'array.
procedure insert (ppa: punt; var ppb: integer); (* CM: procedura che inserisce, prelevandolo dalla lista libera, un elemento nella lista B, facendo puntare ppb ad esso ed assegnandogli un valore pari a quello dell'elemento della lista A puntato da ppa *) var aux: integer; begin aux:=ppb; ppb:=ll; 11 : = pun [ 11 J ; info[ppb] := ppaA.val; pun[ppb]:= aux end; (* fine procedura insert *)
La cultura è un bene dell'umanità (
[email protected])
167
I
due blocchi /1/ e /3/ saranno tradotte rispettivamente in
due
istruzioni di chiamata della procedura 1nsert: insert (pa, pb) e
insert (pa, pun[qb]).
ESERCIZI PROPOSTI 1.
Nella
soluzione
controllare lista B,
che,
presentata non ci si pone il
problema
al momento di inserire un elemento
la lista libera contenga almeno un
di
nella
elemento.
Ri-
scrivere la procedura "merge" tenendo conto di .questa condizione; in particolare, si faccia in modo che, se la procedura
non
mancanza
puo' eseguire correttamente le sue di elementi nella lista libera,
evento al programma chiamante.
La cultura è un bene dell'umanità (
[email protected])
operazioni comunichi
per
questo
20 Realizzazione e gestione di pile e code
TESTO Descrivere
alcune possibili realizzazioni di una pila
e di
una
coda con le relative procedure di gestione.
SOLUZIONE Ricordiamo
che le operazioni fondamentali per la gestione di una
pila sono: - inizializzazione (INIT) - analisi dell'elemento affiorante (TOP) - test sulla presenza di elementi (EMPTY)
(test di "pila vuota")
- inserimento di un elemento (PUSH) - estrazione di un elemento (POP) La
differenza tra l'operazione TOP e l'operazione POP e' che
prima
permette di conoscere il valore dell'elemento
senza modificare la pila,
la
affiorante,
mentre la seconda estrae tale elemento
dalla pila. Se
e'
massimo
prevista
una dimensione massima per la
pila
(cioe'
un
per il numero di elementi in essa contenuti) e' necessa-
La cultura è un bene dell'umanità (
[email protected])
169
rio poter effettuare una ulteriore operazione: - test
sulla
inseribilita'
di elementi (FULL)
(test
di
"pila
piena").
Analogamente,
le
operazioni fondamentali per la gestione di una
coda sono: - inizializzazione (INIT) - analisi del primo elemento (FRONT) - test di "coda vuota" (EMPTY) - inserimento di un elemento (ENQUEUE) - .estrazione di un elemento (DEQUEUE) - test di "coda piena" (FULL)
Avendo che
previsto le funzioni di test,
le operazioni di inserimento,
supponiamo per semplicita'
estrazione e analisi
richiamate solo quando effettivamente eseguibili: esempio che
supporremo per
che la procedura pop sia richiamata avendo
la pila non sia vuota.
Di conseguenza,
vengano
la
certezza
all'interno di tali
procedure non sara' necessario effettuare verifiche di
eseguibi-
lita'. Analizziamo separatamente la soluzione per le pile e per le code.
Pile La
piu' semplice realizzazione per una pila e' quella che fa uso
di: 1)
un
array avente come tipo base il tipo degli elementi della
pila e come tipo indice il subrange degli interi
La cultura è un bene dell'umanità (
[email protected])
l •. n
con
170
n 2)
opportuna costante, dimensione
un
intero
(o
massima della pila;
opportuno subrange)
che
indica
l'elemento
affiorante. Strutturiamo tali dati in un record:
~
Cio'
pila= record i top: O.• n; elem: array [l .. n] of tipobase end;
ha il vantaggio di poter considerare le due componenti
tipo "pila" (l'array e la variabile intera che,
del
con il suo valo-
re, indica la posizione nell'array dell'elemento affiorante) come elementi di un'unica entita' logica. Si
noti
come il tipo di itop sia
o .. n,
in quanto il
valore
o
viene assunto quando la pila e' vuota. Abbiamo, inoltre, indicato con "tipobase", il tipo degli elementi della pila. Le
procedure e le funzioni per la realizzazione delle operazioni
di gestione della pila sono, in questo caso, le seguenti:
procedure init (var p: pila); begin p.itop := O end; (* fine procedura init *)
function top (p: pila) : tipobase; begin top := p.elem[p.itop] end; (* fine function top *)
La cultura è un bene dell'umanità (
[email protected])
!
' I
~
u
irear
----------->
La
gestione
della
coda sara' organizzata in modo tale che
condizione di coda vuota equivalga alla mentre
la
posizione circolare,
coda
sara' piena quando l'indice
precedente e
condizione
quindi
(considerando,
irear
ovviamente,
considerando che la posizione
i front
la O;
punta
alla
l'array
come
n-esima
e'
quella che precede la prima posizione dell'array) a quella puntata da ifront.
Le procedure relative a questa realizzazione della
coda sono le seguenti:
procedure init (var c: coda); begin c.ifront := O; (* CA: la coda e' vuota *) c.irear := O end; (* procedura init *)
function front (c: coda): tipobase; begin front := c.elem (c.ifront] end; (* fine function front *)
function empty (c: coda): boolean; begin empty := (c.ifront = O) end; (* fine function empty *)
La cultura è un bene dell'umanità (
[email protected])
176
procedure enqueue (var c: coda; el: tipobase); begin c.irear := (c.irear mod n) + l; ~: Q ?·, vf' ( c.elem[c.irear] := er;-if c.ifront = O then (* CA: prima dell'inserimento di el la coda era vuota *) ~~ c.ifront := 1 end; (* fine procedura enqueue *)
procedure dequeue (var c: coda; var el: tipobase); begin -I el := c.elem [c.ifront]; ' o~\ ,~ if c.ifront = c.irear then (* CA: dopo la attuale eliminazione, la coda e' vuota *) ~~ begin c.ifront := O; c.irear := O end else c.ifront := (c.ifront mod n) + 1 end-;---(* fine procedura dequeue--;i;"f
function full (c: coda) : boolean; begin full := (c.ifront = (c.irear mod n) + 1) end; (* fine function full *)
Una
realizzazione
analoga
delle
code per mezzo di
a quella presentata per le pile,
sono necessari,
o meglio utili,
a parte il
Le dichiarazioni di tipo sono in questo caso:
punt elem
coda
"elem; record val: tipobase; succ: punt end; record pfront, prear: punt end;
La cultura è un bene dell'umanità (
[email protected])
semplici fatto
e' che
due puntatori, uno all'inizio e
l'altro alla fine della lista.
~
liste
177
Le relative procedure e funzioni, sono:
procedure init (var c: coda); var aux: punt; - begin (* CM: rilascio di tutti gli elementi eventualmente presenti nella coda *) while c.pfront nil do begin aux := c.pfront; c.pfront := c.pfrontA.succ; dispose(aux) end; c.prear := nil (* CA: c.pfront = c.prear=nil; la coda e' vuota *) end; (* fine procedura init *)
1/
function front (c: coda): tipobase; begin front := c.pfrontA.val end; (* fine function front *)
function empty (c:coda): boolean; begin empty := (c.pfront = nil) end; (* fine function empty *)
procedure engueue (var c: coda; el: tipobase); var aux: punt; begin if c.prear = nil then begin . - lf new (c.prear) ; c.pfront := c.prear end else begin 1f'( new(c.prearA.succ); c.prear := c.prearA.succ end; c.prearA.val := el c.prearA.succ := nil end; (* fine procedure enqueue *)
La cultura è un bene dell'umanità (
[email protected])
178
procedure dequeue (var c: coda; var el: tipobase); var aux: punt; begin el := c.pfrontA.val; aux := c.pfront; c.pfront := c.pfrontA.succ; if c.pfront = nil then (* CA: la coda e' vuota *) c.prear := nil; dispose (aux) ~end; (* fine procedura dequeue *)
Come
esempio di esecuzione delle procedure viste,
l'applicazione
della
si
procedura "enqueue" nel caso di
consideri coqa
non
vuota (in questo e nei successivi esempi i puntatori tratteggiati si
riferiscono alla situazione che si viene a creare dopo
l'ap-
plicazione dell'operazione):
c.pfront
c.prear / /
------ - - - -....
\ I
'
t
-------~~~n~il' La
stessa
procedura,
nel caso di coda vuota,
effetto:
c.pfront
~i:'ttii:r---
c.prear
-----\ (-----------J:ftii:[ I
I
I I
I 'I
''
nil
La cultura è un bene dell'umanità (
[email protected])
ha
il
seguente
179
La procedura "dequeue", invece, applicata ad una coda con un solo elemento,
ha l'effetto di assegnare sia a c.pfront che a c.prear
il valor nil. Infine, nel caso di coda con piu' di un elemento, si ha:
4J c.pfront I', __ ----- --,
c.prear
ì I I
I
I
' /
/
nil
'
ESERCIZI PROPOSTI
1.
Modificare supponendo
le in
procedure generale
per la gestione di non
piu'
valida
pile
e
code
l'ipotesi
di
consideri il problema di rappresentare diverse code
me-
eseguibilita' delle operazi?ni. 2.
si
diante Definire
una lista rappresentata a sua volta mediante
array.
i tipi di dati necessari a tale rappresentazione e
le relative procedure e funzioni di gestione.
La cultura è un bene dell'umanità (
[email protected])
21 Visita di una lista doppia
TESTO Scrivere pia
una procedura che effettui la visita di una lista
stampando i valori di tutti i suoi elementi (che si
dop-
suppon-
gono interi) in ordine qualunque.
Esempio Ingresso alla procedura:
6
nil
nil
nil
Uscita:
1 5 3 2 6 4
SOLUZIONE Ricordiamo che una lista doppia e' definita come una lista i
La cultura è un bene dell'umanità (
[email protected])
cui
181
elementi
sono formati dal campo informazione e da due puntatori,
che o contengono il valore di "fine lista",
o puntano ad altret-
tanti elementi della lista. Come
nel caso delle liste semplici,
lista
anche per la visita di
doppia e' possibile pensare sia a una soluzione
una
iterativa
~a~a.
In entrambi i casi, la procedura deve di volta in volta esaminare un
nodo,
stampando
il valore del campo informazione,
per
poi
proseguire la visita seguendo uno dei due puntatori. Non essendosi
fatte ipotesi di alcun genere sulla lista,
nel "corso
della
precedenza. si
gia'
che
visitato
in
La maniera piu' semplice per evitare che in tal caso
visiti~o
campo
visita si incontri un nodo
e' possibile
te lo stesso nodo e' quella
di
prevedere
un
di marcatura in ognuno degli elementi che costituiscono la
lista.
La
definizione dei tipi necessari per
la
realizzazione
della lista doppia e' la seguente.
punt elem
"elem; record info: integer; marca: boolean; pl,p2: punt end;
L'intestazione
della procedura conterra' un solo
puntatore iniziale della lista che
~ue'
parametro,
il
senz'altro essere di tipo
valore. Passando ricorsiva
alla sezione istruzioni, e poi quella iterativa.
La cultura è un bene dell'umanità (
[email protected])
presentiamo prima la versione Per quanto riguarda il
campo
182
marcatore,
esso sara' utilizzato in modo tale che, il suo valore
sara' "true" se e solo se il nodo corrispondente e' gia' stato analizzato durante la visita. inizio
Per semplicita' supponiamo che all'
i campi marcatore siano tutti a "false" e possano
essere
lasciati a "true" dalla procedura di visita. La
versione
ricorsiva della procedura e' molto
semplice:
accedere al nodo iniziale della lista (se esso esiste, la
deve
cioe'
se
lista non e' vuota) e se esso non e' marcato (cioe' il valore
del corrispondente campo marcatore e' "false"),
marcarlo
(cioe'
porre il campo marcatore a "true"), stampare l'informazione relativa e visitare con lo stesso metodo le list e doppie i cui puntatori iniziali si trovano nei campi pl e p2 del record acceduto .
procedure visita (p: punt); (* CM: visita tutti gli elementi di una lista doppia; p rappresenta il puntatore iniziale della lista; si assume che il campo "marca" di ogni nodo sia inizialmente a false *) begin p nil if then if not("pA.marca) then begin p A,marca := true; write (pA,info); (* CM: visita la lista doppia i l cui puntatore iniziale si trova in p A,pl *) visita (p A.pl); (* CM: visita la lista doppia i l cui puntatore iniziale si trova in p " .p2 *) visita (p" .p2) end end; (* fine procedura visita *)
Nella
versione iterativa e' necessario,
secondo un puntatore
ogniqualvolta si avanzi
tralasciandone un altro ancora da visitare,
memorizzare quest'ultimo per poi riconsiderarlo nel seguito.
La cultura è un bene dell'umanità (
[email protected])
183
Una possibile struttura di dati per questa memorizzazione di salvataggio e' la pila.
Supponiamo capacita'
quindi
che sia stata definita una
pila
"pilal"
di
sufficiente (in modo che non sia mai necessario effet-
tuare il test di "pila piena"),
con le relative procedure
push,
pop, init e la funzione empty, come descritte nel problema 20. A
questo punto e' possibile scrivere la versione iterativa della
procedura di visita:
procedure visita (p: punt); (* CM: visita tutti gli elementi di una lista doppia; p e' il puntatore al record da cui bisogna iniziare la visita. Essendo parametro valore, viene usato come puntatore corrente per la visita *) begin (* CM: inizializzazione della pila *) init(pilal); while p nil do if not (pA.marca) then begin pA.marca := truej write (pA.infe); i f pA .p2 nil then (* CM: memorizzazione nella pila del puntatore -che non viene attualmente seguito *) push (pilal,pA.p2); if pA .pl nil then p := pA.pl else (* CA: non si puo' proseguire la visita seguendo il puntatore pA.pl *) if not ( empty(pilal) then pop(pilal,p) else (* CA: la visita e' conclusa *) p := nil end else -e* CA: non si deve proseguire la visita *) if not empty(pilal) then pop(pilal,p) else (* CA: la visita e' conclusa *) - - p := nil end; (* fine procedura visita *)
La cultura è un bene dell'umanità (
[email protected])
184
In questa versione vengono inseriti nella pila solo puntatori non nulli.
Percio', ogni estrazione dalla pila restituisce il punta-
tare a un record esistente nella lista.
In alternativa, e' possibile inserire nella pila tutti i puntatori tralasciati,
anche quelli pari a nil,
rimandando l'esame
al
momento della loro utilizzazione, come nella versione seguente.
procedure visita (p: punt); (* CM: visita tutti gli elementi di una lista doppia; p e' il puntatore al record da cui bisogna iniziare la visita. Essendo parametro valore, viene usato come puntatore corrente per la visita *) begin (* CM: inizializzazione della pila *) init(pilal); (* CM: ciclo di visita: termina quando, contemporaneamente, e' nullo il puntatore corrente ed e' vuota la pila; ad ogni iterazione si effettua una sola delle seguenti operazioni: (1) eventuale visita di un nodo dopo il test sulla marcatura (2) estrazione di un elemento della pila *) while ( p nil) or (net (empty(pilal)) ~* CM: test sul puntatore corrente *) if p nil then (* CA: e' possibile tentare la visita di un nodo *) (* CM: test sulla marcatura *) if not ( pA.marca ) the~ (* CA: il nodo non e' marcato *) (* CM: visita del nodo e avanzamento *) begin stampa (* CM: marcatura del nodo e dell'informazione *) pA. marca := true; write (pA.info); nella pila (* CM: inserimento e avanzamento del puntatore corrente *) push (pilal,pA.p2); p := p" . pl end
La cultura è un bene dell'umanità (
[email protected])
185
(* CA: il nodo e' marcato e quindi non va visitato *) (* CM: p viene posto a nil in modo che all'iterazione successiva si effettui l'estrazione di un elemento dalla pila *) p := nil else (* CA: p e..---nullo e la pila nen e' vuota *) pop (pilal,p) end; (* fine procedura visita *) else
Tutte tura
le soluzioni presentate necessitano di un campo di associato a ogni nod6 della lista.
non essere realizzabile, essere In
potrebbe
in quanto la struttura di dati potrebbe
stata definita in precedenza senza prevedere tale
questo caso,
potrebbe agli
Quest'ipotesi
marca-
campo.
il problema dell'eventuale presenza di cicli si
risolvere memorizzando in una lista tutti
i
puntatori
elementi gia' visitati e scandendo sequenzialmente la lista
ogniqualvolta sia necessario verificare se un nodo e' gia' visitato.
E' evidente come,
c•n
~esta
stato
seluziene, aumenti nete-
velmente la cemplessita' •i temp• •ella prece•ura.
ESERCIZI PROPOSTI
1.
Scrivere
la
procedura
di
visita
di
una
lista
doppia
nell'ipotesi di nen peter •isperre •ei campi di marcatura. 4.
Una
miglior procedura di visita ••vre»»e lasciare il
•i marcatura •i peter
ese~uire
•~ni
campo
recerà •ella lista in une state tale àa
con successo una successiva visita (in prati-
ca, tutti con lo stesso valore). Si pensi alla soluzione di questo problema.
La cultura è un bene dell'umanità (
[email protected])
)(. Visita di un albero binario
TESTO Scrivere due procedure rispettivamente per: - la visita in fpreordine 7\ I~
- la visita 'simmetrica
"'F-==
---
di un albero 1binario.
l
'--------.\
SOLUZIONE Ricordiamo
che
un albero binario e' definito come un albero
in
cui ogni nodo ha al massimo due figli. Una definizione alternativa, che rispecchia fedelmente la struttura ricorsiva di un albero !2..i11~rio
---------
e' la seguente:
DEFINIZIONE: Albero binario e' un insieme finito di nodi che o e'
vuoto,
oppure
alberi
consiste
di
un nodo detto radice e da
due
binari disgiunti detti rispettivamente sottoalbero e sottoalbero destro.
La cultura è un bene dell'umanità (
[email protected])
sinistro
187
Nella
figura seguente viene mostrata la rappresentazione g r afica
di un albero binario etichettato nei nodi con valori interi .
5
-~
-- 7
.---&--- 3
Il
testo del problema non specifica in quale modo si debba
presentare l'albero binario.
rap-
Nel seguito analizzeremo due possi-
bili sue rappresentazioni in Pascal. Per
ognuna di tali rappresentazioni scriveremo poi una delle due
procedure richieste. La prima rappresentazione che prendiamo in considerazione prevede
~ l'uso
di un vettore.fl Prima di parlarne in dettaglio, introduciamo
alcune definizioni e alcune proprieta' degli alberi binari che ci saranno
utili.
Il
lettore e' invitato a considerare
quali
di
queste definizioni si applicano anche ad alberi non binari. Chiameremo
livello
di
distanza dalla radice,
un nodo di un
albero
binario,
la
sua
cioe' il numero di archi di cui e' campo-
sto il cammino dalla radice al nodo.
, JtJ,) fu_,~ '\rJ;~ ~ ~~.
Nella seguente figura e' mostrato un albero binario con i relativi livelli dei suoi nodi.
La cultura è un bene dell'umanità (
[email protected])
188
5
•••••••••••• LIVELLO O
21 12
7
•••••••••••• LIVELLO 1
4
•••••••••••• LIVELLO 2
9
La profonditar di un albero binario e' il massimo livello a cui i nodi
dell'albero giungono.
profondita' zione
e' 2.
Nel caso dell'albero in
figura,
la
Nel seguito ci sara' utile conoscere la rela-
che esiste tra la profondita' di un albero ed
il
massimo
numero dei suoi nodi. Mostriamo,
dapprima,
che
il massimo numero di nodi a livello i i (i>=O) di un albero binario e' 2 ; dimostreremo questa proprieta'
per induzione. Innanzitutto
e'
facile verificare che la proprieta'
vale
i=O. Infatti, il massimo numero di nodi a livello o e' 2 Dobbiamo ora dimostrare che,
per
o = 1.
per ogni i, se il numero massimo di
i
nodi
a
livello i e' 2 allora il numero massimo di nodi a i+l livello i+l e' 2 cio' puo' essere facilmente provato esser-
vando dei
che a livello (i+l) ci possono essere al massimo il doppio nodi presenti a livello i,
poiche' ogni nodo di
un
albero
binario puo' avere al massimo due figli. Percio', a livello i+l i i+l ci potranno essere al massimo 2 *2 = 2 nodi, cio' che volevamo dimostrare. Sfruttando numero
questa proprieta',
e' facile mostrare che il massimo
complessivo di nodi in un albero binario di profondita' k
~·:
k+l
i 2
La cultura è un bene dell'umanità (
[email protected])
2
- 1
189
Infatti
esso equivale alla somma del massimo numero di nodi
che
possono esistere nei livelli da O a K. Diremo che un albero binario e' completo se
ha il massimo numero
di nodi possibile in funzione della sua profondita•,
cioe' se in i
ogni
livello i occupato dai suoi nodi,
si trovano
albero binario completo di profondita' k, k+l di nodi pari a 2 - 1.
ha,
2
nodi;
un
quindi, un numero
Un
albero binario completo puo' essere rappresentato facilmente ( ,, ( k+l mediante un vettore di dimensioni n = 2 secondo il se- ~JJ - 1, guente metodo: )>{la radice e' rappresentata in prima posizione . .2('se
un nodo e' rappresentato in posizione i,
sinistro, se esiste, e' in posizione se esiste, in posizione Come esempio,
allora il
figlio
2*i, ed il figlio destro,
2*i + 1.
si consideri il seguente albero binario completo e
la corrispondente rappresentazione mediante vettore:
41
1 2
8 2
3
5
4
41
5 6 7
18 25 16
~ l ~yla ~ ~~
3: L-d
\-~L,~~
Figura 1
Si
puo' osservare che,
mentre tale tipo di rappresentazione
e'
accettabile per alberi binari completi, e' inefficiente dal punto di
vista
dello spazio di memoria per alberi
La cultura è un bene dell'umanità (
[email protected])
non
completi.
In
190
piu', la rappresentazione presenta i tipici svantaggi .di una rappresentazione sequenziale. Assumiamo,
comunque,
che
si abbia un albero
binario
completo
rappresentato mediante vettore; si vuole scrivere la procedura di visita in preordine. La
visita
in preordine di un albero binario puo'
essere
cosi'
formulata:
VISITA IN PREORDINE DI UN ALBERO BINARIO: Se l'albero non e' vuoto (cioe' se ha almeno un nodo)
allora
visita
stesso
la
radice e poi visita in preordine,
con lo
metodo, il sottoalbero sinistro ed il sottoalbero destro.
Traduciamo questo algoritmo in una procedura di visita supponendo che suoi
si
voglia visitare l'albero per stampare le
nodi
e che l'albero binario sia completo
etichette e
dei
rappresentato
mediante vettore. si assuma, in particolare, che nel programma chiamante compaia la seguente definizione:
const
n
•••I
(*CD: numero massimo di nodi dell'albero binario; se k e' la profondita' dell'albero, n vale (2 elevato a k + 1) -
tipoalb
1 *)
array [l .. n] of integer;
La procedura e' :
La cultura è un bene dell'umanità (
[email protected])
191
procedure preord (alb: tipoalb); (* CM: visita in preordine un albero binario, stampando le etichette dei nodi; l'albero e' rappresentato mediante array, e' completo ed ha un numero di nodi pari a n *) procedure preordl (h: integer); (* CM: visita in preordine l'albero binario la cui radice si trova in posizione h nell'array alb *) begin if h end; (* fine procedura preord *)
Si
noti che la procedura vera e propria di visita e' stata inse-
rita
in un'altra che ha il compito di assegnare il
ziale
al
parametro
che rappresenta la posizione
valore nel
ini-
vettore
della radice dell'albero da visitare. Il
test iniziale serve a terminare le chiamate ricorsive
e
ri-
flette
il fatto che se la procedura e' chiamata con un valore di
h > n,
allora il sottoalbero che si aveva intenzione di visitare
se k e' la profondita' dell'albero, alla k+l costante n sara' stato assegnato il valore 2 - l; se, quindi,
e'
vuoto.
il
parametro
Infatti,
h e' maggiore di tale valore,
la visita non
deve
essere eseguita. Le
due chiamate ricorsive servono per la visita del
sinistro e destro:
si ricordi che,
La cultura è un bene dell'umanità (
[email protected])
sottoalbero
dato un certo nodo in
posi-
192
zione
h
nel vettore,
la radice del sottoalbero s i ni stro e '
in
posizione 2*h (a meno che 2*h superi n, nel qual cas o il sotto a lbero
sinistro non esiste),
quella del sot toalbero de stro e'
in
posizione 2*h+l (se tale valore non supera n) . La seconda rappresentazione che sentare
consideriamo prev ede d i
l'albero binario mediante records e puntatori :
rapp r e ad
o gni
nodo dell'albero corrispondente un record con tre c a mpi ; il campo destinato uno
al
alla etichetta del nodo stesso e due c amp i record
rappresentante il figlio
record rappresentante il figlio destro.
sinistro,
p untat ori , l'altro
al
A tutta la struttura
si
accede mediante il puntatore a lla radice dell'alber o . Con
tale rappresentazione possiamo ovviamente rilasci a re i l v i n-
colo che l'albero binario sia completo: una
efficiente
essa ha il v antaggio
occupazione di memoria e di
permett ere
di
agevoli
operazioni di modifica della struttura dell'albero. Scriveremo,
per
tale rappresentazione,
la procedura di
v isit a
simmetrica. Essa e' specificata dal seguente algoritmo :
VISITA SIMMETRICA DI UN ALBERO BINARIO: Se
l'albero non e' vuoto,
sottoalbero
sinistro,
esegui la visita
simmet ri ca
visita la radice ed esegu i la
d el
v i si t a
simmetrica del sottoalbero destro.
Si puo' osservare che la visita simmetrica non e' att uabile su un albero che non sia binario. Come
esempio,
si consideri la visita simmetrica dell'albero
in
figura 1, eseguito, supponiamo, per la stampa delle etichet te d e i
La cultura è un bene dell'umanità (
[email protected])
193
dY suoi nodi. Il risultato sarebbe la seguente sequenza di valori: 41
2
18
25
8
5
16.
Scriv iamo ora la procedura, supponendo che nell'ambito di visibilita' d i essa siano presenti le seguenti definizioni:
punt= " nodobin; nodobin= record info: tipoet; sin, des: punt end;
La procedura e' :
procedure sirnrnet (alb: punt); ( * CM: visita simmetrica di un albero binario rappresentato con records e puntatori; alb rappresenta il puntatore alla radice *) begin if a l b nil then lte!i n-s irnrnet (allt".sin); write (allt".info); sirnrnet (allt".des) emi end; (* fine procedura sirnrnet *)
f
Se in uscita si volesse ottenere un
\ volesse
s.tamp a-deJ..L!..alb~ro_da
risalire alla struttura dell'albero stesso,
cui si
si dovrebbe
r considerare il problema di ottenere una rappresentazione parente1\ tica de l l'a l bero: \ A tale scopo, scriv ono
le regole grammaticali che
u n a adeguata rappresentazione parentetica
di un albero binario sono:
La cultura è un bene dell'umanità (
[email protected])
de-
"simmetrica"
194
::=/ "(" ")" ::= "( )" .. - ::=
Per ottenere tale stampa dalla procedura "simmet", basta inserire prima istruzione la stampa del simbolo "("f
come
e come ultima,
la stampa del simbolo")". Secondo
tale rappresentazione,
all'albero binario di
figura
1
corrisponderebbe: (
(
(
()41()
)
2
(
()18()
)
)
8
(
(
()25()
)
5
(
()16()
)
)
)
ESERCIZI PROPOSTI 1.
Si
pensi
vettore
a di
adeguata
come modificare la
rappresentazione
un albero binario completo affinche'
a rappresentare anche alberi binari non
mediante essa
sia
completi.
Per tale rappresentazione si scriva poi una procedura per la visita in postordine dell'albero binario. 2.
Si
dice albero binario di ricerca,
supponiamo
etichettato
nei
nodi con
soddisfa la seguente proprieta•: ro,
un albero binario valori
interi)
(che che
per ogni nodo x dell'albe-
tutte le etichette presenti nel sottoalbero sinistro di
x sono minori dell'etichetta del nodo (~ e tutte le etichet-
La cultura è un bene dell'umanità (
[email protected])
195
te
presenti nel sottoalbero destro di x sone ma4Jqisri
l'etichetta del nodo x. valore
intero,
binaria, presente,
Scrivere una funzione che,
noto un
cerchi tale valore in un albero di
ricerca
restituendo oppu:r:e
àel-
il valore nil se tale valore
non
il puntatore al record che contiene
valore, se esso esiste.
La cultura è un bene dell'umanità (
[email protected])
e' tale
~a di un albero in preordine
TESTO scrivere
una procedura per la visita in preordine di un
albero. ~
Si assuma che l'albero sia gia' in memoria, rappresentato mediante lista doppia e che la visita venga effettuata per stampare
la
rappresentazione parentetica dell'albero.
SOLUZIONE Ricordiamo che la visita in preordine (o in ordina anticipato) di un albero (che, nel seguito, assumiamo non vuoto) e' un algoritmo che
permette
di
raggiungere tutti i nodi
dell'albero
in
una
sequenza prestabilita; l'algoritmo puo' essere cosi' formulato:
ALGORITMO DI VISITA IN PREORDINE DI UN ALBERO: 1. Visita la radice 2. Visita in preordine,
con lo stesso metodo,
tutti i
sottoalberi
La
formulazione dell'algoritmo e' ricorsiva e ricalca fedelmente
La cultura è un bene dell'umanità (
[email protected])
197
la struttura tipicamente ricorsiva di un albero.
Come es e mpio si
consideri l'albero rappresentato graficamente nel seguente modo:
D
E
Applicando l'algoritmo precedentemente descritto , e' facile v erificare che i nodi sono visitati nel seguente ordine:
A
Il
problema
B
E
F
C
G
D
richiede una procedura per la visita
in
preordine
assumendo l'albero rappresentato mediante lista doppia . Tale
rappresentazione
prevede
che a ogni
nodo
corrisponda un elemento della lista da cui, una
nuova lista,
nodo N sia una foglia). iista
dell'albero
a sua volta,
formata da tanti elementi quanti sono i
del nodo N (tale lista sara',
detta
N
degli
percio',
inizia figli
vuota nel caso in cui il
Ciascun elemento •i
~esta
archi o lista dei successori)
lista (che e' conterra'
un
puntatore all'elemento rappresentante uno dei figli del nodo N. La
rappresentazione
grafica della lista
all'albero dell'esempio precedente e':
La cultura è un bene dell'umanità (
[email protected])
doppia
corrispondente
198
,,.. lista degli archi che partono dal nodo A - /
E'
facile
'\
verificare che si hanno tanti
elementi
della
lista
doppia quanti sono i nodi e gli archi dell'albero. Da
ogni elemento che rappresenta un nodo dell'albero,
lista
di
elementi corrispondente agli archi
nodo;
da
ogni
partenti
elemento che rappresenta un arco,
cui tale arco e' diretto.
da
parte poi
puntatore verso l'elemento che rappresenta la radice a
parte una quel un
dell'albero
Sia le etichette dei nodi che degli
archi dell'albero possono essere rappresentate mediante opportuni campi associati agli elementi della lista. Per risolvere il nostro problema si deve stabilire la tazione
della
lista
doppia in termini «ei tipi
rappresen-
primitivi
«el
Pascal e formulare la procedura di visita secondo tale rappresentazione. Scegliamo di rappresentare la lista doppia per mezzo di records e puntatori:
ogni elemento della lista doppia sara'
per
di un record collegato agli altri mediante
mezzo
rappresentato puntatori
contenuti in opportuni campi del record stesso. Analizzando
la struttura degli elementi della lista
La cultura è un bene dell'umanità (
[email protected])
doppia,
si
199
~u•'
n•t•re
dell'albero
che !li elementi destinati a rappresentare sono formati da due campi,
i
nodi
uno per l'etichetta
del
nodo e l'altro per il puntatore di inizio lista degli archi;
gli
elementi che rappresentano archi,
sono composti anch'essi da due
campi (nell'ipotesi che l'albero non sia etichettato anche archi), il
negli
uno per il puntatore diretto all'elemento rappresentante
nodo verso cui l'arco e' orientato e l'altro per il puntatore
diretto al successivo arco nella lista degli archi. Ci
sono
almeno
tre
alternative
per
struttura in Pascal (ci si riferira', etichettati
rappresentare
una
tale
nel seguito, ad alberi non
negli archi e si indichera' con
"tipoetichetta"
il
tipo delle etichette dei nodi). a)
Si definisce un solo tipo record, per allo
le
formato da tre campi,
etichette dei nodi e due per
stesso tipo record.
altrettanti
La corrispondente
uno
puntatori
definizione
di
variante:
un
tipi sara':
punt= "elem; elem= record info: tipoetichetta; nextarco, figlio: punt end;
b)
Si definisce un solo tipo record con struttura campo
puntatore
sara' comune a tutti i records,
altro
campo puntatore sara' in alternativa con un campo
le etichette dei nodi:
La cultura è un bene dell'umanità (
[email protected])
mentre
un per
200
punt= "elern; elern= record nextarco: punt; case tipoelern: (arco,nodo) of arco: (figlio: punt); ~ nodo: (info: tipoetichetta)
c)
Si definiscono due tipi di record,
uno per rappresentare
i
nodi dell'albero, e l'altro per rappresentare gli archi:
puntarco= "arco; puntnodo= "nodo; arco= record figlio: puntnodo; nextarco: puntarco end; nodo= record info: tipoetichetta; nextarco: puntarco end;
Affrontiamo
dapprima il problema della visita assumendo l'albero
rappresentato mediante la rappresentazione a). Una procedura ricorsiva che realizza la visita in preordine di un albero cosi' rappresentato e':
procedure preord (p: punt); (* CM: visita un albero in preordine; l'albero e' rappresentato mediante lista doppia; p rappresenta il puntatore alla radice *) begin /1/ visita l'elemento puntato da p, rappresentante la radice dell'albero; (* CM: scansione della lista degli archi; per la scansione si utilizza il parametro valore p *) p := p".nextarco;
La cultura è un bene dell'umanità (
[email protected])
201
while p nil do begin -( * CM: visita il successivo sottoalbero *) preord (pA.figlio); (* CM: avanza nella lista degli archi *) p := pA.nextarco end end; (~ine procedura preord *)
Si puo' notare come la procedura "preord" corrisponda
fedelmente
all'algoritmo di visita presentato all'inizio: mentre, pero', tale
algoritmo era formulato sulla struttura astratta
albero,
la
procedura e' stata scritta in termine della rappresentazione dell'albero mediante lista doppia. Il
punto centrale e' stato quello di tradurre i termini corretti
la chiamata ricorsiva per la visita dei sottoalberi. mento
che
si e' seguito e' il seguente:
poiche'
Il ragionala
procedura
"preord" prevede che il parametro attuale sia il puntatore all'elemento che rappresenta la radice dell'albero che si vuole tare,
per
visitare tutti i suoi sottoalberi
visi-
essa dovra' essere
chiamata ricorsivamente tante volte quanti sono tali sottoalberi, e ogni volta con parametro attuale pari al puntatore all'elemento che rappresenta la radice del sottoalbero. Poiche' tali puntatori si trovano nel campo "figlio" dei che
formano
la lista degli archi che partono dalla
records
radice,
si
dovra' scandire tale lista e chiamare ricorsivamente la procedura passando,
come parametro attuale,
dei records che la compongono.
il valore del campo
"figlio"
Si noti che per tale scansione si
e' potuto usare il parametro p, poiche' essendo esso stato passato
per
valore,
il suo uso all'interno della procedura
La cultura è un bene dell'umanità (
[email protected])
non
ha
20 2
alcun effetto sul parametro attuale (cioe' sulla variabile che si e'
passato nella chiamata della procedura "preord")
cosi'
assicurando
che il puntatore alla radice dell'albero non viene modifi-
cato dalla visita dell'albero stesso. Per terminare la soluzione del nostro problema,
dobbiamo modifi-
care opportunamente la procedura "preord" (scritta,
genericamen-
te,
stampata
per
la
visita in preordine) affinche'
venga
la
rappresentazione parentetica dell'albero. Tale rappresentazione, per un albero non vuoto, e' descritta formalmente dalle seguenti regole sintattiche:
::="("
")Il
::=
Un albero e' percio' rappresentato da: - il simbolo "(" - l'etichetta della radice tutti
i suoi sottoalberi (descritti con la stessa rappresenta-
azione) - il simbolo")".
Considerando chiamata,
che la procedura "preord",
esegue la visita di un albero,
ogni volta
che
viene
sia esso l'albero com-
pleto o i suoi sottoalberi, bastera' modificare la procedura: 1.
aggiungendo,
come
prima istruzione,
stampa del simbolo''(" e, stampa del simbolo")"
La cultura è un bene dell'umanità (
[email protected])
un'istruzione per
la
come ultima, un'istruzione per la
203
2.
traducendo la frase /1/ in un'istruzione per la stampa dell' etichetta della radice.
La versione finale e', quindi:
procedure stampalb - (p: punt); (* CM: visita in preordine di un albero per la stampa della sua rappresentazione parentetica; p e' il puntatore alla radice dell'albero *) begin write ('( ', pA.info); p := pA.nextarco; while p nil do begin -stampalb (pA.figlio); p := pA.nextarco end; write (' ) ') end; (* fine procedura stampalb *)
E'
immediato verificare che la procedura "stampalb" e'
anche
assumendo l'albero rappresentato mediante la
zione b);
infatti,
corretta
rappresenta-
la differente struttura dei records che rap-
presentano i nodi e di quelli che rappresentano gli archi, non ha alcuna influenza sulle istruzioni della procedura stessa. Riguardo, essere
invece,
modificata,
alla rappresentazione c),
la procedura
deve
tenendo conto che il tipo record per la rap-
presentazione degli archi e' differente da quello per la
rappre-
sentazione dei nodi e che, quindi, si dovra' utilizzare un puntatore di tipo opportuno per la scansione della lista degli archi. Ne segue la procedura "stampalbl":
La cultura è un bene dell'umanità (
[email protected])
204
procedure stampalbl (p: puntnodo); (* CM: visita in preordine di un albero per la stampa della sua rappresentazione parentetica; l'albero e' rappresentato mediante lista doppia, realizzata a sua volta con due tipi di records *) var
pa: puntarco;
begin write (' ( ',pA.info); pa := pA.nextarco; while pa nil do begin -stampalbl (paA.figlio); pa := paA.nextarco end; write (' ) ') end; (* fine procedura stampalbl *)
Vogliamo
ora
risolvere l'esercizio considerando una
differente
rappresentazione dell'albero, la rappresentazione mediante albero binario.
Adottando tale rappresentazione l'albero n-ario e' tra-
sformato in un albero binario secondo queste regole: - l'albero binario ha gli stessi nodi dell'albero n-ario; il
figlio sinistro di ogni nodo dell'albero binario
primo
figlio
e'
il
piu' a sinistra del corrispondente albero
n-
aria originario, se esso esiste; - il
figlio
fratello
destro di ogni nodo dell'albero immediatamente
a destra del
binario
corrispondente
dell'albero n-ario originario, se esso esiste.
La cultura è un bene dell'umanità (
[email protected])
e'
il nodo
205
Esempio: A
D
====>
E
e
E
D
G
F
L'albero binario cosi' ottenuto puo' poi essere rappresentato Pascal con records e puntatori,
in
secondo il metodo presentato nel
problema 22.
Si
puo'
notare
che il numero di records utilizzati
in
questa
rappresentazione e' esattamente pari al numero di nodi dell'albero,
mentre nel caso di rappresentazione mediante lista doppia e'
pari
alla
somma del numero dei nodi e del numero
degli
archi.
Valgono inoltre le seguenti osservazioni: - la
sequenza
ottenuto
in
dalla
preordine
dei
trasformazione
nodi
dell'albero
coincide
con
binario
quella
in
preordine dell'albero n-ario originario; - la
sequenza
ottenuto
in
dalla
postordine dei
nodi
dell'albero
trasformazione non coincide con
postordine dell'albero n-ario originario;
La cultura è un bene dell'umanità (
[email protected])
binario
quella
in
206
- qualora potrebbe nodo
a
l'albero
n-ario fosse etichettato negli
archi
si
rappresentare l'etichetta dell'arco nel record del cui l'arco e'
rivolto,
aggiungendo
dalla
trasformazione
un
opportuno
campo.
L'albero
binario
ottenuto
puo'
essere
rappresentato in Pascal definendo i seguenti tipi: ~
punt = Atiponodo; tiponodo = record etic : char; figlio, fratello end;
punt
La procedura ricorsiva per la visita in preordine di un albero nario rappresentato mediante albero binario e':
procedure stampalb2 (p: punt); visita in preordine di un albero per la stampa della {* CM: sua rappresentazione parentetica; l'albero e' rappresentato mediante albero binario, rappresentato a sua volta con records e puntatori *) begin (* CM: visita la radice *) write ('( ', p A.etic); (* CM: visita i figli cominciando dal primo *) P := p A.figlio; while p nil do begin -stampalb2 {p) ; (* CM: vai sul prossimo fratello *) p := pA.fratello end; write (' ) ') end; (* fine procedura stampalb2 *)
La cultura è un bene dell'umanità (
[email protected])
207
ESERCIZI PROPOSTI 1.
Scrivere
una
preordine
di
procedura un
rappresentato
non ricorsiva
albero
mediante
sia nel albero
per
caso
la
che
binario che
visita
l'albero nel
in sia
caso
sia
rappresentato mediante lista doppia. Si assuma che la visita sia
effettuata
la
per
stampa
della
rappresentazione
parentetica dell'albero. 2.
Si
definisca una rappresentazione per un albero etichettato
nei
nodi e negli archi (con i valori delle etichette
stesso tipo).
dello
Assumendo poi un tale albero gia' in memoria,
si scriva una procedura per la stampa della sua rappresentazione
parentetica
in preordine in cui compaiano
anche
le
etichette degli archi.
~-
Si cerchi una rappresentazione mediante vettori di una lista doppia
corrispondente
procedura preordine
ricorsiva di
un
ad ed
un albero.
Si
una iterativa
albero
scriva
per
la
poi visita
mediante
realizzato
una in tale
rappresentazione.
',i.
Scrivere una procedura ricorsiva per la visita in postordine di
un albero effettuata per la stampa della
rappresentazione
parentetica,
che,
in
corrispondente
questo
caso,
descritta dalle seguenti regole grammaticali: ::= "("
::=
La cultura è un bene dell'umanità (
[email protected])
")"
e'
24 Eliminazione di un sottoalbero da un albero
TESTO Sia
dato gia' in memoria un albero rappresentato mediante
-
doppia.
Scrivere una procedura che,
l 'elemento
lista
conoscendo il puntatore al-
della lista doppia che rappresenta un qualunque
dell'albero diverso dalla radice,
elimini dall'albero stesso
nodo il
fl sottoalbero
che ha tale nodo come radice. La procedura deve anche
, ~rilasciare {
(mediante l'istruzione "dispose") tutti gli
1 della
1li
elementi
lista doppia che, a seguito della eliminazione, non vengono
piu' utilizzati.
SOLUZIONE Presenteremo ~ue soluzioni del problema: una basata ~u una precedura iterativa, e l'altra su una procedura ricorsiva. Per
entrambi
i tipi di soluzione assumeremo che nell'ambito
visibilita' della nostra procedura siano stati definiti i ti tipi per la rappresentazione dell'albero:
La cultura è un bene dell'umanità (
[email protected])
di
seguen-
209
~
punt= Aelem; elem= record info: tipoetichetta; figlio, next : punt end;
Entrambe le soluzioni,
poi, si basano su adattamenti degli algo-
ritmi di visita in preordine di un albero, zione del sottoalbero da eliminare,
sia per
l'individua-
sia per ib rilascio di tutti
i records che compongono tale sottoalbero. Iniziamo ad analizzare in dettaglio la soluzione iterativa. Poniamoci
dapprima
scopo
individuare il record che rappresenta
di
il
problema di organizzare la la
visita radice
allo del
sottoalbero da eliminare. Di tale record e' noto il puntatore,
che decidiamo venga passato
come parametro alla procedura. L'operazione
di
eliminaz i one di un sottoalbero
eseguita
sulla
rappresentazione mediante lista doppia si riduce alla eliminazione,
dalla
lista degli archi uscenti dal padre del
dell'elemento
sottoalbero,
rappresentante l'arco diretto alla radice del sot-
toalbero . supponiamo,
ad
esempio,
che il sottoalbero da eliminare
come radice il nodo etichettato con B nella seguente figura:
-----.
'
/
I
1A
/
/
;Y I ' I
AA
' '/ /'
/
/
'
·I f I
D La cultura è un bene dell'umanità (
[email protected])
......
'-
"
' JI
i~· I
abbia
210
L'eliminazione
del sottoalbero,
in questo caso,
corrisponde
a
eliminare, dalla lista degli archi del nodo etichettato con A, il
~~
ecord
indicato con AA,
e cioe' ad aggiornare il puntatore
campo. next del record precedente ad AA
nel modo indicato
nel dalla
reccia tratteggiata in figura. J
Queste considerazioni ci suggeriscono di organizzare la visita in
modo che ogni volta che si raggiunge un record della lista doppia (si assuma che p sia il puntatore a tale record) si c ontrolli che il
valore
puntato
del
da
campo "figlio" del record
p (il cui puntatore
si
trova,
successivo
a
quindi,
nel
quello campo
p A.next) sia uguale al puntatore del record cercato. In caso affermativo, infatti, bastera' assegnare al campo p A.nex t il
valore del campo
successivo
a
pA.next A.next,
quello puntato da p
e
eliminando cosi' il record rilasciare
opportunamente
tutti i records inutilizzati; in caso negativo, invece, si dovra' continuare nello stesso modo la visita.
Possiamo
ora scrivere la prima versione della procedura,
ricor-
dando che per la visita in preordine iterativa di un albero si fa uso di una pila per memorizzare i puntatori dei records ai
quali
bisogna tornare, una volta conclusa la v i sita di un sottoalbero. Lo
schema che seguiremo prevede che ogni volta che si
abbandona
un record che rappresenta un arco dell'albero per iniziare la visita del sottoalbero a
cui tale arco e' diretto,
si
memorizzi
nella pila il puntatore a tale record, in modo che lo si possa di nuovo raggiungere alla fine della visita del sottoalbero.
La cultura è un bene dell'umanità (
[email protected])
211
procedure stacca (p,pp: punt); (* CM: elimina un sottoalbero da un albero. L'albero e' rappresentato mediante lista doppia; p rappresenta il puntatore alla radice dell'albero e pp il puntatore alla radice del sottoalbero da eliminare *) var
continua: boolean; (* CD:
vale false solo quando e'stato trovato il sottoalbero da eliminare (indicando cosi' che la visita puo' essere interrotta), oppure quando la visita e' terminata *)
begin init(pila); continua := true; while continua do if pA.next nil then if pA.nextA.figlio = pp then (* CA: il record cercato e' stato trovato *) begin continua := false; pp := pA.next; pA.next := p A.nextA.next; (* CM: rilascio dei records che formano il sottoalbero eliminato *) distruggi (pp) end else begin p := p A.next; (* CA: p e' diverso da nil *) push(pila,p); p := pA.figlio end else if no:r-{empty(pila)) then pop (pila,p) else continua := farse end; (* fine procedura stacca *)
Si noti che: - e' stata utilizzata una variabile booleana per segnalare che il record
cercato e' stato trovato e la visita puo' essere inter-
rotta, o che la visita e' terminata; - si
e'
"stacca") dure
assunto
l'esistenza
(esternamente
alla
procedura
della pila "pila" e delle relative funzioni e proce-
per la sua gestione;
La cultura è un bene dell'umanità (
[email protected])
212
- il e'
problema della distruzione dei records non piu'
utilizzati
stato temporaneamente risolto con una chiamata a un' oppor-
tuna procedura "distruggi", che dovra' essere definita nell'arobito della procedura "stacca". Resta, zione
percio',
da scrivere la procedura "distruggi".
L'assun-
che e' stata fatta con la chiamata e' che a tale procedura
si passa come parametro il puntatore (a tale scopo si e' usato il parametro pp perche' il suo valore originario non e' piu' sario) a un record che rappresenta un arco dell'albero;
necesessa do-
vra' rilasciare tale record e tutti i records che formano la rappresentazione del sottoalbero raggiungibile mediante il puntatore pp".figlio. La struttura della procedura, tale
sottoalbero,
fatto che,
percio',
ricalchera' la visita di
modificata opportunamente tenendo
conto
del
prima di rilasciare un record, e' necessario raggiun-
gere quello che nella visita lo segue immediatamente,
altrimenti
non piu• raggiungibile.
procedure distruggi (p: punt); (* CM: rilascia tutti gli elementi della lista doppia raggiungibili dal nodo puntato da p; poiche' p e' il puntatore ad un record che rappresenta un arco dell'albero, la procedura dovra' eseguire la dispose su tale record e su tutti i records che formano il relativo sottoalbero, il cui puntatore iniziale e' in p".figlio *) var q: punt; begin (* CM: salvataggio del campo p".figlio e rilascio del puntato da p *) q := p; p := p".figlio; dispose (q);
La cultura è un bene dell'umanità (
[email protected])
record
213
(* CM: rilascio
di tutti i records sottoalbero *) while p nil do begin q := p; p := pA.next; dispose(q); if p nil then begin push(pila,p); P := pA,figliO end else if not (empty(pila)) then pop(pila,p) end end; (*f°ine procedura distruggi *)
che
formano
il
Passiamo alla soluzione ricorsiva. La strategia generale non si distacca molto dalla versione iterativa:
anche qui si trattera' di organizzare in maniera opportuna
una procedura di visita in preordine per trovare il record cercato
e chiamare,
al momento opportuno,
una
procedura
ricorsiva
analoga alla procedura "distruggi" appena vista. E'
interessante pero' notare che bisogna progettare la procedura
in modo che la visita venga interrotta quando si trovi il
record
cercato. Per
fare
questo
si
puo'
pensare di
nuovo
a
una
variabile
booleana "continua" che indichi, con il suo valore, il verificarsi di tale evento. Ci
sono,
almeno in linea di principio,
tre alternativi modi di
utilizzo di tale variabile booleana. 1.
Variabile
locale.
possibile
nel
variabili
definite
Si vede subito che tale utilizzo
nostro
problema.
Infatti
all'interno di una
La cultura è un bene dell'umanità (
[email protected])
sappiamo
procedura
non
e'
che
le
ricorsiva
214
sono locali a in
ogni esecuzione della procedura stessa;
altro modo,
della
ogni
volta
detto
che viene iniziata l'esecuzione
procedura (la prima volta, o a seguito di una chiamata
ricorsiva) viene creata una copia della variabile locale e ogni riferimento a essa s'intende effettuato a tale copia. 2.
Parametro
della
definire tipo
un
valore
procedura.
In
questo
caso
si
dovrebbe
nuovo parametro di tipo variabile (se fosse
di
si avrebbero gli stessi problemi
al
descritti
punto 1) rappresentante proprio la variabile booleana. In questo modo,
quando si dovesse trovare il record cercato,
si porrebbe a "false" il parametro; municato a
tale valore verrebbe co-
tutte le copie della procedura ricorsiva a cui l'
esecuzione dovrebbe tornare, ottenendo l'effetto ~
Variabile
globale.
desiderato.
In questo caso si dovrebbe definire
la
variabile nel campo di visibilita• della procedura ricorsixa (ad
esempio
Poiche'
I
copie
nel
programma o
nella
procedura
chiamante).
essa sarebbe accessibile e modifica);lj]e da tutte della procedura ricorsiva 1
quella vista al punto 2
la soluzione e' analoga
le a
·l
Entrambe le possibili due alternative hanno, pero', lo svantaggio di del
richiedere
la definizione della variabile booleana da
programma chiamante.
necessario
poiche'
Anche nel caso
2,
infatti,
la chiamata della procedura stessa
parte
cio'
e'
richiede
una variabile come parametro. Si dovrebbe percio' definire, fuori dalla nostra procedura, una variabile che e' utile solamente alla procedura ricorsiva,
a discapito della parametricita' della pro-
cedura stessa.
La cultura è un bene dell'umanità (
[email protected])
215
Prima
di presentare una possibile soluzione per
tale
problema,
scriviamo la procedura nela caso si scelga di usare una variabile globale,
come detto nel punto 3,
assumendo che la procedura sia
definita nell'ambito di un programma.
program
alfa(input,output);
var continua: (* CD: usata dalla procedura "stacca" *) boolean; procedure stacca (p, pp: punt); procedure distruggi (p: punt); var q: punt; begin q := p; p := pA.figlio; dispose (q); q := p; p := pA.next; dispose (q); while p nil do begin q := p; p := pA.next; distruggi (q) end end; (*fine procedura distruggi *)
(* CM: istruzioni della procedura stacca *) begin continua:= true; while (pA.next nil) and (continua) do if pA. nextA. figlio = pp _____ - / then begin -pp := pA.next; pA.next := pA.nextA.next; distruggi (pp) ; continua := false end else begin p := pA.next; \ ,tacca (pA.figlio,pp) '-end end; (* fine procedura stacca *) (*CM: istruzioni del programma "alfa" *) begin end.
La cultura è un bene dell'umanità (
[email protected])
216
Abbiamo inserito la procedura "stacca" nell'ambito di un programma,
proprio per sottolineare l'esigenza della definizione
variabile
"continua"
che
non ha altro scopo che
della
servire
alla
procedura stessa. Un
modo per nascondere tale variabile al programma chiamante
quello
e'
di inserire la procedura "stacca" all'interno di un'altra
procedura in cui: - sia dichiarata la variabile "continua" - le
uniche
assegnazione
istruzioni che vi compaiono siano: l'istruzione del
valore iniziale a tale
variabile
di
(evitando
cosi' l'inizializzazione ripetuta nella procedura ricorsiva)
e
la chiamata alla procedura stacca. La struttura del programma diventerebbe (ridenominando la vecchia procedura "stacca" in "staccal" e chiamando,
invece, "stacca" la
nuova procedura) •
program alfa(input,output); var a,b: punt; procedure stacca (p,pp: punt); var continua: boolean; procedure staccal (p,pp: punt);
end; (* fine procedura staccal *) (* CM: inizio istruzioni della procedura stacca *) begin continua := true; staccal(p,pp) end; (* fine procedura stacca *)
La cultura è un bene dell'umanità (
[email protected])
217
(* CM: inizio istruzioni del programma *) begin stacca(a,b); end.
Si puo' notare che, si
ha
pur avendo introdotto una procedura in piu',
il vantaggio che il programma chiamante
e'
indipendente
dalla struttura della procedura; si e' indicato, a tale sc•p•, un esempio di chiamata alla procedura: stacca(a,lt); che e' la chiamata alla procedura piu' esterna, scopo
la quale
ha
lo
di inizializzare la variabile booleana e di eseguire a sua
volta la chiamata alla procedura "staccal",
che fa le eperazieni
vere e preprie sull'alltere. Si sottolinea che le considerazioni precedent' hanno
per vari programmi e,
particolare
di conseguenza, e' richiesto un alto grado
di parametricita' della procedura stessa. Volendo risolvere lo stesso problema nel caso in cui l'albero sia rappresentato dato
un
seguendo accede,
mediante albero binario,
nodo p dell'albero, il
si deve considerare che,
al primo figlio si
puntatore pA.figlio,
mentre agli
partendo dal nodo puntato pA.figlio,
puo' altri
accedere figli
seguendo la catena
di puntatori memorizzati nel campo "fratello" di ogni record. segue questa procedura:
La cultura è un bene dell'umanità (
[email protected])
si
Ne
2 18
procedure stacca (p, pp: punt); (* CM: elimina un sottoalbero da un albero. L'albero e' rappresentato mediante albero binario; p rappresenta il puntatore alla radice dell'albero e pp il puntatore alla radice del sottoalbero da eliminare *) var continua: boolean; (* CD: serve alla procedura staccal *) procedure distruggi(p: punt);
procedure staccal(p, pp: punt); (* CM: procedura ricorsiva che esegue le effettive operazioni *) begin if pA.figlio nil then if pA.figlio = pp - - then beg in pA.figlio := pA.figlio A.fratello; distruggi(pp); continua:= false end else begin p := p A,figlio; staccal(p, pp); while (pA.fratello nil) and (continua) do if p A.fratello = pp-- - then begin p A.fratello := p A.fratello A.fratello; distruggi (pp); continua := false end else begin p := p A.fratello; staccal(p, pp) end end; (* fine procedura staccal *)
(* CM: istruzioni della procedura stacca *) begin continua := true; staccal(p, pp) end; (* fine procedura stacca *)
Si
lascia al lettore la specifica della procedura "distruggi" in
questo
caso.
Si puo' notare che la particolare struttura
rappresentazione
influisce
sull'organizzazione
della
dell'algoritmo,
rendendolo leggermente piu' complesso rispetto al caso di rappre-
La cultura è un bene dell'umanità (
[email protected])
219
sentazione dell'albero mediante lista doppia: complessita'
in particolare, la
nasce dall'esigenza di trattare in modo diverso
il
primo figlio di un nodo dagli altri.
ESERCIZI PROPOSTI
1.
Scrivere la procedura "distruggi" nel caso che l'albero
sia
rappresentato mediante albero binario. 2.
Scrivere
la
versione iterativa delle procedure "stacca"
e
"distruggi" nel caso che l'albero sia rappresentato mediante albero binario. 3.
Modificare
le
procedure scritte per contemplare
anche
caso in cui il nodo da staccare sia la radice dell'albero.
La cultura è un bene dell'umanità (
[email protected])
il
~ruzione di un albero
TESTO Scrivere
una procedura che legga da ingresso la rappresentazione
parentetica
in preordine di un albero non vuoto e costruisca
in
memoria la sua rappresentazione. L'albero e' etichettato nei nodi con caratteri alfabetici.
SOLUZIONE Risolveremo l'albero
questo problema dapprima assumendo di
mediante
lista doppia e poi mediante
rappresentare
albero
binario.
Ricordiamo che la rappresentazione parentetica in preordine di un albero
non vuoto e' formalmente descritta dalle seguenti
regole
grammaticali: ::="("
} ")"
: := "A"/"B"/ .... /"Z" Assumiamo leggere Le
percio'
che i dati d'ingresso che la
procedura
deve
siano conformi a tali regole .
dichiarazioni di tipo relative alla rappresentazione dell'al-
La cultura è un bene dell'umanità (
[email protected])
221
bere mediante lista doppia sono le seguenti: punt= Anodo; nodo= record info: 'A' .• 'Z'; figlio, next: punt end;
~
La
procedura richiesta avra' un solo parametro,
comunicare
al
necessario
programma chiamante il puntatore al
dell'albero che la procedura avra' creato:
nodo
per
radice
per tale parametro il
passaggio dovra' quindi essere di tipo variabile. Proponiamoci di scri"vere una procedura ricorsiva per la soluzione di questo problema,
considerando proprio che la definizione del-
l'albero data dalla regola grammaticale e' essa stessa ricorsiva. Cio'
significa
dovra'
che ogni volta che la procedura
costruire un albero,
viene
chiamata
sia esso l'albero principale
o
un
e'
di
sottoalbero, secondo lo stesso algoritmo. La
prima
operazione
che la procedura dovra' effettuare
creare il nodo relativo alla radice dell'albero,
(sempre presen-
come si puo' verificare dalla grammatica) e
successivamente
te,
chiamare
ricorsivamente
relativi sottoalberi, \
la procedura tante volte quanti sono
c~eando
i
anche i corrispondenti nodi inter-
medi corrispondenti agli archi uscenti dalla radice. Il problema che si presenta e' che il numero di tali non
sottoalberi
e' noto a priori e si deve percio' individuare quale
condi-
zione puo' indicare la fine dei sottoalberi da creare. Analizzando
la struttura dell'ingresso,
si vede che:
che e' finita la costruzione di un sottoalbero, simbolo
in ingresso e' il simbolo "(",
La cultura è un bene dell'umanità (
[email protected])
una volta
se il successivo
si deve eseguire la
co-
222
struzione di un nuovo sottoalbero,
se invece il simbolo e'
")",
la costruzione dell'albero e' terminata, essendo esauriti tutti i suoi sottoalberi. Alla
luce
di queste osservazioni,
scriviamo la procedura
"co-
struisci".
procedure costruisci (var p: punt); (* CM: costruisce un albero leggendo da ingresso la sua rappresentazione parentetica in preordine; l'albero e' rappresentato mediante lista doppia; la procedura fornisce in p il puntatore alla radice dell'albero creato *) var eh: char; q: punt; begin /1/ leggi(ch) F
(* CM: crea
(* CM: legge da ingresso il successivo carattere non blank e assegna il valore alla variabile eh *) il nodo radice e assegna al campo info il valore
di eh *) new(p); p A.info :=eh; q := p; leggi(cn) i while eh = ' (' do begin (* CA: ci sono ancora sottoalberi *) (* CM: creazione di un nuovo record nella lista archi *) new(qA.next); q := qA.next; (* CM: costruzione del sottoalbero *) costruisci(qA.figlio); leggi(ch) end; (*CA: eh=')'; non ci sono piu' sottoalberi *) q A.next := nil end; (* fine procedura costruisci *)
Si
puo'
creando
notare che la costruzione dei sottoalberi opportunamente
la
e'
lista degli archi uscenti
degli
eseguita dal
nodo
radice, lista creata con l'ausilio di una nuova variabile locale, la variabile "q",
usata per non modificare il valore del parame-
tro variabile "p", rappresentante il puntatore al nodo radice. Ogni
volta
che si ripetono le istruzioni
La cultura è un bene dell'umanità (
[email protected])
del
ciclo,
si
deve
223
creare un nuovo sottoalbero. alla
lista
record
degli
archi,
A
tale scopo si aggiunge un
si fa puntare la variabile q
e si richiama la procedura "costruisci",
zione del sottoalbero: attuale
p A.figlio,
in
record a
per la
tale
costru-
la procedura si richia.ma con il parametro modo che il puntatore
alla
radice
del
sottoalbero che verra' costruito verra' inserito correttamente in tale
campo;
si noti che questo si verifica perche' il parametro
formale della procedura "costruisci" e' di tipo variabile. -Nella
procedura,
procedura
la
"leggi",
linea /1/ consiste in
una
chiamata
che deve leggere il successivo carattere
ingresso ignorando pero' eventuali spazi bianchi,
alla in
non significa-
tivi. Scriviamo, percio', la procedura "leggi".
procedure leggi (var eh: char); begin repeat read(ch) until eh ' end~fine procedura leggi *)
Con questa procedura, ro,
puo'
bianchi,
la rappresentazione parentetica dell'albe-
comparire in ingresso con un qualunque numero di spazi anche
tra i simboli significativi,
e in un
qualunque
numero di linee di ingresso. , acciamo
osservare che nella procedura si assume che il
simbolo
''(" indicante l'inizio dell'albero che si vuole che essa costru i sca
sia gia' stato letto da ingresso; \ infatti il primo
simbolo
che
viene letto si assegna al campo info del nodo radice ed
e'
I
Vpercio',
considerato
l'etichetta della radice stessa.
La cultura è un bene dell'umanità (
[email protected])
Cio'
e
I
224
dovuto al fatto che la procedura, durante la costruzione dell'alberé,
viene
richiamata ricorsivamente (per la
sottoalberi)
costruzione
proprio in conseguenza del fatto che si e' letto da
ingresso il relativo simbolo "(" di inizio sottoalbero. parole,
ogni
costruzione
volta
che la procedura viene
di un sottoalbero,
In altre
richiamata
che ha eseguito la chiamata; inserita
anche
per
cioe',
Resta
costruzione dell'albero
la
percio'
ingresso: "crealb"
questa e' la ragione per cui non si
a
lettura
Poiche' la procedura e' ricorsiva, questo vale
cosi' come e' scritta,
ingresso,
la
procedura
all'inizio della procedura l'istruzione di
del simbolo"(".
per
il simbolo"(" di inizio di tale
sottoalbero e' gia' stato letto dalla esecuzione della
e'
dei
complessivo:
la
non leggera' il primo simbolo
parentesi aperta relativa all'albero il tale
procedura,
complessivo.
problema di leggere il primo simbolo scopo si puo' definire
una
di
nuova
"("
in
procedura
che ha il compito di leggere il primo simbolo "("
e
di
chiamare poi la procedura "costruisci". La soluzione finale e•, quindi, la seguente:
p~ocedure
crealb (var p: punt); (* CM: costruisce un albero leggendo da ingresso la sua rappresentazione parentetica in preordine; l'albero e' rappresentato mediante lista doppia; la procedura fornisce in p il puntatore alla radice dell'albero creato *)
var eh: char;
procedure leggi (var eh: char); begin repeat read (eh) until eh' end; (* fine procedura leggi *)
La cultura è un bene dell'umanità (
[email protected])
225
procedure costruisci (var p: punt); (* CM: procedura ricorsiva che esegue le operazioni *) var q: punt; begin (*CA: il simbolo iniziale "(" dell'albero che si costruisce e' gia' stato letto *) new(p); leggi(p A. info); q := p; leggi(ch); while eh = ' ( ' do begin new(qA.next); q := qA.next; costruisci(qA.figlio); leggi(ch) end; qA.next := nil end; (~ine procedura costruisci *)
(* istruzioni della procedura crealb *) begin (* CM: lettura del simbolo "(" di inizio albero*) leggi(ch); (* CM: costruzione dell'albero *) costruisci(p) end; (* fine procedura crealb *)
/ Analizziamo mediante
ora il casa in cU-1-s..i.-....mglia_i:appresentare
albero binario.
non cambia,
La struttura della procedura
l'albero "crealb"
mentre la procedura piu' interna "costruisci" risen-
tira' del diverso metodo di rappresentazione: in particolare, una volta creato il nodo radice dell'albero, si deve tenere conto che il
primo
eventuale
sottoalbero deve essere connesso
"figlio" del record corrispondente alla radice, sottoalberi
devono
radice
precedente sottoalbero.
del
essere connessi al
"crealb":
La cultura è un bene dell'umanità (
[email protected])
campo
Ne segue
al
campo
mentre gli altri "fratello" questa
della
procedura
226
procedure crealb (var p: punt); costruisce un albero leggendo da ingresso la sua (* CM: rappresentazione parentetica in preordine; l'albero e' rappresentato mediante albero binario; la procedura fornisce in p il puntatore alla radice dell'albero creato *) var eh: char; procedure leggi (var eh: char); begin repeat read (eh) until eh< > ' end; (* fine procedura leggi *) procedure costruisci (var p: punt); (* CM : procedura ricorsiva che esegue le operazioni *) var q: punt; begin (* CA: il simbolo iniziale "(" dell'albero che si costruisce e' gia' stato letto *) new(p ) ; leggi(p A,info); p A.fratello := nil; leggi(ch); if Ch = I (I -then begin ( * CM: crea il primo sottoalbero *) costruisci(p A.figlio); q := p A.figlio; leggi(ch); (* CM: crea gli altri eventuali sottoalbe~i *) while eh = ' ( ' do begin costruisci(qA,fratello); q := qA.fratello; leggi(ch) end end else p A.figlio := nil end~ fine procedura costruisci *) (* istruzioni della procedura crealb *) begin (*CM: lettura del simbolo"(" di inizio albero*) leggi(ch); (* CM: costruzione dell'albero *) costruisci(p) end; (* fine procedura crealb *)
Le
solu z ioni presentate finora si basano tutte su procedure
ri-
corsive. Vogliamo ora affrontare il problema della costruzione di
La cultura è un bene dell'umanità (
[email protected])
22 7
un albero con un metodo iterativo, sempre considerando la rappresentazione di un albero mediante albero binario. derazione
da
memorizzare
La prima censi-
fare in questo caso e' relativa alla in qualche modo i puntatori dei record
lasciati per la costruzione dei sottoalberi figli essi
si
possa
che
di
vengono
in modo che ad
di nuovo accedere nel caso in cui gli
connettere un sottoalbero fratello~ una pila.
esigenza
si
debba
Useremo, a questo proposito,
L'algoritmo che presentiamo si basa sull'idea di puntatore p per scandire i vari record
lizzare
un
creati:
si fara' in modo che p punti sempre al record a cui deve
essere connesso il successivo sottoalbero da creare. di
che
uti-
Nel momento
creare un sottoalbero si dovra' solamente decidere se connet-
terlo
al campo "figlio" o al campo "fratello del record
da p;
la scelta si basera' sul valore di una variabile
("primo"), dice
vengono
che,
puntato booleana
opportunamente aggiornata, indichera' se la ra-
del sottoalbero appena creato e' figlio o fratello del nodo
corrispondente al record puntato da p. La procedura e' questa:
procedure crealbiter (var piniz: punt); (* CM: costruisce con metodo iterativo un albero leggendo da ingresso la sua rappresentazione parentetica in preordine; l'albero e' rappresentato mediante lista doppia; la procedura fornisce in p il puntatore alla radice dell'albero creato *) ~
var
tipopila = .... pila: tipopila; p, pp: punt; primo: boolean;
procedure leggi (var eh: char);
La cultura è un bene dell'umanità (
[email protected])
228
procedure e funzioni per la gestione della pila
(* CM: istruzioni della procedura crealbiter *) begin (* CM: inizializzazione della pila *) init(pila); (*CM: lettura primo ' (' *) leggi(ch); (* CM: creazione della radice *) new(piniz); pinizA.fratello := nil; pinizA.figlio := leggi(pinizA.info);~-
(* CM: inizializzazioni *) p := piniz; primo := true; repeat p punta al record a cui deve essere connesso il (* CA: prossimo eventuale sottoalbero da costruire *) leggi(ch); if Ch = I (I then begin new(pp); leggi(ppA.info); ppA.figlio := nil; ppA.fratello := nil; . (* CA: il sottoalbero che ha pp come radice e' il primo sottoalbero di p se e solo se primo vale true, altrimenti e' un suo fratello *) if primo then begin pA.figlio := pp; push(pila,p) end else begin pA.fratello := pp; primo := true end; p := pp end else if primo then primo := false else pop (pila, p) until empty(pila) end~fine procedura crealbiter *)
Si
noti
della
che non si e' specificato il
pila:
metodo
di
realizzazione
le chiamate di procedure e funzioni per la gestione
La cultura è un bene dell'umanità (
[email protected])
229
della pila, cosi' come sono state descritte nel problema 20, sono infatti indipendenti dalla realizzazione. La variabile "primo" indica, nuovo
con il suo valore, se la radice del
sottoalbero da creare debba essere connessa al campo
"fi-
glio" (valore "true") del record puntato da p o al campo "fratello"
(valore ogni
cie' e' ettenuto assegnadole
il
volta che si crea un nuovo record (in modo
valore che
il
successivo sottoalbero sia considerato un sottoalbero figlio)
ed
11
true 11
"false");
assegnandole il valore "false" ogni volta che finisce un sottoalbero
(in
modo che il successivo sottoalbero sia considerato
un
sottoalbero fratello).
ESERCIZI PROPOSTI
1.
Scrivere una procedura ricorsiva e una iterativa per leggere da ingresso la rappresentazione parentetica in postordine di un
albero
e costruire in memoria la
mediante lista doppia.
sua
rappresentazione
L'albero e' etichettato nei nodi con
valori alfabetici. 2.
Scrivere una procedura ricorsiva e una iterativa per leggere da ingresso la rappresentazione parentetica in postordine di un
albero
e costruire in memoria la
mediante albero binario.
sua
rappresentazione
L'albero e' etichettato nei
con valori alfabetici.
La cultura è un bene dell'umanità (
[email protected])
nodi
230
3.
Analizzare scritte mediante
le seguenti due procedure "crealb2" e
entrambe lista
parentetica
doppia
in
correttamente
per
costruire
un
albero
leggendo
la
sua
preordine.
rappresentato
rappresenta z ione
Verificare
il problema (si assuma la
"crealb3"
se
r isolv ono
proc edura
gia' definita) .
procedure crealb2 (var p:punt) ; var pO,q: punt; eh: char; begin leggi(ch); if Ch I (I then p := nil else begin-leggi ( ch); new(p); pA.info :=eh; q . - p; r, \, / repeat 'i' I c;:realb2(p0)! 1 i (•y;;'r, 't--;,. if po k then :~ c + l; (*CM: aggiornamento dell'elemento affiorante di pila2 *) i f not(empty2 (pila2)) then begin pop2(pila2i affiorante); affiorante := affiorante + nodi; push2(pila2, affiorante) end ·
e
end until (p----;;-nil) and (emptyl(pilal)); conta := n - end; (* fine funzione conta *)
Si dev e notare che la funzione scritta e' valida qualunque sia il
metodo
di rappresentazione delle pile:
a tale scopo l'aggiorna-
mento · dell'elemento affiorante di "p i la2" e' stato formulato
in
termini delle operazioni note sulle pile. Si
noti
anche
che
la limitazione
del
Pascal
di
non
poter
parametrizzare i sottoprogrammi rispetto al tipo dei parametri ci ha
costretto a dover definire in modo differente le procedure
le funzioni per la gestione delle due pile:
e
le uniche differenze
tra tali procedure saranno relative appunto al tipo dei parametri.
La cultura è un bene dell'umanità (
[email protected])
240
ESERCIZI PROPOSTI
1.
Scrivere una soluzione iterativa per il problema presentato, assumendo doppia
che e
l'albero
che
sia rappresentato
l'albero
complessivo
non
mediante debba
lista essere
conteggiato. 2.
Scrivere un programma completo che: a) costruisca binario,
un
albero
leggendo
rappresentato
mediante
albero
da ingresso la sua rappresentazione
parentetica in preordine; b) lo
stampi
secondo
la
stessa
rappresentazione
parentetica; c) legga da ingresso un valore intero k; d) calcoli quanti sono i sottoalberi dell'albero che hanno un numero di nodi minori di k, ricorsiva
e
mediante una
procedura
senza includere l ' albero complessivo
conteggio.
La cultura è un bene dell'umanità (
[email protected])
nel
27 Costruzione di un grafo
TESTO Scrivere
una
procedura che legga la matrice di adiacenz a di
(senza memorizzar~a) \ e costruisca la sua
grafo
un
rappresentazione
mediante list~ ) di succes __ j~i _ su_~ponga ~i leggere prevèntiv~~ent~ i_l
I
num~r~ di nodi del grafo_ :_le re2 ati_ve
-e~-~che-t:_~e~ ~-il
tipo "carattere". I
SOLUZIONE Per
rappresentare
faremo quali
un
grafo per mezzo di
uso di un array di puntatori, e'
liste
di
uno per nodo,
il puntatore iniziale di una lista.
successori ognuno
Tale lista
dei sara'
realizzata con records e puntatori; ogni suo elemento rappresenta un
arco uscente da quel nodo e contiene la posizione
del
nodo successore a cui tale arco e' diretto.
etichettato nei nodi, tiene
anche
nell'array
Se il grafo
e'
l'array, oltre ai puntatori iniziali, con-
le etichette;
le eventuali etichette
degli
archi
saranno memorizzate negli elementi delle liste dei successori.
La cultura è un bene dell'umanità (
[email protected])
242
Un
esempio di grafo rappresentato mediante liste
dei successori
e' il seguente:
~® 0 ©
1
A
2
B
3
D
4
e
2
nil
-GB--ELiiiiJ ni l 5
nil
5 1
6
nil
Qualora non sia noto a priori il numero di nodi del grafo,
l'ar-
ray deve essere opportunamente sovradimensionato.
Le
dichiarazioni
di
tipo
e
di
variabili corrispondenti alla
rappresentazione mediante liste di successori sono:
const
nmax=
(* CD: numero massimo di nodi del grafo *)
punt= " elem; elem= record nodo: integer ; next: punt end; tipografo= array [l •• nmax] of record etic: char; (* CD: etichetta del nodo *) succ·: punt end;
La cultura è un bene dell'umanità (
[email protected])
243
Per quanto riguarda la sezione istruzioni,
un primo raffinamento
puo 1 essere il seguente: begin /1/ lettura del numero di nodi; /2/ lettura delle etichette; /3/ lettura della matrice di adiacenza e liste di successori
La
costruzione
delle
fase cruciale di trasformazione di rappresentazione puo'
sere
raffinata tenendo conto che si dovranno scandire
tutte
esle
righe della matrice di adiacenza: la scansione della riga i-esima corri spondera' alla
creazi one
della
lista dei successori rela-
tiva al nodo i-esimo. Tenuto conto di cio' e realizzando lo scambio di informazioni tra procedura bile,
e programma chiamante per mezzo di un parametro varia-
corrispondente all'array dei nodi,
si ottiene il seguente
raffinamento della procedura:
procedure trasforma (var grafo: tipografo); (* CM : legge da ingresso la matrice di adiacenza relativa ad un grafo senza memorizzarla e costruisce la corrispondente rappresentazione mediante liste dei successori *) var
a:
0 .. 1; (*CD: variabile di appoggio per l'elemento della matrice di adiacenza di volta in volta letto *) i,j: 1. .nmax; (* CD: indici per la scansione dei dati corrispondenti alla matrice di adiacenza *) p: punt; (* CD: puntatore ausiliario; di volta in volta punta all'ultimo elemento inserito nella lista corrente *) n: l .. nmax; (*CD: numero di nodi del grafo*)
La cultura è un bene dell'umanità (
[email protected])
244
begin (* CM: lettura del numero di nodi *) readln(n); (* CM: lettura delle etichette dei nodi del grafo *) for i := 1 to n do read(grafo[i].etic); (* CM : lettura della matrice di adiacenza e costruzione delle liste dei successori *) for i := 1 to n do (* CM:-rettura della i-esima riga della matrice e costruzione della lista dei successori dell'i-esimo nodo *) begin (* CM: inizializzazione del pun~atore corrente e del puntatore iniziale alla lista *) p : = nil: grafo---yI].succ := nil (* CM: scansione della i-esima riga della matrice *) for j := 1 to n do /4/ lettura dell'elemento (i,j) della matrice di adiacenza ed eventuale creazione del corrispondente elemento nella lista dei successori del nodo i end end; (* fine procedura trasforma *)
Resta
ora
questo,
da tradurre la frase / 4/ in
particolare
istruzioni
Pascal.
attenzione va posta al problema di
Per
distin-
guere, ogni volta che si crea un elemento della lista, se esso e' il primo della lista (nel qual caso il puntatore a tale deve
elemento
essere memorizzato nel campo "succ" della i-esima posizione
dell'array
dei
nodi)
oppure se non e' il primo
(e
allora
va
connesso all'ultimo elemento che era stato inserito). Si noti che con
questa scelta si ottengono le liste dei successori
secondo i nodi successori.
ordinate
Se questo non fosse necessario,
ogni
elemento si potrebbe inserire al primo posto della lista, semplificando
la
creazione delia lista
stessa.
Adottando
la
soluzione, si ottiene la seguente codifica della frase /4/.
La cultura è un bene dell'umanità (
[email protected])
prima
245
begin (*CM: lettura dell'elemento (i,j) della matrice*)) read (a) ; if a = 1 then (* CA: nel grafo esiste il ramo (i,j) *) begin (* CM: creazione dell'elemento nella lista *) if p = nil then (* CA: l'elemento e' il primo della lista *) begin new (grafo [i) . succ); p :=grafo [i).succ end else begin new (p" .next); p := p " .next end; (* CA:---P-punta all'elemento appena creato*) (* CM: assegnazione dei valori ai campi del record *) p " . nodo . - j ; p ". succ := nil end end
ESERCIZI PROPOSTI
~
E'
noto che il grado di uscita di un nodo di un grafo e' il.
numero
di
archi
che escono da
quel
nodo.
Scrivere
una
funzione che, ricevendo come parametri d'ingresso un grafo e l'etichetta
di un suo nodo,
calcoli il grado di uscita
di
tale nodo. Si risolva questo esercizio nel caso che il grafo sia
rappresentato mediante matrice di adiacenza e nel
caso
che sia rappresentato mediante liste dei successori.
')<
Risolvere
l'esercizio 1.
nel caso si voglia
calcolare
il
grado di ingresso del nodo (cioè' il numero di archi entranti nel nodo) .
La cultura è un bene dell'umanità (
[email protected])
28 Analisi di un grafo
TESTO Scrivere una procedura Pascal che supponendo esistente in memoria un grafo orientato rappresentato mediante lista doppia e ricevendo
in
ingresso il puntatore a un nodo,
stampi le etichette
di
tutti i nodi da esso raggiungibili. Si assuma il grafo etichettato nei nodi con valori di tipo "carattere".
SOLUZIONE Nella rappresentazione di un grafo ogni un
per mezzo di lista
doppia
nodo i del grafo e' associato un elemento della lista, campo
con
a
una
lista di elementi (chiamata la lista dei successori del nodo
i),
tanti
quanti
elementi che
contenente l'etichetta del nodo e un puntatore
a
sono
i successori del nodo.
contiene un puntatore all'elemento della
rappresenta il nodo successore.
della grafo,
Ciascuno
In sostanza,
lista dei successori del nodo i, l'arco
successore.
di
questi
lista
doppia
ogni elemento
rappresenta un arco
che parte appunto dal nodo i e giunge a
Quindi,
le
un
del nodo
eventuali etichette degli archi possono
La cultura è un bene dell'umanità (
[email protected])
247
essere
memorizzate negli elementi che formano le liste dei
sue-
cessori. In figura 1 mostriamo un esempio di grafo e della
corrispondente
rappresentazione mediante lista doppia.
(\\
nil
A
\\ '~ ~
B
I.
-~
( e
nil
Figura 1
Alla struttura si accede mediante il puntatore a un nodo prestabilito; e' necessario, quindi, scegliere tale nodo in modo che da \lesso
sia possibile raggiungere tutti gli altri. ( Se un tale nodo
non esiste,
o comunque se non ci si vuole porre il
individuarlo, elementi siano
si
puo'
modificare la struttura in modo che
della lista doppia che rappresentano i nodi
collegati tra loro,
ulteriore
problema
puntatore,
in un ordine qualunque,
rendendo cosi' accessibili,
del
di gli
grafo
mediante
un
dal nodo ini-
ziale, tutti gli altri((si veda la figura 2 a pagina seguente). Nel
seguito,
faremo l'ipotesi che dal nodo di accesso al
sia possibile raggiungere tutti gli altri. j
La cultura è un bene dell'umanità (
[email protected])
grafo
248
nil
nil
e
nil
nil
Figura 2 Per realizzare in Pascal la rappresentazione descritta, e' passibile definire due tipi record, campo
uno per i nodi del grafo (con
un
per le etichette e un campo puntatore) e uno per gli archi
(con due campi puntatore). Poiche' un grafo orientato puo' contenere
semicicli
•
cicli e durante le operazioni
normalmente necessario rilevarne la presenza,
di
visita
~
e' opportuno cheJ:_
record di tipo "nodo" contengano un ulteriore campo marcatore~
pnodo= "nodo; pramo= "ramo; nodo record etic: char; marca: boolean; succ: pramo end; ramo record head: -pnodo; next: pramo
Riguardo
al nostro problema,
raggiungibile nodo
j
da
im
altro j
ricordiamo che un nodo i
si
se mil grafo esiste un cammino
dig! dal
al nodo i. { E' facile verificare che i nodi raggiungibili
La cultura è un bene dell'umanità (
[email protected])
249
da
un certo nodo i sono tutti i successori di i e tutti
i
nodi
n
raggiungibili da ognuno dei successori di i. Da
questa
definizione -(ricorsiva) segue facilmente la
seguente
versione ricorsiva della procedura.
procedure successori ( p:pnodo ); (* CM: stampa le etichette dei nodi che sono raggiungibili da un nodo di un grafo. Il grafo e' rappresentato mediante lista doppia; p rappresenta il puntatore al nodo di cui si calcolano i nodi raggiungibili. Si assume che, all'inizio della esecuzione della procedura, il campo marcatore di ogni elemento della lista doppia sia a false *)
(* CD: puntatore
var r:pramo;
corrente per la liste degli archi *)
scansione
delle
begin if not p " .marca then--begin (* CA: il nodo puntato da p non e' stato ancora visitato *) p".marca := true; write (p " .etic); (* CM: scansione della lista degli archi uscenti *) r := p".succ; while r nil do begin successori(r".head); r := r".next end end end; (* fine procedura successori *)
Si
puo'
notare
una stretta analogia tra
la
procedura
appena
scritta e quella per la visita in preordine di un albero. Cio' e' naturale grafo.
se
si pensa che un albero differenza
La
tra
le
e' un caso due
procedure
particolare nasce
di
dalla
possibilita' di cicli nel grafo. Vogliamo iterativa.
ora
risolvere
il nostro problema
con
una
procedura
Nel fare questo, si deve tenere conto che, ogni volta
La cultura è un bene dell'umanità (
[email protected])
250
che si passa da un nodo a un successore, e' necessario memorizzare in qualche modo ulteriori successori del nodo
stesso,
menti
a essi si
non
tornare scopo
piu' raggiungibili.
una
In questo modo,
volta che un certo cammino e'
utilizzeremo
una
interrotto.
pila (per le procedure
e
altripuo'
A
tale
funzioni
di
accesso alla pila si veda il problema 20). Una prima versione della procedura e' la seguente:
procedure successoril (p: pnodo); (* CM: versione iterativa della procedura "successori" *) begin init(pilal); (*CA: si assume definita la pila "pilal" *) repeat if /1/ il nodo puntato da p non e' gia' stato visitato then begin /2/ visita il nodo puntato da p; /3/ considera il primo successore sl del nodo p end else /4/ non si puo' seguire ulteriormente il cammino intrapreso; if /5/ il nodo p non era stato gia' visitato ed esiste almeno un suo successore sl then begin /6/ memorizza nella pila il prossimo successore (se esiste); /7/ assegna a p il valore del puntatore del nodo sl end else if not empty(pilal) the~/8/ estrai il nodo affiorante da pilal (successore di un certo nodo n), assegnando a p il valore del suo puntatore e memorizzando nella pila il prossimo successore di n, se esiste until end_; _ _ /9/ non si puo' piu' seguire alcun cammino
La
versione della procedura che abbiamo scritto e' basata
sulla
struttura astratta "grafo". Dobbiamo ora tradurre le frasi che vi compaiono
in istruzioni Pascal,
La cultura è un bene dell'umanità (
[email protected])
adattandole alla
realizzazione
251
del grafo mediante lista doppia. La frase /1/ si traduce immediatamente
in un confronto sul valore del campo "marca" del
puntato da p .
record
La frase /2/ si traduce in un'istruzione di stampa
dell'etichetta del nodo che si sta visitando, mentre la frase /3/ richiede
la
seguente considerazione:
se p punta a un
elemento
della lista rappresentante un nodo del grafo, al primo successore di tale nodo si giunge attraverso la lista dei
successori;
tra-
durremo allora la frase /3/ in un' istruzione di assegnazione alla
variabile
p A.succ,
locale r
cioe'
(di tipo "pramo") del
valore
del
campo
il puntatore iniziale della lista dei successori
del nodo che si e' appena visitato.
Con questa scelta, r punta a
un elemento della lista doppia rappresentante un arco del
grafo.
Se ora traduciamo la frase /4/ nell'assegnazione alla variabile r del valore nil, si vede che la frase /5/ si riduce al test: r nil a r infatti sara' stato assegnato il valore nil o perche' il nodo era gia' stato visitato, oppure perche' la lista dei suoi successori
e' vuota.
campo r A.next e,
La frase /6/ si traduce in un semplice test
sul
nel caso in cui esso non sia nil (cioe' il nodo
p ha almeno un altro successore oltre a quello da cui si prosegue nella
visita),
nella sua memorizzazione nella pila:
con questa
scelta, nella pila si memorizzano puntatori a elementi rappresentanti di archi del grafo. La frase /7/ si traduce nella semplice istruzione di assegnazione p := r A. head mentre la frase /8/ prevede l'estrazione dalla pila dell'elemento affiorante:
La cultura è un bene dell'umanità (
[email protected])
252 pop (pilal, r) e, poiche' esso e' il puntatore a un elemento di tipo "arco", l'assegnazione a p del puntatore al nodo nodo da cui si riprendera' la visita. cord
cui tale arco e' diretto, Inoltre,
se esiste un re-
che segue quello puntato da r nella lista degli
archi,
si
dovra' memorizzare nella pila il suo puntatore (e cioe' il valore del campo r".next). Infine, la condizione di uscita dal ciclo coincide con il test r
=
nil
che si ha quando non si puo' continuare il cammino intrapreso e la pila e' vuota. La procedura completa e':
procedure successoril (p: pnodo); (* CM: versione iterativa della procedura "successori" *) var r: pramo; begin init(pilal); (* CA: si assume definita la pila "pilal" *) repeat if not p " .marca thenbegin p".marca := true; write (p " .etic); r := p " .succ; end else r := nil; if r ni_l_ then begin if r " .next nil then push(pilal~".next); p := r " .head end else if not empty(pilal) thenbegin pop (pilal, r) ; if r " .next nil then push(pila~r " .next); p .- r " .head end until r = nil end; (* fine procedura successoril *)
La cultura è un bene dell'umanità (
[email protected])
253
Nella
seguente
effettuate certo
al
nodo
presente
figura 3 si mostrano le operazioni
che
vengono
momento di seguire un qualunque successore di
(frasi /6/ e /8/):
prima di
seguire
il
nel campo "head" del record puntato da r,
un
puntatore
si memorizza
il valore del campo rA.next, se tale valore e' diverso da nil.
r
p
1. memorizza questo puntatore nella pila next
~~~~~~~~~---1-~~~--~-+--~--[i[j-- - - - :
2. s e gui questo puntatore
'o
!\N ~~'t.J;
,-- ,A.~
.I
I
Figura 3
Il lettore e' invitato a confrontare le procedure presentate
con
quelle descritte nella soluzione al problema 21.
Vogliamo procedure
ora
scritte
Supporremo i ngresso nodi
con
presentare un programma completo che
che la
per
si
il presente problema e
debba scrivere un
valori di tipo carattere),
rappresentazione
di
tale
possibile
~ostruisca
che
legga
da nei
in
memoria
la
di
successori,
raf o e verifichi se da esso
raggiungere tutti gli altri
La cultura è un bene dell'umanità (
[email protected])
le
precedente.
(etichettato
grafo mediante liste
di un nodo del e'
il
programma
matrice di adiacenza di un grafo
utilizzi
nodi l
A
tale
scopo
254
utilizzeremo
la procedura "trasforma" scritta per il problema 26
ed adatteremo la procedura "successori" del presente problema caso
al
di rappresentazione del grafo mediante liste di successori.
La prima versione del programma e':
program sugrafo(input,output); legge da ingresso la matrice di adiacenza di un grafo e (* CM: lo rappresenta mediante liste di successori; legge poi l'etichetta di un nodo e verifica se da esso e' possibile raggiungere tutti gli altri *) const nrnax = ... ; (*CD: numero massimo di nodi del grafo*) ~
"elem; record nodo: integer; next: punt end; tipografo= array [l .• nmax] of record etic: char; marca: boolean; succ: punt end;
punt elem
var grafo: tipografo; x: char; begin (* CM: lettura e memorizzazione del grafo *) trasforma(grafo); (* CM: lettura del nodo *) read(x); (* CM: verifica se dal nodo x sono raggiungibili altri nodi *) if raggiungi(grafo, x) then write('raggiungibili') else write('non raggiungibili') end-.--
Si
noti che nel tipo "tipografo'',
tutti
gli
l'array dei nodi per la memo-
rizzazione delle liste dei successori, e' stato aggiunto il campo "marca'',
necessario per l'analisi del grafo.
Si noti anche
che
l'analisi del grafo e' stata realizzata mediante una chiamata al-
La cultura è un bene dell'umanità (
[email protected])
255
la
funzione
"raggiungi".
Ci resta,
percio',
da
scrivere
la
funzione "raggiungi": essa sara' una funzione booleana che restituira'
il
valore
"true" se e solo se dal nodo
che
gli
viene
passato come parametro sono raggiungibili tutti gli altri:
function raggiungi(g: tipografo; x: char): boolean; verifica se nel grafo g dal nodo x e' possibile (* CM: raggiungere tutti gli altri; g e' rappresentato mediante liste di successori *) var i: integer; begin (* CM: cerca nell'array grafo l'indice i corrispondente nodo ~ che si assume esistente nel grafo *) i
al
:= l;
while (i< nmax) and (grafo[i).etic x) do i : = i + i; -(* CM: (segui la procedura successori a partire da i; wrocedura marchera' tutti i nodi raggiungibili i
la da
*)
successori(i); raggiungi := /1/ tutti i nodi sono stati marcati end; (* fine funzione raggiungi *)
La procedura "successori",
come specificato nella sezione istru-
zioni della funzione, deve marcare tutti i nodi raggiungibili dal nodo corrispondente alla posizione i.
.
Sara' percio' :
e
procedure successori( k: integer); marca tutti i nodi di "grafo" (variabile (* CM: raggiungibili dal nodo corrispondente posizione k *) var p: punt;
La cultura è un bene dell'umanità (
[email protected])
globale) alla
256
begin if not grafo[k].marca then begin grafo[k].marca := true; p := grafo[k].succ; while p nil do begin -successori (pA. nodo); p := pA.next end end end; (* fine procedura successori *)
Infine,
la frase /1/ si tradurra' in un ciclo di scansione
l'array
"grafo",
del-
per controllare che tutti i suoi elementi sono
stati marcati:
i
:= l;
while (i< nmax) and (grafo[i].marca) do i := i + l; -raggiungi := grafo[i].marca
Il programma completo e':
program sugrafo(input,output); (* CM: legge da ingresso la matrice di adiacenza di un grafo e lo rappresenta mediante liste di successori; legge poi l'etichetta di un nodo e verifica se da esso e' possibile raggiungere tutti gli altri *) const nmax = ... ; (*CD: numero massimo di nodi del grafo*) ~
"elem; record nodo: integer; next: punt end; tipografo= array [l .. nmax] of record etic: char; marca: boolean; succ: punt punt elem
var grafo: tipografo; x: char;
La cultura è un bene dell'umanità (
[email protected])
257
procedure trasforma( ..... (* CM: legge da ingresso la matrice di adiacenza d i un grafo e lo rappresenta mediante lis t e di successori *) procedura scritta per il problema 26
function raggiungi(g: tipografo; x : char ) : boolea n; verifica se nel grafo g da l nodo x e' poss i bile ( * CM: raggiungere tutti gli al t ri; r a p p resentato g e' mediante liste di successori *) var i: integer;
procedure successori( k : integer) ; (* CM: marca tutti i nodi di " grafo'' (va r i a bile raggiungibili dal nodo corrispondente posizione k *)
globale) alla
var p: punt; begin if not grafo[k] . marca then begin grafo[k] . marca := true; p := grafo[k].succ; while p nil do begin -successori (p A. nodo); p .- pA.next end end end; (* fine procedura successori *) (* CM: istruzioni della funzione raggiungi *) begin (* CM: cerca nell'array grafo l'indice i corrispondente nodo x, che si assume esistente nel grafo *) i := 1; while (i< nmax) and (grafo[i) . etic x ) do i := i + l; -(* CM: esegui la procedura successori a partire da i; procedura marchera' tutti i nodi raggiungibili i *) successori(i); i := l; while (i< nmax) and (grafo[i).marca) do i := i + l; r a ggiungi := grafo[i).marca end; (* fine funzion e raggiungi * )
La cultura è un bene dell'umanità (
[email protected])
al
la da
258
(* CM: istruzioni del programma *) begin (* CM: lettura e memorizzazione del grafo *) trasforma(grafo); (* CM: lettura del nodo *) read(x); (* CM: verifica se dal nodo x sono raggiungibili altri nodi *) if raggiungi(grafo, x) then write('raggiungibili ' ) else write('non raggiungibili') end-.--
tutti
g li
ESERCIZI PROPOSTI
~
Nelle
soluzioni presentate,
il nodo i niziale compare
come
primo nodo nella stampa. Risolvere l'esercizio con il vincolo che il nodo di cui si vuole calcolare i nodi raggiungibili venga stampato solo se esso e' effettivamente bile
da
se' stesso mediante un cammino,
raggiungi-
cioe' se esso
fa
parte di un ciclo. 2.
Si assuma un grafo gia' esistente in memoria. funzione
che,
Scrivere
una
ricevendo come parametro d'ingresso una
se-
quenza di nodi del grafo, un
cammino.
Risolvere
verifichi che essa ne costituisca l'esercizio
sia nel caso di
rappresentato mediante liste di successori, grafo rappresentato mediante lista doppia.
La cultura è un bene dell'umanità (
[email protected])
grafo
che nel caso di
29 Gestione di una tavola
TESTO Si abbia una tavola in cui la chiave sia una stringa di caratteri (6 caratteri al massimo), betico.
di cui il primo sia un carattere alfa-
La tavola e' rappresentata mediante un array di records,
a cui si accede mediante accesso calcolato hash. La funzione hash che si utilizza e' definita nel seguente modo:
function hash (chiave: tipochiave): integer; begin hash:= 3 * ord(chiave(l]) - ord ('A')) + 1 end;
Si scrivano per questa tavola due prece•ure, rispettivamente per: - la ricerca •i un elemente - l'inserziene •i un elemente
SOLUZIONE Il
teste
•el pr••lema specifica che per la tavola si e'
un'allocazione sparsa, con accesso mediante funzione hash.
La cultura è un bene dell'umanità (
[email protected])
scelto
260
Riguardo alla definizione delle strutture di dati, possiamo assumere gia' dichiarate le seguenti definizioni:
const n = 78; (* CD: dimensione della tavola *) tipodato= record end; tipochiave= array [1 .. 6] of char; tiporec= record chiave: tipochiave; dato: tipodato end; var
tavola: array [l .. n] of tiporec;
Si osservi che: non ci si e' interessati di specificare in dettaglio i campi non chiave della tavola; si e' dimensionato l'array che rappresenta la tavola in modo che
tutti
i valori generabili dalla funzione
nell'intervallo
di
considerato,
a
tale scopo,
chiave
essere
puo'
l'alfabeto
che il primo
uno qualunque dei
stessa; carattere
26
caratteri
cadano si
e'
della del-
inglese.
Dirnensionando generabile
indirizzi della tavola
hash
la tavola a 78 si ha che,
dalla funzione hash,
per ogni indirizzo
si hanno 3 elementi
tavola a disposizione (si veda la figura 1).
La cultura è un bene dell'umanità (
[email protected])
della
261
CHIAVE
hash ('A ..... ') -----> h ash ( 'B ... . . ' )
----->
DATO
1 2 3
4 5
hash ( 'z . ...
6
----->
7
. ' ) ----->
76 77
hash ( ' e ..... ' )
78
Figura 1
Prima di scrivere le procedure, di
••••iam• affrontare il
problema
decidere quale strategia seguire quando si verificano
sioni.
Ricordiamo
colli-
che si verifica una collisione quando la fun-
zione hash restituisce lo stesso valore per due o piu' differenti chiavi.
E' facile rendersi conto che,
nel nostro caso, collide-
ranno tutte le chiavi che iniziano con la stessa lettera. La strategia
che analizzeremo per
di una collisione, per
prima prevede che,
a seguito
inizi una scansione sequenziale della
tavola
cercare o l'elemento desiderato (nel caso che l'accesso
a vvenuto
per la ricerca di un elemento) o un posto libero
tavola (nel caso,
invece,
sia nella
di accesso per inserimento di un ele-
mento) . Scriviamo, percio', la procedura di ricerca adottando questo tipo di strategia.
La cultura è un bene dell'umanità (
[email protected])
262
procedure
ricerca ( key:tipochiave; var trovato: boolean; var j: integer); (* CM: ricerca un elemento nella tavola "tavola", variabile globale; l'accesso alla tavola avviene mediante la funzione "hash"; key rappresenta la chiave dell'elemento da cercare; se la procedura trova l'elemento, pone a true il parametro trovato (altrimenti a false) e fornisce in j l'indirizzo corrispondente *)
var i: integer; begin
~
J
·~
/
:= ~ash (key ( r1])); : = l.;
trovato := false; (* CM: controllo collisione ed eventua le scansione *) repeat if equal(tavola[j).chiave, key) then trovato := true else j := (j mod n) + 1 unt-rr-{trovato) or (j = i) end~fine procedura ricerca *)
La una
procedura
comunica due informazioni al programma
mediante i l parametro "trovato",
chiamante,
che assume il valore
solo se l'elemento cercato e' presente nella tavola,
e
true
un'altra
mediante il parametro · che , se l'elemento e' presente, restituìil ssunta
valore
dell'indirizzo in cui esso e'
esistente
la funzione booleana "e
-
allocato . ] Si
al"
che
e'
confronta,
arattere per carattere, due array di 6 elementi e restituisce il
v alore true se tali array sono uguali,
false altrimenti. Si noti
che
la scansione
la tavola e' usata circolarmente:
termina elementi
o
quando si e' trovato l'elemento o della
tavola
sono stati analizzati,
qu a ndo e si
sequenziale tutti e'
gli
quindi
tornati all'indirizzo iniziale della scansione. Passiamo mento.
ora ad analizzare la procedura d'inserzione di un Per essa,
dobbiamo ridiscutere la struttura dei
La cultura è un bene dell'umanità (
[email protected])
ele-
records
26
della
tavola,
poiche' e' utile avere la possibilita' di d{stin-
guere
tra records disponibili per un'inserzione e
records
che,
invece, sono occupati da dati significativi. Questo
puo ' essere ottenuto aggiungendo al record
"tiporec"
un
campo di tipo "boolean" : tiporec= record ---ri"bero: boolean; dato: tipodato end; L'inserzione chiave, il
nota
la
si accede all'indirizzo fornito dalla funzione hash;
se
record
di
chiave: tipochiave;
un elemento sara' cosi'
acceduto e' libero,
organizzata:
si inserira' l'elemento in
tale
record, altrimenti si iniziera' una scansione sequenziale (usando sempre
la tavola circolarmente) per trovare la
prima
posizione
libera nella tavola in cui poter inserire l'elemento. La procedura che ne risulta e' la seguente:
procedure inserisci (key: tipochiave; dato: tipodato); (*CM: inserisce nel la tavola "tavola" l'elemento che ha per chiave key ; dato rappresenta i campi non chi ve dell'elemento da inserire *) var i: integer;
postotrovato: boolean;
begin i := hash (key[l]); j := i; postotrovato := false; repeat if tavola[j].libero then begin postotrovato : = true; tavola[j].libero .- false; copia(key, dato,j) end else ~ : = (j mod n) + 1 untir-(postotrovato) or (j =i); if not (postotrovato)~ then tavolapiena (* CM: procedura di gestione della condizione di "tavola piena" *) end; (* fine procedura inserisci *)
La cultura è un bene dell'umanità (
[email protected])
264
Si
e' assunta l'esistenza di due procedure:
una
(la
procedura
"copia") che ha il compito di inserire l'elemento (campo chiave e campo
dato) nella posizione
l'altra
("tavolapiena")
che
j
eventualmente trovata libera gestisce la situazione
di
e
tavola
piena, i cui problemi possiamo, in questo esercizio , trascurare. Nella procedura "inserisci" non ci si e' preoccupati di
control-
lare
presente
che l'elemento che si vuole inserire non sia gia'
nella tavola: procedura
di inserzione,
opportunamente sione
se si volesse farlo, si dovrebbe aggiungere, nella una chiamata alla procedura
"ricerca"
modificata · in modo che venga sfruttata la
scan-
della tavola per la ricerca al fine di calcolare anche
posizione
dell'eventuale
record libero per
la
inserzione.
la Le
Erocedure cosi' modificate sono le seguenti:
procedure
ricercai (key: tipochiave; var trovato: boolean; var j: integer; var k: integer); (*CM: ricerca in "tavola" l'elemento di chiave key; se l'elemento e' gia' presente nella tavola, pone trovato a true e fornisce in j la sua posizione; altrimenti fornisce in k l'indirizzo dove l'elemento puo' essere eventualmente inserito; se trovato=true e k=O, la tavola e' piena *)
var i: integer; begin i:= hash(key(l)); j :=i; trovato:= false; repeat if tavola(j].libero then begin if k =o then k := j; ] : = ( j mod n) + 1 end -else if egual (tavola(j].chiave, key) then trovato := true else j := (j mod n) + 1 until (trovato) or (j-;;-i) end~fine procedura ricercal *)
La cultura è un bene dell'umanità (
[email protected])
k .- O;
26 5
procedure inserisci (key: tipochiave; dato: tipodato); ~var presente: boolean;
elem,ins: integer;
lbegin ricercal{key,presente,elem,ins); if presente then erroreins else if ins = O then tavolapiena else copia (key,dato,ins) lend; (* fine procedura inserisci *)
Si osservi che: nella procedura "ricercal" il controllo di uguaglianza delle chiavi
(del
record
acceduto e dell'elemento
viene
eseguito solo se il record acceduto non e ' libero .
nella procedura "ricercal", il
valore
trovata, quindi
in
al parametro k viene
della prima posizione
libera
cercare)
assegnato
eventualmente
modo che l 'eleme;1to da inserire (nel caso,
che la ricercal sia stata chiamata
inserisci)
da
dalla
procedura
venga allocato quanto piu' vicino possibile
al-
l'indirizzo
che la funzione hash fa corrispondere alla
sua
chiave.
valore O per il parametro k indica che non sono
Il
disponibili posizioni libere nella tavola.
nella
procedura
"inserisci",
viene chiamata la
procedura
"erroreins" che si suppone gestisca la situazione in cui gia' presente, nella tavola,
un record con la stessa chiave
dell'elemento che si vuole inserire.
La cultura è un bene dell'umanità (
[email protected])
e'
266
Abbiamo
fin
gestione
qui considerato una delle
delle collisioni,
possibili
strategie
di
quella che prevede l'eventuale scan-
sione sequenziale della tavola. Uno
dei problemi di tale strategia e' che essa tende a
nella
tavola,
collisione.
addensamenti
Come conseguenza,
elemento nella tavola, molti
di chiavi che hanno
dato
formare, luogo
a
puo' capitare che, per cercare un
nota la sua chiave, si debbano analizzare
records che contengono chiavi che con essa non
collidono,
con evidente peggioramento del tempo di ricerca. Si assuma, ad esempio, la tavola di fig.2 e si consideri il caso in cui si voglia cercare l'elemento con chiave 'ART I '.
CHIAVE hash('A .... ') -- > hash ( 'B ••.• ' ) --> hash('C .... ') -->
1 2 3 4 5
DATO
·2-..
- ---- -l-ABBA-~~ · --·-·~ TTO .... --- ·- .-· - --. s ?_l:___ :_:_: : OITO .... ·· j BITTI · . .... •
.:.....:~
--1-·-·---_~~
6
BUCA
7
BERTINI
8 9
CALCO
hash('D .... ') -- > 10
r-
I •••••• J ,---·-!..:_:_:___j I
•• .
ART:J ~_ . :_:.....: : ..:.....J
BRU~~---:
[
~-:- ~4
······· ~ ~--
Figura 2
Non
e'
nostro
alternative;
scopo presentare tutte
considereremo,
La cultura è un bene dell'umanità (
[email protected])
le
possibili
strategie
come esempio, quella che prevede di
267 utilizzare
delle
tavole di trabocco locali,
cioe' destinate
a
contenere gli elementi le cui chiavi hanno colliso in inserzione. In fig. 3
e' schematizzata la struttura di una tavola organizza-
ta al fine di permettere tale strategia.
CHIAVE DATO LIBERO
hash( 'A .... ') -->
1 TAVOLA DI TRABOCCO
2 3
hash('B ....
1
)
-- >
4 5 6
TAVOLA DI TRABOCCO
Figura 3
Ricordiamo prie
che le tavole di trabocco sono anch'esse vere e
tavole
e per esse si potra'scegliere tra i
vari
pro-
tipi
di
allocazione e di accesso. Si
noti che tutta la struttura diventa una tavola ad allocazione
di tipo mista, collegata
in cui allocazione sparsa calcolata e allocazione
convivono.
Vediamo come si puo' rappresentare
questo
tipo di tavola in Pascal, assumendo che per le tavole di trabocco si scelga la allocazione collegata, realizzate, quindi, con liste semplici che collegano i vari elementi della tavola. Le definizioni di dati necessarie sono le seguenti:
La cultura è un bene dell'umanità (
[email protected])
268
const ~
n
=
78;
(* CD: numero massimo di elementi nella tavola *)
tipodato
record
end; tipochiave = array [1 .. 6] of char; tiporec = record chiave: tipochiave; dato: tipodato; libero: boolean end; tabrec record elem:tiporec; case trabocco: boolean of --true: (punt: Alistarec) end; listarec ----record elem: tiporec; punt: Alistarec end; var tavola: array [l .. n] of tabrec;
Si noti che i record che compongono ti che,
l'array
sono record varian-
nel caso il campo "trabocco" valga "true", contengono il
campo puntatore per accedere alla tavola di trabocco
organizzata
come lista semplice. Un esempio di tavola rappresentata secondo le definizioni date e' la seguente:
CHIAVE
DATO
-.-T
hash( 'A ....• )-->l IABBA _ _ _ _ _ -. . 2 ATTO ... . 3 ASSI ... . hash ('B .... ') -->4 BOITO ... . 5
--
La cultura è un bene dell'umanità (
[email protected])
--
LIBERO
false false false false true
TRABOCCO
false false true false false
PUNT
269
ESERCIZI PROPOSTI 1.
Si assuma una tavola organizzata nel modo appena visto sopra e rappresentata,
in Pascal, secondo le definizioni date; si
scrivano, per essa, le seguenti procedure: a) ricerca di un elemento b) inserzione di un elemento c) cancellazione di un elemento.
La cultura è un bene dell'umanità (
[email protected])
La cultura è un bene dell'umanità (
[email protected])
Parte terza Progetti
La cultura è un bene dell'umanità (
[email protected])
La cultura è un bene dell'umanità (
[email protected])
31 Elalleraziene lii testi
TESTO Un testo viene memorizzato sotto forma di lista di paragrafi. Ogni paragrafo e' una lista di parole e di segni d'interpunzione. Ogni parola e' una lista di lettere dell'alfabeto. usando
questa rappresentazione per un testo,
Si noti
gli spazi
che,
bianchi
tra le varie parole non vengono memorizzati.
Scrivere una procedura o funzione Pascal che,
supposto esistente
-
un testo in memoria, legga da ingresso una seçLUenza s di carattsc ri,
scandisca
un paragrafo e cçmti tutte le occorrenze di s nel
paragrafo.
Su s si facciano le seguenti ipotesi: s e' non vuota e lunga al massimo 20 caratteri; se' costituita solo da caratteri dell'alfabeto ed eventualmente blank. e/o
I caratteri blank possono solo essere in prima
ultima posizione,
a significare rispettivamente che
va cercata solo all'inizio e/o fine di parola .
La cultura è un bene dell'umanità (
[email protected])
s
274
Esempio: Paragrafo
"la mamma dell a raga zza ha una gazza ladra"
s = "gazza"
2 occorrenze
s =
1
"
gazza"
s = "la" s = "la s =
"
occorrenza
3 occorrenze
2 occorrenze
"
azza
o
"
s = "ma"
occorrenze
2 occorrenze
SOLUZIONE L'enunciato dati essere
del problema indica esplicitamente le
utilizzati
per
la memorizzazione dei
testi,
strutture che
devono
visibili alla procedura da progettare.
Mostriamo qui la rappresentazione grafica della lista doppia caso
di
dell'esempio
di paragrafo suesposto
e,
nel
definizioni di tipi e variabili che supporremo note.
La cultura è un bene dell'umanità (
[email protected])
seguito,
nel le
275
~
ppar pparola pcar paragrafo
" paragrafo; " parola; " carattere; record contenuto next e nd ; record contenuto next end; record car next end;
parola
carattere
var
Per
pparola; ppar pca r ; pelem char; pcar
testo: ppar;
quanto riguarda la stringa da ricercare ,
e' opportuno memo-
rizzarla senza gli eventuali blank iniziali e finali di caratteri, presenza
o
in un array
utilizzando due variabili booleane per indicare la assenza dei blank.
Una variabile intera
indica
la
lunghezza della stringa (a parte i blank).
Supponiamo che la procedura riceva come parametro il puntatore al paragrafo da esaminare e legga da ingresso la stringa,
stampando
in uscita i risultati.
Le variabili relative alla stringa saranno locali alla procedura, insieme
a una variabile intera utilizzata come contatore del nu-
mero
di occorrenze e a una variabile di tipo "char" per la
tura
della
let-
stringa.
Infine, la sezione istruzioni verra' strutturata in due parti:
La cultura è un bene dell'umanità (
[email protected])
276 procedure conta (parag: ppar; var noccorr: integer); (* CM: legge una stringa da ingresso e conta il numero di volte che tale stringa e' presente in un paragrafo; parag rappresenta il puntatore del paragrafo che bisogna scandire; noccorr rappresenta il risultato *) var
stringa: array [l .. 20 ) of 'A' .. 'Z ' ; lung .integer; b liniz , (* CD: vale true se la stringa in ingre s so contiene blanks iniziali * ) blfina l: boolean; (* CD: v ale true se la stringa in ingresso contiene blanks finali *) eh : char; (* CD: var i abile per la lettura *)
b e g in
/ 1/ l ettura della stringa; /2 / calcolo e stampa del end;
numero della stringa nel p a ragrafo (* fine procedura conta *)
di
occorrenze
La lettura puo' essere immediatamente realizzata per mezzo di
un
ciclo, con due condizioni di uscita, in alternativa: fine
della
stringa (che si assume indicata dalla presenza
ingresso del carattere ' . ') - lettura del carattere blank. Il blocco /1/ verra' cosi' raffinato:
(* CM: lettura della stringa *) bliniz .- false; blfinal . - false; lung := O; readln; read(ch); if Ch= I then begin bliniz .- true; read(ch) end; repe a~
lung := lung + l; stringa [lung] := eh; read(ch) until (eh ') or (eh='·'); if eh = ' ' then ----Slfinal .- true;
La cultura è un bene dell'umanità (
[email protected])
in
277
Si noti l'uso della istruzione "readln": essa e' stata introdotta allo
scopo di evitare la lettura del primo carattere blank
pre-
sente in ingresso in alcune implementazioni del Pascal. \ .si ricorda
che la ragione della presenza di tale carattere e' la seguen-
te: all'inizio di ogni programma la variabile standard "eoln" per il file di input ha valore
- -·-·
11
true 11 ; e' noto che quando per un file
di caratteri x si ha che eoln(x) e' true, allora si ha anche:
cioe' blank.
il
X"
carattere che viene letto in queste condizioni
L'istruzione
lettura
e'
"readln" ha l'effetto di posizionarsi nella
del file "input" al primo carattere significativo
linea d'ingresso corrente e serve, carattere
blank
il
percio',
della
a evitare il
suddetto (le stesse considerazioni sono
primo valide
per le successive linee di ingresso) . Il
passo
parola,
/2/ tenendo
richiede la scansione del
paragrafo
conto del fatto che se bliniz=true
parola allora
per il
confronto deve essere iniziato a ogni inizio di parola, altrimenti a ogni carattere di ogni parola . E'
~in•i necess~ri•
•isperre
di tre puntatori, uno che indichi la parola attualmente in esame, il secondo l'inizio della parte di parola attualmente confrontata e
il
terzo il carattere attualmente
necessarie
le
confrontato.
ulteriori variabili locali (che
Sono
quindi
dovranno
essere
aggiunte alla dichiarazione):
iniz, attuale: pcar; parola: pparola;
(* CD: indica, di volta in volta, da dove deve iniziare le ricerca *) (* CD: puntatore al carattere analizzato *) (* CD: puntatore alla parola analizzata *)
La cultura è un bene dell'umanità (
[email protected])
278
Il blocco /2/ viene cosi' raffinato:
(* CM: calcolo e stampa del numero di occorrenze della stringa nel paragrafo ~) (* CM: inizializzazione del puntatore "parola" in modo che punti alla prima parola del paragrafo *) parola := paragA.contenuto; noccorr := o; (* CM: ciclo di scansione delle parole *) while parola nil ~* CM: scansione di una parola: si conta quante volte la stringa compare nella parola puntata da "parola" *) begin (* CM: posizionamento sul primo carattere della parola *) iniz := parolaA.contenuto; (* CM: ciclo di ricerca della stringa nella parola; se bliniz true, la ricerca e' effettuata solo a partire dal primo carattere della parola; se, invece, bliniz=false, e' effettuata piu' volte, partendo da ogni carattere della parola *) repeat (* CM: ricerca della stringa nella parola; piniz punta al carattere della parola da cui bisogna iniziare a ricercare la stringa *) (* CM: inizializzazione del puntatore che indica il carattere corrente da analizzare *) attuale := iniz; /3/ controlla che la stringa coincida con i caratteri della parola, a partire da quella puntato da iniz. Se coincidono, incrementa noccorr; (* CM: aggiornamento di iniz per una eventuale nuova ricerca *) iniz := inizA.next (* CM: si esce dal ciclo o perche' biliniz=true, e allora la ricerca nella parola andava condotta una volta sola, o perche' iniz=nil, e allora tutte le ricerche sulla parola sono concluse *) until (bliniz) or (iniz = nil); (* CM: posizionamento su una nuova parola *) parola := parolaA.next end; (* CM: stampa del risultato *) writeln; write ('la stringa:"'); if bliniz then write (' '); for nch :=----r-to lung do write (stringa[nch]); if blfinal then write (' '); write ('"compare', noccorr, 'volte nel paragrafo.')
La cultura è un bene dell'umanità (
[email protected])
279
Si
noti
che,
sebbene
la procedura comunichi il
risultato
al
programma chiamante mediante il parametro "noccorr", si e' scelto di far eseguire la stampa del risultato. Resta
ora da raffinare il blocco /3/;
ulteriori
a tale scopo useremo
variabili locali (che quindi dovranno essere
due
aggiunte
nella sezione dichiarazione delle variabili della procedura):
nch: integer; esci: boolean;
La
prima
serve
a contare quanti
caratteri
consecutivi
della
stringa coincidono con la parte di parola che si analizza; condizione necessaria per il successo del confronto e' che, dello stesso, d'ingresso;
alla fine
"nch" sia uguale a "lung", lunghezza della stringa la
seconda
serve a interrompere il
confronto
appena si rilevi che la parte di parola in esame e la stringa
non in
ingresso non coincidono. Particolare attenzione, infine, va posta al problema dei blank finali: se blfinal=true, il confronto avra' avuto
esito positivo solo se i caratteri della parola sono stati
analizzati tutti. Le istruzioni corrispondenti al blocco /3 / sono le seguenti:
nch := O; esci := false; (* CM: ciclo di ricerca della stringa nella parola puntata da parola, a partire dal carattere puntato da iniz *) repeat if attuale A.car = string [nch+l] then (* CA: il carattere attuale della parola e' uguale a quello della stringa *)
La cultura è un bene dell'umanità (
[email protected])
280
begin nch := nch + l; attuale := attuale A.next; (* CM: test sul termine della ricerca: si esce se la parola e' finita oppure la stringa e' stata interamente confrontata *) if (attuale = nil) or (nch = lung) then esci := true end-else ---c*" CA: il carattere attuale della parola e' diverso da quello della stringa e quindi la ricerca e' fallita *) esci := true until esci; (* CM: test sul motivo di uscita dal ciclo per aggiornare, eventualmente, il parametro noccorr *) if (nch = lung) and ((not blfinal) or (attuale nil)) then (* CA: la ricerca ha avuto successo *) noccorr := noccorr + l;
ESERCIZI PROPOSTI 1.
Risolvere l'esercizio assumendo che nella stringa d'ingresso possano comparire i blank in qualunque posizione.
j..
Calcolare la complessita' asintotica di tempo dell'algoritmo realizzato dalla procedura "conta".
3.
Si supponga di aver definito la struttura astratta "stringa" per rappresentare sequenze di caratteri. Le operazioni definite su tale struttura siano le seguenti:
1. create:
() ---> stringa
per creare una stringa vuota;
2. null: stringa ---> boolean
per verificare che una stringa sia vuota·
3. lung: stringa ---> integer
per calcolare 1 . l unghezza di una stringa;
La cultura è un bene dell'umanità (
[email protected])
281
4. appcar: stringa X carattere ---> stringa per appendere un carattere alla fine di una stringa; 5 . concat: stringa X stringa ---> stringa per concatenare due stringhe; 6. substr: stringa X integer X integer ---> stringa per estrarre una sottostringa da una stringa.
Scrivere un programma che consenta di manipolare
interatti-
vamente
accettando
sequenze
stringhe;
il
programma deve
lavorare
di comandi corrispondenti alle operazioni definite
sopra ed eseguendole. possibilita'
di
Il programma deve prevedere anche
la
costruire stringhe con caratteri letti
da
ingresso e stampare stringhe in uscita.
La cultura è un bene dell'umanità (
[email protected])
31 Gestione di programmi
TESTO
Si
assuma che i programmi gestiti da un sistema operativo (iden-
t i ficati
da
un codice opportuno) possano trovarsi
in
uno
de i
seguenti stati: (a) in esecuzione (b) pronti per l'esecuzione (c) in attesa di eventi esterni Scrivere
una
procedura Pascal che gestisca il passaggio
programma "(individuato
dal relativo codice~ da uno stato
di
un
a
un
altro,
ricevendo in ingresso un intero i compreso tra 1 e 5, ch e
i ndica
il
tipo di transizione richiesto,
secondo
le
seguenti
convenzioni: 1:
accettazione
di
un programma e assegnazione a
esso
del l o
stato (b) 2:
eliminazione di un programma attualmente nello stato (a )
3:
passaggio di un programma dallo stato (a) allo stato (b)
4:
passaggio di un programma dallo stato (a) allo stato (c)
5:
passaggio di un programma dallo stato (c) allo stato (b)
La cultura è un bene dell'umanità (
[email protected])
283
Eseguita
l'operazione richiesta,
la procedura deve decidere
se
far passare un programma dallo stato di pronto (b) all'esecuzione (a) e, in caso affermativo, sceglierlo, tenendo presente che: - i programmi in stato di pronto devono essere gestiti a coda; - devono sempre essere in esecuzione non piu' di tre programmi; devono
sempre essere in esecuzione non meno di tre
programmi,
salvo nel caso in cui la coda sia vuotal
SOLUZIONE Scopo della procedura e' la gestione dei programmi da mandare esecuzione,
sulla
base
delle
informazioni di volta
in
in
volta
ricevute. E' necessario che la procedura comunichi all'esterno il programma selezionato per l'esecuzione: il modo piu' semplice in cui questo puo'
essere
indichi
fatto e' per mezzo di un parametro
il codice di tale programma,
variabile,
dccompagnato da
un
che altro
parametro di tipo booleano che indichi se e' stato selezionato un programma. Le strutture di dati per mezzo delle quali vengono memorizzate le informazioni relative allo stato dei programmi saranno realizzate con variabili globali. Dalla
specifica del problema si vede che e' necessario
zare i programmi pronti in una coda; nita
per questo assumeremo defi-
la coda "coda" (variabile globale),
La cultura è un bene dell'umanità (
[email protected])
memoriz-
i cui elementi rappre-
284
sentano
codici
realizzazione
di programmi (si rimanda al problema 20 della
coda
e per le relative
per
procedure
di
la ge-
stione). Inoltre sia
assumeremo che nel campo di visibilita' della
procedura
definita una variabile globale per memorizzare il numero
di
programmi di volta in volta in esecuzione:
var
inesec: o •• 3;
Infine,
le
suddividere
(* CD: numero di programmi in esecuzione *)
operazioni che la procedura deve eseguire si possono in
due passi,
come mostrato dalla
seguente
prima
versione della procedura:
procedure seleziona(prog: codice; trans: 1 .. 5; var esec: boolean; var progresec: codice); (* CM: esegue, sul programma "prog", l'operazione specificata dal parametro "trans"; inoltre, se puo' mandare in esecuzione un programma, comunica questo fatto al programma chiamante mediante il parametro "esec" posto a true; il codice del programma eventualmente mandato in esecuzione e' passato in "progresec" *) begin /1/ trattamento delle informazioni ricevute in ingresso; /2/ eventuale invio di un programma in esecuzione end; (* fine procedura seleziona *)
Le informazioni ricevute in ingresso producono: l'inserimento 1,
3
di un elemento nella coda se trans e' pari
o 5;
la modifica di inesec se trans e' pari a 2, 3 o 4; Quindi il passo /1/ puo' essere
La cultura è un bene dell'umanità (
[email protected])
raffinato come segue:
a
285
if trans in [l,3,5] then enqueue(coda,prog): if trans in [2,3,4] then inesec := inesec - 1 Per quanto riguarda il passo /2/, deve essere inviato un programma
in esecuzione se la coda non e' vuota e i programmi in esecu-
zione sono meno di tre:
if (inesec < 3) and (net empty(coda)) then /3/ invia in esecuzione il primo programma della coda else /4/ non inviare programmi in esecuzione
Val
la
pena di notare come a ogni chiamata della
possibile perche'
dover al
mandare
in esecuzione al
piu'
procedura un
e'
programma,
massimo puo' terminare l'esecuzione di uno dei
pro-
grammi o arrivare un nuovo programma in stato di pronto. Raffiniamo il passo /3/:
begin (* CA: la coda non e' vuota *) dequeue(coda, progresec); esec := true; inesec .- inesec + 1 end
Il passo /4/ si traduce molto semplicemente nell'istruzione: esec .- false La
versione completa della procedura viene quindi ad
seguente:
La cultura è un bene dell'umanità (
[email protected])
essere
la
286 procedure seleziona(prog: codice; trans: 1 .. 5; var esec: boolean; var progresec: codice); (* CM: esegue, sul programma "prog", l'operazione specificata dal parametro "trans"; inoltre, se puo' mandare in esecuzione un programma, comunica questo fatto al programma chiamante mediante il parametro "esec" posto a true; il codice del programma eventualmente mandato in esecuzione e' passato in "progresec" *) begin (* CM: trattamento delle informazioni ricevute in ingresso *) if trans in [1,3,5] then (* CM: inserisci l'elemento con codice prog nella coda *) enqueue(coda, prog); if trans in [2,3,4] then (* CM: i programmi in esecuzione diminuiscono di uno *) inesec := inesec - l; (* CM: eventuale invio in esecuzione di un programma: deve essere inviato in esecuzione un programma se i programmi in esecuzione sono meno di tre e la coda non e' vuota *) if (inesec < 3) and (not empty(coda)) then (* CM: invio di un programma in esecuzione *) begin dequeue(coda, progresec); esec := true; inesec := inesec + 1 end else (*°"CA: non deve essere inviato in esecuzione nessun programma *) esec := false end; (* fine procedura seleziona *)
La
versione della procedura finora presentata assume che i
dati
forniti dall'esterno siano corretti, cioe' che quando si richiede il passaggio di un programma p dallo stato Sl allo stato S2, p si trovi realmente in Sl. Qualora una tale assunzione non possa essere fatta, e' necessario che
la
devono
procedura effettui i relativi essere
controlli;
in
disponibili informazioni riguardo allo
tal stato
caso di
tutti i programmi, non solo di quelli in stato di pronto. Un
possibile
modo di rappresentazione
La cultura è un bene dell'umanità (
[email protected])
consiste
nell'associare
287
sempre
un
record
a ciascun programma riunendo i
stato di attesa (c) in una lista semplice,
programmi
in
associando quelli
in
esecuzione a un array di tre puntatori. Assumeremo
percio' che,
oltre alla coda "coda" (i cui
elementi
sono ora puntatori), siano definiti i seguenti tipi e variabili:
"elem; record cod: codice; next: punt end; var c: punt; -r*" CD: puntatore iniziale della lista dei programmi nello stato (c) *) a: array [1 .. 3] of punt; (*CD: programmi nello stato (a) *) ~
punt elem
Al passaggio di un programma da uno stato all'altro e' sufficiente trasferire il record da una struttura all'altra. La
struttura
generale della procedura rimane invariata,
modificano i raffinamenti dei vari passi. deve
Inoltre,
si
la procedura
segnalare all'esterno l'eventuale verificarsi di un
nei dati di ingresso:
ma
errore
introduciamo a tale scopo un nuovo pararne-
tro di tipo booleano. Un primo raffinamento della procedura viene quindi ad essere:
procedure
seleziona (progr: codice; trans: 1 .. 5; var esec, error: boolean; var progresec: codice);
begin (* CM: trattamento delle informazioni ricevute *) case trans of ~~l: /3 / -Verifica che non esista alcun programma con lo stesso codice di progr : in tal caso inserisci progr nella coda; 2: /4/ verifica che progr sia in esecuzione : in tal caso eliminalo;
La cultura è un bene dell'umanità (
[email protected])
288
3:
/5/
4:
/6/
5:
/7/
verifica spostalo verifica spostalo verifica spostalo
che progr sia in esecuzione in tal caso nella coda; che progr sia in esecuzione in tal caso nella lista; che progr sia nella lista : in tal caso nella coda
end; (*CM: eventuale invio di un programma in esecuzione *) if /8/ almeno uno dei puntatori dell'array non e' nil e la coda non e' vuota then /9/ togli dalla coda l'elemento di testa e fallo puntare dal primo puntatore disponibile dell'array (* fine procedura seleziona *)
si assumeranno definite le seguenti funzioni e procedure:
function isinesec (p: codice): 0 • • 3; (* CM: vale O se p non e' in esecuzione; altrimenti fornisce posizione di p nell'array "a" (1,2 o 3) *)
la
function isinlista (p: codice): boolean; (*CM: vale true se p e' nello stato (c), cioe' e' presente nella lista c *)
function isincoda (p: codice): boolean; (* CM: vale true se p e' presente nella coda "coda" *)
procedure inlista (p: punt) ; (* CM: inserisce il record puntato da p nella lista c *)
procedure outlista (p: codice, var pu: punt); (* CM: elimina dalla lista c il record con p nel restituisce in pu il suo puntatore *)
Lasciamo al lettore,
come esercizio,
campo
cod
e
la codifica delle suddette
procedure, presentando solo la loro utilizzazione nel corpo della
La cultura è un bene dell'umanità (
[email protected])
289
procedura seleziona, come segue.
procedura seleziona (progr: codice; trans: 1 .. 5; var esec, errar: boolean; var progresec: codice); var
indice: 1. . 3 ; p: punt;
( * CD: indice per la ricerca nell'array *) (* CD : p untatore a usiliario *)
begin (* CM: trattamento delle i nformazioni ricevute in ingresso * ) case trans of --1 : (* CM:- verifica che non esista alcun programma con lo s t esso cod i c e di progr e in tal caso inserisci progr nella coda *) if (isinesec(progr) O) or (isinlista(progr)) or (isincoda(progr)) the!lerror := true else begin (* CA: non esiste alcun programma c on lo stesso c odice *) error := f alse; new(p); p A. cod := progr; enqueue(coda, p) end; 2 (* CM: verifica che il programma sia in esecuzione e in tal caso eliminalo *) begin indice:= isinesec(progr); if indice O then (* CA: il programma e' in esecuzione *) begin error := false; dispose (a[indice)); a[indice) := nil end else error := true end_;__ 3 ~CM: verifica che il programma sia in esecuzione e in tal caso spostalo nella coda *) begin indice:= isinesec (progr); if indice O then (* CA: il programma e' in esecuzione *) begin error := false; enqueue(coda,a[indice)); a[indice] .- nil end else error := tru e end_;__
La cultura è un bene dell'umanità (
[email protected])
290
4
5
(* CM: verifica
che il programma sia in esecuzione in tal caso spostalo nella lista *)
e
begin indice:= isinesec(progr); if indiceO then (* CA: il programma e' in esecuzione *) begin error := false; inlista(a[indice]); a[indice] := nil end else error := true end_;__ ~CM: verifica che il programma sia nella lista e in tal caso spostalo nella coda *) if isinlista(progr) then begin errar := false; outlista(progr,p); enqueue(coda,p) end else errar := true
end;
~CM:
eventuale invio in esecuzione di un programma: deve essere inviato in esecuzione un programma se i programmi in esecuzione sono meno di tre e la coda non e' vuota *) if not(error) nil)) then if ((a[l] = nil) or (a[2] = nil) or (a[3] and (not codavuota(coda))-then begin (* CM: invio di un programma in esecuzione *) esec := true; dequeue(coda, p); progresec := p A. codice; i f a[l] = nil then a[l] := p else if a[2] = nil then a[2] := p else a[3] := p end else ~CA: non deve essere inviato in esecuzione nessun programma *) esec := false end; (* fine procedura seleziona *)
La cultura è un bene dell'umanità (
[email protected])
291
ESERCIZI PROPOSTI
1.
Scrivere le procedure e le funzioni le cui intestazioni sono state descritte nel corso dello svolgimento dell'esercizio.
2.
Si
vuole
gestire
"quasi-coda"
l'accesso a una stampante
(rappresentata
in Pascal
mediante
mediante
una
record
e
puntatori). Le richieste di stampa sono del tipo: < nf, lf, tu >
dove nf indica il nome del file da stampare, lf e' un intero positivo tu
che indica la lunghezza del file,
e il val ore di
indica se la richiesta e' da parte di un utente
normale
(tu=O) o privilegiato (tu=l) . Le richieste vengono messe nella "quasi-coda" nell'ordine di arrivo.
Quando la stampante e' pronta per una nuova stampa,
il successivo file da stampare viene prelevato dalla "quasicoda" secondo la seguente regola:
si sceglie il primo
di utente privilegiato che sia tra le prime 8 richieste; esso minore
non
esiste,
si
sceglie il primo file
o uguale a 3 che sia tra le prime
5
di
file se
lunghezza
richieste;
se
anch'esso non esiste, si sceglie il primo file de l la "quasicoda". Inoltre, allo scopo di valutare l'efficacia della disciplina di gestione della stampante,
ogniqualvolta siano stati man-
dati in stampa 30 files, si vuole calcolare:
La cultura è un bene dell'umanità (
[email protected])
292
il numero di files di utenti privilegiati mandati in stamp a ; - il numero di files di lunghezza minore o uguale a 3
mandati
in stampa; - la lunghezza media dei files mandati in stampa. Scrivere
le funzioni/procedure Pascal necessarie a
gestire
la "quasi-coda" e ad eseguire le valutazioni richieste .
/ "
; _)
L. D
+ -~.
(4- '1
'-
-
I
~
,,?·
'*'ì
I
La cultura è un bene dell'umanità (
[email protected])
'\
32 Valutazione di una espressione aritmetica
TESTO
Scriv ere un frammento di programma Pascal che , supposto esistente in memoria un albero binario, rappresentante un'espressione aritmetica, con i nodi intermedi etichettati con caratteri scelti fra
' + ',
1_ I
legga
'*'
e le foglie etichettate con caratteri alfabetici,
e memorizzi opportunamente una sequenza di coppie
tere alfabetico, tico
numero intero> in cui ciascun carattere alfabe-
compare al piu' in una coppia e calcoli e stampi il
dell'espressione
Il
programma deve comunicare che la linea spezzata
esce
dai
segmento
limiti e'
del rettangolo (il
infatti
fuori
punto
finale
dal rettangolo) e
che
dell'esempio dell'ottavo ci
sono
2
sovrapposizioni (fra i segmenti 2 e 6 e fra i segmenti 7 e 8) e 7 intersezioni (relativamente alle coppie di segmenti:
1 e 4,
1 e
6, 2 e 7, 2 e 8, 4 e 7, 4 e 8, 6 e 8).
Iniziamo, mediante nello
allora,
il
progetto dell'algoritmo,
raffinamenti successivi.
sviluppo
dei
vari
passi
versione finale del programma.
che
condurremo
Le variabili che introdurremo sararnno
poi
definite
nella
Un primo raffinamento puo' essere
il seguente:
La cultura è un bene dell'umanità (
[email protected])
316
begin
/1/
lettura e memorizzazione delle coordinate dei vertici del rettangolo; lettura del numero di segmenti che compongono la spezzata e delle coordinate del punto iniziale; lettura dei dati relativi a ciascun segmento e calcolo del numero delle sovrapposizioni e intersezioni tra essi
/2/ /3/ end. Al
passo
/1/,
le coordinate lette sono quelle di
due
vertici
opposti del rettangolo, ma non e' noto l'ordine con cui esse sono presenti in ingresso. e
E' quindi opportuno verificare tale ordine
memorizzarle in modo che sia possibile nel seguito distinguere
il punto con ascissa minima da quello con ordinata massima. ------------------ frase /1/ ------------------
(* CM:
lettura e memorizzazione delle coordinate dei del rettangolo *) readln (xmin, ymin, xmax, ymax) ; if xmin > xmax then scambia (xmin, xmax); if ymin > ymax then scambia (ymin, ymax)
La di
procedura "scambia" dovra' semplicemente scambiare il due
variabili
intere,
passatele
come
vertici
v alore
parametri.
Il
raffinamento della frase /2/ e' immediato: ------------------ frase / 2/
-------------------
(* CM: lettura del numero di segmenti *) readln (nseg) ; (* CM: lettura delle coordinate del punto iniziale della spezzata *) readln (x,y); (* CM: verifica di contenimento nel rettangolo *) if (x < xmin) or (x > xmax) or (y < ymin) or (y > ymax) then writeln('il punto iniziale e'' fuori-cl:el rettang o lo')
La cultura è un bene dell'umanità (
[email protected])
317
La
verifica di contenimento di un punto nel rettangolo
sulla
verifica di appartenenza di due valori (le due
si
basa
coordinate
del punto) a un intervallo: xmin Km,
viene ripetuto i l procedimento s ul la meta' della
tavola che contiene le chiavi superiori a 1':n . opo ogni confronto, 1imensione
o la ricerca termina con successo oppure la
della tavola su cui la ricerca continua sara' all'in-
circa dimezzata rispetto alla dimensione originaria. Percio', dopo h confronti
la tavola che rimane da analizzare ha,
La cultura è un bene dell'umanità (
[email protected])
3 59
al massimo, dimensione par i all'intero appena superiore a: h n /
2
(se n e' il numero
di elementi presenti
Nel caso peggiore ,
quind i ,
nella tavola) .
il metodo r i chied e O(log n)
(i logaritmi si intendono in base 2) confro n t i . La cor ri s p ondente procedura in Pascal e ' :
procedure r icbin (k: tipochiave ; var i: integer); ( * CM: ricerca binaria in una tavola che s i assume ordi nat a * )
procedure ricbinl (a,b: integer); (* CM: procedura ricorsiva che esegue la r i cerca binaria nella parte di tavola compresa tra gli indici a e b *)
begin if b < a then i := o else begin i := (a+b) div 2; if tavola[i].chiave > k then ricbinl(a, i-1) else if tavola (i).chiave< K ~~ then ricbinl(i+l, b) end end; (* fine procedura ricbinl *)
( * istruzioni della procedura ricbin *) begin ricbinl(l,n) end; (* fine procedura ricbin *)
Si osservi che : la
procedura che realizza la vera e propria r icerca b i n a ri a
e' la procedura "ricbinl", che e' stata definita all ' interno
La cultura è un bene dell'umanità (
[email protected])
360
della
procedura "ricbin" affinche' i parametri "a"
utili
solo per la ricerca,
"b",
non siano visibili all'esterno.
la procedura piu' esterna che,
E'
e
con la prima chiamata
a
"ricbinl", assegna i valori iniziali a tali parametri. - se il record cercato non e' presente nella tavola, il valore assunto dal parametro "i", e' zero . Come abbiamo visto,
nella ricerca binaria viene confrontato sem-
pre il record di mezzo della tavola che ancora rimane da zare:
questo
procedimento
puo' essere
schematizzato
analizmediante
quello che viene chiamato l'albero binario di decisione, in cui i valori
dei
vengono eseguire
nodi corrispondono alle posizione della
via la
via
considerate per il
confronto.
tavole
che
Supponendo
di
7)
il
ricerca su una tavola con 7 elementi,
(n =
corrispondente albero di decisione e':
Come si vede, Se
la
chiave
la prima posizione che si analizza e' trovata e' minore di quella
successiva posizione sara' =
6
(1+3)/2 = 2,
cercata,
( 1+7) /2 allora
altrimenti sara'
4. la
( 5+7) /2
e cosi' via.
Nell'albero di decisione, un qualunque cammino dalla
radice a un
nodo rappresenta la sequenza delle posizioni della tavola in sono
=
presenti
i
record che vengono analizzati
La cultura è un bene dell'umanità (
[email protected])
o
trovando
cui la
361
chiave
cercata
o
determinando che essa non e'
presente
nella
tavola: in quest'ultimo caso, il cammino giunge fino ad una delle foglie.
Ricordando
la relazione che sussiste tra il
numero
di
nodi
di un albero del tipo mostrato in figura e la sua profondi-
ta',
e'
facile vedere che l'algoritmo
eseg~e
un numero di
con-
fronti pari a O(log n).
La
schematizzazione vista per rappresentare il
suddivisione ricerca tavola
di
binaria, non
allocazione
sia
una ci
tavola organizzata
sequenzialmente
conduce ad analizzare il caso
organizzata
collegata,
procedimento
sequenzialmente,
ma
in
di
nella cui
la
secondo
la
ed in particolare come albero binario di
ricerca. Supponiamo
che
si siano dichiarate le seguenti
definizioni
di
tipo per l'albero binario di ricerca.
punt tiporec
"tiporec; record chiave: tipochiave; dato: tipodato; figliosin, figliodes: punt end;
var alb: punt; (* CD: puntatore alla radice dell'albero *)
La procedura di ricerca su questa struttura e': procedure albric (p: punt; k: tipochiave; vari :punt); (* CM: esegue la ricerca di un elemento su un albero binario di ricerca; p rappresenta il puntatore alla radice dell'albero, k la chiave da cercare, ed i il puntatore del record cercato; se tale record non esiste, i viene posto a nil *)
La cultura è un bene dell'umanità (
[email protected])
36 2
begin i f p = nil then i := nil else if pA.chiave = k then i := p else if pA.chiave > k then albric(pA.figliosin, k, i) else albric(pA.figliodes, k, i) end; (* fine procedura albric *)
Si
puo'
notare
che
il
numero
di
confronti
necessari
e'
linearmente proporzionale alla profondita' dell'albero; e' quindi importante
che,
durante la gestione della tavola
rappresentata
mediante un albero binario di ricerca, le inserzioni e le cancellazioni siano eseguite in modo tale che la profondita' dell'albero stesso sia minimizzata. Ritorniamo
ora
al caso della ricerca binaria
eseguita
tavola organizzata secondo l'allocazione sequenziale; do,
seppure
elenco
su
una
tale meto-
ispirato al modo in cui un essere umano consulta un
ordinato
per la ricerca di un elemento,
non
coglie
il
fatto che la posizione in cui si esegue il confronto nella tavola che rimane da analizzare non e' indipendente dalla chiave che cerca:
si
se, ad esempio, si sta cercando nel dizionario un termine
che inizia con la lettera V,
si tendera' ad aprire il dizionario
alla pagina piu' vicina alle ultime che non a quella centrale: in questo
modo,
l'elemento cercato si trovera' prima,
poiche'
ad
ogni passo si tendera' gradualmente ad avvicinarsi ad esso. Per
tenere
l'algoritmo posizione
conto
di
questa osservazione
si
puo'
modificare
di ricerca binaria eseguendo il confronto non mediana
della tavola ma sulla
mediante la seguente espressione:
La cultura è un bene dell'umanità (
[email protected])
posizione
i
sulla
ottenuta
363
i dove
Ka
(k - Ka) /
rappresenta
posizione
della
dell'ultimo.
Kb - Ka) )
* n
la chiave del record che occupa
tavola che si deve analizzare e
La
differenza
tra
ctue chiavi e'
la
Kb
prima
la
fatta
chiave rispetto
all'ordinamento che sussiste tra le chiavi della tavola. L'algoritmo
che
interpolazione"; metodo
risulta
esso
e'
chiamato
"ricerca
mediante
ha una complessita' asintotica uguale
ricerca
medie
dipendono fortemente dalla distribuzione dei valori della
chiave
tavola.
(ossia
quando
mediante
h~nno
mentre
le
L'ottimo si raggiunge con distribuzione i
nell'intervallo pratici
binaria
al
prestazioni
nella
della
ne
valori
presenti
[Ka, Kb)): in questo
variano caso,
uniformemente
alcuni
esperimenti
mostrato che il comportamento medio della
interpolazione
e'
migliore di
quello
uniforme
della
ricerca ricerca
binaria per valori di n maggiori di 500.
ESERCIZI PROPOSTI
1.
Scriv8re
una procedura Pascal che realizzi
l'algoritmo
di
ricerca mediante interpolazione. 2.
Data
una tavola rappresentata mediante un albero binario di
ricerca,
trovare un algoritmo di inserimento di un elemento
nella tavola che minimizza la profondita' dell'albero. 3.
Scrivere una procedura iterativa che realizzi l'algoritmo di ricerca binaria.
La cultura è un bene dell'umanità (
[email protected])
38 Ordinamento di un insieme
TESTO
Scrivere una procedura che ricevendo in ingresso restituisca
ordinato
secondo
un vettore,
valori non decrescenti
dei
lo suoj
elementi.
SOLUZIONE
Abbiamo elemento
visto
nell'esercizio 37 ché il tempo di ricerca
di
un
in un insieme di n elementi puo' essere dell'ordine
di
(log n) solo se l'insieme stesso e' ordinato. Questa è' una delle ragioni per cui il problema di ordinare un insieme e' stato molto studiato
in informatica e sono stati proposti diversi
per la sua soluzione, rispet~o
algoritmi
con l'obiettivo di migliorare l'efficienza
alle soluzioni che via via erano disponibili.
Noi presenteremo,
anche per questo
problema, diversi algoritmi,
analizzando pregi e difetti di ognuno. Nel seguito assumeremo che l'insieme
da ordinare sia rappresentato mediante un array
definito:
La cultura è un bene dell'umanità (
[email protected])
cosi'
365
const
n
= ...
tipoins
array [l .. n] of tipobase;
dove "tipobase" puo' essere un qualunque tipo, con il vincolo che sia
definito
valori.
Il
un
ordinamento
sull'insieme
dei
corrispondenti
nostro problema e' quello di ordinare il vettore per
valori non decrescenti delle sue componenti. La
prima
soluzione si basa sulla semplice osservazione
ordinamento
si puo' esèguirè mediante una serie di
che
un
ricerche
di
minimo: Sull'insieme
di
n elementi si ricerca il minimo e
scambia con quello che compare in prima
posizione;
si si
ripete poi il procedimènto sull'insieme di n-1 elementi ottenuto cosi'
dall'originario ignorando il primo elemento e via
fino
all'insieme
formato
da
un
unico
elemento. Questo algoritmo e' realizzato in Pascal dalla seguènte procedura ricorsiva (il nome selectsort deriva dal fatto che l'algoritmo e' in
genere
chiamato
"selection
sorting",
ordinamento
per
selezione).
procedure selectsort (var ins: tipoins); (* CM: ordina il vettore ins per valori non decrescenti delle sue componenti *) procedure ordl (i: integer); (*CM: ordina il sottovettore ins[i] .... ins[n] con il metodo del "selection sorting" *) vari, j, imin: integer; app: tipobase;
La cultura è un bene dell'umanità (
[email protected])
366
begin if i < n then begin (* CM:
calcolo dell'indice corrispondente minimo tra ins[i] e ins[n] *)
al
imin := i; for j := i+l to n do if ins[j] =pivot) and (j > i)
do]:= j if i
l;
< j
then scarnbia(ins[i], ins[j]) until (i >= j) ; if ins[i] >= pivot then i := i - l; scambia(ins[i], ins[m]); partiziona := i end; (* fine funzione partiziona *)
La cultura è un bene dell'umanità (
[email protected])
372
Si noti che: - l'indice i non puo' mai superare il valore n poiche' il
suo
e' condizionato dal fatto che i sia minore di
incremento
j
(che, posto inizialmente pari a n, puo' poi solo diminuire); l'indice
j,
analogamente,
non
puo' mai
assumere
valori
minori di m; - l'indice
i e' utilizzato in modo che le componenti comp rese
tra (m+l) e (i-1) sono - l 'indice j,
invece,
s~mpre
minori del pivot;
in modo che le componenti comprese tra
(j+l) e n sono sempre maggiori o uguali al pivot; - all'uscita del ciclo di repeat,
quindi,
o l'indice i punta
alla componente maggiore o uguale al pivot "p i u' a sinistra" tra
ins[m+l]
ed
in~[n]
decrementa i di 1), pivot
ed
e
si
oppure punta alla componente minore del
"piu' a destra".
scambiati
(nel qual caso ins[i]>=pivot
Percio',
ins[i] e
ins[m]
vengono
il valore di i rappresenta l'indice al
quale
corrisponde il pivot; - si e' assunto l'esistenza della procedura scambia. Possiamo ora scrivere la procedura di ordinamento. procedure quicksort (var ins: tipoins); (* CM: ordina il vettore ins per valori non il metodo "quicksort" *) function partiziona ........ .
procedure scambia .......... .
La cultura è un bene dell'umanità (
[email protected])
decrescenti,
con
373
procedure quicksortl (h,k: integer); (* CM: procedura ricorsiva che richi ama par t iziona *) v ar p: intege r; begin if h < k then begin p := parti ziona (h, k); quicksortl( h , p-1); quicksortl (p+l, h) end end; (* fine procedura qui c k sortl * )
(* istruzioni de l la proc e dura quicksort *) begin quicksortl (l , n) en d; (* fi ne proc edu ra quicksort *)
Si
e'
gia'
detto
che la
complessita'
f (n )
della
procedura
"qui c k sort" e' , nel caso medio, f (n)
=
O(n
*
log n) .
Non dimostreremo questa p roprieta' ; caso peggiore, si ha f(n) Per
fare
questo ,
=
mostriamo ,
invece, che, nel
O(n ** 2).
ana li zziamo il comportamento della
procedura
"partiziona" . Indichiamo con p(n) la sua complessita'. Si
puo' notare che durante il ciclo di repeat ogni elemento
vettore e' confrontato con il piv o t al massimo due volte.
del
Infat-
ti ,
tutti gli elementi che si trovano dalla seconda posizione in
poi
f ino
al
primo elemento ma ggiore o uguale
sottoposti ad un solo confronto; si
al
pivot,
sono
cosi' anche quegli elementi che
trovano dall'ultima posizione fino al primo
elemento
minore
del pivot (spostandosi verso sinistra) . Per gli altri,
si potra' avere al massimo un ulteriore confronto
dopo lo scambio subito . eia' porta a concludere che p(n)
=
La cultura è un bene dell'umanità (
[email protected])
O(n) .
3 74
Passando
alla procedura "quicksort",
si puo' notare che,
configurazione dei dati e' tale che,
ad ogni passo, il partizio-
namento fa si' che il pivot e' restituito nella posizione na, n.
vi
media-
sara' un numero di chiamate ricorsive dell'ordine di log
Il caso peggiore,
mento
se la
restituisce,
comunque, e' quello per cui il partizionaad
ogni passo,
il pivot i n
una
posizione
estrema cosicche' si ha sempre una successiva chiamata per
l'or-
dinamento di un vettore con un numero di componenti minore di uno rispetto al vettore precedente. In questo caso il partizionamento verra' invocato n volte per operare su vettori rispettivamente di n, n-1, n-2, ... , 2 componenti . Si ha percio' che f(n) = O(n E' poi immediato verificare che,
f(n)
fl (n
Riguardo allo spazio di memoria, siva
**
2).
nel caso peggiore,
**
si ha anche
2).
si noti che la procedura ricor-
necessita di una pila la cui dimensione e' dell'ordine
numero di chiamate ricorsive;
del
si noti che il vettore da ordinare
e' globale rispetto alla procedura ricorsiva "quicksortl". Percio' si avra' che, nel caso peggiore, l'occupazione di memoria della
procedura
quicksort
sara'
dell'ordine
di
n;
si
puo'
dimostrare, pero', che nel caso medio la dimensione della pila e' dell'ordine di log n. Tutti
gli
algoritmi
finora visti hanno una
valutata nel caso peggiore, e O(n Ci
si puo' chiedere,
inferiore
**
complessita'
che,
2).
a questo punto,
qual e' la
alla complessita' del problema
delimitazione
dell'ordinamento.
Per
fare questo, come e' noto, si cerca di individuare la piu' grande
La cultura è un bene dell'umanità (
[email protected])
375 g tale che si possa affermare che la complessita' del problema e' lì (g(n)). Si ricorda che la complessita' di un problema e' lì (g(n)) se esiste un algoritmo per la risoluzione di quel problema i l cu i costo
di
esecuzione
considerazioni
e'
dell'ordine
di
scegliamo come misura della
g(n).
queste
In
complessita'
(cioe'
come operazion e dominante) il confronto tra elemE, n ti. Si
puo'
dimostrare
complessita'
che
la
alla
*
log n) .
si puo' allora porre il problema di trov are un algoritmo
ordini
un vettore di n elementi con un costo di esecuzione
l'ordine di (n un
inferiore
dal problema dell'ordinamento e' (n
Ci
delimitazione
tale
*
del-
log n).
algoritmo e' quello che viene chiamato "merge
(ordinamento per fusione). zione:
che
sorting"
Esso si basa su una semplice osserva-
supponendo di disporre di due vettori ordinati per valori
non decrescenti,
e' possibile ottenere un nuovo vettore ordinato
contenente tutte le componenti dei vettori originari, mediante un procedimento di fusione (merge) realizzato dalla seguente dura
(in cui si assume che i vettori orig i nari siano i n
precerealta'
due sottovettori di un unico vettore ins, definito come variabile globale): procedure merge (1, m, p: integer); i sottovettori ins[l] ... ins[m) e ins[m+l] .. . ins[p) sono (* CM: assunti ordinati. Essi sono fusi per ottenere un nuovo vettore ordinato in ins[l] ... ins[p) contenente t utte le componenti dei due sottovettori originari *)
La cultura è un bene dell'umanità (
[email protected])
376
var app: tipoins;
vari, k, j : integer;
begin := l ; j := m + l; k := l; (* CM: il merge dei due vetto ri si costruisce nel vettore app, nelle corrispondenti component i * ) while (i = l; quello
circolarmente
in
a ogni
estrazione
posizione
m-esima
la lista dei pretendenti);
- comunichi l'ultimo pretendente rimasto, che sara' il prescelto. Resta
inteso che non vi potete aspettare alcun aiuto su problemi
riguardanti algoritmi,
linguaggi
di
programmazione,
strutture
di
dati,
ecc . ne' dal re ne' dai maghi di corte (che, anzi, vi
guardano con invidia e sospetto).
Ultimo avvertimento:
molto irascibile e vi ha dato tempo fino al tramonto.
La cultura è un bene dell'umanità (
[email protected])
il re e '
39 2
ES ERCIZ_IO A20 scrivere
un
massimo)
e
programma le
che legga N parole (di 30
stampi in gruppi in modo tale
che
caratteri solo
al
parole
appartenenti allo stesso gruppo siano anagrammi l'una dell'altra . Esempio: Input:
DANYL
output:
ALIAS
ARSA
ALIAS
ARSA, SARA LYNDA, DANYL, DYLAN
La cultura è un bene dell'umanità (
[email protected])
DYLAN
SARA
LYNDA