GreyCode генератор

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

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

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

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

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

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

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

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

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

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

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

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

Подсчет кол-ва нулевых подмассивов

Март 21, 2023 г.

Разбор задачи с литкода. (2348. Number of Zero-Filled Subarrays). Суть: есть массив чисел, нужно подсчитать кол-во подмассивов, состоящих из нулей. Например, дан массив [0, 0, 1]. Как видим, есть последовательность из двух нулей в начале ...

Читать

Вычисление заголовка столбца в Excel

Март 23, 2023 г.

Leetcode задача #168. Excel Sheet column title.Задача помечена как простая, тем не менее, не сразу понял как её решать. Дано число, это номер столбца для Excel таблицы, требуется сгенерировать его буквенное имя. Иными словами сопоставить 1 -> A, ...

Читать

 

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

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



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