returnează R[J, S];
==
La prima vedere, numărul stărilor este $2 * (2N)^6^ = 2 * 60^6^ = 93,312 * 10^9^$, deci numărul stărilor este prea mare pentru a intra în limite rezonabile de spaţiu şi timp. Observăm totuşi că toate stările îndeplinesc condiţia $n{~0~} + n{~1~} + n{~2A~} + n{~2B~} + n{~3~} + n{~4~} = N$. Numărul total al stărilor este numărul tuplurilor care îndeplinesc egalitatea şi condiţiile $n{~k~} ≥ 0$. Vom numerota cele 6 tipuri de grămezi prin numere de la 0 la 5. Vom calcula valorile $N{~S~}[g, b, v]$ care reprezintă numărul de variante de a grupa $b$ bile în $g$ grămezi, astfel încât cea mai mică grămadă să aibă cel puţin mărimea tipului de indice $0 ≤ v ≤ 5$. Notăm cu $D$ şirul dimensiunilor tipurilor, $(0, 1, 2, 2, 3, 4)$ şi observăm că o stare descrisă prin $(g, b, v)$ ori are o grămadă de dimensiune $D{~v~}$ ori toate grămezile sunt mai mari decât această dimensiune. Atunci recurenţa de calcul pentru $N{~S~}$ este: $N{~S~}[g, b, v] = N{~S~}[g, b, v + 1] + N{~S~}[g - 1, b - D{~v~}, v]$ cu cazul particular $N{~S~}[0, 0, 5] = 1$. Numărul total de stări este valoarea $N{~S~}[N, 2*N, 0]$. Pentru valoarea maximă a lui $N$ din enunţ, am obţinut $S[30, 60, 0] = 8266$. Rezultă deci că numărul total real al stărilor este relativ mic, iar soluţia noastră se încadrează în limitele de timp şi spaţiu date.
La prima vedere, numărul stărilor este $2 * (2N)^6^ = 2 * 60^6^ = 93,312 * 10^9^$, deci numărul stărilor este prea mare pentru a intra în limite rezonabile de spaţiu şi timp. Observăm totuşi că toate stările îndeplinesc condiţia $n{~0~} + n{~1~} + n{~2A~} + n{~2B~} + n{~3~} + n{~4~} = N$. Numărul total al stărilor este numărul tuplurilor care îndeplinesc egalitatea şi condiţiile $n{~k~} ≥ 0$. Vom numerota cele 6 tipuri de grămezi prin numere de la 0 la 5. Vom calcula valorile $N{~S~}[g, b, v]$ care reprezintă numărul de variante de a grupa $b$ bile în $g$ grămezi, astfel încât cea mai mică grămadă să aibă cel puţin mărimea tipului de indice $0 ≤ v ≤ 5$. Notăm cu $D$ şirul dimensiunilor tipurilor, $(0, 1, 2, 2, 3, 4)$ şi observăm că o stare descrisă prin $(g, b, v)$ ori are o grămadă de dimensiune $D{~v~}$ ori toate grămezile sunt mai mari decât această dimensiune. Atunci recurenţa de calcul pentru $N{~S~}$ este: $N{~S~}[g, b, v] = N{~S~}[g, b, v + 1] + N{~S~}[g - 1, b - D{~v~}, v]$ cu cazul particular $N{~S~}[0, 0, 5] = 1$. Numărul total de stări este valoarea $N{~S~}[N, 2*N, 0]$. Pentru valoarea maximă a lui $N$ din enunţ, am obţinut $N{~S~}(30) = N{~S~}[30, 60, 0] = 8266$. Rezultă deci că numărul total real al stărilor este relativ mic, iar soluţia noastră se încadrează în limitele de timp şi spaţiu date.
Pentru o stare $S$ dată, numărul stărilor posibile $S'$ în care putem ajunge este foarte mic. În cel mai rău caz, perechile de grămezi care reprezintă mutarea din pasul curent sunt din mulţimea ${(0, 2A), (0, 2B), (0, 3), (0, 4), (1, 3), (1, 4), (2A, 4), (2B, 4)}$, deci un jucător are maxim 8 mutări posibile de efectuat. După ce am ales tipurile de grămezi pe care efectuăm mutarea, este irelevantă alegerea grămezilor cu dimensiunile date, deoarece toate alegerile duc la aceeaşi stare următoare.
Un mod de a stoca tabloul $R$ astfel încât spaţiul necesar să fie minim este folosirea unui dicţionar care să stocheze valorile $R[J, n_0, n_1, n_{2A}, n_{2B}, n_3, n_4]$ pentru toate stările valide, folosind astfel doar $O(N{~S~}(N))$ spaţiu. Dicţionarul poate fi implementat printr-o tabelă de dispersie sau arbori binari de căutare, în C++ folosind chiar $map$ sau $hash_map$ din STL. Altă opţiune este codificarea fiecărei stări $S$ printr-un număr întreg cuprins între 1 şi $N{~S~}(N)$, caz în care tabloul $R$ poate fi stocat într-o matrice de dimensiune $2xN{~S~}(N)$. Asocierea dintre descrierea unei stări (numărul de grămezi de fiecare tip) şi numărul său de ordine poate fi precalculată şi stocată într-un dicţionar sau poate fi calculată în $O(1)$ cu ajutorul unor formule. În primul caz, vom genera prin backtracking toate variantele posibile de stări într-o ordine oarecare şi vom aloca fiecărei stări câte un număr, stocând izomorfismul într-un dicţionar.
Varianta mai complexă, dar mai elegantă presupune stabilirea unei ordini fixe a stărilor şi apoi folosirea unor tehnici combinatoriale pentru a calcula numărul corespunzător unei stări sau starea corespunzătoare unui număr. Vom defini mai formal o stare ca un 6-tuplu $(n{~0~}, n{~1~}, n{~2A~}, n{~2B~}, n{~3~}, n{~4~})$ şi vom ordona toate stările lexicografic (stările sunt ordonate după $n{~0~}$; în caz de egalitate, sortarea se face după $n{~1~}$ ş.a.m.d.). Atunci numărul de ordine $I(S)$ al unei stări $S$ este:
<tex> $I(S) = 1 + \sum_{v=1}^{5} E[(N - \sum_{u<v} n_u), (2N - \sum_{u<v} D[u] n_u), (v - 1)] $</tex>
Numărul de ordine al unei stări calculat de formula de mai sus este numărul de stări care au o valoare mai mică pentru $n{~0~}$ plus numărul de stări care au aceeaşi valoare pentru $n{~0~}$ dar o valoare mai mică pentru $n{~1~}$ ş.a.m.d. $E[g, b, v]$ este numărul de stări cu $g$ grămezi care au în total $b$ bile iar cea mai mică grămadă are exact $n{~v~}$ bile.
<tex> $E[g, b, v] = S[g, b, v] - S[g, b, v + 1]$ </tex>
Inversa funcţiei $I(S)$ calculează
To be continued ...
