Ajutați-mă cu subpunctul a) vă rog.... Idea question from @Danutz98

Danutz98 @Danutz98

September 2019 1 216 Report

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

CinevaFaraNume

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$