Задачи с бинарными последовательностями мне очень нравятся из-за их «эвристичности». Решение часто скрывается в двух шагах, но додуматься не просто.
Следующая задача описывается так — нужно сгенерировать n-разрядный «серый код».
Если вы не знакомы с тем, что такое GrayCode, то вот его краткое описание.
Двоичный код последовательности чисел называемый GreyCode, должен отличаться у соседних чисел всего в одном разряде. При этом последнее и первое числа также должны следовать этому правилу.
Пример серого кода для 2х разрядов: [00, 01, 11, 10].
Как выстроить последовательность для N разрядов? Давайте рассмотрим еще пару примеров кода: добавим gray code для n = 1 и 3.
|
1 2 3 |
[0, 1] [00, 01, 11, 10] [000, 001, 011, 010, 110, 111, 101, 100] |
Чтобы перейти от n = 1 к n = 2, я добавил к [0,1] тот же самый массив, но в обратном порядке, а также установил старший бит. Этот трюк позволил мне соблюсти правило серого кода внутри добавляемой последовательности — т.к. я её получил как бы на предыдущем шаге, а добавление старшего бита обеспечило граничные условия.
Рассмотрим вариант реализации:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
function grayCode(n: number): number[] { // начнем с готовой последовательности для n = 1 const base = [0, 1] // это старший бит для получения следующего разряда let next = 2 // пока не исчерпаем заданное число разрядов // будем проводить генерацию кода while (n > 1) { base.push(...[...base].reverse().map(value => value + next)) next *= 2; n -- } return base; }; |
Тяжелая артиллерия в виде функций работы с массивами в данном примере не удачный выбор, если требуется хорошее быстродействие. Оператор […] и функции reverse и map создают временные массивы, и каждый раз интерпретатор выполняет их поэлементный перебор по цепочке функций.
В данном случае обычный цикл for будет более эффективен.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
function grayCode(n: number): number[] { const base = [0, 1] let next = 2 while (n > 1) { // перебираем массив с конца и добавляем // элементы в него же for (let i = base.length - 1; i >= 0; i --) base.push(base[i] + next) // умножение на 2 можно заменить сдвигом next <<= 1; n -- } return base; }; |
