# PBinfo #4490 – Gray – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Pentru un număr natural n dat, codul Gray(n) se referă la ordonarea tuturor șirurilor binare de lungime n, astfel încât oricare două șiruri alăturate să difere prin exact un bit. Astfel codul Gray(1) constă din două secvențe binare de lungime 1:
0
1
Codul Gray(2) este:
00
01
11
10
Pentru obținerea codului Gray(3) se procedează astfel: Se scrie codul Gray(2), apoi din nou Gray(2), dar cu șirurile scrise în ordine inversă:
00
01
11
10
------
10
11
01
00
Apoi la primele patru secvențe li se adaugă la început bitul 0, iar la ultimele patru li se adaugă la început un bit de 1:
000
001
011
010
------
110
111
101
100

Procedeul continuă până când obținem codul Gray(n). Fiind în total 2n secvențe binare în codul Gray(n), le numerotăm cu numere de la 0 la 2n-1. Se creează astfel o corespondență între orice șir binar din codul Gray și un șir binar reprezentând scrierea unui număr natural în baza 2. De exemplu, pentru n = 3:

Număr  Baza_2  Cod_Gray
0      000     000
1      001     001
2      010     011
3      011     010
4      100     110
5      101     111
6      110     101
7      111     100

Cerința
Dată o secvență de n biți reprezentând un cod binar, să se determine secvența asociată din codul Gray(n), apoi dat un șir de n biți reprezentând o secvență a codului Gray(n), să se determine codul binar asociat.

Date de intrare
Se citește de la tastatură un număr n, apoi, fără spații, de pe a doua linie un șir b1 b2 … bn de cifre binare, iar de pe a treia linie un șir binar g1 g2 … gn reprezentând o secvență din codul Gray(n).

Date de ieșire
Programul va afișa pe ecran pe prima linie secvența din codul Gray(n) asociată lui b1 b2 … bn, iar pe a doua linie secvența binară asociată secvenței g1 g2 … gn a codului Gray(n).

Restricții și precizări

1 ≤ n ≤ 500

Exemplu:
Intrare

3
011
111
Ieșire

010
101
Explicație
Pentru codul binar 011 avem corespunzătoare secvența 010 din codul Gray(3), iar secvenței 111 din codul Gray(3) îi corespunde șirul binar 101.

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
int b[505], g[505], sol[505], n;
void BinaryToGray(int b[], int g[], int n)
{
    g[1] = b[1];
    for (int i = 2; i <= n; i++)
        g[i] = (b[i] + b[i - 1]) % 2;
}
void GrayToBinary(int g[], int b[], int n)
{
    b[1] = g[1];
    for (int i = 2; i <= n; i++)
        b[i] = (g[i] + b[i - 1]) % 2;
}
void Afis(int a[], int n)
{
    for (int i = 1; i <= n; i++)
        cout << a[i];
    cout << "\n";
}
int main()
{
    char s[505];
    cin >> n;
    cin >> (s + 1);
    for (int i = 1; i <= n; i++)
        b[i] = s[i] - '0';
    cin >> (s + 1);
    for (int i = 1; i <= n; i++)
        g[i] = s[i] - '0';
    BinaryToGray(b, sol, n);
    Afis(sol, n);
    GrayToBinary(g, sol, n);
    Afis(sol, n);
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4490)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4490/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4490/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)