'implica-te, transcrie acest articol':implica-te/scrie-articole

h1. Coduri Gray
 
(Categoria _Matematica_, autor _Cosmin Negruseri_)
 
h2. Introducere
 
Acest articol prezinta notiunea de **Cod Gray** si unele aplicatii ale lui in probleme de la concursurile de programare.
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 şir. _De exemplu_, dacă 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>.
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.
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>
Din cele de mai sus obtinem urmatoarele metode:
 
== code(cpp) |
int binToGray(int x) {
     return x ^ (x >> 1);
}
==
 
== code(cpp) |
int  grayToBin(int y) {
     int ret = 0;
    while (y > 0) {
        ret ^= y;
        y >>= 1;
     }
     return ret;
}
==
 
Sa vedem mai departe cateva probleme: