Diferente pentru pd intre reviziile #111 si #112

Nu exista diferente intre titluri.

Diferente intre continut:

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>
<tex> $I(S) = 1 + \sum_{v=0}^{5} E[(N - \sum_{u \leq v} n_u), (2N - \sum_{u \leq v} D[u] n_u), v] $</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ă

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.