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ă...
