Question

Ajutați-mă cu subpunctul a) vă rog.

Answer 1

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 $2^{n-[n/2]+1} - 1$(suma primelor n-[n/2] randuri ale triunghiului), iar pentru restul, la linia n-[n/2] -1 avem $2^{n-[n/2]+1} - 4 = 2^{n-[n/2]+1} - 2^2$, si atunci totalul de apeluri facute (doar pentru triunghiul lui pascal format) sunt:

$2^{n-[n/2]+1} - 1 = \frac{2^n}{2^{[n/2]}}\cdot 2 - 1$

Daca n este par: [n/2] = n/2

$\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}$

Daca n este impar: $[n/2] = \frac{n-1}{2}$

$\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}$

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 ($q \approx 1.85, b_1 = 1.57$) si valoarea totala de apeluri o putem obtine inmultind suma de mai sus cu un termen al acestei progresii, astfel complexitatea este aproximativ $\sqrt{2}^n$