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

Задача

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

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

#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$. Оформим данный алгоритм в виде рекурсивной функции.

e-olymp

ideone

Related Images:

Похожее

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

Руслан Масальский says: 23/12/2018 at 12:37

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

Войдите, чтобы ответить
- Дарья Найденова says: 23/12/2018 at 13:09
  
  Спасибо, Руслан. Исправила
- Никита Семерня says: 23/12/2018 at 13:33
  
  Даш, проверь ещё раз код, там всё ещё беда с отступами.
- Дарья Найденова says: 23/12/2018 at 13:59
  
  Точно, спасибо. Теперь все исправила
Владислав Бебик says: 23/12/2018 at 18:02

Поставь пожалуйста, что это задача из раздела циклы.

Войдите, чтобы ответить
Мазурок Игорь Евгеньевич says: 23/12/2018 at 22:48
- На обоих сайтах по ссылкам в коде хаотичные отступы. Исправьте пожалуйста.
- В таблицах тестов и вообще по тексту масса ненужных пустых строк. Уберите, пожалуйста. Будь их 10-20, я бы и сам убрал, а так давайте уже Вы.
Войдите, чтобы ответить
- Дарья Найденова says: 24/12/2018 at 02:41
  
  Ссылки изменила. Отступы убрала. Спасибо за замечание. Надеюсь, все)
- Мазурок Игорь Евгеньевич says: 24/12/2018 at 23:29
  
  Убрала? Отступы в коде? Где? Зачем?
Мазурок Игорь Евгеньевич says: 24/12/2018 at 23:35

В Вашей работе в самом конце есть две ссылки. Если по ним перейти, то можно будет посмотреть код Вашей программы. В обоих местах код совершенно хаотично разбросан по холсту. В творческом беспорядке. Странно, что Вы не видите. Отправил снимок экрана на почту.

Войдите, чтобы ответить
- Дарья Найденова says: 25/12/2018 at 00:51
  
  Прошу прощение за невнимательность. Исправила.