UK 
EnglishТипова
Polski🗼 Ханойська вежа — рекурсивний розв'язувач та 2ⁿ−1 ходів
Дивіться, як Ханойська вежа розв'язує себе оптимальною рекурсією на 1–10 дисках з анімацією підняти-перенести-опустити. Лічильники стежать за ходами відносно мінімуму 2ⁿ−1; перемкніться в ручний режим і розв'яжіть вручну.
Схожі симуляції
Про Ханойську вежу
Ханойська вежа — математична головоломка, винайдена французьким математиком Едуардом Люка 1883 року. Завдання полягає в тому, щоб перенести стопку з N дисків зі стрижня-джерела на стрижень-призначення, використовуючи третій допоміжний стрижень, дотримуючись правила, що більший диск не можна класти на менший. Оптимальний рекурсивний розв'язок досягає цього рівно за 2N − 1 ходів, що доведено є мінімумом: кожну підвежу з N−1 дисків потрібно перенести двічі (один раз зняти й один раз повернути на найбільший диск), плюс один хід для нижнього диска. Для N=64 дисків — легендарної умови головоломки — мінімальна кількість ходів перевищує 1,8 × 1019, що вимагатиме мільярдів років при одному ході за секунду.
Ця симуляція анімує рекурсивний розв'язок для 1–8 дисків, малюючи кожен хід крок за кроком із налаштовуваною швидкістю. Поруч зі стрижнями відображається дерево рекурсивних викликів, що робить видимою структуру «розділяй і володарюй»: кожен виклик Hanoi(N) породжує два виклики Hanoi(N−1), ілюструючи експоненціальне зростання кількості ходів.
Часті запитання
Чому Ханойська вежа вимагає рівно 2N − 1 ходів?
За індукцією: для N=1 достатньо одного ходу (21−1=1). Для N дисків спершу потрібно перенести верхні N−1 дисків на допоміжний стрижень (2N−1−1 ходів), потім перенести найбільший диск на стрижень призначення (1 хід), а тоді перенести стопку з N−1 дисків на стрижень призначення (ще 2N−1−1 ходів). Разом: 2·(2N−1−1)+1 = 2N−1. Аргумент про нижню межу показує, що жоден розв'язок не може зробити це за меншу кількість ходів.
Який ітеративний алгоритм існує для Ханойської вежі?
Елегантний ітеративний алгоритм чергує два правила: (1) зробити дозволений хід, що включає найменший диск, і (2) зробити єдиний дозволений хід, що не включає найменший диск. Також працює двійкова інтерпретація: диск, який рухається на кроці m, — це диск на позиції найнижчого встановленого біта числа m. Це напряму пов'язує Ханойську вежу з двійковим лічбою та перебором коду Грея.
Як Ханойська вежа ілюструє рекурсію та принцип «розділяй і володарюй»?
Триряковий рекурсивний розв'язок є ідеальним прикладом принципу «розділяй і володарюй»: задача з N дисками розкладається на дві підзадачі розміру N−1 та один базовий випадок (перенести один диск). Дерево викликів — це повне бінарне дерево глибини N із 2N−1 листовими викликами (по одному на хід), тож загальний обсяг роботи становить рівно 2N−1. Це канонічний приклад, який використовують майже в кожному вступному підручнику з алгоритмів.
Чи існує формула в замкненому вигляді для того, на якому стрижні опиниться диск k після m ходів?
Так. Диск k (нумерація з нуля, від найменшого) перебуває на стрижні (біт k числа m) XOR (біт k+1 числа m) у стандартному кодуванні з трьома стрижнями, де m записано у двійковій системі. Це дозволяє обчислити будь-який стан за O(log m) без симуляції всіх попередніх ходів — корисна властивість для перевірки великих послідовностей Ханойської вежі обчислювальним шляхом або для реалізації швидкого пошуку станів.
У чому полягає гіпотеза Фрейма-Стюарта для чотирьох і більше стрижнів?
З чотирма стрижнями може вистачити менш ніж 2N−1 ходів. Алгоритм Фрейма-Стюарта (1941) висуває гіпотезу, що оптимальна кількість ходів становить приблизно 2·√(2N) для великих N — експоненційно краще, ніж у випадку з трьома стрижнями. Гіпотезу для чотирьох стрижнів довів Буш (Bousch) у 2014 році. Для п'яти і більше стрижнів оптимальна кількість ходів залишається відкритою проблемою комбінаторики.
Скільки часу знадобилося б, щоб розв'язати Ханойську вежу з 64 дисками?
Мінімальна кількість ходів для 64 дисків становить 264−1 ≈ 1,84 × 1019. При одному ході на секунду це зайняло б близько 585 мільярдів років — приблизно у 42 рази більше за поточний вік Всесвіту. Люка згадував це ще 1883 року, жартома припускаючи, що ченці, які завершать головоломку, покладуть край світові.
Як Ханойська вежа пов'язана з двійковим лічбою та «лінійковою» послідовністю?
Послідовність номерів дисків, які рухаються в оптимальному розв'язку, — 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, … — відома як «лінійкова» послідовність або лінійка Штерна-Броко. Диск, який рухається на кроці m, дорівнює найбільшому степеню двійки, що ділить m (позиції найнижчого встановленого біта). Ця послідовність ізоморфна послідовності позицій бітів, що змінюються при двійковому лічбі від 0 до 2N−1.
Чи можна розв'язати Ханойську вежу нерекурсивно, за допомогою явного стека?
Так. Потрібно поміщати кортежі (n, джерело, ціль, допоміжний) у стек. Виймаючи кортеж: якщо n=1, виконати хід; інакше — покласти три менші кортежі у зворотному порядку. Це усуває накладні витрати на виклики функцій і дає ту саму послідовність. Однак це все одно вимагає O(2N) записів у стеку для зберігання всіх відкладених підзадач, тож просторова складність ідентична рекурсивному підходу.
Як граф Ханойської вежі пов'язаний із трикутником Серпінського?
Граф Ханойської вежі — де вершини це допустимі конфігурації дисків, а ребра це дозволені ходи одним диском — ізоморфний фракталу трикутника Серпінського рівня N. 3N станів задачі з N дисками утворюють самоподібний граф, у якому три копії задачі з N−1 диском з'єднані у кутових вершинах. Цей зв'язок лежить в основі застосувань у фрактальному аналізі та дослідженнях теоретико-графової складності.
Чи використовується Ханойська вежа в нейропсихологічному тестуванні?
Так. Ханойська вежа (та її близький родич — Лондонська вежа) — стандартні завдання в нейропсихологічній діагностиці для оцінювання виконавчих функцій, робочої пам'яті та здатності до планування. Дослідження показують, що пацієнти з ураженнями лобової частки або хворобою Паркінсона показують значно гірші результати в завданнях з великою кількістю дисків, що робить цей тест чутливим інструментом дослідження функції префронтальної кори в клінічних дослідженнях.