Fie
n un numar natural. Codul Gray de ordin n
(notat Gray(n)) este constituit
din toate secventele binare de lungime n,
plasate astfel încât oricare doua secvente consecutive difera pe
o singura pozitie.
Pentru a construi Gray(n) se
poate aplica urmatorul procedeu recursiv:
Gray(1) este:
0
1
Pentru a determina Gray(n) cu
n>1, vom utiliza Gray(n-1)
astfel:
Primele 2n-1 secvente
din Gray(n) se obtin precedând
cu un 0 fiecare dintre cele 2n-1
secvente Gray(n-1).
Ultimele 2n-1 secvente
din Gray(n) se obtin precedând
cu un 1 fiecare dintre cele 2n-1
secvente din Gray(n-1), considerate
în ordine inversa.
Exemplu:
| Gray(2) | Gray(3) |
| 00 01 11 10 |
000 001 011 010 110 111 101 100 |
Codul
Gray(n) permite codificarea numerelor naturale din multimea {0,
1, ..., 2n-1}
Ca orice cod si codul Gray trebuie sa permita realizarea operatiilor de codificare/decodificare.
Operatia de codificare
Se da P un numar natural din
multimea {0, 1, ..., 2n-1}.
Sa se determine numarul natural M
a carui scriere în baza 2 este cea de a P-a
secventa din Gray(n).
Operatia de decodificare
Se da M un numar natural din
multimea {0, 1, ..., 2n-1}.
Sa se determine numarul natural P
cu proprietatea ca scrierea lui M
în baza 2 reprezinta cea
de a P-a secventa din Gray(n).
Cerinta
Scrieti un program care sa realizeze operatii de codificare/decodificare.
Date
de intrare
Fisierul de intrare gray.in contine
o singura linie ce contine 3 valori c
n x separate prin câte un singur spatiu. Valoarea c
este un caracter ce poate fi doar 'C'
sau 'D'. Valoarea n
este un numar natural ce indica ordinul codului Gray. Valoarea x
este un numar natural din multimea {0,
1, …, 2n-1}. În cazul în care c='C'
se cere codificarea numarului x,
iar în cazul în care c='D',
se solicita decodificarea numarului x.
Date
de iesire
Fisierul de iesire gray.out va
contine o singura linie pe care va fi scris un singur numar natural, reprezentând
valoarea x codificata, respectiv
decodificata (în functie de valoarea caracterului c
din fisierul de intrare).
Restrictii
n<=500
În codul Gray secventele sunt numerotate de la 0.
Exemple
| gray.in | gray.out | gray.in | gray.out |
| C
3 7 |
4 |
D
3 4 |
7 |
Timp maxim de executie/test: 0.1 secunde
prof.
Emanuela Cerchez
Liceul de
Informatica "Grigore Moisil" Iasi
Contact:emanuela.cerchez@gmail.com