Задача

Frank Gray (13 September 1887 – 23 May 1969) was a physicist and researcher at Bell Labs who made numerous innovations in television, both mechanical and electronic

Коды Грея получили своё название по имени Франка Грея (Frank Gray), физика из Bell Telephone Laboratories, который в 1930-х годах изобрёл метод, в настоящее время используемый для передачи цветного телевизионного сигнала, совместно с существующими методами передачи и получения чёрно-белого сигнала; т.е. при получении цветного сигнала чёрно-белым приёмником изображение выводится оттенками серого цвета.
Хотя существует множество различных вариантов кодов Грея, рассмотрим только один: «двоичный отражённый (рефлексный) код Грея». Именно этот код обычно имеется в виду, когда говорят о неконкретном «коде Грея».
Отображённый двоичный код Грея строится следующим образом. Начинаем со строк [latex]0[/latex] и [latex]1[/latex], которые представляют соответственно целые числа [latex]0[/latex] и [latex]1[/latex].
[latex]0[/latex] [latex]1[/latex] Возьмём отражение этих строк относительно горизонтальной оси после приведённого списка и поместим [latex]1[/latex] слева от новых записей списка, а слева от уже имевшихся разместим [latex]0[/latex].
[latex]00[/latex] [latex]01[/latex] [latex]11[/latex] [latex]10[/latex] Таким образом получен отражённый код Грея для [latex]n = 2[/latex]. Чтобы получить код для [latex]n = 3[/latex], повторим описанную процедуру и получим:
[latex]000[/latex] [latex]001[/latex] [latex]011[/latex] [latex]010[/latex] [latex]110[/latex] [latex]111[/latex] [latex]101[/latex] [latex]100[/latex] При таком способе построения легко увидеть по индукции по [latex]n[/latex], что, во-первых, каждая из [latex]2n[/latex] комбинаций битов появляется в списке, причём только один раз; во-вторых, при переходе от одного элемента списка к рядом стоящему изменяется только один бит; в-третьих, только один бит изменяется при переходе от последнего элемента списка к первому. Коды Грея, обладающие последним свойством называются циклическими, и отражённый код Грея обязательно является таковым.
Для каждого заданного числа [latex]k[/latex] вывести десятичное значение [latex]k[/latex]-го кода Грея.

Входные данные

Во входном файле содержится некоторый набор тестовых данных, каждое число [latex]k[/latex] ([latex]0 ≤ k ≤ 10^{18}[/latex]) в наборе задано в отдельной строке. Количество наборов данных в одном тесте не превышает [latex]10^5[/latex].

Выходные данные

Для каждого заданного числа [latex]k[/latex] вывести в отдельной строке десятичное значение [latex]k[/latex]-го кода Грея.

Тесты

№	Входные данные	Выходные данные
1	3	2
	14	9
	5	7
	12	10
2	0	0
	72	108
	265	397
	4781	7163
	50642	42811
3	1010234	581415
	96721758	119682801
	640214927	893162568
	2456987013	3679188807
	51027963402	60418988303
	1000000000000000000	797398725282889728

Код программы

#include <iostream>

using namespace std;

int main() {
    unsigned long int k;
    while (cin >> k) {
        cout <<  (k  ^ (k >> 1)) << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

unsigned long int k;

while (cin >> k) {

cout << (k ^ (k >> 1)) << endl;

}

return 0;

}

Решение задачи

Объявляем переменную [latex]k[/latex] ([latex]0 ≤ k ≤ 10^{18}[/latex]) типа unsigned long int для считывания чисел из входного потока. Цикл while работает столько раз, сколько чисел во входном потоке (по условию задачи их количество [latex]\le 10^5[/latex]). В цикле вычисляется Код Грея числа [latex]k[/latex] путем побитовой операции «исключающее ИЛИ», применимого к [latex]k[/latex] и к результату побитового сдвига [latex]k[/latex] на [latex]1[/latex] бит вправо ([latex]k \gg 1[/latex]).
Ссылка на алгоритм ниже.

Ссылки

Code Gray: theory
e-olymp
ideone

Related Images:

Задача

Френк Грей. Bell Lab 1930

Бинарные коды Грея генерируются следующим образом. Рассмотрим последовательность
0
1
Отобразим строки вниз относительно горизонтальной черты, припишем к первой половине строк спереди 0, а ко второй отображенной половине 1. Получим последовательность:
00
01
11
10
Продолжая процесс, на следующем шаге получим последовательность из 8 чисел. Справа от кода находится его десятичное значение
000 0
001 1
011 3
010 2
110 6
111 7
101 5
100 4
Приведенные последовательности называются кодами Грея длины $n = 1, 2, 3$. Всего существует $2n$ разных кодов длины $n$. Каждые два соседних кода отличаются одним битом.

Входные данные

Первая строка содержит количество тестов $n$ (не более 250000). Каждая следующая строка содержит два числа: $n$ $(1 ≤ n ≤ 30)$ и $k$ $(0 ≤ k < 2^n)$.

Выходные данные

Для каждого теста в отдельной строке вывести число, которое находится в $k$ — ой позиции последовательности кодов Грея длины $n$.

Тесты

№

Входные данные

Выходные данные

14
1 0
1 1
2 0
2 1
2 2
2 3
3 0
3 1
3 2
3 3
3 4
3 5
3 6
3 7

0
1
0
1
3
2
0
1
3
2
6
7
5
4

3
2 1
1 2
3 3

1
1
2

1
0 0

2
2 3
1 3

2
1

Код программы

#include <iostream>
using namespace std;
 
int f(int n, int k) {
    if (!n) return 0;
    int tmp = 1 << (n - 1);
    if (k < tmp) return f(n - 1, k);
    return tmp + f(n - 1, (1 << n) - 1 - k);
}
 
int main() {
    int N, n, k;
    cin >> N;
    for (int i = N; i > 0; i--)  {
        cin >> n >> k;
        cout << f(n,k) << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int f(int n, int k) {

if (!n) return 0;

int tmp = 1 << (n - 1);

if (k < tmp) return f(n - 1, k);

return tmp + f(n - 1, (1 << n) - 1 - k);

}

int main() {

int N, n, k;

cin >> N;

for (int i = N; i > 0; i--) {

cin >> n >> k;

cout << f(n,k) << endl;

}

return 0;

}

Решение

В случае, если значение бинарного кода находится в первой части последовательности, т.е. $x$ < $2^{n-1}$, то ищем число, стоящее в позиции $k$ кода Грея длины $n-1$. В другом же случае ищем число, прибавив к
$2^{n-1}$ число в позиции $2^n-k-1$ длины $n-1$. Оформим данный алгоритм в виде рекурсивной функции.

Related Images: