CORSO DI PROGRAMMAZIONE MOD. B prof. E. Burattini Gruppo 3 (ML-ZZ) a.a. 2005-2006
description
Transcript of CORSO DI PROGRAMMAZIONE MOD. B prof. E. Burattini Gruppo 3 (ML-ZZ) a.a. 2005-2006
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);TYPEVett=ARRAY[1..10] OF integer;VAR A1:vett; N1,som1:integer;PROCEDURE somma(VAR A:vett;VAR som:integer;N:integer);BEGINIF N=0 THEN som:=0 ELSEBEGIN writeln(' push ',n:3,som:5); Somma(A,som,(N-1)); som:=som+A[N]; writeln(' pop ',n:3,som:5); END;END;
(*MAIN*)BEGINN1:=10;FOR i:=1 TO N1 DO
Read(A1[i];somma(A1,som1,N1);
writeln('La somma Š ',som1:4); readlnEND.
sommave1
(*MAIN*)BEGINN1:=10;FOR i:=1 TO N1 DO
Read(A1[i];somma(A1,som1,N1);
writeln('La somma Š ',som1:4); readlnEND.
sommave2
PROGRAM sommavet(output,input);TYPEVett=ARRAY[1..10] OF integer;VAR A1:vett; N1,som1:integer;PROCEDURE somma(VAR A:vett;VAR som:integer;N:integer);BEGINIF N=0 THEN writeln(' fine ')ELSEBEGIN writeln(' push ',n:3,som:5); som:=som+A[N]; Somma(A,som,(N-1)); writeln(' pop ',n:3,som:5);END;END;
(*MAIN*)BEGINN1:=10;FOR i:=1 TO N1 DO
Read(A1[i];somma(A1,som1,N1);
writeln('La somma Š ',som1:4); readlnEND.
sommave3
PROGRAM sommavet(output,input);TYPEVett=ARRAY[1..10] OF integer;VAR A1:vett; N1,som1:integer;PROCEDURE somma(VAR A:vett;VAR som:integer;N:integer);BEGINIF N<>0 THENBEGIN writeln(' push ',n:3,som:5); som:=som+A[N]; Somma(A,som,(N-1)); writeln(' pop ',n:3,som:5);END;END;
(*MAIN*)BEGINN1:=10;FOR i:=1 TO N1 DO
Read(A1[i];somma(A1,som1,N1);
writeln('La somma Š ',som1:4); readlnEND.
sommavef
PROGRAM sommavet3(output,input);TYPEVett=ARRAY[1..10] OF integer;VAR A1:vett; N1:integer;FUNCTION somma(VAR A:vett;N:integer):integer;BEGINIF N=0 THEN somma:=0 ELSE Somma:=Somma(A,(N-1))+A[N];END;
PROGRAM sommavet(output,input);TYPEVett=ARRAY[1..10] OF integer;VARA1:vett; i,N1,somp1,somd1:integer;PROCEDURE somma(VAR A:vett;VAR somp,somd:integer;N:integer);BEGINIF N=0 THEN BEGIN somp:=0; somd:=0 END ELSE BEGIN Somma(A,somp,somd,(N-1)); IF A[N] MOD 2=0 THEN somp:=somp+A[N] ELSE somd:=somd+A[N]; END;END;
(*MAIN*)BEGINN1:=10;FOR i:=1 TO N1 DO
Read(A1[i];N1:=10;writeln;FOR i:=1 TO N1 DOwrite(A1[i]:4);writeln;somma(A1,somp1,somd1,N1); writeln('La somma pari è ',somp1:4,
' la somma dispari è ',somd1:4); readlnEND.
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;
Dato un vettore di interi scrivere una procedura ricorsiva che trovi il valore del numero più grande in esso contenuto
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; .
ESERCIZI
ESERCIZI
•Sommare le seguenti espressioni per tutti gli interi compresi tra N1 ed N2
FUNCTION Sommatoria (N11,N22:integer):integer;BEGINIF N11=N22 THENSommatoria:=N22*N22+1ELSESommatoria :=N22*N22+1+Sommatoria(N11,N22-1)END;
ii2;i2i1i 322 ;
sopn1n3
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
FUNCTION Vettori(IndiceA:integer; VAR max:integer;VAR A1:arrayx):integer;
{Cerca l'elemento massimo del vettore A }BEGINIF IndiceA =0 THENMax:=0 ELSEVettori:=Vettori(IndiceA-1,max,A1);IF A1[IndiceA]>max THEN max:= A1[IndiceA];Vettori:=max;END;
PROCEDURE Differenza(IndiceA:integer; VAR diff:integer;VAR A1:arrayx);
{ Trova la massima differenza nel vettore A }BEGINIF IndiceA =1 THEN diff:=0 ELSE
Differenza(IndiceA-1,diff,A1);IF abs(A1[IndiceA]- A1[IndiceA-1])>diff THENdiff:= abs(A1[IndiceA]-A1[IndiceA-1]);
END;
{MAIN}BEGINN:=9;A[1]:=………………….;scriviVettore(A,N);differenza(N,D,A);writeln(‘differenza massima‘,D);writeln('massimo',Vettori(N,N,A));END.
maxvet
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;
FUNCTION Diagona(i,N1:integer;VAR A1:arrayx;VAR MD1,MD2:integer):boolean;{Controlla se la somma delle due diagonali sono uguali}BEGINIF i>N1 THENDiagona:=FALSEELSE BEGIN
MD1:=MD1+A1[i,i];MD2:=MD2+A1[i,n1+1-i];Diagona:=diagona(i+1,N1,A,MD1,MD2);END;
IF MD1=MD2 THEN Diagona:=TRUE;END;
{MAIN}BEGINA[…,…]:=xxxx;N:=5;i1:=1;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.}TYPEArrayx=Array[1..10,1..10] of integer;VARA:arrayx;N,i1,j1:integer;
{MAIN}BEGINA[..,..]:=xxxx;N:=5;i1:=1;j1:=1;ScriviMatrice(A,N);writeln('Righe ',righe(i1,j1,N,N,A));readln;END.
FUNCTION righe(i,j,N1,M1:integer;VAR A1:arrayx):boolean;{Cerca due righe uguali}BEGINIF i=N1 THEN
Righe:=FALSEELSE
IF j>M1 THEN Righe:=TRUE
ELSEIF A1[i,j]= A1[i+1,j] THENRighe:=righe(i,j+1,N1,M1,A1)ELSERighe:=righe(i+1,1,N1,M1,A1)
END;
END;
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;
FUNCTION massim(i,N1:integer;VAR A1:arrayx;VAR temp:integer):integer;{Cerca il massimo delle due diagonali}BEGINIF i=N1 THENTemp:=0ELSEMassim:=massim(i+1,N1,A1,temp);IF temp<A[i,i] THEN temp:=A[i,i];IF temp<A[i,N1-i+1] THEN temp:= A[i,N1-i+1];Massim:=temp;END;
END;
{MAIN}BEGINA[..,..]:=xxx;N:=5;i1:=1;ScriviMatrice(A,N);writeln('Massimo ',massim(i1,N,A,tem));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 .}TYPEArrayx=Array[1..10,1..10] of integer;VARA: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 BEGIN
IF conta=i THENBEGINConta:=0;Riga:=riga(i+1,1,N1,A1,conta)
END ELSE riga:=FALSE
ENDELSE
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;
{MAIN}BEGINA[…,…]:=-xxxx;N:=5;i1:=1;j1:=1;conta:=0;ScriviMatrice(A,N);writeln(' la riga ',Riga(i1,j1,N, A, conta));readlnEND.
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;
FUNCTION Simme(i,j,N1:integer;VAR A1:arrayx):boolean;{Controlla se la matrice è simmetrica}BEGINIF i>N1 THENSimme:=TRUEELSE
IF j>N1 THEN simme:=simme(i+1,i+2,N1,A1)ELSE
IF A1[i,j]<>A1[j,i] THENSimme:=FALSEELSEsimme:=simme(i,j+1,N1,A1)
END;
{MAIN}BEGINA[1,1]:=1;N:=5;i1:=1;j1:=1;ScriviMatrice(A,N);writeln('La simmetria ',simme(i1,j1,N,A));readlnEND.
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
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.
***************************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.