Нерекурсивное понимание алгоритма кода Грея

Question

Это задание из книги алгоритмов.

Дело в том, что я совершенно не знаю, с чего начать!

Trace the following non-recursive algorithm to generate the binary reflexive
Gray code of order 4. Start with the n-bit string of all 0’s. 
For i = 1, 2, ... 2^n-1, generate the i-th bit string by flipping bit b in the 
previous bit string, where b is the position of the least significant 1 in the 
binary representation of i. 

Итак, я знаю, что код Грея для 1 бита должен быть 0 1на 2 00 01 11 10 и т.п.

Много вопросов

1) Знаю ли я, что для n = 1 я могу начать с 0 1?

2) Как я должен понимать "начать с n-битной строки всех 0"?

3) "Предыдущая битовая строка"? Какая строка является "предыдущей"? Предыдущее значит от младшего n-битного? (например, для n=2, предыдущий является тем из n = 1)?

4) Как мне даже преобразовать 1-битные строки в 2-битные строки, если единственная операция - перевернуть?

Это меня сильно смущает. Единственный "человеческий" метод, который я до сих пор понимаю: взять наборы из младшего n-бита, продублировать их, инвертировать 2-й набор, добавить 0 в каждый элемент 1-го набора, добавить 1 в каждый элемент 2-го набора. Готово (пример: 0 1 -> 0 1 | 0 1 -> 0 1 | 1 0 -> 00 01 | 11 10 -> 11 01 11 10 сделанный.

Спасибо за любую помощь

Answer 1

Ответ на все четыре ваших вопроса состоит в том, что этот алгоритм не начинается с более низких значений n, Все генерируемые им строки имеют одинаковую длину, и i-th (за i = 1,..., 2ⁿ-1) строка генерируется из (i-1)-th один.

Вот первые несколько шагов для n = 4:

Начните с G₀ = 0000

Чтобы сгенерировать G₁, переверните 0-th бит в G₀, как 0 позиция наименее значимой 1 в двоичном представлении 1 = 0001_б. G₁ = 0001,

Чтобы сгенерировать G₂, переверните 1-st бит в G₁, как 1 позиция наименее значимой 1 в двоичном представлении 2 = 0010_б. G₂ = 0011,

Чтобы сгенерировать G₃, переверните 0-th немного в G₂, как 0 позиция наименее значимой 1 в двоичном представлении 3 = 0011_б. G₃ = 0010,

Чтобы сгенерировать G₄, переверните 2-nd немного в G₃, как 2 позиция наименее значимой 1 в двоичном представлении 4 = 0100_б. G₄ = 0110,

Чтобы сгенерировать G₅, переверните 0-th немного в G₄, как 0 позиция наименее значимой 1 в двоичном представлении 5 = 0101_б. G₅ = 0111,