Ce calculeaza algoritmul dat?
Am nevoie de subpunctul b) vă rog.
Răspunsuri la întrebare
Răspuns:
calculează termenii triunghiului Pascal, care se calculează după formula recurentă: a[i,j]=a[i-1,j]+a[i-1,j-1] (am folosit notaţia pascal a elementelor matricei)
Explicație:
Triunghiul Pascal: incepe de la linia şi coloana 0 (n este linia, iar k este coloana, şi cum 0<=k<=n, obţinem un triunghi din matrice)
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
.............
Vom calcula prin apelarea lui ALG a tuturor termenilor până la linia a 6-ea, adică a liniei cu indicele 5, şi astfel poate facem ceva concluzii şi pt. subpunctul a... :)))
ALG(0,0)=1, ALG(1,0)=1, ALG(1,1)=1, ALG(2,0)=1, ALG(2,1)=ALG(1,1)+ALG(1,0)=1+1=2, ALG(2,2)=1, ALG(3,0)=1, ALG(3,1)=ALG(2,1)+ ALG(2,0)= ALG(1,1)+ALG(1,0)+1=1+1+1=3, ALG(3,2)=ALG(2,2)+ALG(2,1)= 1+ ALG(1,1)+ALG(1,0)=1+1+1=3, ALG(3,3)=1, Trecem la linia cu indicele 4:
ALG(4,0)=1, ALG(4,1)=ALG(3,1)+ALG(3,0)=ALG(2,1)+ ALG(2,0)+1 =ALG(1,1)+ALG(1,0) + 1+1=1+1+1+1=4, ALG(4,2)=ALG(3,2)+ALG(3,1)= ALG(2,2)+ALG(2,1)+ALG(2,1)+ ALG(2,0)=1+ALG(1,1)+ALG(1,0)+ALG(1,1)+ALG(1,0) +1=1+1+1+1+1+1=6, ALG(4,3)=ALG(3,3)+ALG(3,2)=1+ALG(2,2)+ALG(2,1)= 1+1+ ALG(1,1)+ALG(1,0)=1+1+1+1=4, ALG(4,4)=1, Trecem la linia cu indicele 5:
ALG(5,0)=1, ALG(5,1)=ALG(4,1)+ALG(4,0)=ALG(3,1)+ALG(3,0)+1=ALG(2,1)+ ALG(2,0)+1+1= ALG(1,1)+ALG(1,0)+1+1+1=1+1+1+1+1=5,
ALG(5,2)=ALG(4,2)+ALG(4,1)=ALG(3,2)+ALG(3,1)+ALG(3,1)+ALG(3,0)= ALG(2,2)+ALG(2,1)+ALG(2,1)+ ALG(2,0)+ALG(2,1)+ ALG(2,0)+1= 1 + ALG(1,1)+ALG(1,0)+ALG(1,1)+ALG(1,0)+1+ALG(1,1)+ALG(1,0)+1+1= 10, UUFFF , ÎN FINE FACEM ALG(5,3)= ALG(4,3)+ALG(4,2)=ALG(3,3)+ALG(3,2)+ ALG(3,2)+ALG(3,1)=1+ALG(2,2)+ALG(2,1)+ALG(2,2)+ALG(2,1)+ALG(2,1)+ ALG(2,0)=1+1+ALG(1,1)+ALG(1,0)+1+ALG(1,1)+ALG(1,0)+ALG(1,1)+ALG(1,0)+1= 1+1+1+1+1+1+1+1+1+1=10.
Aici pentru ALG(5,3) poţi număra numărul de apeluri şi să observi că unele apeluri se fac repetat, adică exponenţial