Алгоритм Ханойської вежі: Python, C++ Code

Автор: Сара Чен Сара Чен
Hours оновлений

⚡ Розумний підсумок

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

  • 🗼 Налаштування головоломки: Три кілочки та n дисків, розташованих у порядку зменшення розміру на вихідному кілочку, очікують переміщення до кілочка призначення за допомогою допоміжного кілочка.
  • 📜 Правила: Одночасно рухається лише один диск, може рухатися лише верхній диск будь-якого кілочка, а більший диск не може спиратися на менший диск.
  • 🔁 Рекурсивна ідея: Перемістіть n-1 дисків до допоміжного кілочка, перемістіть найбільший диск до кілочка призначення, потім перемістіть n-1 дисків з допоміжного кілочка до кілочка призначення.
  • 🇧🇷 Складність часу: Розв'язання n дисків вимагає 2^n – 1 ходів, що дає експоненціальну часову складність O(2^n), яка дуже швидко зростає зі збільшенням n.
  • 🧠 Складність простору: Стек рекурсії містить до n кадрів одночасно, тому просторова складність рекурсивного розв'язку дорівнює O(n).
  • 🛠️ Область застосування: Викладання рекурсії, схем ротації резервних копій, переміщення даних на основі стеку, робототехнічного секвенування та розуміння розробки алгоритмів «розділяй і володарюй».
Детальніше

Алгоритм Ханойської вежі

Що таке Ханойська вежа?

Ханойська вежа — це математична головоломка, що складається з трьох стрижнів та стопки дисків зменшуваного розміру, розміщених один над одним. Вона також відома як Вежа Брахми або вежа Лукаса, оскільки французький математик Едуар Люка представив її у 1883 році. Головоломка заснована на легендах про переміщення золотих дисків між трьома стрижнями.

Ця головоломка має три стрижні та змінну кількість дисків, що складаються один на одного. Стрижні розташовані у вигляді циклічних веж, тож більші диски складаються знизу, а менші — зверху.

Спочатку нам дають три кілочки або стрижні. На одному з них (кілочок A у прикладі) усі диски складені один в один. Мета полягає в тому, щоб перемістити весь стопку з одного стрижня (A) на інший (C), дотримуючись кількох певних правил.

Ось початкова налаштування головоломки:

Проблема Ханойської вежі

Проблема Ханойської вежі

І це кінцева мета:

Вежа Ханоя

Правила Ханойської вежі

Ось основні правила для Ханойської вежі:

  • У початковому стані головоломки всі диски складені на стрижні один.
  • У кінцевому стані всі диски зі стрижня один укладаються на стрижень два або стрижень три.
  • Тільки один диск може переміщатися з одного стрижня на інший у будь-який момент часу.
  • Переміщувати можна лише верхній диск на стрижні.
  • Диск не можна розмістити поверх меншого диска.

Оригінальна легенда розповідала про переміщення 64 дисків. Жерці могли переміщувати по одному диску за раз згідно з правилами. Згідно з легендою, існувало пророцтво, що світ закінчиться, якщо вони зможуть завершити цю дію. У розділі про часову складність ми покажемо, що для встановлення Ханойської вежі з n дисків потрібно 2^n – 1 ходів.

Отже, якби жерцям знадобилася 1 секунда, щоб перемістити один диск, загальний час для розв'язання головоломки становитиме 2^64 – 1 секунду, або приблизно 584 942 417 356 років, 26 днів, 7 годин і 15 секунд.

Алгоритм для Ханойської вежі

Найпоширеніший спосіб розв'язання задачі Ханойської вежі – це рекурсивний алгоритм. Спочатку ми вибираємо два стрижні як джерело та призначення; запасний кілочок діє як допоміжний або помічник.

Ось кроки, щоб вирішити головоломку Ханойської вежі:

  • Перемістіть верхні n-1 диски від вихідного кілка до допоміжного.
  • Перемістіть n-й диск з вихідного кілочка на цільовий кілочок.
  • Перемістіть решту n-1 дисків з допоміжного кілочка на цільовий кілочок.

Примітка: Якщо у нас є один диск, ми можемо перемістити його безпосередньо від джерела до місця призначення.

Як вирішити головоломку Ханойської вежі

Проілюструємо алгоритм для трьох дисків. Розглянемо кілочок A як джерело, кілочок B як допоміжний диск, а кілочок C як пункт призначення.

Крок 1) Спочатку всі диски складаються на кілочку А.

Вирішіть головоломку Ханойська вежа

На цьому етапі: Джерело = Кілочок A, Призначення = Кілочок C, Помічник = Кілочок B.

Тепер нам потрібно перемістити верхні n-1 диски з вихідного на допоміжний.

Примітка: Хоча ми можемо переміщувати лише один диск за раз, цей крок зводить нашу задачу з 3 дисками до задачі з 2 дисками, яка обробляється рекурсивним викликом.

Крок 2) Коли ми здійснюємо рекурсивний виклик з кілочка A, маючи кілочок B як пункт призначення, ми використовуємо кілочок C як допоміжний механізм.

Зверніть увагу, що ми повернулися до першого етапу для тієї ж задачі про Ханойську вежу, але тепер для двох дисків. Ми переміщуємо n-1 (тобто один) диск від джерела до допоміжного, що переміщує найменший диск від кілочка A до кілочка C.

Вирішіть головоломку Ханойська вежа

На цьому етапі: Джерело = кілочок A, Пункт призначення = кілочок B, Помічник = кілочок C.

Крок 3) Згідно з алгоритмом, n-й (2-й) диск тепер переміщується до місця призначення, кілочка B.

Вирішіть головоломку Ханойська вежа

На цьому етапі: Джерело = кілочок A, Пункт призначення = кілочок B, Помічник = кілочок C.

СТАТТІ ПО ТЕМІ

Крок 4) Тепер ми переміщуємо n-1 диск (диск один) з допоміжного кілочка C до цільового кілочка B, дотримуючись третього етапу алгоритму.

Вирішіть головоломку Ханойська вежа

На цьому етапі: Джерело = кілочок A, Пункт призначення = кілочок B, Помічник = кілочок C.

Крок 5) Після завершення рекурсивного виклику ми повертаємося до попередніх налаштувань на першому етапі алгоритму.

Крок 6) На другому етапі ми переміщуємо диск 3 з вихідного кілочка A до цільового кілочка C.

На цьому етапі: Джерело = кілочок A, Пункт призначення = кілочок C, Помічник = кілочок B.

Крок 7) Наступне завдання — перемістити решту дисків з допоміжного вузла (кілочок B) до місця призначення (кілочок C). Цього разу ми використовуватимемо оригінальний вузол (кілочок A) як допоміжний вузол.

Вирішіть головоломку Ханойська вежа

Крок 8) Оскільки ми не можемо перемістити два диски одночасно, ми виконуємо рекурсивний виклик для диска 1. Згідно з нашим алгоритм, пунктом призначення на цьому кроці є кілочок A.

Вирішіть головоломку Ханойська вежа

На цьому етапі: Джерело = кілочок B, Пункт призначення = кілочок A, Помічник = кілочок C.

Крок 9) Наш рекурсивний виклик завершено. Тепер ми переміщуємо диск 2 з його джерела до місця призначення.

Вирішіть головоломку Ханойська вежа

На цьому етапі: Джерело = кілочок B, Пункт призначення = кілочок C, Помічник = кілочок A.

Крок 10) Ми завершуємо переміщенням решти n-1 диска (диск 1) з допоміжного пристрою до місця призначення.

Вирішіть головоломку Ханойська вежа

На цьому етапі: Джерело = кілочок A, Пункт призначення = кілочок C, Помічник = кілочок B.

Псевдо Code для Ханойської вежі

START
Procedure Tower_Of_Hanoi(disk, source, dest, helper)
    IF disk == 1 THEN
        move disk from source to dest
    ELSE
        Tower_Of_Hanoi(disk - 1, source, helper, dest)
        move disk from source to dest
        Tower_Of_Hanoi(disk - 1, helper, dest, source)
    END IF
END Procedure

Програмний код в C++

#include <bits/stdc++.h>
using namespace std;
void tower_of_hanoi(int num, string source, string dest, string helper) {
    if (num == 1) {
        cout << " Move disk 1 from tower " << source << " to tower " << dest << endl;
        return;
    }
    tower_of_hanoi(num - 1, source, helper, dest);
    cout << " Move disk " << num << " from tower " << source << " to tower " << dest << endl;
    tower_of_hanoi(num - 1, helper, dest, source);
}
int main() {
    int num;
    cin >> num;
    printf("The sequence of moves :\n");
    tower_of_hanoi(num, "I", "III", "II");
    return 0;
}

вихід:

3
The sequence of moves :
Move disk 1 from tower I to tower III
Move disk 2 from tower I to tower II
Move disk 1 from tower III to tower II
Move disk 3 from tower I to tower III
Move disk 1 from tower II to tower I
Move disk 2 from tower II to tower III
Move disk 1 from tower I to tower III

Програмний код в Python

def tower_of_hanoi(n, source, destination, helper):
    if n == 1:
        print("Move disk 1 from peg", source, "to peg", destination)
        return
    tower_of_hanoi(n - 1, source, helper, destination)
    print("Move disk", n, "from peg", source, "to peg", destination)
    tower_of_hanoi(n - 1, helper, destination, source)
# n = number of disks
n = 3
tower_of_hanoi(n, 'A', 'B', 'C')

вихід:

Move disk 1 from peg A to peg B
Move disk 2 from peg A to peg C
Move disk 1 from peg B to peg C
Move disk 3 from peg A to peg B
Move disk 1 from peg C to peg A
Move disk 2 from peg C to peg B
Move disk 1 from peg A to peg B

Складність Ханойської вежі

Ось часова та просторова складність Ханойської вежі:

1) Часова складність:

Озираючись на алгоритм, ми виконуємо рекурсивний виклик для (n-1) дисків двічі за виклик. Кожна (n-1) рекурсія розбивається на ((n-1)-1) рекурсій і так далі, доки ми не досягнемо базового випадку з одним диском.

Для трьох дисків:

  • Диск 3 двічі викликає рекурсивну функцію для диска 2.
  • Диск 2 двічі викликає рекурсивну функцію для диска 1.
  • Диск 1 рухається за постійний час, що дає час для розв'язання для трьох дисків.

Виражається як рекурентність:

= 2 × (Час розв'язання для двох дисків) + константа часу переміщення диска 3

= 2 × (2 × час розв'язання для одного диска + постійний час переміщення диска 2) + постійний час переміщення диска 3

= (2 × 2) × постійний час переміщення диска 1 + 2 × постійний час переміщення диска 2 + постійний час переміщення диска 3

Для n дисків це стає:

2н-1 × константа часу переміщення диска 1 + 2н-2 × постійний час переміщення диска 2 + ….

Ця геометрична прогресія дорівнює O(2n – 1), що спрощується до O(2n), експоненціальна часова складність.

2) Складність простору:

Просторова складність Ханойської вежі становить O(n). Рекурсія використовує стек викликів, а максимальна глибина стеку дорівнює n, кількості дисків. Саме тому просторова складність становить O(n).

Поширені запитання

Алгоритм «Вежа Ханоя» — це рекурсивна процедура, яка переміщує n дисків з вихідного кілочка до кінцевого, використовуючи один допоміжний кілочок, ніколи не розміщуючи більший диск поверх меншого.

Мінімальна кількість ходів для n дисків дорівнює 2^n – 1. Трьом дискам потрібно 7 ходів, чотирьом дискам – 15, а десяти дискам – 1,023 ходи.

Часова складність становить O(2^n), оскільки кожен додатковий диск подвоює роботу. Рекурентна формула T(n) = 2T(n-1) + 1 вирішує 2^n – 1, що є експоненціальною.

Просторова складність становить O(n), оскільки стек рекурсійних викликів містить один кадр для кожного оброблюваного диска. Максимальна глибина рекурсії досягає n, тому необхідна допоміжна пам'ять лінійно залежить від кількості дисків.

Так. Ітераційне рішення використовує цикл із фіксованим шаблоном: на непарних ходах циклічно міняється місцем найменший диск між кілочками, а на парних ходах робиться єдиний допустимий не найменший хід.

Алгоритм навчає рекурсії, моделює схеми резервного копіювання та ротації для зберігання, керує секвенуванням роботизованої руки та використовується в нейропсихологічних тестах, що вимірюють здатність до планування.

Агенти навчання з підкріпленням вирішують задачу "Вежа Ханоя", розглядаючи кожну конфігурацію диска як стан, а кожен рух як дію. Це загальний орієнтир для планування та ієрархічного навчання політик.

Так. GitHub Copilot, ChatGPT та Gemini генерувати рекурсивні рішення для Ханойської вежі в Python, C++ та JavaРозробникам все одно слід перевіряти базові випадки та порядок аргументів.

Підсумуйте цей пост за допомогою: