Изменения

*<tex>\mathtt{GrayCode}</tex> {{---}} двумерный массивтипа '''boolean''', в котором <tex>\mathtt{GrayCode[a, b]}</tex> {{---}} <tex>b</tex>-ый бит в <tex>a</tex>-ом коде Грея,*<tex>\mathtt{p}</tex> {{---}} Счетчик количества уже имеющихся кодов,*<tex>\mathtt{t}</tex> {{---}} Показывает количество кодов в <tex>(a-1)</tex>-м коде Грея.

GrayCode[1, n] = 0''false'' GrayCode[2, n] = 1 ''true'' <font color=green> // Построение кода длины 1 </font> p = 2 <font color=green> // Где p {{---}} количество уже имеющихся кодов </font>

GrayCode[k] = GrayCode[t] <font color=green> // Отражение имеющихся кодов </font> GrayCode[t, n + 1 - i] = 0''false'' GrayCode[k, n + 1 - i] = 1 ''true'' <font color=green> // Добавление 0 и 1 в начало </font>

Пусть существует зеркальный двоичный код Грея <tex>M</tex> длины <tex>n</tex>, для которого выполнено, что для любого <tex>i</tex> выполняется <tex>е\enskip enspace M_i = i \oplus (\lfloor i / 2 \rfloor)</tex>

Для любого <tex>x < 2^n</tex> выполняется <tex>\enskip enspace L_x = 0M_x</tex> и, по условию, равно

<tex>L_x = 0(x_{n-1}x_{n-2}... \dots x_{0} \oplus 0x_{n-1}x_{n-2}... \dots x_{1})</tex> раскрыв скобки, получим новое выражение <tex>L_x</tex>:

<tex>= 0x_{n-1}x_{n-2}... \dots x_{0} \oplus 00x_{n-1}x_{n-2}... \dots x_{1}</tex> что равно (второе слагаемое равно первому, побитово сдвинутого вправо.)

Для любого <tex>x \leqslant geqslant 2^n</tex> выполняется <tex>\enskip enspace L_x = 1</tex><tex>M_y</tex>, где <tex>y = 2^{n+1} - 1 - x = \neg x</tex>, то есть

<tex>L_x = 1(\overline {x_{n-1} x_{n-2}... \dots x_{0}} \oplus 0 \overline {x_{n-1} x_{n-2}... \dots x_{1}})</tex> что по свойству '''xor''' (<tex>\neg x \oplus \neg y = x \oplus y</tex>) равно

<tex>= 1(\overline {x_{n-1}}x_{n-2}... \dots x_{0} \oplus 0x_{n-1}x_{n-2}... \dots x_{1})</tex> или (все по тому же свойству)

<tex>= 1(x_{n-1}x_{n-2}... \dots x_{0} \oplus 1x_{n-1}x_{n-2}... \dots x_{1})</tex> раскрыв скобки, получим

<tex>= 1x_{n-1}x_{n-2}... \dots x_{0} \oplus 01x_{n-1}x_{n-2}... \dots x_{1}</tex> откуда получаем, зная из условия, что старший разряд <tex>L_x</tex> равен <tex>1</tex>

<tex>= x_{n}x_{n-1}x_{n-2}... \dots x_{0} \oplus 0x_{n}x_{n-1}x_{n-2}... \dots x_{1}</tex> что, аналогично первому пункту, равно

Чтобы показать это точнее, пусть <tex>G</tex> {{---}} это <tex>R</tex>-ичный полный цикл Грея, имеющий последовательность перехода <tex>(\delta_k)</tex>, которая определяет различие последующего бита <tex>\delta_k = i</tex>, для <tex>k = 0 \dots n</tex> если в коде Грея с предыдущим<tex>i</tex>-й и <tex>(i+1)</tex> биты различны и различие последнего с первым)<tex>n</tex> {{---}} кол-во таких различий; отсчёты переходов (спектры) <tex>G</tex> являются наборами целых чисел, определенных как <tex>\lambda_k = |\{ j \in \mathbb{Z}_{R^n} : \delta_j = k \}| \,</tex> для <tex> k \in \mathbb{Z}_R</tex>.

'''Не путать''' с [[:Цепные_коды|цепными кодами.]], получаемых циклическим сдвигом.

Поставим в соответствие каждому <tex>i</tex>-ому биту текущего кода Грея <tex>i</tex>-ый диск (причём самому младшему биту соответствует наименьший по размеру диск, а самому старшему биту — наибольший). Поскольку на каждом шаге изменяется ровно один бит, то мы можем понимать изменение бита <tex>i</tex> как перемещение <tex>i</tex>-го диска. То есть, будем понимать переход от последовательности <tex>101</tex> к <tex>100</tex> как перемещение <tex>0</tex>-го диска на свободное место, а от <tex>010</tex> к <tex>110</tex> {{- --}} как перемещение <tex>2</tex>-го диска на свободное место.

Заметим, что для всех дисков, кроме наименьшего, на каждом шаге имеется ровно один вариант хода (за исключением стартовой и финальной позиций). Для самого маленького диска всегда есть две свободные позиции, потому что он самый маленький, тего можно положить сверху на любой диск.кЕсли диск не самый маленький, то для него может быть не более одной свободной позиции. два варианта хода означаютДопустим, что свободны два оставшихся стержня, а это значитдля него свободные две позиции. Это означает, что на самом верху исходного лежит двух других стержнях расположены диски размером больше, чем рассматриваемый. А так как рассматриваемый диск не самый маленький, то где-то расположен наименьший(по условию). Либо он расположен на рассматриваемом диске, тогда мы не можем переместить рассматриваемый, либо на каком-то другом, но тогда у нашего диска остаётся не более одной свободной позиции. Для наименьшего диска всегда имеется два варианта хода, однако имеется стратегия выбора хода, всегда приводящая к ответу: если <tex>n</tex> нечётно, то последовательность перемещений наименьшего диска имеет вид <tex>r_{1} \rightarrow r_{3} \rightarrow r_{2} \rightarrow r_{1} \rightarrow r_{3} \rightarrow r_{2} \rightarrow \ldots .</tex>(где <tex>r_{1}</tex> — стартовый стержень, <tex>r_{3}</tex> — финальный стержень, <tex>r_{2}</tex> — оставшийся стержень), а если <tex>n</tex> чётно, то <tex>r_{1} \rightarrow r_{2} \rightarrow r_{3} \rightarrow r_{1} \rightarrow r_{2} \rightarrow r_{3} \rightarrow \ldots.</tex>

Выбор обусловлен тем, на каком стержне окажется в конце пирамидка, решение с помощью кода Грея является следствием классического нерекурсивного решения<ref>[https://en.wikipedia.org/wiki/Tower_of_Hanoi#Non-recursive_solution Wikipedia {{---}} Tower of Hanoi Non-recursive solution]</ref>. ==См. Также== *[[:Коды_антигрея|Коды антигрея]]