317
правок
Изменения
→Задача о Ханойских башнях
Поставим в соответствие каждому <tex>i</tex>-ому биту текущего кода Грея <tex>i</tex>-ый диск (причём самому младшему биту соответствует наименьший по размеру диск, а самому старшему биту — наибольший). Поскольку на каждом шаге изменяется ровно один бит, то мы можем понимать изменение бита <tex>i</tex> как перемещение <tex>i</tex>-го диска.
Заметим, что для всех дисков, кроме наименьшего, на каждом шаге имеется ровно один вариант хода (за исключением стартовой и финальной позиций). Для наименьшего диска всегда имеется два варианта хода, однако имеется стратегия выбора хода, всегда приводящая к ответу: если <tex>n</tex> нечётно, то последовательность перемещений наименьшего диска имеет вид <tex>f r_{1} \rightarrow t r_{3} \rightarrow r r_{2} \rightarrow f r_{1} \rightarrow t r_{3} \rightarrow r r_{2} \rightarrow \ldots .</tex>(где <tex>fr_{1}</tex> — стартовый стержень, <tex>tr_{3}</tex> — финальный стержень, <tex>rr_{2}</tex> — оставшийся стержень), а если <tex>n</tex> чётно, то <tex>f r_{1} \rightarrow r r_{2} \rightarrow t r_{3} \rightarrow f r_{1} \rightarrow r r_{2} \rightarrow t r_{3} \rightarrow \ldots.</tex>
==Примечания==
