h1. Coduri Gray
(Categoria _Matematica_, autor _Cosmin Negruseri_)
== include(page="template/implica-te/scrie-articole" user_id="alecman") ==
h2. Introducere
(Categoria _Matematica_, Autor _Cosmin Negruseri_)
Acest articol prezinta notiunea de **Cod Gray** si unele aplicatii ale lui in probleme de la concursurile de programare.
(toc){width: 20em}*{text-align:center} *Cuprins*
* 'Introducere':coduri-gray#introducere
* 'Problema 1: Turnurile din Hanoi':coduri-gray#hanoi
* 'Problema 2: Becuri':coduri-gray#becuri
* 'Problema 3: Matrix':coduri-gray#matrix
* 'Problema 4: Divizori':coduri-gray#divizori
* 'Problema 5: Sortnet':coduri-gray#sortnet
* 'Bibliografie':coduri-gray#biblio
Un cod _Gray_ de ordin <tex>n</tex> este un sir care contine toate numerele de la <tex>0</tex> la <tex>2^{n-1}</tex>, astfel ca oricare doua numere consecutive din sir difera in reprezentarea binara prin exact un bit. Pentru <tex>n >= 2</tex> exista mai multe coduri _Gray_ distincte. Un cod mai des intalnit, numit in engleza **binary reflected Gray code** (in continuare cand vom vorbi despre codul _Gray_ ne vom referi de fapt la acest cod). Modul de constructie al acestui cod este unul intuitiv: la fiecare pas adaugam numarul adaugat anterior, caruia ii modificam cel mai putin semnificativ bit, astfel ca numarul obtinut sa nu mai fi fost adaugat inainte la sir. _De exemplu_, daca ordinul este doi si avem la inceput numarul <tex>0</tex> in sir, vom adauga <tex>1</tex>, apoi <tex>3</tex>, iar apoi <tex>4</tex>.
h2(#introducere). Introducere
In acest articol vom nota acest cod cu <tex>G_{n}</tex>. O alta metoda de constructie care obtine acelasi cod _Gray_ este de a determina mai intai pe <tex>G_{n-1}</tex>, apoi daca notam cu <tex>G'_{n-1}</tex> sirul <tex>G_{n-1}</tex> inversat, atunci obtinem pe <tex>G_{n}</tex> daca punem cate un bit de <tex>0</tex> in fata fiecarui numar din <tex>G_{n-1}</tex>, iar acestea sunt urmate de numerele din <tex>G'_{n-1}</tex> carora le adaugam cate un bit de <tex>1</tex> ca bit semnificativ ( pe scurt <tex>G_{n} = 0G_{n-1},1G'_{n-1}</tex> (1) ). Observam ca acest cod este unul circular, adica ultimul numar si primul numar din cod difera prin **exact un bit**. Observam de asemenea ca fiecare cod de ordin <tex>n</tex> il contine pe cel de <tex>n-1</tex> ca prefix, deci am putea nota prin <tex>G_{\infty}</tex> sirul numerelor naturale in care orice doua numere consecutive difera in reprezentarea binara prin exact un bit si pentru care sirul primelor <tex>2^{n}</tex> elemente coincide cu <tex>G_{n}</tex>, oricare ar fi acest <tex>n</tex> un numar natural.
Un cod Gray de ordin $n$ este un sir care contine toate numerele de la $0$ la $2^n-1^$, astfel incat orice doua numere consecutive din sir sa difere in reprezentarea lor binara prin exact un bit. Exista mai multe coduri Gray distincte, cel mai des intalnit fiind asa-numitul **"binary reflected Gray code"** (in continuare cand vom vorbi despre codul Gray ne vom referi de fapt la acest cod). Modul de constructie este destul de intuitiv: fiecare numar nou este format din cel anterior prin modificarea celui mai putin semnificativ bit, astfel incat numarul sa nu mai fi fost adaugat inainte la sir (de exemplu, pentru $n = 2$ si primul numar $0$, sirul obtinut va fi $0, 1, 3, 2$).
Fie <tex>g(x)</tex> al <tex>x</tex>-lea numar din <tex>G_{\infty}</tex> (prin <tex>g(x)</tex> notam codul _Gray_ al numarului <tex>x</tex>) si <tex>g(y)-1</tex> la ce pozitie apare numarul <tex>y</tex> in sirul <tex>G_{\infty}</tex>. Ne punem problema calcularii eficiente a celor doua functii. Se poate demonstra prin inductie ca daca avem un numar <tex>x</tex> cu reprezentarea binara <tex>(... a_{2} a_{1} a_{0})_{2}</tex> si codul lui _Gray_, cu reprezentarea binara <tex>(... b_{2} b_{1} b_{0})_{2}</tex>, atunci avem <tex>b_{i} = a_{i} </tex> ^ <tex>a_{i+1}</tex> (2). _De exemplu_, daca avem numarul <tex>6</tex> cu reprezentarea binara <tex>110</tex>, atunci <tex>b_{0} = a_{0}</tex> ^ <tex>a_{1} = 0 </tex> ^ <tex>1 = 1</tex>, <tex>b_{1} = a_{1}</tex> ^ <tex>a_{2} = 1</tex> ^ <tex>1 = 0</tex>, <tex>b_{2} = a_{2}</tex> ^ <tex>a_{3} = 1</tex> ^ <tex>0 = 1</tex>, deci <tex>g(110) = 101</tex>. Din aceasta relatie tragem concluzia ca <tex>g(i) = x ^ (x / 2)</tex> (unde prin / am notat **impartire intreaga**). Din (2) obtinem ca <tex>b_{i}</tex> ^ <tex>b_{i+1}</tex> ^ <tex>b_{i+2}</tex> ^ <tex>... = (a_{i}</tex> ^ <tex>a_{i+1})</tex> ^ <tex>(a_{i+1}</tex> ^ <tex>a_{i+2})</tex> ^ <tex>(a_{i+2}</tex> ^ <tex>a_{i+3})</tex> ^ <tex>... = a_{i}</tex>. Aceasta suma este finita deoarece vom avea un <tex>b_{i}</tex> egal cu <tex>0</tex> si un <tex>a_{i}</tex> egal cu <tex>0</tex>, daca <tex>i</tex> este indeajuns de mare. Astfel <tex>g-1(y) = y</tex> ^ <tex>y/2</tex> ^ <tex>y/4</tex> ^ <tex>...</tex>
In continuare vom nota acest cod cu $G{~n~}$. Putem da astfel o noua metoda de constructie. Fie $G'{~n-1~}$ sirul $G{~n-1~}$ inversat, atunci obtinem $G{~n~}$ daca punem cate un bit $0$ in fata fiecarui numar din $G{~n-1~}$, urmat de numerele din $G'{~n-1~}$, carora le adaugam cate un $1$ ca bit semnificativ ( pe scurt $G{~n~} = 0G{~n-1~},1G'{~n-1~} (1)$). Se poate observa ca acest cod este circular, diferenta intre ultimul si primul numar fiind de exact un bit. De asemenea, orice cod de ordin $n$ il contine pe cel de $n-1$ ca prefix, deci am putea nota prin $G{~∞~}$ sirul numerelor naturale in care orice doua numere consecutive difera in reprezentarea binara prin exact un bit si pentru care sirul primelor $2^n^$ elemente coincide cu $G{~n~}$ (∀ $n$ ∈ _**N**_).
Fie $g(x)$ al $x$-lea numar din $G{~∞~}$ si $g-1(y)$ pozitia la care apare numarul $y$ in sirul $G{~∞~}$. Se pune problema calcularii eficiente a celor doua functii. Se poate demonstra prin inductie ca daca avem un numar $x$ cu reprezentarea binara $(...a{~2~}a{~1~}a{~0~}){~2~}$ si codul lui Gray $(...b{~2~}b{~1~}b{~0~}){~2~}$, atunci avem $b{~i~} = a{~i~} ^∧^ a{~i+1~}$ (2). De exemplu, pentru numarul $6$ cu reprezentarea binara $110$, atunci $g(110) = 101$. De aici se deduce ca $g(x) = x ^∧^ (x / 2)$. Din (2) obtinem ca $b{~i~} ^∧^ b{~i+1~} ^∧^ b{~i+2~} ^∧^ ... = (a{~i~} ^∧^ a{~i+1~}) ^∧^ (a{~i+1~} ^∧^ a{~i+2~}) ^∧^ (a{~i+2~} ^∧^ a{~i+3~}) ^∧^ ... = a{~i~}$. Suma este finita deoarece va exista un $b{~i~}$ egal cu $0$ si un $a{~i~}$ egal cu $0$ (daca $i$ este indeajuns de mare). Rezulta astfel ca $g-1(y) = y ^∧^ y/2 ^∧^ y/4 ^∧^ ...$
Din cele de mai sus obtinem urmatoarele metode:
}
==
Sa vedem mai departe cateva probleme:
h2. Problema 1: _Turnurile din Hanoi_
h2(#hanoi). Problema 1: _Turnurile din Hanoi_
Avem trei tije si <tex>n</tex> discuri de dimensiuni diferite plasate in ordinea descrescatoare a dimensiunilor pe prima tija. Se doreste mutarea tuturor discurilor pe cea de a doua tija, singurul tip de miscare posibila fiind mutarea unui disc de pe o tija pe alta, cu conditia ca pe tija destinatie discul din varf (daca exista un asemenea disc) sa fie mai mare decat discul pe care il mutam acum.
Avem trei tije si $n$ discuri de dimensiuni diferite plasate in ordinea descrescatoare a dimensiunilor pe prima tija. Se doreste mutarea tuturor discurilor pe cea de a doua tija, singurul tip de miscare posibila fiind mutarea unui disc de pe o tija pe alta, cu conditia ca pe tija destinatie discul din varf (daca exista un asemenea disc) sa fie mai mare decat discul pe care il mutam acum.
h3. Rezolvare:
h3. Rezolvare
Aceasta este o problema clasica in predarea recursivitatii, dar ea are o solutie care se foloseste de codul _Gray_. Urmarim pas cu pas ce bit se schimba de la numerele consecutive ale lui <tex>G_{n}</tex>, acest bit corespunde discului pe care il vom muta (cel mai putin semnificativ bit corespunde celui mai mic disc, iar cel mai semnificativ bit corespunde celui mai mare disc). Problema este ca stim ce disc sa mutam, dar nu stim pe ce tija. Dar exista o regula simpla care ne poate ajuta: un disc nu trebuie plasat pe alt disc cu aceeasi paritate. Aceasta strategie rezolva si ea in numar minim de pasi problema, acest numar fiind <tex>2^{n} - 1</tex>.
Aceasta este o problema clasica in predarea recursivitatii, dar ea are o solutie care se foloseste de codul Gray. Urmarim la fiecare pas ce bit se schimba de la numerele consecutive ale lui $G{~n~}$ - acest bit corespunde discului pe care il vom muta (cel mai putin semnificativ bit corespunde celui mai mic disc etc). Problema este ca nu stim pe ce tija trebuie sa mutam discul respectiv. Exista o regula simpla care ne poate ajuta: un disc nu trebuie plasat pe alt disc cu aceeasi paritate. Folosind aceasta strategie, putem rezolva problema in numar minim de pasi ( $2^n^ - 1$ ).
h2. Problema 2:
h2(#becuri). Problema 2: _Becuri_
Un bec este conectat la <tex>n</tex> intrerupatoare. Fiecarui astfel de intrerupator ii poate fi schimbata starea prin apasare. Problema este ca nu stim starea lor initiala. Se cere sa se determine o strategie care ar face numar minim de apasari in cazul cel mai rau, pentru a aprinde becul.
Un bec este conectat la $n$ intrerupatoare. Fiecarui astfel de intrerupator ii poate fi schimbata starea prin apasare. Problema este ca nu stim starea lor initiala. Se cere sa se determine o strategie care ar face numar minim de apasari in cazul cel mai defavorabil, pentru a aprinde becul.
h3. Rezolvare
Pentru a fi siguri ca aprindem becul trebuie in cel mai rau caz sa trecem prin toate configuratiile apasat/ne-apasat ale intrerupatoarelor. Pentru a schimba starea curenta trebuie sa apasam cel putin un buton, deci in cazul cel mai defavorabil va trebui sa facem cel putin $2^n^ - 1$ apasari. Codul Gray ne da o posibilitate de a trece prin toate configuratiile trecand de la una la alta prin o apasare de buton, rezolvandu-ne problema.
Pentru a fi siguri ca aprindem becul trebuie in cel mai rau caz sa trecem prin toate configuratiile apasat/ne-apasat ale intrerupatoarelor. Pentru a schimba starea curenta trebuie sa apasam cel putin un buton, deci in cazul cel mai defavorabil va trebui sa facem cel putin <tex>2^{n} - 1</tex> apasari. Codul _Gray_ ne da o posibilitate de a trece prin toate configuratiile trecand de la una la alta prin o apasare de buton, rezolvandu-ne problema.
h2. Problema 3: _Matrix_ ( acm.sgu.ru - 249)
h2(#matrix). Problema 3: '_Matrix_':http://acm.sgu.ru/problem.php?contest=0&problem=249 (SGU)
Trebuie sa aranjati numerele de la <tex>0</tex> la <tex>2^{n + m}-1</tex> intr-o matrice cu <tex>2^{n}</tex> randuri si <tex>2^{m}</tex> coloane. De asemenea, numerele care sunt situate in celule adiacente pe verticala sau orizontala trebuie sa difere prin exact un bit in reprezentarea lor binara. Matricea este ciclica, adica pentru fiecare rand celula cea mai din stanga se considera invecinata cu cea mai din dreapta, de asemenea pentru fiecare coloana celula cea mai de sus se considera invecinata cu celula cea mai de jos. La intrare se dau numerele <tex>n</tex> si <tex>m</tex> (<tex>0 < n, m; n + m <= 20</tex>). Trebuie sa afisati o asemenea matrice. De exemplu daca <tex>n = 1</tex> si <tex>m = 1</tex> o matrice ar fi
<tex>\lceil 0</tex> <tex>2 \rceil</tex>
<tex>\lfloor 1</tex> <tex>3 \rfloor</tex>.
Trebuie sa aranjati numerele de la $0$ la $2^(n + m)^ - 1$ intr-o matrice cu $2^n^$ randuri si $2^m^$ coloane. De asemenea, numerele care sunt situate in celule adiacente pe verticala sau orizontala trebuie sa difere prin exact un bit in reprezentarea lor binara. Matricea este ciclica, adica pentru fiecare rand celula cea mai din stanga se considera invecinata cu cea mai din dreapta, de asemenea pentru fiecare coloana celula cea mai de sus se considera invecinata cu celula cea mai de jos. La intrare se dau numerele $n$ si $m$ ( $0 < n, m; n + m <= 20$ ). Trebuie sa afisati o asemenea matrice. De exemplu daca $n = 1$ si $m = 1$ o matrice ar fi
( $0$ $2$ )
( $1$ $3$ )
h3. Rezolvare:
h3. Rezolvare
O prima metoda ar fi de determinare a codului <tex>G_{n+m}</tex>, iar apoi de a-l scrie serpuit in matrice, adica in liniile de index par de la stanga la dreapta, iar in liniile de index impar de la dreapta la stanga.
O prima metoda ar fi de a determina codului $G{~n+m~}$, iar apoi de a-l scrie serpuit in matrice (liniile de index par de la stanga la dreapta, cele de index impar in sens invers).
De exemplu, daca <tex>n = 2</tex> si <tex>m = 2</tex> avem:
<tex>G_{4} = {0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, 1000}</tex>
De exemplu, daca $n = 2$ si $m = 2$ avem:
$G{~4~} = {0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, 1000}$
| 0000 | 0001 | 0011 | 0010 |
| 0100 | 0101 | 0111 | 0110 |
| 1100 | 1101 | 1111 | 1110 |
| 1000 | 1001 | 1011 | 1010 |
Alta modalitate de rezolvare care ne da de fapt aceeasi matrice este urmatoarea: Intregul din celula <tex>(i, j)</tex> a matricei va fi in reprezentarea binara rezultatul concatenarii reprezentarii binare a intregului de index <tex>i</tex> din codul <tex>G_{n}</tex> cu reprezentarea binara a intregului de index <tex>j</tex> din codul <tex>G_{m}</tex>.
Alta modalitate de rezolvare care ne da de fapt aceeasi matrice este urmatoarea: in celula $(i,j)$ vom avea rezultatul concatenarii reprezentarilor binare ale lui $i$ (din codul $G{~n~}$) si $j$ (din codul $G{~m~}$).
De exemplu, daca avem <tex>n = 3</tex> si <tex>M = 2</tex>:
De exemplu, matricea pentru $n = 3$ si $m = 2$ este:
|_. - |_. 00 |_. 01 |_. 11 |_. 10 |
|_. 000 | 00000 | 00001 | 00011 | 00010 |
|_. 101 | 10100 | 10101 | 10111 | 10111 |
|_. 100 | 10000 | 10001 | 10011 | 10010 |
Este evident ca orice doua numere din matrice vor fi diferite, orice doua numere adiacente in matrice sunt diferite in reprezentarea binara prin exact un bit. In concurs limita de timp era foarte stransa si trebuia folosita functia prezentata anterior. Deci pe linia <tex>i</tex> coloana <tex>j</tex> a matricei scriem numarul <code>(binToGray(i) << M) | binToGray(j)</code>.
Este evident ca orice doua numere adiacente in matrice sunt diferite in reprezentarea binara prin exact un bit. In concurs limita de timp era foarte stransa si trebuia folosita functia prezentata anterior. Deci pe linia $i$, coloana $j$ a matricei scriem numarul (binToGray(i) << M) | binToGray(j).
h2. Problema 4: _Divizori_
h2(#divizori). Problema 4: '_Divizori_':problema/divizori
Vom considera un numar natural <tex>N</tex>. In sirul <tex>A</tex> vom aseza toti divizorii lui <tex>N(2<=N<=2.000.000.000)</tex>. Se cere sa se permute elementele sirului <tex>A</tex> astfel incat pentru oricare doua elemente consecutive <tex>A[i]</tex> si <tex>A[i+1]</tex> sa avem fie <tex>A[i]=A[i+1]*p</tex>, fie <tex>A[i+1]=A[i]*p</tex>, unde <tex>p</tex> este un numar prim oarecare. Valoarea <tex>p</tex> poate diferi de la o pereche de elemente la alta. De exemplu pentru <tex>N = 12</tex> o posibila solutie ar fi <tex>1, 2, 3, 4, 12, 6, 3</tex>.
Vom considera un numar natural $N$. In sirul $A$ vom aseza toti divizorii lui $N (2 <= N <= 2.000.000.000)$. Se cere sa se permute elementele sirului $A$ astfel incat pentru oricare doua elemente consecutive $A[i]$ si $A[i+1]$ sa avem fie $A[i] = A[i+1] * p$, fie $A[i+1] = A[i] * p$ ( $p$ numar prim oarecare). Valoarea $p$ poate diferi de la o pereche de elemente la alta. De exemplu, pentru $N = 12$ o posibila solutie ar fi $1, 2, 3, 4, 12, 6, 3$.
h3. Rezolvare
Numarul <tex>N</tex> are maxim <tex>2*N^{1/2}</tex> divizori. Daca descompunem numarul <tex>N</tex> in factori primi atunci il vom putea scrie sub forma <tex>P_{1}^{E_{1}}*P_{2}^{E_{2}}*...*P_{k}^{E_{k}}</tex>, unde <tex>P_{1}, P_{2}, ..., P_{k}</tex> sunt numere prime si <tex>E_{1}, E_{2}, ..., E_{k}</tex> numere naturale mai mari ca zero. Un divizor al lui N va fi reprezentat printr-un vector de exponenti <tex>(e_{1}, e_{2}, ..., e_{k})</tex> unde <tex>0<=e_{i}<=E_{k}</tex>. Prin urmare, problema noastra poate fi usor redusa la urmatoarea cerinta: ordonati toti vectorii <tex>(e_{1}, e_{2}, ..., e_{k})</tex> unde <tex>0<=e_{i}<=E_{k}</tex>, intr-un sir cu proprietatea ca diferenta intre doi vectori consecutivi se realizeaza la o singura pozitie a vectorilor si cele doua elemente ale vectorilor de pe pozitia respectiva difera prin o unitate.
Numarul $N$ are maxim $2*N^1/2^$ divizori. Descompunerea lui $N$ in factori primi are forma $P{~1~}^E{~1~}^ * P{~2~}^E{~2~}^ * ... * P{~k~}^E{~k~}^$ ( $P{~1~}, P{~2~}, ..., P{~k~}$ - numere prime, si $E{~i~} ∈ _**N**_, E{~i~} > 0$ ). Un divizor al lui $N$ va fi reprezentat printr-un vector de exponenti $(e{~1~}, e{~2~}, ..., e{~k~})$ unde $0<=e{~i~}<=E{~k~}$. Prin urmare, problema noastra poate fi usor redusa la urmatoarea cerinta: ordonati toti vectorii $(e{~1~}, e{~2~}, ..., e{~k~})$ intr-un sir cu proprietatea ca diferenta intre doi vectori consecutivi se realizeaza la o singura pozitie a vectorilor si cele doua elemente ale vectorilor de pe pozitia respectiva difera prin o unitate.
Exemplul din enuntul problemei se poate reprezenta astfel:
<tex>1, 2, 4, 12, 6, 3</tex>
<tex>P_{1}=2 E_{1}=2</tex>
<tex>P_{2}=3 E_{2}=1</tex>
<tex>(0,0), (1,0), (2,0), (2,1), (1,1), (0,1)</tex>
Aceasta problema este o generalizare a determinarii codului _Gray_ si poate fi rezolvata generalizand metoda expusa mai sus. Presupunem ca stim sa generam o solutie pentru <tex>M=N/(P_{k}E_{k})</tex> (o solutie pentru un numar cu <tex>k-1</tex> factori primi). Sa vedem cum generam o solutie pentru <tex>N</tex>. Fie <tex>C</tex> vectorul solutie pentru <tex>M</tex> si <tex>R</tex> vectorul <tex>C</tex> inversat (primul element al lui <tex>R</tex> este ultimul al lui <tex>C</tex>, etc.). O solutie pentru <tex>N</tex> poate fi obtinuta in urmatoarea forma:
<tex>C, P_{k}*R, {P_{k}}}^{2}*C {P_{k}}^{3}*R ...</tex>
Astfel am concatenat <tex>E_{k}</tex> coduri pentru <tex>M</tex>, inmultind cu <tex>P_{k}</tex> si pe fiecare pozitie impara am pus secventa inversata pentru <tex>M</tex>. Am facut aceasta pentru ca cele doua capete ce vor ajunge in codul final consecutive sa difere numai prin <tex>P_{k}</tex>.
_Exemplu_: <tex>E_{1}=3; E_{2}=2; E_{3}=1</tex>
<tex>(0,0,0) (1,0,0) (2,0,0) (3,0,0)</tex>
Solutia pentru un factor prim.
<tex>(0,0,0) (1,0,0) (2,0,0) (3,0,0) (3,1,0) (2,1,0) (1,1,0) (0,1,0) (0,2,0) (1,2,0) (2,2,0) (3,2,0)</tex>
Solutia pentru doi factori primi.
<tex>(0,0,0) (1,0,0) (2,0,0) (3,0,0) (3,1,0) (2,1,0) (1,1,0) (0,1,0) (0,2,0) (1,2,0) (2,2,0) (3,2,0)</tex>
<tex>(3,2,1) (2,2,1) (1,2,1) (0,2,1) (0,1,1) (1,1,1) (2,1,1) (3,1,1) (3,0,1) (2,0,1) (1,0,1) (0,0,1)</tex>
Solutia pentru cei trei factori primi.
$1, 2, 4, 12, 6, 3$
$P{~1~} = 2 E{~1~} = 2$
$P{~2~} = 3 E{~2~} = 1$
$(0,0), (1,0), (2,0), (2,1), (1,1), (0,1)$
Aceasta problema este o generalizare a determinarii codului Gray si poate fi rezolvata generalizand metoda expusa mai sus. Presupunem ca stim sa generam o solutie pentru $M = N/(P{~k~}E{~k~})$ (o solutie pentru un numar cu $k-1$ factori primi). Sa vedem cum generam o solutie pentru $N$. Fie $C$ vectorul solutie pentru $M$ si $R$ vectorul $C$ inversat. O solutie poate fi:
$C, P{~k~}*R, P{~k~}^2^*C, P{~k~}^3^*R ...$
Astfel am concatenat $E{~k~}$ coduri pentru $M$, inmultind cu $P{~k~}$ si pe fiecare pozitie impara am pus secventa inversata pentru $M$. Am facut aceasta pentru ca cele doua capete ce vor ajunge in codul final consecutive sa difere numai prin $P{~k~}$.
Exemplu: $E{~1~} = 3; E{~2~} = 2; E{~3~} = 1$
$(0,0,0) (1,0,0) (2,0,0) (3,0,0)$ - Solutia pentru un factor prim.
$(0,0,0) (1,0,0) (2,0,0) (3,0,0) (3,1,0) (2,1,0) (1,1,0) (0,1,0) (0,2,0) (1,2,0) (2,2,0) (3,2,0)$ - Solutia pentru doi factori primi.
$(0,0,0) (1,0,0) (2,0,0) (3,0,0) (3,1,0) (2,1,0) (1,1,0) (0,1,0) (0,2,0) (1,2,0) (2,2,0) (3,2,0)$
$(3,2,1) (2,2,1) (1,2,1) (0,2,1) (0,1,1) (1,1,1) (2,1,1) (3,1,1) (3,0,1) (2,0,1) (1,0,1) (0,0,1)$ - Solutia pentru cei trei factori primi.
Complexitatea finala a solutiei este <tex>O(T)</tex> unde <tex>T</tex> reprezinta numarul de divizori ai lui <tex>N</tex>.
Complexitatea finala a solutiei este $O(T)$ unde $T$ reprezinta numarul de divizori ai lui $N$.
h2. Problema 5: _Sortnet_ (Mihai Patrascu, lot 2002)
h2(#sortnet). Problema 5: '_Sortnet_':problema/sortnet (Lot 2002)
O retea completa de sortare este o retea de sortare cu <tex>N</tex> fire de adancime <tex>D</tex> ce are <tex>D * (N/2)</tex> comparatori. Amintim principiul <tex>0-1</tex> care spune ca o retea de sortare sorteaza orice <tex>N</tex> numere daca aceasta sorteaza orice secventa de <tex>N</tex> numere <tex>0</tex> sau <tex>1</tex>. Problema noastra cere cate astfel de secvente de <tex>0</tex> si <tex>1</tex> nu sunt sortate corect.
O retea completa de sortare este o retea de sortare cu $N$ fire de adancime $D$ ce are $D * (N/2)$ comparatori. Amintim principiul $0-1$ care spune ca o retea de sortare sorteaza orice $N$ numere daca aceasta sorteaza orice secventa de $N$ numere $0-1$. Problema noastra cere sa se determine cate astfel de secvente de $0-1$ nu sunt sortate corect.
h3. Rezolvarea lui Mihai Patrascu
Observam ca dupa primul strat de comparatori sunt exact <tex>3^(N/2)</tex> rezultate posibile, pentru ca intrarile trecute printr-un comparator se transforma astfel <tex>0, 0 -> 0, 0 ; 0, 1 -> 1, 0; 1, 0 -> 1, 0; 1, 1 -> 1, 1</tex>. Pentru a testa fiecare astfel de rezultat daca e sortat sau nu de urmatoarele <tex>D-1</tex> straturi, nu vor trebui simulate toate in complexitate <tex>O(N * 3^{N/2} * D)</tex>. Prin generarea secventelor conform codului _Gray_ in baza 3 putem doar sa urmarim modificarea rezultatului pentru doua rezultate succesive in <tex>O(D)</tex>. Un numar in baza trei il transformam in unul in baza doi cu numar dublu de cifre, astfel <tex>0</tex> trece in <tex>00</tex>, <tex>1</tex> trece in <tex>10</tex> si <tex>2</tex> trece in <tex>11</tex>, acest cod reprezentand un rezultat posibil dupa evaluarea unei secvente binare de catre primul strat al retelei. Modificarea unei cifre in baza trei conform codului _Gray_ generalizat pentru numere in aceasta baza, duce la modificarea unei cifre in codul binar a unui bit. Urmarirea modificarilor facute de acest bit schimbat in evaluarile facute de reteaua de sortare o putem face in complexitate <tex>O(D)</tex>. Astfel complexitatea finala este <tex>O(3^{N/2} * D)</tex>.
Observam ca dupa primul strat de comparatori sunt exact $3^(N/2)^$ rezultate posibile, pentru ca intrarile trecute printr-un comparator se transforma astfel:
| (0,0) -> (0,0) | (0,1) -> (1,0) | (1,0) -> (1,0) | (1,1) -> (1,1) |
Pentru a testa fiecare astfel de rezultat daca e sortat sau nu de urmatoarele $D-1$ straturi, nu vor trebui simulate toate in complexitate $O(N * 3^N/2^ * D)$. Prin generarea secventelor conform codului Gray in baza 3 putem doar sa urmarim modificarea rezultatului pentru doua rezultate succesive in $O(D)$. Un numar in baza trei il transformam in baza doi cu numar dublu de cifre, astfel:
Mentionam ca problema este pe site-ul InfoArena ("Sortnet":http://infoarena.ro/problema/sortnet) si acolo o rezolvare <tex>O(2^{N} * D)</tex> intra in timp, dar si pentru aceasta trebuie sa folosim codul _Gray_ si sa urmarim modificarile date de schimbarea unui bit in evaluare.
Dam mai jos rezolvarea eleganta si usor de inteles a lui Mircea Pasoi:
| 0 -> 00 | 1 -> 10 | 2 - > 11 |
acest cod reprezentand un rezultat posibil dupa evaluarea unei secvente binare de catre primul strat al retelei. Modificarea unei cifre in baza trei conform codului Gray generalizat pentru numere in aceasta baza, duce la modificarea unei cifre in codul binar a unui bit. Urmarirea modificarilor facute de acest bit schimbat in evaluarile facute de reteaua de sortare o putem face in complexitate $O(D)$. Astfel complexitatea finala este $O(3^N/2^ * D)$.
Mentionam ca problema este pe site-ul InfoArena ('Sortnet':problema/sortnet) si acolo o rezolvare $O(2^N^ * D)$ intra in timp, dar si pentru aceasta trebuie sa folosim codul Gray si sa urmarim modificarile date de schimbarea unui bit in evaluare. Dam mai jos rezolvarea eleganta si usor de inteles a lui Mircea Pasoi:
== code(cpp) |
#include <stdio.h>
#define MAX_N 20
#define MAX_M 33
#define MAX_C 59049
#define FIN "sortnet.in"
#define FOUT "sortnet.out"
#define GRAY(x) ((x) ^ ((x) >> 1))
#define BIT(a, b) (((a) & (1 << (b))) > 0)
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define SORTED(x) (((x) & ((x)+1)) == 0)
#define FOR(i, a, b) for (i = (a); i < (b); i++)
int N, M, G[ 33 ][ 20 ], V[ 33 ], V2[ 33 ], Res;
inline int GRAY(int x)
{
return x ^ ( x >> 1 );
}
inline int BIT(int a, int b)
{
return (a & (1 << b)) > 0;
}
inline int MIN(int a, int b)
{
return (a < b) ? a : b;
}
inline int MAX(int a, int b)
{
return (a > b) ? a : b;
}
int N, M, G[MAX_M][MAX_N], V[MAX_M], V2[MAX_M], Res;
inline int SORTED(int x)
{
return (x & (x+1)) == 0;
}
int works(int n, int a)
{
int i, b, t;
V2[0] = n;
FOR (i, 0, M)
for (i = 0; i < M; i++)
{
b = G[i][a];
if ((BIT(V[i], MAX(a, b)) && !BIT(V[i], MIN(a, b))) ||
