E008. Gray code

Источник: e-maxx.ru/algo, страница PDF 25.

Định nghĩa

Кодом Грея называется такая система нумерования неотрицательных чисел, когда коды двух соседних чисел отличаются ровно в одном бите. НаVí dụ, для чисел длины 3 бита имеем такую последовательность кодов Грея:

,

,

,

,

,

,

,

. НаVí dụ,

. Этот код был изобретен Фрэнком Грэем (Frank Gray) в 1953 году.

Нахождение кода Грея

Рассмотрим биты числа

и биты числа

. Заметим, что

-ый бит

равен единице только в том случае, когда

-ый бит

равен единице, а

-ый бит равен нулю, или наоборот (

-ый бит равен нулю, а

-ый равен

единице). Таким образом, имеем: :

int g (int n) {

return n ^ (n >> 1);

}

Нахождение обратного кода Грея

it is required по коду Грея

восстановить исходное number

. Будем идти от старших битов к младшим (пусть самый младший бит имеет номер 1, а самый старший — ).

Получаем такие соотношения между битами

числа

и битами

числа

:

В виде программного кода это проще всего записать так:

int rev_g (int g) {

int n = 0;

for (; g; g>>=1)

n ^= g;

return n;

}

Applications

Коды Грея имеют несколько применений в различных областях, иногда достаточно неожиданных:

●

-битный Gray code соответствует гамильтонову циклу по

-мерному кубу.

● В технике, коды Грея используются для минимизации ошибок при преобразовании аналоговых сигналов

в цифровые (наVí dụ, в датчиках). В частности, коды Грея и были открыты в связи с этим применением.

● Коды Грея применяются в решении задачи о Ханойских башнях.

Пусть

— количество дисков. Начнём с кода Грея длины

, состоящего из одних нулей (т.е.

), и будем двигаться

по кодам Грея (от

переходить к

). Поставим в соответствие каждому

-ому биту текущего кода Грея

-

ый диск (причём самому младшему биту соответствует наименьший по размеру диск, а самому старшему биту — наибольший). Поскольку на каждом шаге изменяется ровно один бит, то мы можем понимать изменение бита

как перемещение

-го диска. Заметим, что для всех дисков, кроме наименьшего, на каждом шаге имеется ровно один вариант хода (за исключением стартовой и финальной позиций). Для наименьшего диска всегда имеется два варианта хода, однако имеется стратегия выбора хода, всегда приводящая к ответу: если

нечётно,

то последовательность перемещений наименьшего диска имеет вид

(где

— стартовый стержень,

— финальный стержень,

— оставшийся стержень), а если

чётно,

то

.

● Коды Грея также находят применение в теории генетических Thuật toánов.

Задачи в online judges

Список задач, которые можно сдать, используя коды Грея:

● SGU #249 "Matrix" [Complexity: средняя]