317
правок
Изменения
→Задача о Ханойских башнях
Пусть <tex>n</tex> — количество дисков. Начнём с кода Грея длины <tex>n</tex>, состоящего из одних нулей (т.е. <tex>G(0)</tex>), и будем двигаться по кодам Грея (от <tex>G(i)</tex> переходить к <tex>G(i+1)</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>
Выбор обусловлен тем, на каком стержне окажется в конце пирамидка.
==Примечания==
