e-olymp 1519. Коды Грея

Задача

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

Френк Грей. 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$.

Тесты

Входные данные Выходные данные
1 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
2 3
2 1
1 2
3 3
1
1
2
3 1
0 0
0
4 2
2 3
1 3
2
1

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

Решение

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

e-olymp

ideone

10 thoughts on “e-olymp 1519. Коды Грея

  1. Подправьте пожалуйста отступы и while (N--) это плохо на практике, в данном случае оно то будет работать но желательно такого не делать, вдруг потом в коде где-то пригодится это N а у вас оно уже будет равно 0 и очень трудно будет потом найти ошибку

    • На обоих сайтах по ссылкам в коде хаотичные отступы. Исправьте пожалуйста.
    • В таблицах тестов и вообще по тексту масса ненужных пустых строк. Уберите, пожалуйста. Будь их 10-20, я бы и сам убрал, а так давайте уже Вы.
  2. В Вашей работе в самом конце есть две ссылки. Если по ним перейти, то можно будет посмотреть код Вашей программы. В обоих местах код совершенно хаотично разбросан по холсту. В творческом беспорядке. Странно, что Вы не видите. Отправил снимок экрана на почту.

Добавить комментарий