Ещё один простой способ генерации кода Грея связан со следующим процессом:
Начинаем с буквы А. Далее поступаем по следующем правилу: приписываем справа следующую букву, а после неё - повторяем все ранее записанные символы. После первого шага получим строку
АВА
После второго: АВАСАВА
После третьего:
АВАСАВАDАВАСАВА
Теперь возьмём двоичное число 0000 и обозначим его цифры как DCBA. Пробежимся по строке и будем менять на противоположную ту цифру, которая соответствует текущему символу в строке:
А: 0001
В: 0011
А: 0010
С: 0110
А: 0111
В: 0101
А: 0100
D: 1100
А: 1101
В: 1111
А: 1110
С: 1010
А: 1011
В: 1001
А: 1000
Как отметил наш читатель Вадим, есть ещё один рекурсивный способ: сначала получаем код Грея длины 3, записываем его сначала в прямом порядке, а потом в обратном. И дописываем перед первой половиной 0, а перед второй — 1.
Не обязательно с длины 3. Можно с 1 начать. Просто этот способ хорош тем, что очень легко доказывается «греевость» нового построенного кода. Ну и программируется легко. В «Алгоритмических трюках для программистов» вроде ещё какие-то способы были. Не помню точно.
ОтветитьУдалитьДа-да, я просто показал только один шаг, а так выходит аналогично собиранию строки АВАСАВАDАВАСАВА
ОтветитьУдалить