![](/user_photo/_userpic.png)
1237
.pdf![](/html/65386/197/html_iKcM6MDRdd.T73H/htmlconvd-Nx3lha151x1.jpg)
Ещё раз проанализируем последовательность переноса для трёх дисков 1213121, для четырёх дисков: 1213121412131215121312141…
Делаем выводы [30].
1.Итак, каждый нечетный перенос – это перенос первого диска.
2.Сначала переносится первый диск, потом не первый, затем снова первый, потом не первый и т.д.
3.Для первого диска всегда есть два варианта переноса. Если начальное количество дисков четно, то первый диск движется по часовой стрелке, а если нечетно – то против.
4.Понятие «не первый диск» полностью определяет, какой диск
икуда следует переносить в данный момент, поскольку для «не первого диска» вариант всего один.
Попробуем по «рабоче-крестьянски» нарисовать схему алгоритма. Получаем что-то вроде (рис. П3.24).
Рис. П3.24. Алгоритм решения задачи о Ханойской башне
Теперь надо раскрыть алгоритмы переноса дисков. Перенос против часовой стрелки (рис. П3.25).
151
![](/html/65386/197/html_iKcM6MDRdd.T73H/htmlconvd-Nx3lha152x1.jpg)
Рис. П3.25. Алгоритм переноса против часовой стрелки
Перенос по часовой стрелке (рис. П.3.26).
Рис. П3.26. Алгоритм переноса по часовой стрелке
152
![](/html/65386/197/html_iKcM6MDRdd.T73H/htmlconvd-Nx3lha153x1.jpg)
Рассмотрим перенос не первого диска – наименьшего из не первых. Для этого преобразуем схему алгоритма на рис. П3.26 – сделаем три выхода, получим рис. П3.27.
Рис. П3.27. Алгоритм переноса по часовой стрелке с выходами А, В, С
Тогда для определения не первого диска и его переноса по варианту А получим рис. П3.28.
153
![](/html/65386/197/html_iKcM6MDRdd.T73H/htmlconvd-Nx3lha154x1.jpg)
Рис. П3.28. Алгоритм переноса не первого диска по варианту А
Для определения не первого диска и его переноса по варианту В получим рис. П.3.29.
154
![](/html/65386/197/html_iKcM6MDRdd.T73H/htmlconvd-Nx3lha155x1.jpg)
Рис. П3.29. Алгоритм переноса не первого диска по варианту В
Для определения не первого диска и его переноса по варианту С получим рис. П.3.30.
155
![](/html/65386/197/html_iKcM6MDRdd.T73H/htmlconvd-Nx3lha156x1.jpg)
Рис. П3.30. Алгоритм переноса не первого диска по варианту С
Эти три алгоритма на рис. П3.28–П3.30 применимы и для переноса по часовой стрелке с такими же выходами А, В, С (рис. П3.31).
156
![](/html/65386/197/html_iKcM6MDRdd.T73H/htmlconvd-Nx3lha157x1.jpg)
Рис. П3.31. Алгоритм переноса по часовой стрелке
свыходами А, В, С
Взаключение приведём рисунок Ханойской башни наоборот
(рис. П3.32).
Рис. П3.32. Ханойская башня «наоборот»
Кроме того, оказывается, задача о Ханойской башне хорошо согласуется с такой структурой, как куб [31]. Оптимальное решение – это движение почти по гамильтонову циклу для трёхмерного куба ХYХZХYZ и для 4-мерного ХYХZХYХWХYХZХYХ (рис. П3.33).
157
![](/html/65386/197/html_iKcM6MDRdd.T73H/htmlconvd-Nx3lha158x1.jpg)
Рис. П3.33. Ханойская башня и куб соседних чисел
Если заменить Х на А, У на В, Z на С, то оптимальный путь в четырёхмерном кубе, якобы соответствует обозначениям дюймовой линейки – она образуется при делении дюймового отрезка на два [31] (рис. П3.34).
Рис. П3.34. Обозначения дюймовой линейки
158
Учебное издание
ТЮРИН Сергей Феофентович
ТЕОРИЯ ГРАФОВ И ЕЁ ПРИЛОЖЕНИЯ
Учебное пособие
Редактор и корректор И.Н. Жеганина
––––––––––––––––––––––––––––––––––––––––––––––––––––––––
Подписано в печать 9.11.15. Формат 60×90/16. Усл. печ. л. 10,0. Тираж 100 экз. Заказ № 219/2015.
––––––––––––––––––––––––––––––––––––––––––––––––––––––––
Издательство Пермского национального исследовательского
политехнического университета Адрес: 614990, г. Пермь, Комсомольский пр., 29, к. 113.
Тел. (342) 219-80-33
159