GreyCode генератор

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

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

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

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

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

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

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

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

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

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

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

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

Задача о неперекрывающихся интервалах

Июнь 7, 2023 г.

Задачи об интервалах легко решаются перебором. Но если элементов много, то нужно сообразить в каком порядке их лучше перебирать, чтобы избежать лишних вычислений. Формулируется задача так: дан массив интервалов, каждый из которых определен двумя числами ...

Читать

Задача - число островов

Март 25, 2023 г.

Разбираю задачу #200 с литкода, число островов (number of islands). Задан двумерный массив, в котором участки суши помечены как "1", а участки воды - как "0". Требуется подсчитать число получившихся островов. При этом считается, что участки суши образуют ...

Читать

 

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

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



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