Ханойська вежа

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Приклад ханойської вежі із вісьмома дисками
Анімоване розв'язування задачі Ханойська вежа для T(4,3).

Ханойська вежа (також Вежа Брахми або Вежа Лукаса, іноді в множині Ханойські вежі) — це математична гра або головоломка. Утворена трьома стрижнями і кількома дисками різних розмірів, які можна насунути на будь-який стрижень. Початковий стан головолмки має два порожніх стрижні і всі диски на третьому в монотонно спадному порядку з низу до гори, так утворюється побудова, що нагадує вежу.

Ціллю головоломки є перенести весь стос дисків на інший стрижень, дотримуючись таких правил:

  • За раз можна рухати лише один диск.
  • Кожен крок полягає в перенесенні верхнього диска з одного зі стрижнєв і насування його на інший зверху інших дисків, які вже можуть бути присутніми на другому стрижні.
  • Диск не можна класти з гори меншого диска.

З трьома дисками, головоломку можна розв'язати за сім кроків.

Походження[ред.ред. код]

На Заході задачку вперше оприлюднив французький математик Едуард Лукас у 1863. Існує легенда про храм в Індії, який містив велику кімнату з трьома стовпами і 64 золотими дисками на них. Жрець брагман, виконував команду давнього пророцтва, переставляючи ці диски згідно з правилами головоломки, від того часу. Звідси друга назва головоломки — головоломка веж Брагми. Згідно з легендою, після завершального руху настане кінець світу.[1] Не ясно чи Лукас вигадав цю легенду або надихнувся нею.

Якщо легенда правдива, і якщо жрець може пересувати диски зі швидкістю один раз в секунду, найменша кількість пересувів займе в нього 264−1 секунд або близько 585 мільярдів років[2] або 18,446,744,073,709,551,615 пересувів до завершення.

Також існують інші версії легенди. Наприклад, в деяких викладеннях, храм був монастирем і жрець був монахом. Храм чи монастир може стояти в різних частинах світу — включно з Ханоєм, В'єтнам, і може приналежати будь-якій релігії. В деяких варіаціях додаються інші складові, такі як те, що вежі створили на початку світу, або що жрець чи монах може робити лише один рух в день.

Розв'язання[ред.ред. код]

Головоломку можна розв'язати для будь-якої кількості дисків, більшість іграшкових версій мають близько семи-дев'яти. Багатьом новачкам гра видається нерозв'язною, хоча існує простий алгоритм розв'язання. Кількість рухів необхідна для розв'язання становить 2n -1, де n — найменша кількість дисків.[3]

Ітеративний розв'язок[ред.ред. код]

Наступний розв'язок є простим розв'язком для іграшкової головоломки.

Чергуйте рухи між найменшим і не найменшим дисками. Коли рухаєте найменший диск, завжди рухайте його до наступної позиції в одному напрямку (праворуч, якщо початкова кількість дисків парна і ліворуч, якщо непарна). Якщо в обраному напрямку немає вежі, пересувайте найменший диск до протилежного краю, тоді продовжуйте в обраному напрямку. Наприклад, якщо ви почали з трьома дисками, вам треба рухати найменший диск на протилежний край, тоді продовжити в напрямку ліворуч. Тоді черга не найменшого диску, тут ми маємо лише один варіант. Так ми завершимо головоломку, використавши найменшу кількість рухів для цього.

Примітки[ред.ред. код]

  1. Spitznagel, Edward L. (1971). Selected topics in mathematics. Holt, Rinehart and Winston. с. 137. ISBN 0-03-084693-5. 
  2. Ivan Moscovich, 1000 playthinks: puzzles, paradoxes, illusions & games, Workman Pub., 2001 ISBN 0-7611-1826-8.
  3. Petković, Miodrag (2009). Famous Puzzles of Great Mathematicians. AMS Bookstore. с. 197. ISBN 0-8218-4814-3. 

Посилання[ред.ред. код]