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.
PROGRAM sommavet(output,input);
TYPE
Vett=ARRAY[1..10] OF integer;
VAR
A1:vett; N1,som1:integer;
PROCEDURE somma(VAR A:vett;VAR som:integer;N:integer);
BEGIN
IF N=0 THEN
som:=0
(*MAIN*)
ELSE
BEGIN
BEGIN
N1:=10;
writeln(' push ',n:3,som:5);
FOR i:=1 TO N1 DO
Somma(A,som,(N-1));
Read(A1[i];
som:=som+A[N];
somma(A1,som1,N1);
writeln(' pop ',n:3,som:5);
writeln('La somma Š ',som1:4);
END;
readln
END;
END.
sommave1
PROGRAM sommavet(output,input);
TYPE
Vett=ARRAY[1..10] OF integer;
VAR
A1:vett; N1,som1:integer;
PROCEDURE somma(VAR A:vett;VAR som:integer;N:integer);
BEGIN
IF N=0 THEN
(*MAIN*)
writeln(' fine ')
BEGIN
ELSE
N1:=10;
BEGIN
FOR i:=1 TO N1 DO
writeln(' push ',n:3,som:5);
Read(A1[i];
som:=som+A[N];
somma(A1,som1,N1);
Somma(A,som,(N-1));
writeln('La somma Š ',som1:4);
writeln(' pop ',n:3,som:5);
readln
END;
END.
END;
sommave2
PROGRAM sommavet(output,input);
TYPE
Vett=ARRAY[1..10] OF integer;
VAR
A1:vett; N1,som1:integer;
PROCEDURE somma(VAR A:vett;VAR som:integer;N:integer);
BEGIN
IF N<>0 THEN
(*MAIN*)
BEGIN
BEGIN
writeln(' push ',n:3,som:5);
N1:=10;
som:=som+A[N];
FOR i:=1 TO N1 DO
Somma(A,som,(N-1));
Read(A1[i];
writeln(' pop ',n:3,som:5);
somma(A1,som1,N1);
END;
writeln('La somma Š ',som1:4);
END;
readln
END.
sommave3
PROGRAM sommavet3(output,input);
TYPE
Vett=ARRAY[1..10] OF integer;
VAR
A1:vett; N1:integer;
FUNCTION somma(VAR A:vett;N:integer):integer;
BEGIN
IF N=0 THEN
(*MAIN*)
somma:=0
BEGIN
ELSE
N1:=10;
Somma:=Somma(A,(N-1))+A[N];
FOR i:=1 TO N1 DO
END;
Read(A1[i];
somma(A1,som1,N1);
writeln('La somma Š ',som1:4);
readln
END.
sommavef
PROGRAM sommavet(output,input);
TYPE
Vett=ARRAY[1..10] OF integer;
VAR
A1:vett; i,N1,somp1,somd1:integer;
PROCEDURE somma(VAR A:vett;VAR somp,somd:integer;N:integer);
BEGIN
IF N=0 THEN
BEGIN
(*MAIN*)
somp:=0;
BEGIN
somd:=0
N1:=10;
END
FOR i:=1 TO N1 DO
ELSE
Read(A1[i];
BEGIN
N1:=10;
Somma(A,somp,somd,(N-1)); writeln;
IF A[N] MOD 2=0 THEN
FOR i:=1 TO N1 DO
somp:=somp+A[N]
write(A1[i]:4);
ELSE
writeln;
somd:=somd+A[N];
somma(A1,somp1,somd1,N1);
END;
writeln('La somma pari è ',somp1:4,
END;
' la somma dispari è ',somd1:4);
readln
END.
Dato un vettore di interi scrivere una procedura ricorsiva che
trovi il valore del numero più grande in esso contenuto
FUNCTION Vettor(Indice:integer;VAR A1:arrayx;
VAR Max:integer):integer;
BEGIN
IF Indice =0 THEN
MAX:=0
ELSE
BEGIN
Vettor:= Vettor (Indice-1,A1, Max);
IF (A1[Indice] > Max) THEN Max :=A1[Indice];
END;
Vettor:= Max;
END;
PROGRAM Diagonale(input,output);
{ Assegnata una matrice MxM determinare, con una procedura ricorsiva,
il valore massimo in ciascuna delle due diagonali principali.}
TYPE
Arrayx=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;
{******** MAIN************}
N:=5;
BEGIN
ScriviMatrice(A,N);
IF N1=0 THEN
Diagona(N,N,A,M1,M2);
BEGIN
writeln(' I Massimi sono ', M1,' e ',M2);
MD1:=0;
readln
MD2:=0;
END.
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}
VAR
N2,N3:integer;
BEGIN
IF N1=0 THEN
BEGIN
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;
.
ESERCIZI
ESERCIZI
•Sommare le seguenti espressioni per tutti gli interi compresi tra N1 ed
N2
i  1;
2
i  2i ; 2i  i
2
3
FUNCTION Sommatoria (N11,N22:integer):integer;
BEGIN
IF N11=N22 THEN
Sommatoria:=N22*N22+1
ELSE
Sommatoria :=N22*N22+1+Sommatoria(N11,N22-1)
END;
sopn1n3
Esercizi sui vettori. Scrivere una funzione e/o procedura ricorsiva che
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)
FUNCTION Vettori(IndiceA:integer; VAR max:integer;
VAR A1:arrayx):integer;
{Cerca l'elemento massimo del vettore A }
BEGIN
IF IndiceA =0 THEN
Max:=0
ELSE
{MAIN}
Vettori:=Vettori(IndiceA-1,max,A1);
BEGIN
IF A1[IndiceA]>max THEN
N:=9;
max:= A1[IndiceA];
A[1]:=………………….;
Vettori:=max;
scriviVettore(A,N);
END;
differenza(N,D,A);
writeln(‘differenza massima‘,D);
writeln('massimo',Vettori(N,N,A));
END.
PROCEDURE Differenza(IndiceA:integer;
VAR diff:integer;VAR A1:arrayx);
{ Trova la massima differenza nel vettore A }
BEGIN
IF IndiceA =1 THEN
diff:=0
ELSE
Differenza(IndiceA-1,diff,A1);
IF abs(A1[IndiceA]- A1[IndiceA-1])>diff THEN
diff:= abs(A1[IndiceA]-A1[IndiceA-1]);
END;
maxvet
Esercizi sulle matrici
Assegnata una matrice A di interi
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.
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.
Esempio
1
3
5
2
4
6
8
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.
Esempio
Cercare le occorrenze di ‘e’ nel seguente testo:
La Vispa Teresa
Avea tra l’erbetta
A volo sorpresa
Gentile 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.}
TYPE
Arrayx=Array[1..10,1..10] of integer;
VAR
A:arrayx;
N,i1,M1,M2:integer;
FUNCTION Diagona(i,N1:integer;VAR A1:arrayx;VAR MD1,MD2:integer):boolean;
{Controlla se la somma delle due diagonali sono uguali}
BEGIN
IF i>N1 THEN
Diagona:=FALSE
ELSE
BEGIN
MD1:=MD1+A1[i,i];
MD2:=MD2+A1[i,n1+1-i];
Diagona:=diagona(i+1,N1,A,MD1,MD2); {MAIN}
BEGIN
END;
A[…,…]:=xxxx;
IF MD1=MD2 THEN Diagona:=TRUE;
N:=5;i1:=1;
END;
ScriviMatrice(A,N);
writeln('Somme uguali ',Diagona(i1,N,A,M1,M2));
readln;
END.
PROGRAM Diagonale(input,output);
{ Assegnata una matrice MxM determinare, con una funzione ricorsiva,
se ci sono due righe uguali.}
TYPE
Arrayx=Array[1..10,1..10] of integer;
VAR
A:arrayx;
N,i1,j1:integer;
FUNCTION righe(i,j,N1,M1:integer;VAR A1:arrayx):boolean;
{Cerca due righe uguali}
BEGIN
IF i=N1 THEN
Righe:=FALSE
ELSE
IF j>M1 THEN
Righe:=TRUE
ELSE
IF A1[i,j]= A1[i+1,j] THEN
Righe:=righe(i,j+1,N1,M1,A1)
ELSE
Righe:=righe(i+1,1,N1,M1,A1)
END;
END;
{MAIN}
BEGIN
A[..,..]:=xxxx;
N:=5;i1:=1;j1:=1;
ScriviMatrice(A,N);
writeln('Righe ',righe(i1,j1,N,N,A));
readln;
END.
PROGRAM Diagonale(input,output);
{ Assegnata una matrice MxM determinare, con una funzione ricorsiva,
il valore massimo tra i massimi delle diagonali principali.}
TYPE
Arrayx=Array[1..10,1..10] of integer;
VAR
A:arrayx;
N,i1,tem:integer;
FUNCTION massim(i,N1:integer;VAR A1:arrayx;VAR temp:integer):integer;
{Cerca il massimo delle due diagonali}
BEGIN
IF i=N1 THEN
Temp:=0
ELSE
{MAIN}
Massim:=massim(i+1,N1,A1,temp);
BEGIN
IF temp<A[i,i] THEN temp:=A[i,i];
A[..,..]:=xxx;
IF temp<A[i,N1-i+1] THEN temp:= A[i,N1-i+1];
N:=5;i1:=1;
Massim:=temp;
ScriviMatrice(A,N);
END;
writeln('Massimo ',massim(i1,N,A,tem));
END;
readln;
END.
PROGRAM Diagonale(input,output);
{ Assegnata una matrice MxM, con una funzione ricorsiva, Controlla che in ogni riga i ci sono giusto i numeri negativi .}
TYPE
Arrayx=Array[1..10,1..10] of integer;
VAR
A:arrayx;
N,i1,j1,conta:integer;
FUNCTION Riga(i,j,N1:integer;VAR A1:arrayx;VAR conta:integer):boolean;
{Controlla che in ogni riga i ci sono giusto i numeri negativi}
BEGIN
IF i>N1 THEN
riga:=TRUE
ELSE
IF J>N1 THEN
{MAIN}
BEGIN
BEGIN
IF conta=i THEN
A[…,…]:=-xxxx;
BEGIN
N:=5;i1:=1;
Conta:=0;
j1:=1;
Riga:=riga(i+1,1,N1,A1,conta)
conta:=0;
END
ScriviMatrice(A,N);
ELSE
writeln(' la riga ',Riga(i1,j1,N, A, conta));
riga:=FALSE
readln
END
END.
ELSE
BEGIN
IF A1[i,j]<0 THEN conta:=conta+1;
IF conta<=i THEN Riga:=riga(i,j+1,N1,A1,conta)
ELSE
riga:=FALSE
END;
END;
PROGRAM Diagonale(input,output);
{ Assegnata una matrice MxM determinare, con una funzione ricorsiva,
se è simmetrica.}
TYPE
Arrayx=Array[1..10,1..10] of integer;
VAR
A:arrayx;
N,i1,j1:integer;
FUNCTION Simme(i,j,N1:integer;VAR A1:arrayx):boolean;
{Controlla se la matrice è simmetrica}
BEGIN
IF i>N1 THEN
Simme:=TRUE
ELSE
IF j>N1 THEN simme:=simme(i+1,i+2,N1,A1)
ELSE
IF A1[i,j]<>A1[j,i] THEN
{MAIN}
Simme:=FALSE
BEGIN
ELSE
A[1,1]:=1;
simme:=simme(i,j+1,N1,A1)
N:=5;i1:=1;j1:=1;
END;
ScriviMatrice(A,N);
writeln('La simmetria ',simme(i1,j1,N,A));
readln
END.
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
Esercizio
La 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.
Algoritmo
1 - 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 1
3 - 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)
END
END;
BEGIN
FOR i:=2 TO 4 DO
BEGIN
nmossa:=0;
writeln(' ----------------------------- ');
writeln(' mossa per',i:3,' dischi');
Hanoi(i,0,1,2);
readln
END
END.
***************************
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
8
7
5
20
3
1
9
3
16
2
4
2
1
9
5
2
6
4
11
15
24
13
FALSE
17
TRUE
2
1
4
2
3
3
1
3
6
5
4
0
5
4
2
5
9
10
15
16
16
13
11
10
ESERCIZIO
Assegnate due stringhe M1 e M2 verificare se M2 è un prefisso di S1
con una procedura ricorsiva.