(Categoria _Matematica_, autor _Cosmin Negruseri_)

h2. Introducere

(toc)*{text-align:center} *Cuprins*
* 'Introducere':coduri-gray#introducere
* 'Problema 1: Turnurile din Hanoi':coduri-gray#hanoi
* 'Problema 2: Becuri':coduri-gray#prob2
* 'Problema 3: Matrix':coduri-gray#matrix
* 'Problema 4: Divizori':coduri-gray#divizori
* 'Problema 5: Sortnet':coduri-gray#sortnet

Acest articol prezinta notiunea de **Cod Gray** si unele aplicatii ale lui in probleme de la concursurile de programare.

h2(#introducere). Introducere

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>.

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 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.

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 <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>

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(i) = 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  grayToBin(int y) {

int grayToBin(int y) {

    int ret = 0;
    while (y > 0) {
        ret ^= y;

}
==

Sa vedem mai departe cateva probleme:
 

h2. 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.