Individual Teoria Recursiei
Individual Teoria Recursiei
Individual Teoria Recursiei
LUCRU INDIVIDUAL
TEORIA RECURSIILOR
Chișinău, 2017
CUPRINS:
1
Problema 1
Factorial
Să se determine factorialul unui numar. Să se alcătuiască variant nerecursivă şi recursivă ȋn Pascal şi
C care va afisa rezultatul pentru factorial.
2
Rezultat program Pascal nerecursiv Rezultat program Pascal recursiv
1, n 0,1
Fact(n)=
Fact ( n 1) * n, n 2
3
Problema 2
Suma numerelor pare.
Să se elaboreze un program care calculează suma numerelor pare pozitive până la n. În pascal și c+
+, metoda recursivă și nerecursivă.
4
pare.\n"; recursiei.\n";
cout<<"Rezolvare prin metoda cout<<"Introdu n= ";cin>>n;
nerecursiva.\n"; for(i=1; i<=n;i++)
cout<<"Introdu n= ";cin>>n; cout<<setw(4)<<i<<". t=
for(i=1; i<=n;i++) "<<setw(4)<<2*i<<";
cout<<setw(4)<<i<<". t= S("<<setw(4)<<i<<")=
"<<setw(4)<<2*i<<"; "<<setw(10)<<suma_p(i)<<";"<<endl;
S("<<setw(4)<<i<<")= }
"<<setw(10)<<suma_p(i)<<";"<<endl;
}
0, ă =0
={
−1
+2∗ ă >0
5
Problema 3
Suma numerelor impare.
Să se elaboreze un program care calculează suma numerelor impare pozitive până la n. În pascal și
c++, metoda recursivă și nerecursivă.
0, ă =0
={
−1
+2∗ −1 ă >0
7
Problema 4
Șirul Fibonacci
Se cere de scris un program ȋn Pascal şi C varianta recursivă şi nerecursivă a şirului de numere
Fibonacci:1,1,2,3,5,8,...21.
8
Rezultat program Pascal nerecursiv Rezultat program Pascal recursiv
Fibn 1, n 1, 2
Fib ( n 1) Fib ( n 2), n 2
9
Problema 5
Șirul Fibonacci modificat
Se cere de scris un program ȋn Pascal şi C,varianta recursivă şi nerecursivă, care afişează la ecran
şirul de numere: 1,1,1,2,3,7,23,164....
10
Rezultat program Pascal nerecursiv Rezultat program Pascal recursiv
Fibn 1, n 1, 2, 3
Fib ( n 1) * Fib ( n 2) Fib ( n 3), n 3
11
Problema 6
Suma sirului de numere
Să se calculeze suma primilor n termini ai şirului de numere : 1, 5, 9, 13, 17, … ,4n-3, …
12
Rezultat program Pascal nerecursiv Rezultat program Pascal recursiv
0, n 0
S(n)=
S (n 1) 4 * n 3
13
Problema 7
Suma numerelor
Este dat şirulde numere 1,6,11,16,21,….Să se determine suma primelor n numere a şiruluidat.Să se
alcătuiască variant nerecursiv şi recursiv ȋn Pascal şi C.
14
Rezultat program Pascal nerecursiv Rezultat program Pascal recursiv
1, n 0
S(n)=
S ( n 1) 5* n 4, n 1
15
Problema 8
Suma numerelor
Este datşirulde numere 1,6,11,16,21,….Să se determine suma primelor n numere a şirului dat. Să se
alcătuiască variant nerecursivă şi recursive ȋn Pascal şi C.
16
Rezultat program Pascal nerecursiv Rezultat program Pascal recursiv
1, n 0
S(n)=
S ( n 1) 5* n 4
17
Problema 9
Algoritmul lui Euclid
Să se determine cel mai mare divizor comun a două numere naturale. Să se scrie varianta recursivă
si nerecursivă in Pascal şi C.
18
Rezultat program Pascal nerecursiv Rezultat program Pascal recursiv
a,
ab
CMMDC(a,b)= cmmdc(a b, b), a b
cmmdc(a, b a), b a
19
Problema 10
Algoritmul lui Euclid
Să se determine cel mai mare divizor comun a trei numere naturale. Să se scrie varianta recursivă si
nerecursivă in Pascal şi C.
20
Rezultat program Pascal nerecursiv Rezultat program Pascal recursiv
a,abc
CMMDC(a,b,c)=
cmmdc (cmmdc (a , b ), b ) , a , b , c
21
Problema 11
Recursivitatea indirectă.
Calcularea valorilor a 2 funcţii F(x) şi G(x). Să se alcătuiască un program Pascal şi C utilizȋnd
recursia indirectă pentru a calcula valorile funcţiilor:
x 2, x 1 x ,x 0
f ( x) și g ( x)
g (x 1), x 1 f (x ) 1, 0
x
Program Pascal recursiv-indirect Program C recursiv-indirect
uses crt; # include<stdio.h>
var x:integer; # include<conio.h>
Function F(x:integer):integer; int G(int);
Forward; int F(int x){
Function G(x:integer):integer; if (x>1) return G(x-1);
begin else return x+2;}
if (x>=0) then G:=F(x)+1 int G(int x){
else G:=-x; if(x>=0) return F(x)+1;
end; else return -x;}
Function F(x:integer):integer;
begin void main (){
if (x>1) then F:=G(x-1) int x;
else F:=x+2;end; clrscr();
Begin printf ("Introdu x=");
Write ('Introdu x=');readln(x); scanf ("%d",&x);
Writeln ('F(',x,')=',F(x)); printf ("\n F(x)=%d",F(x));
Writeln ('G(',x,')=',G(x)); printf ("\n G(x)=%d",G(x));
readkey; getch();
End. }
22
Problema 12
Recursivitatea indirectă.
Calcularea valorilor a 2 funcţii F(x) şi G(x). Să se alcătuiască un program Pascal şi C utilizȋnd
recursia indirectă pentru a calcula valorile funcţiilor:
x2, x3 a ( x ) 5, x 0
a ( x) și b ( x) (x 1) 2, x 0
b ( x 2), x 3
Program Pascal recursiv-indirect Program C recursiv-indirect
uses crt; #include<stdio.h>
var x:integer; #include<conio.h>
Function A(x:integer):integer; int B(int);
Forward; int A(int x){
Function B(x:integer):integer; if(x<=3) return x*x;
begin else return B(x-2);}
if (x>=0) then B:=A(x)+5 int B(int x){
else B:=(x+1)*(x+1); end; if(x>=0) return A(x)+5;
Function A(x:integer):integer; else return(x+1)*(x+1);}
begin
if (x<=3) then A:=(x)*(x)else void main() {
A:=B(x-2);end; int x;
Begin clrscr();
Write ('introdu x=');readln(x); printf ("Introdu x=");
Writeln ('A(',x,')=',A(x)); scanf ("%d",&x);
Writeln ('B(',x,')=',B(x)); printf("\n A(x)=%d",A(x));
readkey; printf("\n B(x)=%d",B(x));
End. getch();
}
23
Problema 13
Recursivitatea indirectă.
Calcularea valorilor a 2 funcţii F(x) şi G(x). Să se alcătuiască un program Pascal şi C utilizȋnd
recursia indirectă pentru a calcula valorile funcţiilor:
x2, x3 (x 1)2 , x 0 x2, x0
a ( x ) b ( x 2),3 x 6 b ( x ) c ( 1) 1, 0 x 5 c ( x ) b ( x 1), 0 x 5
c ( x 1), x 6 a ( x ) 5, x 5 a ( x 1), x 5
25
Problema 14
Recursivitatea indirectă.
Calcularea valorilor a 2 funcţii F(x) şi G(x). Să se alcătuiască un program Pascal şi C utilizȋnd
recursia indirectă pentru a calcula valorile funcţiilor:
a,n0 b, n 0
a ( n) a b b ( n)
n 1 n1
,n0 a b ,n0
n 1n1
2
26
Problema 15
Recursivitatea indirectă.
Să se elaboreze un program care calculează valoarea termenilor an și bn pentru un x cunoscut. În
pascal și c++, metoda recursivă și nerecursivă.
Fie date trei serii:
ă =0 ă =0 ă =0
a ={ −1
,b = {3 și c = {3
+ +
−1 −1
−1 −1
, >0 ∗ ∗ , >0 + + , >0
√ −1 −1 √ −1 −1
3
28
Problema 16
Funcția Ackermann.
Să se alcătuiască un program Pascal pentru funcţia Ackermann:
introdu m, n: 0 0 introdu m, n: 0 0
Ack(0,0)=1 Ack(0,0)=1
29
Problema 17
Funcția Hermite.
Să se alcătuiască un program Pascal şi C pentru funcţia Hermite:
introdu m, n: 0 0 introdu m, n: 0 0
Hermite(0,0)=1 Hermite(0,0)=1
30
Problema 18
Funcția Cebâșev.
Să se alcăuiască un program Pascal şi unu C pentru funcţiile Cebȋşev:
introdu m, n: 0 0 introdu m, n: 0 0
Cevisev(0,0)=1 Cevisev(0,0)=1
31
Problema 19
Funcția Manna Pnuiele.
Să se alcăuiască un program Pascal şi unu C pentru funcţiile Manna Pnuiele:
introdu x: 1 introdu x: 1
Manapnuiele (1)=1 Manapnuiele (1)=1
32
Problema 20
Turnurile Hanoi.
Sunt date 3 tirje x, y, z. Pe tirja x sunt plasate n discuri aşezate ȋn ordinea descrescătoare a
diametrelor. Se cere de trecut toate discurile de pe tirja x pe tirja y folosind tirja intermediară z,
astfel ȋncȋt să se respecte următoarea condiţie: discul mai mic totdeauna se află deasupra celui mai
mare la orice transfer.
33
Problema 21
Compoziția a două funcții.
Sunt date două funcții f(x) și g(x):
2
2 +1<5 ( )={4+25≤<8
3 ≥8
2 ( )={
5 −3 +2≤1 2−+5>1
Se cere de găsit compziția:
1. f(g(f(x))); 2. g(f(g(x)));
3. f(g(f(g(f(x))))); 4. f(g(f(f(x))));
34
}
35
Problema 22
Să se elaboreze un program care calculează cmmdc pentru n numere. În pascal și c++, metoda
recursivă.
Program Pascal recursiv-indirect Program C recursiv-indirect
program cmmdc_n; #include <iostream.h>
uses crt; #include <conio.h>
type vector = array[1..100] of integer; #include <math.h>
var x:vector; n,i:integer; #include <stdlib.h>
function cmmdc(a,b:integer):integer; int x[100];
begin int cmmdc(int a, int b)
if(a=b) then cmmdc:=a {
else if(a==b)
if(a>b) then cmmdc:=cmmdc(a-b,b) return a;
else else
if(b>a) then cmmdc:=cmmdc(a,b- if(a>b)
a); return cmmdc(a-b,b);
end; else
function div_imp(p,q:integer):integer; return cmmdc(a,b-a);
var mij, d1, d2:integer; }
begin int div_imp(int p, int q){
if(abs(p-q)<=1) then int mij, d1, d2;
div_imp:=cmmdc(x[p], x[q]) if(abs(p-q)<=1) {return cmmdc(x[p],
else x[q]);}
begin else{
mij:=((p+q) div 2); //div_t x //int x.quot//x.rem
d1:=div_imp(p, mij); mij=div((p+q), 2).quot;
d2:=div_imp(mij+1,q); d1=div_imp(p, mij);
div_imp:=cmmdc(d1,d2); d2=div_imp(mij+1,q);
end; return cmmdc(d1,d2);
end; }
begin }
clrscr; void main()
writeln('Algoritmul Euclid. {
Determinarea cmmdc a n numere clrscr();
naturale.'); int a, b, n, i;
writeln('Rezolvare prin metoda cout<<"Algoritmul Euclid.
recursiva.'); Determinarea cmmdc a n numere
write('introdu numarul de elemente naturale."<<endl;
n='); cout<<"Rezolvare prin metoda
readln(n); recursiva."<<endl;
writeln('Introdu elementele'); cout<<"introdu numarul de elemente
for i:=1 to n do n=";cin>>n;
begin cout<<"Introdu elementele"<<endl;
write('x[',i,']= ');readln(x[i]); for (i=1; i<=n; i++){
end; cout<<"x["<<i<<"]= ";cin>>x[i];
write('cmmdc('); }
for i:=1 to n-1 do cout<<"cmmdc(";
write(x[i],', '); for (i=1; i<=n-1; i++){
write(x[n],')= '); cout<<x[i]<<", ";}
36
writeln(div_imp(1,n)); cout<<x[n]<<")= ";
end. cout<<div_imp(1,n);
}
37
Problema 23
Generarea părților unui număr.
Se dă un număr natural n. Să se elaboreze programele, în pascal și c++, metoda recursivă, care
generează toate partile lui n.
38
Rezultat program Pascal recursiv Rezultat program C recursiv
39
Problema 24
Curba Hilbert.
Hilbert a găsit o curbă care poate să treacăprin fiecare punct al spațiului. Numim curba Hilbert de
ordinul k curba realizată după următoarea regulă:
k k
1. trece prin fiecare nod al grilei 2 *2 ;
2. Trece prin noduri vecine ale curbei.
Curba Hilbert are următoarele elemente:
A B C D
41
Problema 25
Curba Sierpinski.
Sierpinski a găsit o curbă care poate să treacă prin fiecare punct al spațiului.
42
A(i- h;y=y+h;lineto((double)x*k,(double)y*k)
1);y:=y+h;y:=y+h;LineTo(round(x*k),roun ;
d(y*k)); D(i-1); }}
C(i-1);x:=x- void main(void){
h;y:=y+h;LineTo(round(x*k),round(y*k)); clrscr();
D(i-1); int gdriver = DETECT, gmode,
end; end; errorcode;
begin initgraph(&gdriver, &gmode,
Gd := Detect; "c:\\tcpp\\bgi");
InitGraph(Gd, Gm, 'C:\BP\BGI'); errorcode = graphresult();
ErrCode:=GraphResult; if (errorcode != grOk){
if ErrCode = grOk then printf("Graphics error: %s\n",
begin grapherrormsg(errorcode));
i:=0; h:=Cadru div 4; x:=3*h; printf("Press any key to halt:");
y:=3*h; k:=SizeWin/Cadru; getch();
repeat }else{
i:=i+1; x:=x-h; h:=h div 2; setbkcolor(15); i=0; h=div(Cadru,
y:=y+h; 4).quot; x=3*h; y=3*h;
HighVideo; SetColor(i); k=(double)SizeWin/Cadru;
SetLineStyle(SolidLn, 0, 1); do{ i=i+1; x=x-h; h=div(h, 2).quot;
MoveTo(round(x*k),round(y*k)); y=y+h;
A(i);x:=x+h;y:=y- setcolor(i);
h;LineTo(round(x*k),round(y*k)) setlinestyle(SOLID_LINE, 1, 1);
; B(i);x:=x-h;y:=y- moveto((double)x*k,(double)y*k);
h;LineTo(round(x*k),round(y*k)) A(i);x=x+h;y=y-
; C(i);x:=x- h;lineto((double)x*k,
h;y:=y+h;LineTo(round(x*k),round(y*k)); (double)y*k); B(i);x=x-h;y=y-
h;lineto((double)x*k,
D(i);x:=x+h;y:=y+h;LineTo(round(x*k),ro (double)y*k); C(i);x=x-
und(y*k)); h;y=y+h;lineto((double)x*k,(double)y*k)
until (i=n); ;
end
else D(i);x=x+h;y=y+h;lineto((double)x*k,(do
writeln('Eroare: ', uble)y*k); }
GraphErrorMsg(ErrCode)); while (!(i==n));
Readln; CloseGraph; getch(); }
end. closegraph();}
43
Problema 26
Covorul Sierpinski.
Vom considera o functie recursiva denumita SerpCov(), cu 3 parametri:
1. x,y-coordonatele centrului;
2. r-latura patratului central.
daca r>0, vom apela recursiv functia SerpCov() de 4 ori, pentru a desena fractalii corespunzatori celor
4 colturi ale patratului de latura r și cu centrul în punctul de coordonate (x,y);
44
Rezultat program Pascal recursiv Rezultat program C recursiv
N=4 N=6
45
Problema 27
Exemplu de transformare
47
Problema 28
Arborele.
Se dă un segment AB. Cu ajutorul lui se construieşte un arbore, aşa cum se vede în figura de mai
jos:
48
SetBkColor(15); printf("Press any key to halt:");
SetLineStyle(SolidLn, 0, 1); getch();
desenez(getmaxx div 2, getmaxy, }else{
getmaxx div 2, getmaxy-250,1,ls); setbkcolor(15);
end setlinestyle(SOLID_LINE, 1, 1);
else desenez(div(getmaxx(),2).quot,
writeln('Eroare: ', getmaxy(), div(getmaxx(),2).quot,
GraphErrorMsg(ErrCode)); getmaxy()-250, 1, ls);
Readln; getch();
CloseGraph; }
end. closegraph();
}
49
Problema 29
Generarea permutărilor.
Permutări a mulțimii A cu n elemente sunt toate mulțimele ordonate care se pot forma cu cele n
elemente ale lui A. Să se elaboreze un program care afișează toate permutările unei mulțimi cu
elemente de la 1 la n numere. În pascal și c++, metoda recursivă.
51
Problema 30
Generarea aranjamentelor.
Se dau două mulţimi A={1,2,...,p} şi B={1,2,...,n}. Se cer toate funcţiile injective definite pe A cu
p
valori în B. O astfel de problemă este una de generare a aranjamentelor de n luate câte p (A n).
Să se elaboreze un program care afișează toate aranjamentele unei mulțimi cu elemente de la 1 la n
numere a câte p. În pascal și c++, metoda recursivă.
Exemplu: p=2, n=3. Avem: 12, 21, 13, 31, 23, 32.
52
Rezultat program Pascal recursiv Rezultat program C recursiv
53
Problema 31
Generarea combinărilor.
Fiind dată mulţimea A={1,2,...,n}, se cer toate submulţimile ei cu p elemente. Deci “generarea
combinărilor de n, luate câte p”. De exemplu, dacă n=4 şi p=3, soluţiile sunt următoarele: {1,2,3},
{1,2,4}, {1,3,4} şi {2,3,4}.
Să se elaboreze un program care afișează toate combinările unei mulțimi cu elemente de la 1 la n
numere a câte p. În pascal și c++, metoda recursivă.
54
Rezultat program Pascal recursiv Rezultat program C recursiv
55
Problema 32
Problema celor n dame.
Fiind dată o tablă de şah cu dimensiunea n×n, se cer toate soluţiile de aranjare a n dame, astfel încât
să nu se afle două dame pe aceeaşi linie, coloană sau diagonală (damele să nu se atace reciproc). De
exemplu, dacă n=4, o soluţie este reprezentată în figura de mai jos:
57
Problema 33
62
Problema 34
64
Problema 35
Labirintul
Se dă un labirint sub formă de matrice cu m linii şi n coloane. Fiecare element al matricei
reprezintă o cameră a labirintului. Într-una din camere, de coordonate lin şi col, se găseşte un om. Se
cere să se găsească toate ieşirile din labirint. Nu este permis ca un drum să treacă de două ori prin
aceeaşi cameră. O primă problemă care se pune este precizarea modului de codificare a ieşirilor din
fiecare cameră a labirintului.
Fie l(i,j) un element al matricei. Acesta poate lua valori între 0 şi 15. Se consideră ieşirile spre
nord, est, sud şi vest, luate în această ordine. Pentru fiecare direcţie cu ieşire se
reţine 1, iar în caz contrar, se reţine 0. Un şir de patru cifre 1 sau 0 formează un
număr în baza 2. Acest număr este convertit în baza 10 şi reţinut în l(i,j). De
exemplu, pentru o cameră care are ieşire în nord şi vest, avem 1001 (2) =9 (10).
66
Rezultat program Pascal recursiv Rezultat program C recursiv
67