Coduri Gray
h1. Coduri Gray
NegruÅŸeri Cosmin
== include(page="template/implica-te/scrie-articole" user_id="alecman") ==
Acest articol prezintă noţiunea de cod Gray şi unele aplicaţii ale lui în probleme de la concursurile de programare.
Un cod Gray de ordin n este un şir care conţine toate numerele de la 0 la 2^n – 1astfel ca oricare două numere consecutive din şir diferă în reprezentarea binară prin exact un bit. Pentru n >= 2 există mai multe coduri Gray distincte. Un cod mai des întâlnit, numit în engleză binary reflected Gray code, mai jos ne când vorbim despre codul Gray ne vom referi de fapt la acest cod. Modul de construcţie al acestui cod este unul intuitiv: la fiecare pas adăugăm numărul adăugat anterior căruia îi modificăm cel mai puţin semnificativ bit, astfel ca numărul obţinut să nu mai fi fost adăugat înainte la şir. De exemplu dacă ordinul este doi şi avem la început numărul 0 în şir vom adăuga 1, apoi 3 iar apoi 4. În acest articol vom nota acest cod cu Gn. O altă metodă de construcţie care obţine acelaşi cod Gray este de a determina mai întâi pe Gn-1, apoi dacă notăm cu Ğn-1 şirul Gn-1 inversat, atunci obţinem pe Gn dacă punem câte un bit de 0 în faţa fiecărui număr din Gn-1 iar acestea sunt urmate de numerele din Ğn-1 cărora le adăugăm câte un bit de 1 ca bit semnificativ, pe scurt Gn = 0Gn-1, 1Ğn-1 (1). Observăm că acest cod este unul circular, adică ultimul număr şi primul număr din cod diferă prin exact un bit. Observăm de asemenea că fiecare cod de ordin n îl conţine pe cel de n-1 ca prefix, deci am putea nota prin G∞ şirul numerelor naturale în care orice două numere consecutive diferă în reprezentarea binară prin exact un bit şi pentru care şirul primelor 2^n elemente coincide cu Gn oricare ar fi acest n un număr natural. Fie g(x) al x-lea număr din G∞(prin g(x) notăm codul Gray al numărului x) şi g-1(y) la ce poziţie apare numărul y în şirul G∞. Ne punem problema calculării eficiente a celor două funcţii. Se poate demonstra prin inducţie că dacă avem un număr x cu reprezentarea binară (…a2 a1 a0)2 şi codul lui Gray cu reprezentarea binară (… b2 b1 b0)2. Atunci avem bi = ai ^ ai+1 (2). De exemplu dacă avem numărul 6 cu reprezentarea binară 110, atunci b0 = a0 ^ a1 = 0 ^ 1 = 1, b1 = a1 ^ a2 = 1 ^ 1 = 0, b2 = a2 ^ a3 = 1^ 0 = 1, deci g(110) = 101. Din această relaţie tragem concluzia că g(i) = x ^ (x / 2) (unde prin / am notat împărţire întreagă). Din (2) obţinem că bi ^ bi+1 ^ bi+2 ^ … = (ai ^ ai+1) ^ (ai+1 ^ ai+2) ^ (ai+2 ^ ai+3) ^… = ai. Această sumă este finită deoarece vom avea un bi egal cu 0 şi un ai egal cu 0, dacă i este de ajuns de mare. Astfel g-1(y) = y ^ y/2 ^ y/4 ^ …
Din cele de mai sus obţinem următoarele metode:
(Categoria _Matematica_, Autor _Cosmin Negruseri_)
(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
h2(#introducere). Introducere
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$).
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:
== code(cpp) |
int binToGray(int x) {
return x ^ (x >> 1);
return x ^ (x >> 1);
}
==
int grayToBin(int y) {
int ret = 0;
== code(cpp) |
int grayToBin(int y) {
int ret = 0;
while (y > 0) {
ret ^= y;
y >>= 1;
}
return ret;
}
return ret;
}
==
h2(#hanoi). Problema 1: _Turnurile din Hanoi_
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
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(#becuri). Problema 2: _Becuri_
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.
h2(#matrix). Problema 3: '_Matrix_':http://acm.sgu.ru/problem.php?contest=0&problem=249 (SGU)
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
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 $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: 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, matricea pentru $n = 3$ si $m = 2$ este:
|_. - |_. 00 |_. 01 |_. 11 |_. 10 |
|_. 000 | 00000 | 00001 | 00011 | 00010 |
|_. 001 | 00100 | 00101 | 00111 | 00110 |
|_. 011 | 01100 | 01101 | 01111 | 01110 |
|_. 010 | 01000 | 01001 | 01011 | 01010 |
|_. 110 | 11000 | 11001 | 11011 | 11010 |
|_. 111 | 11100 | 11101 | 11111 | 11110 |
|_. 101 | 10100 | 10101 | 10111 | 10111 |
|_. 100 | 10000 | 10001 | 10011 | 10010 |
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(#divizori). Problema 4: '_Divizori_':problema/divizori
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
Să vedem mai departe câteva probleme.
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:
$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)$
Problema 1: Turnurile din Hanoi
Avem trei tije şi n discuri de dimensiuni diferite plasate în ordinea descrescătoare a dimensiunilor pe prima tijă. Se doreşte mutarea tuturor discurilor pe cea de a doua tijă, iar mutările acceptate sunt mutarea unui disc de pe o tijă pe alta cu condiţia ca pe tija destinaţie discul din vârf dacă există un asemenea disc să fie mai mare ca discul ce îl mutăm acum.
Rezolvare:
Aceasta este o problemă clasică în predarea recursivităţii, dar ea are o soluţie care se foloseşte de codul Gray. Urmărim pas cu pas ce bit se schimbă de la numerele consecutive ale lui Gn, acest bit corespunde discului pe care îl vom muta (cel mai puţin semnificativ bit corespunde celui mai mic disc, iar cel mai semnificativ bit corespunde celui mai mare disc). Problema este că ştim ce disc să mutăm, dar nu ştim pe ce ţija. Dar există o regulă simplă care ne poate ajuta: un disc nu trebuie plasat pe alt disc ce are aceiaşi paritate. Această strategie rezolvă şi ea în număr minim de paşi problema, acest număr fiind 2^n - 1.
Problema 2:
Un bec este conectat la n întrerupătoare, fiecarui astfel de întrerupător îi poate fi schimbată starea prin apăsare. Problema este că nu ştim starea lor îniţială. Se cere să se determine o strategie care ar face număr minim de apăsări în cazul cel mai rău, pentru a aprinde becul.
Rezolvare:
Pentru a fi siguri că aprindem becul trebuie în cel mai rău caz să trecem prin toate configuraţiile apăsat/ne-apăsat ale întrerupătoarelor. Pentru a schimba starea curentă trebuie să apăsăm cel puţin un buton, deci în cazul cel mai defavorabil va trebui să facem cel puţin 2^n - 1 apăsări. Codul Gray ne dă o posibilitate de a trece prin toate configuraţiile trecând de la una la alta prin o apăsare de buton, rezolvându-ne problema.
Problema 3: Matrix (249 acm.sgu.ru)
Trebuie să aranjaţi numerele de la 0 la 2^(n + m) – 1 într-o matrice cu 2^n rânduri şi 2^m coloane. De asemenea numerele care sunt situate în celule adiacente pe verticală sau orizontală trebuie să difere prin exact un bit în reprezentarea lor binară. Matricea este ciclică, adică pentru fiecare rând celula cea mai din stânga se consideră învecintată cu cea mai din dreapta, de asemenea pentru fiecare coloană celula cea mai de sus se consideră învecinată cu celula cea mai de jos. La intrare se dau numerele n şi m (0 < n, m; n + m <= 20). Trebuie să afişaţi o asemenea matrice. De exemplu dacă n = 1 şi m = 1 o matrice ar fi
(0 2)
(1 3).
Rezolvare:
O primă metodă ar fi de determinare a codului Gn+m iar apoi de a îl scrie şerpuit în matrice, adică pe de index par de la stânga la dreapta iar în liniile de index impar de la dreapta la stânga.
De exemplu dacă n = 2 şi m = 2 avem:
G4 = 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
Altă modalitate de rezolvare care ne dă de fapt aceiaşi matrice este următoarea:
Întregul din celula (i, j) a matricei va fi în reprezentarea binară rezultatul concatenării reprezentării binare a întregului de index i din codul Gn cu reprezentarea binară a întregului de index j din codul Gm.
De exemplu dacă avem N = 3 şi M = 2
00 01 11 10
000 00000 00001 00011 00010
001 00100 00101 00111 00110
011 01100 01101 01111 01110
010 01000 01001 01011 01010
110 11000 11001 11011 11010
111 11100 11101 11111 11110
101 10100 10101 10111 10111
100 10000 10001 10011 10010
Este evident că orice două numere din matrice vor fi diferite, orice două numere adiacente în matrice sunt diferite în reprezentarea binară prin exact un bit. În concurs limita de timp era foarte strânsă şi trebuia folosită funcţia prezentată anterior. Deci pe linia i coloana j a matricei scriem numărul (binToGray(i) << M) | binToGray(j).
Problema 4: Divizori (algoritmus)
Vom considera un număr natural N. În şirul A vom aşeza toţi divizorii lui N (2<=N<=2.000.000.000). Se cere să se permute elementele ţirului A astfel încât pentru oricare două elemente consecutive A[i] şi A[i+1] să avem fie A[i]=A[i+1]*p, fie A[i+1]=A[i]*p, unde p este un număr prim oarecare. Valoarea p poate diferi de la o pereche de elemente la alta. De exemplu pentru N = 12 o posibilă soluţie ar fi 1 2 3 4 12 6 3.
Rezolvare:
Numărul N are maxim 2*N1/2 divizori. Dacă descompunem numărul N în factori primi atunci îl vom putea scrie în forma P1E1*P2E2*...*PkEk, unde P1, P2, ..., Pk sunt numere prime şi E1, E2, ..., Ek numere naturale mai mari ca zero. Un divizor al lui N va fi reprezentat printr-un vector de exponenţi (e1, e2, ..., ek) unde 0<=ei<=Ek. Prin urmare, problema noastra poate fi uşor redusa la urmatoarea cerinţa: ordonaţi toti vectorii (e1, e2, ..., ek) unde 0<=ei<=Ek, într-un şir cu proprietatea că diferenţa între doi vectori consecutivi se realizeaza la o singura poziţie a vectorilor şi cele două elemente ale vectorilor de pe poziţia respectiva diferă prin o unitate.
Exemplul din enunţul problemei se poate reprezenta astfel:
1 2 4 12 6 3
P1=2 E1=2
P2=3 E2=1
(0,0) (1,0) (2,0) (2,1) (1,1) (0,1)
Această problemă este o generalizare a determinării codului Gray şi poate fi rezolvată generalizănd metoda expusă mai sus.
Presupunem că ştim să generăm o soluţie pentru M=N/(PkEk) (o soluţie pentru un număr cu k-1 factori primi). Să vedem cum generăm o soluţie pentru N. Fie C vectorul soluţie pentru M, şi R vectorul C inversat (primul element al lui R este ultimul al lui C, etc.). O soluţie pentru N poate fi obţinută în urmatoarea formă:
C Pk*R Pk2*C Pk3*R ...
Astfel am concatenat Ek coduri pentru M, înmulţind cu Pk şi pe fiecare pozitie impara am pus secvenţa inversată pentru M. Am facut aceasta pentru ca cele doua capete ce vor ajunge în codul final consecutive să difere numai prin Pk.
Exemplu E1=3; E2=2; E3=1
(0,0,0) (1,0,0) (2,0,0) (3,0,0)
Soluţia 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)
Soluţia 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)
Soluţia pentru cei trei factori primi.
Complexitatea finală a soluţiei este O(T) unde T reprezinta numărul de divizori ai lui N.
Problema 5:
Sortnet (Mihai Pătraşcu, lot 2002)
O reţea completă de sortare este o reţea de sortare cu N fire de adâncime D ce are D * (N/2) comparatori. Amitim principiul 0-1 care spune că o reţea de sortare sortează orice N numere dacă aceasta sortează orice secvenţă de N numere 0 sau 1. Problema noastră cere câte astfel de secvenţe de 0 şi 1 nu sunt sortate corect.
Soluţia lui Mihai Pătraşcu:
Observăm că după primul strat de comparatori sunt exact 3^(N/2) rezltate posibile, pentru că intrările trecute printr-un comparator se transformă astfel 0, 0 -> 0, 0 ; 0, 1 -> 1, 0; 1, 0 -> 1, 0; 1, 1 -> 1, 1. Pentru a testa fiecare astfel de rezultat dacă e sortat sau nu de următoarele D-1 straturi, nu vor trebui simulate toate în complexitate O(N * (3^N/2) * D). Prin generarea secvenţelor conform codului Gray în baza 3 putem doar să urmărim modificarea rezltatului pentru două rezultate succesive în O(D). Un număr în baza trei îl transformăm în unul în baza doi cu număr dublu de cifre, astfel 0 trece în 00, 1 trece în 10 şi 2 trece în 11, acest cod reprezentând un rezultat posibil după evaluarea unei secvenţe binare de către primul strat al reţelei. Modificarea unei cifre în baza trei conform codului Gray generalizat pentru numere în această bază, duce la modificarea unei cifre în codul binar a unui bit. Urmărirea modificărilor făcute de acest bit schimbat în evaluările făcute de reţeaua de sortare o putem face în complexitate O(D). Astfel complexitatea finală este O(3^(N/2) * D).
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~}$.
Menţionăm că problema este pe siteul infoarena şi acolo o rezolvare O(2^N * D) intră în timp, dar şi pentru aceasta trebuie să folosim codul Gray şi să urmărim modificările date de schimbarea unui bit în evaluare.
Dăm mai jos rezolvarea elegantă şi uşor de înţeles a lui Mircea Paşoi:
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 $O(T)$ unde $T$ reprezinta numarul de divizori ai lui $N$.
h2(#sortnet). Problema 5: '_Sortnet_':problema/sortnet (Lot 2002)
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 $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:
| 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;
int N, M, G[MAX_M][MAX_N], V[MAX_M], V2[MAX_M], 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;
}
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))) ||
