Folosind acest program:
#include <iostream>
using namespace std;
int nrApelari[1000][1000];
int totalApelari = 0;
int alg(int n, int k){
nrApelari[n][k]++;
totalApelari++;
//cout << n << ' ' << k << '\n';
if (k == 0 || n == k)
return 1;
else return alg(n-1, k) + alg(n-1,k-1);
}
int main(){
int n,k;
cin >> n >> k;
alg(n,k);
cout << "\n\n\n\n\n::::\n\n\n\n\n";
for(int i = 0; i <= n; i++){
for(int j = 0; j <= k && j <= i; j++){
cout << nrApelari[i][j] << '\t';
}
cout << '\n';
}
cout << "\n\n\n" << totalApelari<<"\n";
return 0;
}
Pentru datele de intrare n, [n/2]
Se poate observa ca se formeaza n-[n/2] randuri ale triunghiului lui pascal, in matricea nrApelari, avand in total [tex] 2^{n-[n/2]+1} - 1[/tex](suma primelor n-[n/2] randuri ale triunghiului), iar pentru restul, la linia n-[n/2] -1 avem [tex]2^{n-[n/2]+1} - 4 = 2^{n-[n/2]+1} - 2^2[/tex], si atunci totalul de apeluri facute (doar pentru triunghiul lui pascal format) sunt:
[tex]2^{n-[n/2]+1} - 1 = \frac{2^n}{2^{[n/2]}}\cdot 2 - 1[/tex]
Daca n este par: [n/2] = n/2
[tex]\frac{2^n}{2^{[n/2]}}\cdot 2 - 1 = \frac{2^n}{2^{n/2}} \cdot 2 - 1 = \frac{2^n}{\sqrt{2^n}}\cdot 2 - 1 = \frac{2^n\cdot \sqrt{2^n}}{2^n} \cdot 2 - 1 = \sqrt{2^n}\cdot 2 - 1 = 2^{n/2+1} - 1 \rightarrow 2^{1/2\cdot n} = (2^{(1/2)})^n = (\sqrt{2})^{n}[/tex]
Daca n este impar: [tex][n/2] = \frac{n-1}{2}[/tex]
[tex]\frac{2^n}{2^{[n/2]}}\cdot 2 - 1 = \frac{2^n}{2^{\frac{n-1}{2}}}\cdot 2 - 1 = \frac{2^n}{\sqrt{2^{n-1}}} \cdot 2 - 1 = \frac{2^n\cdot \sqrt{2^{n-1}}}{2^{n-1}}\cdot 2 - 1 = \frac{2^n\cdot \sqrt{2^{n-1}}}{\frac{2^n}{2}}\cdot 2 - 1 = \sqrt{2^{n-1}} \cdot 4 - 1 = 2^{\frac{n-1}{2}} \cdot 4 - 1 = 2^{\frac{n-1}{2} + 2} - 1 = 2^{\frac{n}{2}+ 1.5} - 1 = 2^{\frac{n/2}}\cdot 2^{1/2} - 1 \rightarrow 2^{1/2\cdot n} = (2^{(1/2)})^n = (\sqrt{2})^{n}[/tex]
Acum pentru partea din primele [n/2] randuri, raportul dintre numarul total si suma tuturor elementelor din triunghiul lui pascal de jos este aproximativ intr-o progresie geometrica ([tex] q \approx 1.85, b_1 = 1.57[/tex]) si valoarea totala de apeluri o putem obtine inmultind suma de mai sus cu un termen al acestei progresii, astfel complexitatea este aproximativ [tex]\sqrt{2}^n[/tex]
