Ещё один простой способ генерации кода Грея связан со следующим процессом:
Начинаем с буквы А. Далее поступаем по следующем правилу: приписываем справа следующую букву, а после неё - повторяем все ранее записанные символы. После первого шага получим строку
АВА
После второго: АВАСАВА
После третьего:
АВАСАВАDАВАСАВА
Теперь возьмём двоичное число 0000 и обозначим его цифры как DCBA. Пробежимся по строке и будем менять на противоположную ту цифру, которая соответствует текущему символу в строке:
А: 0001
В: 0011
А: 0010
С: 0110
А: 0111
В: 0101
А: 0100
D: 1100
А: 1101
В: 1111
А: 1110
С: 1010
А: 1011
В: 1001
А: 1000
Как отметил наш читатель Вадим, есть ещё один рекурсивный способ: сначала получаем код Грея длины 3, записываем его сначала в прямом порядке, а потом в обратном. И дописываем перед первой половиной 0, а перед второй — 1.
Подписаться на:
Комментарии к сообщению (Atom)
Популярные сообщения
-
Когда был Гаусс маленький, с кудрявой головой... В общем, великий математик Карл Фридрих Гаусс, тоже учился в школе. В школе этой в одном ... -
Наш давний друг, Наталия Макарова, приглашает присоединиться к своему проекту составления базы данных канонических форм диагональных латинск...
-
Ещё одна задачка про матрицы. Рассмотрим матрицы 3х3, элементами которых могут быть только нули, единицы и двойки. Всего таким матриц будет ...
-
Давайте начнём новый, 2022й год с интересной задачи. Рассмотрим квадратную таблицу. Попробуем её заполнить натуральными числами так, чтобы с...
-
Стабильно в первую пятёрку самых читаемых постов блога "Десять Букв" входит заметка о правильно-неправильном выносе из-под корня ...
-
Вот такая интересная последовательность: 9, 171, 27, 4, 9, 59, 18, 4, 18, 81, 9, 581,... Продолжите её. Подскажу, что лет 10 назад её ра...
-
С нового учебного года я начал читать два интересных блога по русскому языку. Блог ученика Мир глазами человека и блог учителя Оно вам на...
-
Следующим простым за числом 2011 будет число 2017. За ним идёт 2027. Так вот, если мы сформируем из этих трёх чисел одно: 201120172027, то о...
-
Число 2012 открывает серию из четырёх чисел, каждое из которых представляется в виде произведения ровно трёх простых. 2012 = 2 * 2 * 503 2...
-
Нет, здесь не будут представлены задачи тысячелетия, за решение которых объявлены премии в миллион долларов. Просто за время существования ...
Не обязательно с длины 3. Можно с 1 начать. Просто этот способ хорош тем, что очень легко доказывается «греевость» нового построенного кода. Ну и программируется легко. В «Алгоритмических трюках для программистов» вроде ещё какие-то способы были. Не помню точно.
ОтветитьУдалитьДа-да, я просто показал только один шаг, а так выходит аналогично собиранию строки АВАСАВАDАВАСАВА
ОтветитьУдалить