CAPITOLO 15
125
description
CAPITOLO 15. Top. Top. STACK. STACK. Le operazioni fondamentali che si fanno sugli stack sono: riempimento e svuotamento. Questo implica che durante lo svolgimento del programma il numero di oggetti nello stack può cambiare. - PowerPoint PPT Presentation
Transcript of CAPITOLO 15
1
Le Cataste o Stack• Uno stack è una successione lineare di elementi,
eventualmente anche vuota
• Se gli elementi che compongono uno stack sono tutti dello stesso tipo lo stack è detto omogeneo.
• Le operazioni elementari che possono esser effettuate su uno stack sono: aggiungere un elemento, cancellare e/o estrarre un elemento.
Top
STACK
Top
Le operazioni fondamentali che si fanno sugli stack sono:riempimento e svuotamento.Questo implica che durante lo svolgimento del programma il numero di oggetti nello stack può cambiare.
Per descrivere uno stack è sufficiente sapere quali sono gli oggetti (Items) nello stack e il loro numero (Top).
STACK
OPERAZIONI SUGLI STACK
In uno stack l’elemento inserito per ultimo viene estratto per primo (LIFO - Last In First Out).
In uno stack occorrerrà solo conoscere il numero di oggetti (Top).
Aggiungere ed eliminare oggetti.
Items[ ] è un array in cui si collocano gli oggetti, Top il numero di oggetti, l’operazione di aggiungere oggetti si chiama push e quella di eliminare oggetti pop. Quando Top=0 allora lo stack è vuoto.
OPERAZIONI SUGLI STACK
AGGIUNGERE
Top Top + 1Items[Top] Item
ELIMINARE
Top Top - 1
DIMOSTRAZIONI PER INDUZIONE
La dimostrazione per induzione è una tecnica per provare che un asserto S(n) vale per tutti gli interi n maggiori di un certo limite inferiore.Supposto vero l’asserto la dimostrazione consiste in:• individuare un caso base, il minimo valore di n, diciamo k, per cui si dimostra l’asserto S(k)• dimostrare il passo induttivo, cioè che per ogni n k , dove S(k) è la base induttiva, S(n) implica S(n+1) o equivalentemente supposto vero S(n) dimostrare che è vero S(n+1).
EsempioVogliamo dimostrare che:
122 1nn
0i
i
12
122
0
10
0i
i
caso basePoniamo n=0 avremo che è quindi dimostrato vero
Il membro sinistro può essere riscritto come
Avendo supposto vero l’asserto
Sostituiamo b) in a)
1nn
0i
i1n
0i
i 222
a)
122 1nn
0i
i
b)
1212*22122 2n1n1n1n1n
0i
i
passo induttivoDobbiamo ora dimostrare che 122 2n
1n
0i
i
c.v.d.
122 1nn
0i
i
Supposto sia vero
RICORSIVITA’
Algoritmo ricorsivo
Un algoritmo è ricorsivo quando per trovare la soluzione ad un dato problema fa uso della soluzione trovata per lo stesso problema presentato in una versione più ridotta.
ESEMPIO
Problema del Massimo Comun Divisore (MCD o GCD)Dati due numeri interi m ed n trovare il più grande intero positivo che divide sia m che n.
Soluzioni possibiliScomposizione in fattori primiAlgoritmo di Euclide
ALGORITMO DI EUCLIDE PER IL MASSIMO COMUN DIVISORE
(300 A.C.)
Siano m ed n due numeri naturali e supponiamo sia m>n
•1 Si divide m per n
•2 Se il resto è zero allora n è il MCD tra m e n.
•3 Se il resto è diverso da zero torna al primo passo scambiando m con n e n con r (cioè dividi n per r)
NR
RR’ R’
M
MCD=R’
ALGORITMO DI EUCLIDE
Pseudo codiceIF M o N sono valori che rappresentano una soluzione valida THEN
GCD valore della soluzione (M o N) ELSE
GCD GCD(N, M MOD N)
PROGRAM Euclide;VAR M,N:integer;
BEGINwriteln('Assegna M e N ');read(M);read(N);writeln('Il MCD e'':= ',MCD(M,N));readlnEND.
FUNCTION MCD(M,N:integer):integer; VAR Resto:integer;
BEGIN Resto:=M MOD N; WHILE Resto<>0 DO BEGIN M:=N; N:=Resto; Resto:=M MOD N
END; MCD:=N END;
FUNCTION GCD(M,N:integer):integer; BEGIN IF N=0 THEN GCD:=M ELSE GCD:=GCD(N,M MOD N) END;
writeln('Il GCD e'':= ',GCD(M,N));
GCD(66,48)
N=0?No
GCD(48,18)
GCD(48,18)
GCD(18,12)
GCD(18,12)
N=0?No
GCD(12,6)
GCD(12,6)
N=0?No
GCD(6,0)
N=0?No
N=0?Si
GCD 6
GCD(6,0)
GCDGCD GCD GCD
FUNCTION GCD(M,N:integer):integer;BEGIN IF N=0 THEN GCD:=M ELSE BEGIN writeln(’**push** GCD(',M,',',N,')'); writeln; GCD:=GCD(N,M MOD N); writeln(’**pop** N= ',M MOD N) END END;
GCD:=GCD(N, M MOD N)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
GCD(30,18)
N=0?No
GCD(18,12)
GCD(18,12)
N=0?No
GCD(12,6)
GCD(12,6)
N=0?No
GCD(6,0)
N=0?Si
GCD 6
GCD(6,0)
GCDGCD GCD
GCD:=GCD(N, M MOD N)
FUNCTION GCD(M,N:integer):integer;BEGIN IF N=0 THEN
GCD:=M ELSE
GCD:=GCD(N,M MOD N);END;
GCD(30,18)
GCD(18,12)
GCD(12,6)
GCD(6,0) =6
=6
=6
=6
Ogni algoritmo ricorsivo deve essere tale che durante i passi della ricorsione, cioè della riduzione del problema, si giunge sempre ad una soluzione. Questa soluzione è detta caso base o STOPPING CASE.Nel caso del GCD il caso base è il caso in cui N=0.
Caso base : è una soluzione per un algoritmo ricorsivo per la quale non sono necessarie ulteriori chiamate ricorsive. Ogni algoritmo ricorsivo, per essere valido, richiede almeno un caso base.
Il meccanismo di gestione delle chiamate ricorsive è quello dello stack, si fa cioè ricorso alla tecnica LIFO ed è chiamato Run-time stack.
Un esempio di ricorsione per accumulazione
Problema Si vuole calcolare la potenza Nma del numero reale Xre.
Soluzione
0Nper 1
0Nper * 1NXX
NX
Base Case
Ricorsione
FUNCTION PotenzaN(Xre:real,N:integer):real;BEGIN IF N=0 THEN PotenzaN :=1 ELSE PotenzaN:= Xre*PotenzaN(Xre,N-1);END;
PotenzaN(0.9,3)
N=0?No
PotenzaN(0.9,2)
PotenzaN(0.9,2) PotenzaN(0.9,1)
N=0?No
PotenzaN(0.9,0)
PotenzaN(0.9,0)
PotenzaN(0.9,1)
N=0?No
N=0?Si
PotenzaN 1
PotenzaN 0.9*PotenzaN 0.9*PotenzaN 0.9*
PotenzaN(0.9,3)
FUNCTION PotenzaN(Xre:real,N:integer):real;BEGIN IF N=0 THEN
PotenzaN :=1 ELSE
PotenzaN:= Xre*PotenzaN(Xre,N-1);END;
0.9*PotenzaN(0.9,3)
0.9*PotenzaN(0.9,2)
0.9*PotenzaN(0.9,1)
0.9*PotenzaN(0.9,0) =1
=0.9*1
=0.9*0.9
=0.9*0.9*0.9
DIMOSTRAZIONE PER INDUZIONE
Vogliamo dimostrare che S(n): a)1nn XXX
caso basePoniamo n=1 avremo che è quindi dimostrato vero
XX
XXX 01
Avendo supposto vero l’asserto sostituiamo in b) il valore che si ottiene da a)
passo induttivoDobbiamo ora dimostrare che b)
n1n XXX
nn XXXX
q.e.d.
COME FUNZIONA LA RICORSIVITA’
PROCEDURE(p’1 ,…., p’k ) caso base ? NO allora applica
PROCEDURE(p”1 ,…., p”k ) caso base ? NO allora applica
PROCEDURE(p*1 ,…., p*k )
caso base ? SI allora applicala soluzione a
Applica la soluzione a
PROCEDURE(p1 ,…., pk ) caso base ? NO allora applica
Applica la soluzione a
Dove (pi1 ,…., pi
k ) sono problemi ridotti del problema precedente
IF i parametri fanno riferimento a un caso base THENrisolvi il problema
ELSEusa i valori dei parametri per un problema ridottoCHIAMA LA PROCEDURA O FUNZIONE PERRISOLVERE IL PROBLEMA RIDOTTO
Possiamo dire che è stato applicato il metodo del
DIVIDE ET IMPERA
Un algoritmo iterativo consiste in un unico processo che ripete le stesse identiche operazioni molte volte.
Un algoritmo ricorsivo consiste in un numero finito di processi aperti uno dopo l’altro e posti in uno stack. Non appena si chiude un processo subito si scende nello stack e si chiude il processo immediatemente seguente e così via di seguito.
Per scrivere un algoritmo ricorsivo bisogna soddisfare le seguenti condizioni:
1. Esiste almeno un caso base la cui soluzione è banale
2. Tutti i sottoproblemi devono poter essere risolti in termini di versioni ridotte di uno stesso problema
3. Le azioni applicate per la soluzione di un problema ridotto portano sempre alla soluzione di un problema più grande
4. In funzione di quanto sia grande il problema iniziale deve essere sempre possibile trovare almeno un caso base nel corso della elaborazione del problema originale.
FUNCTION Sum(N:integer):integer;BEGIN
IF N=0 THEN Sum :=0ELSE Sum :=N+ Sum(N-1)END;
Sommatoria dei primi N interi positivi
1. La somma dei primi 0 interi positivi vale 0.2. La somma dei primi N interi positivi è uguale alla somma dei primi N-1 interi più N.
5+ Sum(4)
2+Sum(1)
3+ Sum(2)
4+ Sum(3)
Sum =15
1+ Sum(0) Sum =1
Sum =3
Sum =6
Sum =10
Sia N=5
DIMOSTRAZIONE PER INDUZIONE
Vogliamo dimostrare che S(n): a)2
)1n(Ni
N
1i
caso basePoniamo n=1 avremo che è quindi dimostrato vero1i
1
1i
Possiamo scrivere
2
)2N()1N(
2
)1N(2)1N(N
)1N(2
)1N(N)1N(ii
N
1i
1N
1i
q.e.d.
passo induttivoDobbiamo ora dimostrare che b)
2
)2N()1N(i
1N
1i
Quando si applica un processo ricorsivo tipo quello della accumulazione bisogna assicurarsi che i valori accumulati nelle relative variabili siano correttamente passati da un processo all’altro. Inoltre il valore assunto da una variabile in un processo ricorsivo non deve essere distrutto dal lancio di un altro processo ricorsivo. Di qui la necessità di passare le variabili utilizzando la chiamata per VAR.Esempio:Fare la somma dei primi N interi positivi e mostrare le somme parziali ogni M passi.
Pseudo-codiceIF N=0 THEN scrivi un messaggioSum 0ELSE ShowSums(N-1, M, Sum)Sum Sum +NIF N MOD M=0 THEN scrivi N e Sum
PROGRAM SommaRicorsiva(input,output); VAR Nin,Min,Sumout:integer; PROCEDURE ShowSums(N,M:integer; VAR Sum:integer); VAR Temp:integer; BEGIN IF N=0 THEN BEGIN Sum:=0 END ELSE BEGIN ShowSums(N-1,M,Sum); Sum:=Sum+N; Temp:=N MOD M; IF N MOD M=0 THEN writeln('La somma dei primi ',N:1,' numeri e'' = ',Sum:1,'.') END END;
BEGIN writeln(' Assegna N e M '); readln(Nin); readln(Min); writeln(' N M Sum'); ShowSums (Nin,Min,Sumout); writeln('La somma dei primi ',Nin:1,' numeri e'' = ',
Sumout:1,'.'); END.
Assegna N e M72 N M Sum push** 7 2 0 push** 6 2 0 push** 5 2 0 push** 4 2 0 push** 3 2 0 push** 2 2 0 push** 1 2 0 Somme parziali pop** 1 2 0 pop** 2 2 1La somma dei primi 2 numeri e' = 3. pop** 3 2 3 pop** 4 2 6La somma dei primi 4 numeri e' = 10. pop** 5 2 10 pop** 6 2 15La somma dei primi 6 numeri e' = 21. pop** 7 2 21
La somma dei primi 7 numeri e' = 28.
ESERCIZIO
Sia dato un vettore A di interi di dimensione N, scrivere una funzione ricorsiva che restituisca la somma di tutti gli elementi di A.
Sia dato un vettore A di interi di dimensione N, scrivere una procedura ricorsiva che restituisca la somma di tutti gli elementi pari di A e la somma di tutti gli elementi dispari di A.
Un algoritmo ricorsivo deve essere completo, deve cioè sempre esistere una soluzione qualunque sia l’input.La completezza dipende dal dominio su cui si definisce l’algoritmo.
Esempio: PotenzaN se definito sugli interi non è completo perché non funziona per gli interi negativi (infatti N-1 per N negativo non raggiunge mai lo 0).
Diventa completo se il domino di definizione è quello dei numeri interi positivi.
Stack InfinitoSi genera quando per un qualche input di un algoritmo ricorsivo non si raggiunge mai il caso base.
EsempioDato un testo scritto su un file e formato da più righe leggerlo e riscriverlo in ordine inverso rispetto alle righe.Es.
La Vispa Teresa avea tra l’erbetta a volo sorpresagentil farfalletta
gentil farfalletta a volo sorpresaavea tra l’erbettaLa Vispa Teresa
Pseudo-codice
reset(Teresa)InvertiRighe (Teresa)
PROCEDURE MostraRigheInvertite (VAR Teresa:text);BEGIN
StoreDisplay(Teresa)END;
PROGRAM InvertiRighe(Teresa,output);VARTeresa:text;PROCEDURE StoreDisplay(VAR Teresa:text);{procedura ricorsiva: la prima linea letta è l’ultima mostrata a video}BEGIN………..END;
{ BODY }BEGIN
reset(Teresa);MostraRigheInvertite
END.
*push* La vispa Teresa*push* avea tra l'erbetta*push* a volo sorpresa*push* gentil Farfalletta *pop* gentil Farfalletta *pop* a volo sorpresa *pop* avea tra l'erbetta *pop* La vispa Teresa
PROGRAM InvertiRighe(output,FInput);CONSTLungMax=80; {massima lunghezza permessa alle stringhe }TYPE Stringa=STRING[LungMax];VARFInput: text;PROCEDURE StoreDisplay(VAR FInput:text);VARRigo: Stringa;BEGIN IF NOT eof(FInput) THEN BEGIN readln(FInput,Rigo); writeln('*push* ',Rigo); StoreDisplay(FInput); writeln(' *pop* ',Rigo) ENDEND;
{BODY }BEGINassign(FInput,'C:\TP\ESEMPI\TERESA.TXT');reset(FInput);StoreDisplay(FInput);readlnEND.
Caso base
GCD:=GCD(N, M MOD N)GCD(30,18)
N=0?No
GCD(18,12)
GCD(18,12)
N=0?No
GCD(12,6)
GCD(12,6)
N=0?No
GCD(6,0)
N=0?Si
GCD 6
GCD(6,0)
GCDGCD GCD
FUNCTION GCD(M,N:integer):integer;BEGIN IF N=0 THEN
GCD:=M ELSE
GCD:=GCD(N,M MOD N);END;
GCD(30,18)
GCD(18,12)
GCD(12,6)
GCD(6,0) =6
=6
=6
=6
caso basePoniamo GCD(M,0)=M
passo induttivoDobbiamo ora dimostrare che GCD(M’,N’)=GCD(N, M MOD N)
DIMOSTRAZIONE PER INDUZIONE DELLA CORRETTEZZA DELL’ALGORTIMO RICORSIVO PER IL GCD
Supponiamo GCD(M’,N’)=X
allora M’=hX e N’=zX dove h e z sono interi
essendo N’=M MOD N questo implica per definizione che
M=kN+N’ dove k è un intero
ma N’=zX
allora M=kN+zX inoltre N=M’=hX quindi
M=khX+zX=(kh+z)X=wX
essendo allora sia M che N divisibili per X questo è il GCD(M,N)
ESERCIZIO
Sia dato un vettore A di interi di dimensione N, scrivere una funzione ricorsiva che restituisca la somma di tutti gli elementi di A.
Sia dato un vettore A di interi di dimensione N, scrivere una procedura ricorsiva che restituisca la somma di tutti gli elementi pari di A e la somma di tutti gli elementi dispari di A.
esercizi
ALTRI ESEMPISupponiamo di avere 3 lettere a b c . Vogliamo sapere quante permutazioni si possono fare con questi 3 caratteri.- ci sono 3 maniere per scegliere quale lettera mettere in terza posizione (genericamente n)
abc acb cba- per ognuna delle 3 scelte precedenti ci sono 2 maniere diverse per scegliere la lettere da mettere in seconda posizione in totale 3*2 (genericamente n*(n-1))abc bacacb cabcba bca- per ognuna delle 6 scelte precedenti c’è 1 sola maniera per scegliere la lettere da mettere in prima posizione in totale 3*2*1 (genericamente n*(n-1)…..*1)abc bacacb cabcba bca
FATTORIALE
1*)2*(***)2(*)1(*!
1!0
NNNN
FUNCTION Fattoriale(N:integer):integer;VAR
Count, Product: integer;BEGIN
Product:=1;FOR Count:=2 TO N DO Product:=Product*Count;Fattoriale:=Product
END;
FUNCTION Fattoriale (N:integer):integer;BEGIN
IF N=0 THEN Fattoriale:=1ELSE Fattoriale:=N*Fattoriale(N-1)END;
Dato un vettore di interi scrivere una procedura ricorsiva che trovi il valore del numero più grande in esso contenuto
esercizi
PROGRAM Diagonale(input,output);{ Assegnata una matrice MxM determinare, con una procedura ricorsiva,il valore massimo in ciascuna delle due diagonali principali.}
{******** MAIN************}N:=5;ScriviMatrice(A,N);Diagona(N,N,A,M1,M2);writeln(' I Massimi sono ', M1,' e ',M2);readlnEND.
TYPEArrayx=Array[1..10,1..10] of integer;VAR A:arrayx;N, M1,M2:integer;
PROCEDURE Diagona(Niniz,N1:integer;VAR A1:arrayx;VAR MD1,MD2:integer);{Scorri a partire dal basso ricorsivamente la matrice. Seleziona nelle due diagonali gli elementi più grandi}VAR N2,N3:integer;
BEGINIF N1=0 THEN
BEGIN MD1:=0; MD2:=0;
END ELSE BEGIN
Diagona(Niniz,N1-1,A1,MD1,MD2); IF A1[N1,N1]>MD1 THEN MD1:= A1[N1,N1]; IF A1[N1,Niniz-N1+1]>MD2 THEN MD2:= A1[N1,Niniz-N1+1];
END;END;
FUNCTION Diagona(Niniz,N1:integer;VAR A1:arrayx;VAR MD1,MD2:integer):integer;{Scorri a partire dal basso ricorsivamente la matrice. Seleziona nelle due diagonali gli elementi più grandi e di questi stampa il maggiore}
VARN2,N3:integer;BEGIN
IF N1=0 THENBEGIN
MD1:=0; MD2:=0;
END ELSE BEGIN
Diagona:=Diagona(Niniz,N1-1,A1,MD1,MD2); IF A1[N1,N1]>MD1 THEN MD1:= A1[N1,N1]; IF A1[N1,Niniz-N1+1]>MD2 THEN MD2:= A1[N1,Niniz-N1+1]; END;Diagona:=MD1;IF MD1 < MD2 Then Diagona:=MD2;END; .
Esempio con due casi base
Problema:Assegnare agli elementi dell’Array di interi Ints, dei numeri compresi nell’intervallo 1..TotaleAssegnato. Ogni numero viene dato da tastiera.Il processo di lettura cessa o quando si introducono tutti i numeri concessi (MaxElements) oppure quando si introduce un numero negativo. Subito dopo si effettua l’assegnazione.
In questo caso i casi base possibili sono due:• abbiamo letto il massimo numero possibile di valori• abbiamo letto un numero negativo
In entrambi i casi la lettura deve terminare e si effettua l’assegnazione
Pseudo-CodiceInserisci(Left,TotaleAssegnato,Ints){Indichiamo con Left quanti numeri positivi è ancora possibile assegnare e con Temp il valore letto }IF Left = 0 THEN gestisci il caso base N°1ELSE read(Temp) IF Temp<=0 THEN
gestisci il caso base N°2 ELSE Inserisci(Left-1,TotaleAssegnato,Ints) istruzioni dopo la ricorsione
TotaleAssegnato = 0
TotaleAssegnato = TotaleAssegnato + 1Ints[TotaleAssegnato ] Temp
Temp< = 0
PROGRAM CaseBase2(input,output);CONST MaxElements=4;TYPEIntsArray=ARRAY[1..MaxElements] OF integer;VARInts:IntsArray;Left, TotaleAssegnato, I:integer;PROCEDURE Inserisci(Left:integer; VAR TotaleAssegnato:integer; VAR Ints:IntsArray);VAR Temp: integer;BEGIN IF Left=0 THEN
BEGIN readln; writeln('Non possono essere letti altri valori. '); TotaleAssegnato:=0; END
ELSEBEGIN read(Temp); IF Temp <=0 THEN
BEGIN writeln('E'' stato introdotto un numero negativo. '); TotaleAssegnato:=0;
END ELSE
BEGIN Inserisci(Left-1, TotaleAssegnato,Ints); TotaleAssegnato:= TotaleAssegnato+1; Ints[TotaleAssegnato]:=Temp END
ENDEND;
{BODY}BEGINwriteln('Inizia inserzione dati max= ',MaxElements);writeln;Inserisci(MaxElements,TotaleAssegnato,Ints);writeln(' ARRAY ');FOR I:=1 TO TotaleAssegnato DOwriteln(Ints[I]);readlnEND.
Inizia inserzione dati max= 4 Left TotaleAssegnato1 push** 4 02 push** 3 03 push** 2 04 push** 1 0Non possono essere letti altri valori. pop** 1 0 pop** 2 1 pop** 3 2 pop** 4 3
ARRAY 4 3 2 1
Inizia inserzione dati max= 4 Left TotaleAssegnato11 push** 4 012 push** 3 0-2E' stato introdotto un numero negativo. pop** 3 0 pop** 4 1
ARRAY 12 11
Alcuni suggerimenti
Fatti importanti• come si passano i valori dei parametri
a- usare una chiamata per valore per determinare se il CASE BASE è verificato
b- se il processo ricorsivo è di tipo per accumulazione usare la chiamata per VAR per la variabile di accumulazione
c- usare una variabile locale se il suo valore è istanziato all’interno del processo ricorsivo per cui ad ogni passo della ricorsione riprende il valore di partenza
PROCEDURE Inserisci(Left:integer; VAR TotaleAssegnato:integer; VAR Ints:IntsArray);
VAR
Temp: integer;
•l’ordine con cui le istruzioni vengono eseguite, se prima o dopo la chiamata ricorsivaA- se una o più istruzioni riducono la dimensione del problema esse devono
precedere la chiamata ricorsiva B- se una o più istruzioni necessitano del risultato della ricorsione vanno
poste dopo la chiamata ricorsiva
ElaboraTesto(Rigo)
Pseudo codice
IF Not eof(InFile) THEN
readln(Finput,Rigo)
ElaboraTesto(Rigo)
BEGIN
read(Temp);
IF Temp <=0 THEN
BEGIN
writeln('E'' stato introdotto un numero negativo. ');
TotaleAssegnato:=0;
END
ELSE
BEGIN
Inserisci(Left-1, TotaleAssegnato,Ints);
TotaleAssegnato:= TotaleAssegnato+1;
Ints[TotaleAssegnato]:=Temp
END
END
PROCEDURE Inserisci2(Left:integer; VAR Ints:IntsArray);VAR
Temp: integer;BEGIN IF Left<>0 THEN
BEGIN Inserisci(Left-1,Ints); read(Temp); Ints[Left]:=Temp
END END
END;
PROCEDURE Inserisci3(Left:integer; VAR Ints:IntsArray);VAR
Temp: integer;BEGINIF Left<>0 THENBEGINread(Temp);Inserisci(Left-1,Ints);Ints[Left]:=TempENDEND;
Inserisci2 push** 5
push** 4 push** 3 push** 2 push** 1
pop** 1 10 pop** 2 20 pop** 3 30 pop** 4 40pop** 5 50
ARRAY1020304050
Inserisci3 push** 510 push** 4 20 push** 3 30 push** 240 push** 150
pop** 1 pop** 2 pop** 3 pop** 4 ARRAY5040302010
ESERCIZI
FUNCTION Sommatoria (N11,N22:integer):integer;BEGIN
IF (N11=N22) THENIF (N11 MOD 2)=0 THENSommatoria:=N22ELSESommatoria:=0
ELSEIF (N22 MOD 2)=0 THENSommatoria :=N22+Sommatoria(N11,N22-1) ;ELSESommatoria := Sommatoria(N11,N22-1);
END;
?
ESERCIZI
• Sommare tutti gli interi pari compresi tra i numeri N1 ed N2 assegnati
sopn1n2
ESERCIZI
•Sommare le seguenti espressioni per tutti gli interi compresi tra N1 ed N2
ii2;i2i1i 322 ;
esercizi
1) Restituisca il minimo o il massimo in un vettore di interi;
2) Restituisca l’indice del minimo e/o del massimo; (funzione o procedura)
3) Trova la massima differenza in valore assoluto tra un elemento ed il precedente ( escluso il primo)
Esercizi sui vettori. Scrivere una funzione e/o procedura ricorsiva che
esercizi
Assegnato un vettore A di interi di lunghezza N ed un numero x, calcolare le occorrenze di x in A.
Procedure occorre(A: vettore; i,x,N:integer; var conta:integer);
Begin
if i<=N then
begin
if a[i]=x then conta:=conta+1;
occorre(A,i+1,x,N,conta);
end;
End;
Consideriamo una procedura ricorsiva.
Se non siamo giunti alla fine allora
se A[i]=x allora incrementa un contatore
richiama la procedura per un caso più semplice
PROCEDURE occorre(N,i,x:integer; var conta:integer; VAR A1:arrayx);Begin if i<=N then begin if a[i]=x then conta:=conta+1; occorre(N,i+1,x, conta,A1); end;End;
FUNCTION occorrere(i,x1:integer; VAR A1:arrayx):integer;Begin if i=0 then
occorrere:=0ELSE
if a[i]=x1 then occorrere:= occorrere(i-1,x1,A1)+1ELSE occorrere:= occorrere(i-1,x1,A1);End;
SULLE MATRICI
Come controlliamo ogni elemento della matrice?
Partendo dalla riga=1 e colonna=1 possiamo procedere per linee orizzontali: quando la colonna arriva al valore n ( nell’esempio N=3) allora scatta alla riga successiva e la colonna diventa 1:
Se j>N allora i=i+1 e j=1
Caso Base: se i>N allora siamo giunti alla fine della matrice senza incontrare errori: la matrice è unitaria; se durante il controllo trova che la condizione non è verificata deve ritornare il valore false
Assegnata una matrice quadrata NxN, scrivere una funzione ricorsiva che restituisca true se la matrice è unitaria, false altrimenti.
100
010
001
100
00-1
001
RICORSIONE SULLE MATRICI
IF i>N THEN
unitaria=true
ELSE
IF condizione NON vera THEN
unitaria=false
else IF j>N THEN
unitaria=unitaria (a,i+1,1,N)
ELSE
unitaria=unitaria(a,i,j+1,N)
Assegnata una matrice quadrata NxN, scrivere una funzione ricorsiva che restituisca true se la matrice è unitaria, false altrimenti.
100
010
001
100
00-1
001
Caso base: i>N
Matrice unitaria
Else è unitaria se
altrimenti
NON unitaria
A[i,j]=1 se i=j
A[i,j]=0 se i<>j
RICORSIONE SULLE MATRICIfunction unitaria(var a: matrice;i,j,n: integer): boolean;
begin
if (i>n) then
unitaria:=true
else
if ((i=j) and (a[i,j]<>1)) or ((i<>j) and (a[i,j]<>0)) then
unitaria:=false
else if j>n then
unitaria:=unitaria(a,i+1,1,n)
else
unitaria:=unitaria(a,i,j+1,n);
end;
Esercizi sulle matrici
1) scrivere una funzione ricorsiva che restituisca true se è simmetrica, false altrimenti.
2) scrivere una procedura o funzione ricorsiva che restituisca il valore true se la matrice possiede due righe uguali, false altrimenti.
3) scrivere una procedura o funzione ricorsiva che calcoli la somma delle righe dispari e quelle delle righe pari
4) scrivere una funzione ricorsiva che restituisca true se tutti gli elementi della diagonale principale sono positivi
5) scrivere una procedura o funzione ricorsiva che controlli se la somma degli elementi della diagonale principale è uguale a quella della diagonale secondaria
6) scrivere una procedura o funzione ricorsiva che restituisca il valore true se ogni riga i-esima della matrice possiede un numero di i valori negativi, false altrimenti.
Assegnata una matrice A di interi
Altri esercizi sulla ricorsione.Un caso base
1 - Assegnata una matrice MxM determinare, con una funzione ricorsiva, il valore massimo tra i massimi delle diagonali principali.Esempio1 3 52 4 68 1 10
Il valore massimo appartenente alla prima diagonale principale è 10 in A[3,3]Il valore massimo appartenente alla seconda diagonale principale è 8 in A[3,1]Il valore massimo cercato è quindi 10 in A[3,3].
2 - Assegnato un file di testo con stringhe lunghe N per ogni rigo, determinare quante sono le occorrenze di un carattere preassegnato con una funzione ricorsiva.EsempioCercare le occorrenze di ‘e’ nel seguente testo:La Vispa TeresaAvea tra l’erbettaA volo sorpresaGentile farfalletta
‘e’ ricorre 9 volte
PROGRAM Diagonale(input,output);{ Assegnata una matrice MxM determinare, con una funzione ricorsiva,se la somma delle due diagonali sono uguali.}TYPEArrayx=Array[1..10,1..10] of integer;VARA:arrayx;N,i1,M1,M2:integer;
esercizi
PROGRAM Diagonale(input,output);{ Assegnata una matrice MxM determinare, con una funzione ricorsiva,se ci sono due righe uguali.}TYPEArrayx=Array[1..10,1..10] of integer;VARA:arrayx;N,i1,j1:integer;
esercizi
PROGRAM Diagonale(input,output);{ Assegnata una matrice MxM determinare, con una funzione ricorsiva,il valore massimo tra i massimi delle diagonali principali.}TYPEArrayx=Array[1..10,1..10] of integer;VARA:arrayx;N,i1,tem:integer;
esercizi
PROGRAM Diagonale(input,output);{ Assegnata una matrice MxM, con una funzione ricorsiva, Controlla che in ogni riga i ci sono giusto “ i” numeri negativi .}TYPEArrayx=Array[1..10,1..10] of integer;VARA:arrayx;N,i1,j1,conta:integer;
esercizi
PROGRAM Diagonale(input,output);{ Assegnata una matrice MxM determinare, con una funzione ricorsiva,se è simmetrica.}TYPEArrayx=Array[1..10,1..10] of integer;VARA:arrayx;N,i1,j1:integer;
esercizi
Ricorsione non lineare = più di una chiamata ricorsiva per blocco
Per capire bene come opera una ricorsione non lineare si traccia un albero che mostra la storia dello stack.
Ricorsione lineare = al massimo una chiamata ricorsiva per blocco
EsempioPROGRAM TreeExample;PROCEDURE C(N:integer); BEGIN
IF N>0 THEN C(N-1)
END;PROCEDURE B; BEGIN
C(1) END;PROCEDURE A; BEGIN
B END;
{MAIN}BEGIN
A;C(1);writeln(‘Fine’)
END.
PROCEDURE A
PROCEDURE B
PROCEDURE C(1)
PROCEDURE C(0)
MAIN
PROCEDURE C(1)
PROCEDURE C(0)
main chiama A
A chiama B
B chiama C(1)
C(1) chiama C(0)
C(0) ritorna a C(1)
C(1) ritorna a B
B ritorna A
A ritorna a main
main chiama C(1)
C(1) chiama C(0)
C(0) ritorna a C(1)
C(1) ritorna a main
main chiama Fine
Fine
PROGRAM TreeExample(output);PROCEDURE C(N:integer); BEGIN
IF N>0 THEN BEGIN writeln('C(',N,') chiama C(',N-1,')');
C(N-1); writeln(' C(',N-1,') ritorna a C(',N,')') END END;PROCEDURE B; BEGIN writeln('B chiama C(1)');
C(1); writeln(' C(1) ritorna a B') END;PROCEDURE A; BEGIN writeln('A chiama B');
B; writeln('B ritorna A') END;BEGINwriteln('main chiama A');A;writeln('A ritorna a main');writeln('main chiama C(1)');C(1);writeln('C(1) ritorna a main');writeln('main chiama Fine');writeln('Fine');readlnEND.
main
C(0) ritorna a C(1)
C(1) ritorna a B
B ritorna A
A ritorna a main
C(1) ritorna a main
C(0) ritorna a C(1)
main chiama A
AA chiama B
B
B chiama C(1)
C(1)
C(1) chiama C(0)
C(0)
Fine ritorna a main
main chiama C(1)
C(1)
C(1) chiama C(0)
C(0)
main chiama Finewriteln
C(0)
main
A
B
C(1)
C(1)
C(0)
writeln
EsempioPROGRAM TreeExample;PROCEDURE C(N:integer); BEGIN
IF N>0 THEN C(N-1)
END;PROCEDURE B; BEGIN
C(1) END;PROCEDURE A; BEGIN
B END;
{MAIN}BEGIN
A;C(1);writeln(‘Fine’)
END.
Regole per costruire l’albero della storia dello stack
1. Ogni albero deve avere una radice principale
2. L’albero è fatto di nodi che rappresentano i processi che sono eseguiti ad un certo passo. Ogni nodo rappresenta esattamente un processo. Se è necessario si mettono etichette che indicano il processo.
3. Un ramo dell’albero rappresenta una chiamata e un ritorno di un processo rispetto ad un altro. Se ci sono più processi ricorsivi si indicano in ordine a partire da sinistra.
4. Ogni nodo è visitato una sola volta (push e pop) e nessun processo può terminare se prima non sono terminati tutti quelli che ha chiamato.
ProblemaNel 1228 messer Leonardo Pisano si pose il seguente problema:posta una coppia di conigli in un recinto supponiamo che questa coppia dopo un mese genera un’altra coppia, questa a sua volta dopo un altro mese ne genera un’altra e contemporaneamente anche le precedenti generano altre coppie. Dopo un anno, cioè dopo 12 mesi quanti conigli ci saranno nel recinto?
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233
EsempioI numeri di Fibonacci definiti ricorsivamente.
N=1 : Fib(N) 1N=0 : Fib(N) 0 N>=2 : Fib(N) Fib(N-2)+FIB(N-1)
FUNCTION Fibonacci(N:integer):integer;{ritorna l’N-esimo numero di Fibonacci}BEGIN IF N=0 THEN
Fibonacci:=0 ELSE IF N=1 THEN
Fibonacci:=1 ELSE
Fibonacci:= Fibonacci(N-2) + Fibonacci(N-1)END.
Ricorsione lineare: al più una chiamata ricorsiva nell’ambito di uno stesso processo ricorsivo.
Ricorsione non lineare: più di una chiamata ricorsiva nell’ambito di uno stesso processo ricorsivo.
main
F(3)
F(1) F(2)
F(4)
F(2)
Fibonacci(4)
F(1) F(0)
F(1) F(0)
main
F(3)
F(1) F(2)
F(1) F(0)
Fibonacci(3)
FUNCTION Fibonacci(N:integer):integer;BEGIN IF N=0 THEN
Fibonacci:=0 ELSE IF N=1 THEN
Fibonacci:=1 ELSE
Fibonacci:= Fibonacci(N-2) + Fibonacci(N-1)END.
Fibonacci(6)F(6)
F(5)F(4) +
F(2) F(3)+
F(2) F(1)+F(0)F(1) + 01 +
1 F(3)+
F(0)F(1) + 01 +
2
1 1+
3
F(3)
F(1)
F(2)
F(4)
F(5)
F(3)
F(6)
F(1) F(2)
F(3)
F(4)
F(2)
F(2)F(0)F(1)
F(0)
F(1)
F(0)F(1) F(1) F(0)F(0)F(1)
fibon1
Complessità dell’algoritmo per il calcolo dei numeri di Fibonacci
E’ stato dimostrato che per N abbastanza grande la complessità di F(N), cioè il numero di chiamate ricorsive, è circa O(1.61N)
N 1,61^N 1 MFLOP 1 TERAFLOP
1 2
10 117
20 13.694 0,01 sec
40 187.514.580 3,13 minuti
50 21.942.888.767 6,10 ore
100 481.490.367.451.071.000.000 15.480.014 anni 15.480
200 231.832.973.948.168.000.000.000.000.000.000.000.000.000 7,45348E+27 anni7,45E+24
PROGRAM ContaCall(output);VAR
Calls:real; No:integer;FUNCTION Fibonacci(N:integer; VAR Calls:real):real;{ritorna l'N-esimo numero di Fibonacci}BEGIN Calls:=Calls+1; IF N=0 THEN
Fibonacci:=0 ELSE IF N=1 THEN
Fibonacci:=1 ELSE
Fibonacci:= Fibonacci(N-2,Calls) + Fibonacci(N-1,Calls)END;
{BODY}BEGINFOR No:=1 TO 40 DO BEGIN
Calls:=0;IF No MOD 5=0 THENwriteln('Fibonacci(',No:1,') = ',
Fibonacci(No,Calls):20:0,' chiamate= ',Calls:20:0) END;readlnEND.
Fibonacci(5) = 3 chiamate= 9Fibonacci(10) = 34 chiamate= 109Fibonacci(15) = 377 chiamate= 1219Fibonacci(20) = 4181 chiamate= 13529Fibonacci(25) = 46368 chiamate= 150049Fibonacci(30) = 514229 chiamate= 1664079Fibonacci(35) = 5702887 chiamate= 18454929Fibonacci(40) = 63245986 chiamate= 204668309
fibon
Per ridurre da O (1.61N) a O(N) la complessità di calcolo per i numeri di Fibonacci invece di chiamare ricorsivamente la procedura di calcolo per ogni nodo dell’albero dello stack depositiamo i risultati di ogni computazione in un array e li richiamiamo, senza più calcolarli ogni volta che ne abbiamo bisogno.
Detto FibNos l’array in cui si depositano i numeri parziali possiamo costruire una procedura ricorsiva alla seguente maniera:caso baseQuando N=2 allora poni
FibNos[2] 1FibNos[1] 0
CHIAMATA RICORSIVAFibNos[N] FibNos[N-2] + FibNos[N-1]
Pseudo CodiceSetFibNo(N:integer; VAR FibNos:FibNoArr);
IF N=2 THEN BEGIN FibNos[2]:=1; FibNos[1]:=1 END ELSE BEGIN SetFibNo(N-1,FibNos);
FibNos[N]:=FibNos[N-2] + FibNos[N-1]
SvantaggioSiamo limitati dalla dimensione dell’array per determinare N massimo
PROGRAM ContaCallVeloce(output);{calcola l'N-esimo numero di Fibonacci in O(N) }CONST MaxFib=50;TYPEFibNoArr=ARRAY[1..MaxFib] OF real;VARFibNos:FibNoArr;VAR No:integer;PROCEDURE SetFibNo(N:integer; VAR FibNos:FibNoArr);{ritorna l'N-esimo numero di Fibonacci}BEGIN IF N=2 THEN BEGIN FibNos[2]:=1; FibNos[1]:=1 END ELSE BEGIN SetFibNo(N-1,FibNos);
FibNos[N]:=FibNos[N-2] + FibNos[N-1] ENDEND;
{BODY}BEGINFOR No:=1 TO 40 DO BEGIN
IF No MOD 5=0 THEN BEGIN SetFibNo(No,FibNos); writeln('Fibonacci(',No:1,') = ',No,FibNos[No]:20:0) END END;readlnEND.
SetFibNo(4)
SetFibNo(3)
SetFibNo(2)
F(3)
F(1) F(2)
F(4)
F(2)
FibNo[4]
FibNo[3]
FibNo[2]
FibNo[1]
fibona
Esercizio
1- Assegnato un intero N, calcolare il rapporto tra le coppie di numeri di Fibonacci F(n+1)/F(n) e per ogni coppia sottrarre a detto rapporto la radice positiva dell’equazione
x2-x-1=0.
2- Calcolare il MCD tra la somma dei numeri di Fibonacci compresi tra 1 e 10 e quelli compresi tra 11 e 20compresi tra 11 e 20 e quelli compresi tra 21 e 30compresi tra 21 e 30 e quelli compresi tra 31 e 40
Testo consigliato da leggere MARIO LIVIO – La sezione aurea
Calcolare con una funzione ricorsiva l’N-esimo termine della successione seguente
a1=3a2=1a3=-1
an=an-1*an-2-(an-3+an-1+an-2)
Caso base N=1 -> S(1)=3, S(2)=1, S(3)=-1
Chiamata ricorsiva -> S(N):=S(N-1)*S(N-2)-(S(N-3)+S(N-1)+S(N-2))
ESERCIZIO
FUNCTION Success(A1,A2,A3:real;N:integer):real;{ritorna l'N-esimo valore di una successione}BEGINIF N=1 THEN Success:=A1 ELSE IF N=2 THEN Success:=A2
ELSE IF N=3 THEN Success:=A3 ELSE BEGINSuccess:= Success(A1,A2,A3,N-1)* Success(A1,A2,A3,N-2)- (Success(A1,A2,A3,N-3)+ Success(A1,A2,A3,N-1)+Success(A1,A2,A3,N-2));
END;
END;
ESERCIZIO
Tracciare l’albero di ricorsione perA1=1; A2=2; A3=3 e N=7
ALGORITMI DI RICERCA LINEARE
Problema: Cercare tra i valori contenuti in un Array un preassegnatovalore.
Esempio: Data una lista di N numeri verificare se esiste un preassegnatoValore.
Condizioni di uscita:- la ricerca è finita se nessun elemento uguale a quello cercato esiste- la ricerca è finita se almeno un elemento uguale a quello cercato è
stato trovato
Partire dall’ultimo elemento della lista e risalire fino in cima nella ricerca dell’elemento.
Soluzione: Gestire opportunamente l’indice dell’array in cui sono contenuti gli elementi su cui fare la ricerca.I criteri per stabilire il nuovo valore da attribuire all’indice possonoessere i più diversi. E’ però importante che una volta stabilito che un elemento individuatoda un certo indice non è quello cercato questo elemento non venga piùesaminato.
Algoritmo 10.2Indice NumeroTotaleElementiTrovato falseWHILE NOT (Indice=0) AND NOT Trovato DO
IF UnArray[Indice]= ValoreCercato Trovato trueELSE Indice Indice-1
Poiché ad ogni passo della ricerca eliminiamo un elemento il massimonumero di passi è pari al numero di elementi.
Indicatore:=CercaIndice(Nome, NumeroElementi,ValoreCercato);IF Indicatore<>0 THEN BEGIN write(ValoreCercato,’ è stato trovato nella posizione ‘,Indicatore:2); ENDELSE write(ValoreCercato,’ non è stato trovato ‘);
FUNCTION CercaIndice(VAR Nome: NomeArray; NumeroElementi:integer;
ValoreCercato:NomeStringa):integer;
VAR
Indice:integer;
Trovato: boolean;
BEGIN
WHILE NOT (Indice=0) AND NOT Trovato DO
IF Nome[Indice]=ValoreCercato THEN
Trovato:= true
ELSE
Indice:= Indice-1;
CercaIndice:= Indice
END.
Ricerca ricorsivaPseudo codice
FUNCTION Indice (VAR UnArray; Chiave; SubRange):ITypeIF terminato THEN
Indice 0ELSE
prendi un CandidatoIF UnArray[Candidato] = Chiave THEN
Indice CandidatoELSE
rivedi il SubRange riducendo le dimensioni del problema Indice Indice(UnArray, Chiave, SubRangeRidotto)
Indice Indice(UnArray, Chiave, SubRangeIniziale)
ESPRESSIONE RICORSIVA
caso base 2
caso base 1
Caratteristiche di una ricerca ricorsiva
• Gli array passati al blocco ricorsivo vengono chiamati per VAR.
• Una chiamata ricorsiva implica sempre una riduzione del sub range di possibili candidati. Quindi nell’intestazione è presente almeno un parametro che rappresenta il subrange di elementi. Il valore del parametro in ogni istante di computazione è funzione di un qualche subrange candidato locale. Questa espressione i cui valori devono rappresentare una riduzione del subrange candidato viene calcolata e al successivo processo di ricerca i valori vengono applicati.
•La condizione di terminazione è espressa in termini dei parametri del subrange candidato. Questa condizione rappresenta il caso base quando non restano altri subrange candidati alla ricerca.
• L’altro caso base si ha quando la ricerca ha buon esito, quando cioè Array[Candidate] coincide con Chiave.
EsercizioDato un Array del tipo
FIGLIO PADRE MADRE
aldo giulio maria giulio carlo anna carlo bruno pina ugo luca giulio maria ugo carla
Scrivere un programma che con tre funzioni ricorsive dica:1 - Dato X chi è il padre e la madre di X2 - Dati X e Y determini se X è figlio di Y per parte di padre3 - Dati X e Y determini se X è nonno o nonna di Y
figlio padre madre
aldo giulio maria
giulio carlo anna
carlo bruno pina
ugo luca giulio
maria ugo carla
{MAIN} BEGIN writeln('Dammi figlio ');readln(X); writeln('Il padre di ',X,' è ',CercaAvo(F,X, Nfamiglie,I1,padre)); writeln('La madre di ',X,' è ',CercaAvo(F,X, Nfamiglie,I1,madre)); END;
PROGRAM Famiglia(output);{calcola le parentele }TYPEstring30=STRING[30];genitori=(figlio,padre,madre,nessuno);Typearr=ARRAY[1..10,genitori] OF string30;VARA1:TypeArr;N1,Nfamiglie,I,J,I1,J1:integer; X,Y:string30;
FUNCTION CercaAvo(VAR A:Typearr;X:string30;Nfam,I:integer;avo:genitori):string30;{determina chi è il padre di X}BEGINIF i>Nfam THEN
CercaAvo:='ignoto'ELSE
IF (A[I,figlio]=X) THENCercaAvo:=A[I,avo]ELSECercaAvo:=CercaAvo(A,X, Nfam,I+1,avo)
END;
figlio padre madre
aldo giulio maria
giulio carlo anna
carlo bruno pina
ugo luca giulio
maria ugo carla
{MAIN} BEGIN writeln('Dammi padre ');readln(X); writeln('Dammi figlio ');readln(Y); writeln(X,' padre di ',Y,' è ',VerificaPadre(F,X,Y, Nfamiglie,I1)); END;
PROGRAM Famiglia(output);{calcola le parentele }TYPEstring30=STRING[30];genitori=(figlio,padre,madre,nessuno);Typearr=ARRAY[1..10,genitori] OF string30;VARA1:TypeArr;N1,Nfamiglie,I,J,I1,J1:integer; X,Y:string30;
FUNCTION VerificaPadre(VAR A:Typearr;XP,YF:string30;M,I:integer):boolean;{determina chi è il padre di X}BEGINIF i>M THEN
VerificaPadre:=FALSEELSE
IF (A[I,figlio]=YF) AND (A[I,padre]=XP) THENVerificaPadre:=TRUEELSEVerificaPadre:= VerificaPadre (A,XP,YF,M,I+1)
END;
Una funzione di Search lineare può essere del tipoLinear(UnArray, Chiave, TotalElements) dove si presuppone che il subrange di candidati sia tra 1.. TotalElements.
EsempioSupponiamo di avere un Array di stringhe Studenti, in cui si riportano gli studenti per MATRICOLA. Su questo array vogliamo fare delle ricerche. Una chiamata di funzione tipica èIndice:=Linear(Studenti, MatrCercata, N)
FUNCTION Linear (VAR Studenti: Stinga; MatrCercata;Stringa; N :integer):integer;
BEGINIF N=0 THEN
Linear:= 0ELSE IF Studenti[N]=MatrCercata THEN
Linear:=NELSE
Linear:=Linear(Studenti; MatrCercata; N-1)END;
ESPRESSIONE RICORSIVA
caso base 2
caso base 1
RICERCA LINEARE
RICERCA BINARIA
Data una lista di N elementi ordinati cercare se tra essi esiste un determinato elemento.
Dividiamo gli elementi ordinati in due parti. Quello che cerchiamopuò appartenere o alla prima o alla seconda parte, essendo tutti glielementi ordinati. Dividiamo la parte scelta ancora in due e applichiamo ancora il ragionamento precedente. L’algoritmo termina o quando l’ultimo elemento rimasto dalle successive suddivisioni è uguale a quello cercato, oppure quando l’intervallo rimasto non è più suddivisibile il che implica che il nostro elemento non appartiene alla lista.
Basso 1Alto ElementiTotaliWHILE NOT (Basso<=Alto) DO
Metà (Basso+Alto) DIV 2IF Interi[Metà ]< ValoreCercato THEN Basso Metà+1ELSE
Alto Metà-1 IF Alto<= ElementiTotali THEN IF Interi[Basso]=Valore Cercato THEN Indice Basso ELSE Indice 0 ELSE Indice 0
Una funzione di Search binario ha bisogno di due parametri per individuare il subrange: Lo e Hi.
L’indice candidato per la nuova ricerca è dato da:Mid (Lo+Hi) DIV 2
1° caso base è dato quando Lo>Hi2° caso base è dato quando l’elemento cercato è stato trovato
La chiamata iniziale è del tipoBinary(UnArray, Chiave, 1, TotalElements)
Pseudo Codice
FUNCTION Binary(VAR UnArray; Chiave; Lo, Hi):TipoIndice;IF Lo>Hi THEN Binary 0ELSE Mid (Lo+Hi) DIV 2 IF UnArray[Mid]=Chiave THEN
Binary Mid ELSE
IF UnArray[Mid]<Chiave THEN Binary Binary(UnArray, Chiave, Mid+1, Hi)ELSE Binary Binary(UnArray, Chiave, Lo, Mid-1)
Binary Binary(UnArray, Chiave, 1, UltimoElemento)
ProblemaScrivere una funzione ricorsiva che ritorna vero se gli elementi di UnArray di interi, con valori assegnati nel subrange 1..TotElem, sono in ordine crescente.
Obiettivo ricerca un elemento che sia fuori ordine in un dato subrange.Riduciamo di volta in volta il subrange fino a quando in questo resta un solo elemento allora vuol dire che la ricerca è finita e la risposta è TRUE.Se invece si verifica che è vera l’espressione
UnArray[N-1]>UnArray[N]questo significa che è stato trovato un elemento non in ordine e la funzione ritorna FALSE.
FUNCTION Ordinato(VAR UnArray:IntsArray; N:integer):boolean;BEGIN
IF N=1 THEN Ordinato:= TRUEELSE
IF UnArray[N-1] > UnArray[N] THEN Ordinato:= FALSE
ELSE Ordinato:=Ordinato(UnArray,N-1)
FUNCTION Minimo(VAR UnArray:IntsArray; Candidato,N:integer):integer;BEGIN
IF N=0 THEN Minimo:= CandidatoELSE
IF UnArray[N] < UnArray[Candidato] THEN Minimo:= Minimo(UnArray, N, N-1)
ELSE Minimo:= Minimo(UnArray,Candidato,N-1)
Dato un Array di interi cercare in quale posizione si trova il numero più piccolo.Iniziamo con l’ipotesi che l’ultimo elemento dell’Array sia il minimo e ricorsivamente risaliamo l’array.
ESERCIZIO
Scrivere un algoritmo ricorsivo per il calcolo della funzione booleana tale che assegnate due stringhe Sl e S2 restituisca TRUE se la seconda è contenuta tutta o in parte nella prima. FALSE altrimenti.Esempio:
Se Sl=‘Smacchiare’ e S2=‘Macchia’ allora la funzione vale TRUE.
Se Sl='Mentecatto' e S2=’tatto' allora la funzione vale FALSE
MERGE - SORT
Un algoritmo di sort classico ha in genere una complessità di calcolo pari a O(N2). Vediamo un algoritmo che, fondato sul criterio del DIVIDE ET IMPERA, ha una complessità più bassa.
Il merge-sort è fondato sul principio ricorsivo di ridurre il problema di partenza di un fattore 2 e nessun processo ricorsivo attivato viene fatto più di una volta.
3 5 2 6 4 1 7 5
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
3 5 2 6 4 1 7 5
1 2 3 4 5 6 7 853 62 14 57
1 2 3 4 5 6 7 8
153 2 6 4 7 5
53 62 41 75
2 3 5 6 1 4 5 7
1 2 3 4 5 5 6 7
Complessità del MERGE-SORTI nodi dell’albero di sort sono log N. Per ogni nodo si fa un sort in i*N/i passi dove i rappresenta la profondità del nodo
N
i
NNi
Ni
log
1
log
3 5 2 6 4 1 7 5
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
3 5 2 6 4 1 7 5
1 2 3 4 5 6 7 853 62 14 57
1 2 3 4 5 6 7 8153 2 6 4 7 5
53 62 41 75
2 3 5 6 1 4 5 7
1 2 3 4 5 5 6 7
i N° passi1 1*N2 2*N/24 4*N/48 8*N/8j j*N/j …….. ……..log N log N*N/log Ntotale N*log N
Pseudo codicePROCEDURE SortIt(Lo,Hi:IType; VAR AnArray:ArrayType);usa i valori degli indici in input (Lo,Hi) per dividere AnArray in due subarray (inferiore e superiore) IF gli indici del subarray inferiore implicano un array ordinabile
THENSortIt(usa come indici quelli del subarray inferiore ,AnArray)
IF gli indici del subarray superiore implicano un array ordinabile THEN
SortIt(usa come indici quelli del subarray superiore ,AnArray)
SortIt(1, TotalElement, AnArray)
Si parte con la richiesta di ordinare gli elementi dell’array compresi tra 1 e TotalElement, si riduce poi questo intervallo attraverso Lo e Hi fino a quando nel subarray non resta che un elemento. Questo è ovviamente ordinato e quindi si attiva la catena pop.
Per dividere i Subarrays usiamo una variabile locale Mid. Questi Subarrays saranno prima ordinati (sorted) o poi (fusi) merged.
CASO BASE si ha quando i due subarrays sono ridotti ad una sola variabile cioè sono banalmente ordinati.
Quando si arriva al Caso Base allora si attiva il processo di Merge tra i due arrays adiacenti rimasti.Se invece siamo in presenza di subarrays con più di un elemento questo implica che il subarray deve essere ordinato.
Sort(7,8)
Sort(5,6)
Sort(5,8)
Sort(3,4)
Sort(1,2)
Sort(1,4)
Sort(1,8)
3 5 2 6 4 1 7 5
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
3 5 2 6 4 1 7 5
1 2 3 4 5 6 7 853 62 14 57
1 2 3 4 5 6 7 8153 2 6 4 7 5
53 62 41 75
2 3 5 6 1 4 5 7
1 2 3 4 5 5 6 7
1
3
2 4 5
6
7
PROGRAM Mergesort(output,Infile);CONSTLo=1;Hi=8;TYPETipoArr=ARRAY[1..8] OF integer;VAR AnArray:TipoArr; I, Mid:integer;
PROCEDURE SortIt(Lo, Hi: integer; VAR AnArray:TipoArr);
VARMid:integer;BEGINMid:=(Lo+Hi) DIV 2;IF Lo < Mid THEN
SortIt(Lo,Mid,AnArray);IF Mid+1 < Hi THEN
BEGIN SortIt(Mid+1,Hi,AnArray);END;
Merge(Lo,Mid,Hi,AnArray);END;
PROCEDURE Merge(Lo, Mid, Hi: integer; VAR AnArray:TipoArr);
VARTemp: TipoArr;Index, Index1, Index2 :integer;BEGINIndex1:=Lo;Index2:=Mid+1;FOR Index:=Lo TO Hi DO
BEGINIF Index1 > Mid THEN
BEGINUpdate(AnArray, Index2, Temp[Index]);
ENDELSE IF Index2 > Hi THEN
Update(AnArray, Index1, Temp[Index]);ELSE IF AnArray[Index1] < AnArray[Index2] THEN BEGIN
Update(AnArray, Index1, Temp[Index]); END ELSE
Update(AnArray, Index2, Temp[Index]);END;FOR Index:=Lo TO Hi DOAnArray[Index]:=Temp[Index];FOR Index:=Lo TO Hi DOwrite(AnArray[Index]:3);
writeln;END;
PROCEDURE Update(VAR AnArray:TipoArr; VAR CandidateIndex:integer;
VAR NewElement:integer);BEGIN NewElement:=AnArray[CandidateIndex]; CandidateIndex:=CandidateIndex+1END;
{ ******** MAIN *******}
BEGINSortIt(Lo,Hi,AnArray);END.
PROCEDURE Merge(Lo, Mid, Hi: integer; VAR AnArray:ArrayType);BEGINEND;
PROCEDURE SortIt(Lo, Hi: integer; VAR AnArray:ArrayType);VARMid:integer;BEGINMid:=(Lo+Hi) DIV 2;IF Lo<Mid THEN SortIt(Lo, Mid, AnArray)IF Mid+1 < Hi THEN SortIt(Mid+1, Hi, AnArray)Merge(Lo, Mid, Hi, AnArray)END;
Sort(1,2)
Sort(1,4)
Sort(1,8)
1 4 8
Lo Mid Hi Mid+1
IF Lo < Mid THEN SortIt(Lo, Mid, AnArray) IF Mid+1 < Hi THEN SortIt(Mid+1, Hi, AnArray)
Mid (Lo+Hi) DIV 2
mer
ge
1 2 4 1 1 2 2 m
erge
1 8 5
Sort(5,8)
5 6 8
mer
ge
Sort(5,6)5 6 5
Sort(7,8)7 8 8
mer
ge
mer
ge
Sort(3,4)
3 3 4 4
merge
Una maniera per verificare se la procedura SortIt funziona bene è quella di scrivere la procedura di merge, con le seguenti scritte di controllo.
PROCEDURE Merge(Lo, Mid, Hi:integer; VAR AnArray:ArrayType)BEGIN
write(‘Subrange del 1° Merge (‘,Lo:1,’..’,Mid:1,’)’);write(‘Subrange 2° Merge (‘,Mid+1:1,’..’,Hi:1,’)’);write(‘Subrange Ordinato (‘,Lo:1,’..’,Ni:1,’)’);
END;
PROCEDURE Update(VAR AnArray:ArrayType; VAR CandidateI:integer; VAR NewElements:ElementType);BEGINNewElement:=AnArray[CandidateI];CandidateI:= CandidateI+1END;
PROCEDURE Merge(Lo, Mid, Hi: integer; VAR AnArray:ArrayType);VARTemp: ArrayType;I, I1, I2 :integer;BEGIN I1:=Lo; I2:=Mid+1;
FOR I:=Lo TO HiIF I1 > Mid THEN Update(AnArray, I2, Temp[I])ELSE IF I2 > Hi THEN Update(AnArray, I1, Temp[I])ELSE IF AnArray[I1] < AnArray[I2] THEN Update(AnArray, I1, Temp[I])ELSE
Update(AnArray, I2, Temp[I])FOR I:=Lo TO Hi DO
AnArray[I]:=Temp[I]END;
I1=LoI2=Mid+1
I=Lo I1>Mid I2>Hi A(I1)<A(I2)
A(I1) T(I)
T(I) A(I2)I2 I2+1
I=Hi
I=Lo I=Hi
UP(A,I2,T(I))
UP(A,I1,T(I))
T(I) A(I1)I1 I1+1
UP(A,I1,T(I))UP(A,I2,T(I))
T(I) A(I1)I1 I1+1
T(I) A(I2)I2 I2+1
SISI SI
Se è stata controllata tutta la prima metà allora aggiungi diret -tamente la seconda
Se è stata controllata tutta la seconda metà allora aggiungi direttamente la prima
Inserisci l’elemento più piccolo e incrementa opportunamente l’indice
I1=LoI2=Mid+1
I=Lo I1>Mid I2>Hi A(I1)<A(I2)
A(I1) T(I)
T(I) A(I2)I2 I2+1
I=Hi
I=Lo I=Hi
UP(A,I2,T(I))
UP(A,I1,T(I))
T(I) A(I1)I1 I1+1
UP(A,I1,T(I))UP(A,I2,T(I))
T(I) A(I1)I1 I1+1
T(I) A(I2)I2 I2+1
2 8 21 24 13 15 17 181 2 3 4 5 6 7 8
A BD
C
I I1 I2 INCR. xx T(I) 1 1 5 INCR. I1 2
C2 2 5 INCR. I1 8
C
3 3 5 INCR. I2 13
D
4 3 6 INCR. I2 15
D5 3 7 INCR. I2 17
D6 3 8 INCR. I1 18
B7 4 8 INCR. I1 21
B8 5 8 INCR. I2 24
A
Merge-Sort
Svantaggi del Merge-Sort
Necessita di un vettore di appoggio
Effettua gli spostamenti anche se il vettore di partenza è già ordinato
EsercizioLa Torre di Hanoi.Dati tre pioli verticali e n dischi di dimensioni decrescenti infilati nel primo piolo trasferire tutti i dischi sul secondo piolo, in maniera da mantenere l’ordine decrescente, dal basso verso l’alto, adoperando un terzo piolo di appoggio.
Algoritmo1 - sposta i primi n-1 dischi dal piolo 0 al piolo 2 rispettando l’ordine 2 - sposta l’ultimo disco dal piolo 0 al piolo 13 - sposta i primi n-1 dischi dal piolo 2 al piolo 1 rispettando l’ordine
Descrivere il processo ricorsivo implementato nel seguente programma e l’albero di ricorsione
PROGRAM TorreDiHanoi (output);TYPE piolo=0..2;VAR i, nmossa: integer;PROCEDURE muovi(disco:integer; sorgente, destinazione:piolo);BEGIN nmossa:=nmossa+1; writeln(nmossa:3, ' muovi il disco ',disco:2, ' da',sorgente:2, ' a', destinazione:2)END;
PROCEDURE Hanoi(n:integer; sorgente, destinazione, ausiliario:piolo);BEGIN IF n=1 THEN muovi(1,sorgente, destinazione) ELSE BEGIN Hanoi(n-1,sorgente, ausiliario, destinazione); muovi(n,sorgente, destinazione); Hanoi(n-1, ausiliario, destinazione,sorgente) ENDEND;BEGIN FOR i:=2 TO 4 DO BEGIN nmossa:=0; writeln(' ----------------------------- '); writeln(' mossa per',i:3,' dischi'); Hanoi(i,0,1,2); readln ENDEND.
CONSIGLI PER LA PROGETTAZIONE DI ALGORITMI RICORSIVI
1 – Assicurarsi di aver preso in considerazione tutti i possibili casi base
Ad esempio nel caso del Fattoriale non avevamo tenuto conto del caso di N<0
FUNCTION Fattoriale (N:integer):integer;BEGIN
IF N=0 THEN Fattoriale:=1ELSE Fattoriale:=N*Fattoriale(N-1)END;
RICORDARSI CHEl’ordine con cui le istruzioni vengono eseguite, se prima o dopo la chiamata ricorsivaA- se una o più istruzioni riducono la dimensione del problema esse devono
precedere la chiamata ricorsiva B- se una o più istruzioni necessitano del risultato della ricorsione vanno
poste dopo la chiamata ricorsiva
CORREZIONE ESERCIZI
PROGRAM Simmetrica(input,output);{ Assegnata una matrice NxN determinare, con una procedura ricorsiva,se è simmetrica.}TYPEArrayx=Array[1..10,1..10] of integer;VARA:arrayx; N,M1,M2:integer;FUNCTION simme(VAR A1:arrayx;M,I,J:integer):boolean;BEGINIF i>M THEN simme:=TRUE ELSE IF A1[i,j]=A1[j,i] THEN BEGIN IF j<=i THEN simme:=simme(A1,M,i,j+1) ELSE simme:=simme(A1,M,i+1,1) END ELSE simme:=FALSEEND;
{******** MAIN************}N:=5;M1:=2;M2:=1;ScriviMatrice(A,N);writeln;writeln(' La simmetria Š ',simme(A,N,M1,M2));readlnEND.
PROGRAM palin(output,input);TYPEStrin=STRING[10];VAR A1:strin;N1,som1:integer;FUNCTION palindroma(VAR A:strin;N,i:integer):boolean;BEGINIF i>N DIV 2 THEN palindroma:=TRUE ELSE BEGIN IF A[i]=A[N-i+1] THEN palindroma:=palindroma(A,N,i+1) ELSE palindroma:=FALSE END;END;
***MAIN***BEGINA1:='annna';N1:=length(A1);writeln(A1,' è ',palindroma(A1,N1,1));readlnEND.
***************************Fornire una funzione ricorsiva tale che assegnata una lista ordinata di numeri interi dica quanti e quali dei numeri in essa contenuti sono numeri di Fibonacci.
Es. L1=[1,3,7,11,13, 19, 21, 33, 34]I numeri di Fibonacci presenti nella lista sono 6 (1, 3, 13, 21, 34)
***************************Data una matrice di interi MxN scrivere una funzione ricorsiva che valga TRUE se la somma degli elementi di ogni riga è minore della riga precedente e la somma degli elementi di ogni colonna è maggiore della somma della colonna precedente, FALSE altrimenti.
1 3 2 58 1 4 27 9 2 65 3 1 4
2 3 6 51 3 5 44 1 4 22 3 0 5
TRUE
FALSE
11152413
16131110
20 16 9 17
9 10 15 16
ESERCIZIO
Assegnate due stringhe M1 e M2 verificare se M2 è un prefisso di S1 con una procedura ricorsiva.
