Page 85 - 2589

знаходитися над меншим. У якості додаткової умови необхідно
знайти рішення, що вимагає найменшого числа кроків.
Занумеруємо диски в порядку їх спадання їх діаметрів:

m ,m  1 ,..., 1. Позначимо через X,Y,Z множини дисків, надітих
відповідно на перший, другий і третій кілок на будь якому з

кроків.
При цьому досить вказати тільки множини X і Z оскільки
множина Y виходить як доповнення множин X і Z до повного
числа дисків. Кожною з множин. X або Z може бути одна з

наступних комбінацій дисків : 0, 1, 2, 21, 3, 31, 32, 321, 4, 41, 42,
421, 43, 431, 432, 4321 ... Ці комбінації можна зображувати

умовними точками на осях X і Z, як показано на рис.4.6 так що
будь-яке розташування дисків (стан системи) відповідає точці на
площині (X,Z). Сполучаючи ці точки лініями, що вказують
можливі на кожному кроці переміщення дисків, отримаємо

неорієнтований граф, на якому можна знайти шляхля переходу з
початкової точки графа в кінцеву.

Побудову графа можна зробити шляхом переходу від m
дисків до m+1. При m= 1 можливі стани представлятимуться
множиною 1{( 0 , ), 0 , 0 ( ), 1 , 0 ( )} якій відповідає граф на рис.4.6, з

вказаним на ньому найкоротшим переходом із початкового стану
(1,0) в кінцевий (0,1).

Рисунок 4.6 – Графи переходів в задачі про ханойську вежу

Для отримання загального правила припустимо, що вже

побудований граф для випадку m дисків, який назвемо m-графом.
Неважко переконатися, що такий граф матиме вигляд

85