Se numesc :

Numerele lui Stirling de speta I :

h4. Numerele lui Stirling de speta I :

s(n,m) = numarul de permutari de ordin $n$ cu exact $m$ cicluri.

$s(n,m)$ = numarul de permutari de ordin $n$ cu exact $m$ cicluri.

Numerele lui Stirling de speta II :

h4. Numerele lui Stirling de speta II :

S(n,m) = numarul de partitionari ale unei submultimi de $n$ elemente in $m$ submultimi nevide.

$S(n,m)$ = numarul de partitionari ale unei multimi de $n$ elemente in $m$ submultimi nevide.

h2. Cerinta

h2. Indicatii de rezolvare

**Backtracking**:

 
h4. Backtracking:
 

Ideea "naiva" de rezolvare a acestei probleme presupune generarea tuturor permutarilor de ordin n si calcularea numarului de cicluri a fiecareia dintre acestea. Aceasta rezolvare are complexitatea exponentiala si va obtine 10 puncte.
"Stirling de speta I - Wikipedia":http://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind

<tex> S(n,m) = S(n-1,m-1) + k*S(n-1,m) </tex>

**Recursivitate**:

h4. Recursivitate:
 

Pentru un singur test, o metoda optima de rezolvare este cea care foloseste o functie recursiva si calculeaza la fiecare pas elementele necesare recurentei pasului actual. Totusi, daca nu este folosita memoizarea, la un numar mai mare de teste, aceasta rezolvare va iesi din timp. Aceasta metoda are complexitatea o(N*M*T). Folosind aceasta metoda veti obtine 50 de puncte, o sursa ce foloseste aceasta metoda poate fi gasita "aici":http://infoarena.ro/job_detail/429247?action=view-source.

**Programare dinamica**:

h4. Programare dinamica:
 

Solutia optima a acestei probleme este cea care foloseste metoda programarii dinamice. astfel vor fi precalculate 2 matrici s[N][M] si S[N][M] cu semnificatia s[i][j]=s(i,j) si S[i][j]=S(i,j). Folosindu-se aceasta metoda, la fiecare test vom raspunde in o(1) la intrebare si deci complexitatea va fi o(N*M + T). Aceasta rezolvare obtine 100 de puncte si o sursa ce o foloseste poate fi gasita "aici":http://infoarena.ro/job_detail/429246?action=view-source.
==Include(page="template/taskfooter" task_id="stirling")==