Question

Recursivitate.

Proiectați un algoritm polinomial pentru a calcula valoarea ALG(n,k).

Am nevoie de subpunctul c.

Answer 1

Răspuns:

#include <iostream>

using namespace std;

long long n,k,m,p1=1,p2=1,i,ALGnk;

int main()

{

   cin >> n >> k;

   for (i=n; i>k; --i )

       p1=p1*i;

   m=n-k;

   for (i=2; i<=m; ++i)

       p2=p2*i;

   ALGnk=p1/p2;

   cout << ALGnk;

   return 0;

}

Explicație:

Am văzut că algoritmul ALG calculează numerele din triunghiul lui Pascal. Cum s-a propus să calculăm ALG(5,3), asta e termenul de pe linia cu indicele 5 şi coloana 3. Metoda recursivă este o metodă ca aspect simplă, dar cu o mare risipă de memorie şi timp. În subpunctul a) tr. să înţelegem şi argumentăm că algoritmul recursiv este exponenţial ( O(2^k), mai discutăm la aceast subiect...).  O parcurgere for i - -- for j  ne dă un algoritm O(n^2), adică polinomial. Asa algoritm ar fi să generăm Triunghiul lui Pascal până la numărul solicitat, folosind formula recurentă a[i][j]=a[i-1][j] + a[i-1][j-1].

Codul postat de mine aici realizează o complexitate O(n) , deci e tot polinomial. Se ştie de la mate, că o linie a triunghiului lui Pascal sunt coieficienţii binomiali Combinări din n luate câte k, unde k ia valori de la 0 la  n. Atunci termenul ALG(5,3) este Combinări din 5 luate câte 3. Pentru calcularea lui am folosit formula combinărilor. şi atât... :)))

Ceva neclar, întreabă...