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.