1632
правки
Изменения
м
rollbackEdits.php mass rollback
{| border="0"
|align="left" colspan="4"|
*<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>-м коде Грея.
<code>
buildCode(n):
Для кода длиной <tex>1</tex> бит утверждение проверяется непосредственно.
Пусть существует зеркальный двоичный код Грея <tex>M</tex> длины <tex>n</tex>, для которого выполнено, что для любого <tex>i</tex> выполняется <tex>е\enskip enspace M_i = i \oplus (\lfloor i / 2 \rfloor)</tex>
Обозначим за <tex>L</tex> код длины <tex>n + 1</tex>, полученный из <tex>M</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>= x \oplus (\lfloor x / 2 \rfloor)</tex>
Для любого <tex>x \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>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> (с помощью кода Грея мы знаем индекс диска, которых необходимо переместить.
==См. Также==
