Применение кода Грея для решения башня рекурсия граф головоломка

Коды Грея применяются в решении задачи о Ханойских башнях. Пусть N — количество дисков. Начнём с кода Грея длины N, состоящего из одних нулей (то есть G (0)), и будем двигаться по кодам Грея (от G (i) переходить к G (i+1)). Поставим в соответствие каждому I-ому биту текущего кода Грея I-ый диск (причём самому младшему биту соответствует наименьший по размеру диск, а самому старшему биту — наибольший).

Поскольку на каждом шаге изменяется ровно один бит, то мы можем понимать изменение бита I как перемещение I-го диска. Заметим, что для всех дисков, кроме наименьшего, на каждом шаге имеется ровно один вариант хода (за исключением стартовой и финальной позиций). Для наименьшего диска всегда имеется два варианта хода, однако имеется стратегия выбора хода, всегда приводящая к ответу: если N нечётно, то последовательность перемещений наименьшего диска имеет вид f->t->r->f->t->r->… (где f-стартовый стержень, t-финальный стержень, r-оставшийся стержень), а если N чётно, то f->r->t->f->r->t->…

Различные задачи с измененным условием

Ханойские башни — старая задача и она уже давно решена, поэтому сейчас существует уже много задач, условие которых было изменено или доработано для усложнения.

В данной курсовой работе были рассмотрены некоторые из них:

) Постановлением ЮНЕСКО оригинал Ханойской башни был подвергнут реставрации. В связи с этим во время пользования головоломкой нельзя было перекладывать кольца с первого стержня сразу на третий и наоборот.

Решите головоломку (переложите все кольца с первого стержня на третий) с учетом этих ограничений. Вам не нужно находить минимальное решение, но количество совершенных перемещений не должно быть больше 200 000, при условии, что количество дисков не превосходит 10. Каждое перемещение задается тремя числами: номер кольца, исходный стержень, конечный стержень (приложение 3).

На дорогах Ханоя было введено одностороннее круговое движение, поэтому теперь диск со стержня 1 можно перекладывать только на стержень 2, со стержня 2 на 3, а со стержня 3 на 1.

Решите головоломку с учетом этих ограничений. Вам не нужно находить минимальное решение, но количество совершенных перемещений не должно быть больше 200 000, при условии, что количество дисков не превосходит 10 (приложение 5).