GreyCode генератор

Задачи с бинарными последовательностями мне очень нравятся из-за их «эвристичности». Решение часто скрывается в двух шагах, но додуматься не просто.

Следующая задача описывается так — нужно сгенерировать n-разрядный «серый код».

Если вы не знакомы с тем, что такое GrayCode, то вот его краткое описание.

Двоичный код последовательности чисел называемый GreyCode, должен отличаться у соседних чисел всего в одном разряде. При этом последнее и первое числа также должны следовать этому правилу.

Пример серого кода для 2х разрядов: [00, 01, 11, 10].

Как выстроить последовательность для N разрядов? Давайте рассмотрим еще пару примеров кода: добавим gray code для n = 1 и 3.

Чтобы перейти от n = 1 к n = 2, я добавил к [0,1] тот же самый массив, но в обратном порядке, а также установил старший бит. Этот трюк позволил мне соблюсти правило серого кода внутри добавляемой последовательности — т.к. я её получил как бы на предыдущем шаге, а добавление старшего бита обеспечило граничные условия.

Рассмотрим вариант реализации:

Тяжелая артиллерия в виде функций работы с массивами в данном примере не удачный выбор, если требуется хорошее быстродействие. Оператор […] и функции reverse и map создают временные массивы, и каждый раз интерпретатор выполняет их поэлементный перебор по цепочке функций.

В данном случае обычный цикл for будет более эффективен.

Написать комментарий

Мало букафф? Читайте есчо !

Задача: подсчета кол-ва возможных маршрутов

Июнь 25, 2023 г.

Решаем задачу с литкода №1575 Count All Possible Routes. Дан массив чисел, описывающий города. Указаны индексы стартового города (start) и города, куда нужно приехать (finish), а также запас топлива (fuel). Требуется найти кол-во путей, по которым ...

Читать

Классическая задача о размене монет

Январь 24, 2023 г.

Дана сумма amount и номиналы монет. Требуется разменять сумму минимальным набором монет. Если рассматривать набор монет, который используется в реальной жизни, т.е. [1коп, 5коп, 10коп, 50коп, 1р, 2р, 5р, 10р], то во-первых, решение всегда существует, ...

Читать

 

Комментарии к «GreyCode генератор»

Понравилась статья? Есть вопросы? - пишите в комментариях.



Комментарий: