Алгоритм Ханойской башни: Python, C++ Code

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

⚡ Умное резюме

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

  • 🗼 Настройка головоломки: Три штифта и n дисков, расположенных в порядке уменьшения размера, сложены на исходном штифте и ожидают перемещения на целевой штифт с помощью вспомогательного штифта.
  • 📜 Правила: Одновременно может двигаться только один диск, перемещаться может только верхний диск любого штырька, и больший диск не может опираться на меньший диск.
  • 🔁 Рекурсивная идея: Переместите n-1 диск на вспомогательный штырь, переместите самый большой диск на целевой штырь, затем переместите n-1 дисков со вспомогательного штыря на целевой.
  • 🇧🇷 Сложность времени: Для решения задачи с n дисками требуется 2^n – 1 ходов, что дает экспоненциальную временную сложность O(2^n), которая очень быстро растет с увеличением n.
  • ???? Космическая сложность: Стек рекурсии вмещает до n кадров одновременно, поэтому пространственная сложность рекурсивного решения составляет O(n).
  • 🇧🇷 Области применения: Обучение рекурсии, схемам резервного вращения, перемещению данных на основе стека, последовательности действий в робототехнике и пониманию принципов проектирования алгоритмов «разделяй и властвуй».
Читать

Алгоритм Ханойской башни

Что такое Ханойская башня?

Ханойская башня — это математическая головоломка, состоящая из трех стержней и стопки дисков уменьшающегося размера, расположенных один над другим. Она также известна как Башня Брахмы или Башня Лукаса, поскольку французский математик Эдуард Лукас представил её в 1883 году. Головоломка основана на легендах о перемещении золотых дисков между тремя стержнями.

Эта головоломка состоит из трех стержней и переменного количества сложенных друг на друга дисков. Стержни расположены в виде циклических башен, так что большие диски сложены внизу, а меньшие — сверху.

В начале нам даны три стержня. На одном из них (стержень А в примере) сложены все диски. Цель — переместить всю стопку с одного стержня (А) на другой (С), соблюдая несколько определенных правил.

Вот первоначальная конфигурация головоломки:

Проблема Ханойской башни

Проблема Ханойской башни

И вот конечная цель:

Башня Ханоя

Правила Ханойской башни

Вот основные правила посещения Ханойской башни:

  • В исходном состоянии головоломки все диски сложены на первом стержне.
  • В конечном итоге все диски с первого стержня укладываются на второй или третий стержень.
  • В любой момент времени с одного стержня на другой может перемещаться только один диск.
  • Перемещать можно только самый верхний диск на стержне.
  • Один диск нельзя положить поверх другого, меньшего по размеру.

Первоначальная легенда повествовала о перемещении 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 дисков из источника в помощник.

Примечание: Хотя мы можем перемещать только один диск за раз, этот шаг сводит нашу задачу с тремя дисками к задаче с двумя дисками, которая решается рекурсивным вызовом.

Шаг 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. В соответствии с нашим алгоритмНа этом этапе пунктом назначения является штырь А.

Решите головоломку Ханойской башни

На данном этапе: Источник = штырь 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 вызывается дважды.
  • Первый диск движется за постоянное время, что позволяет решить задачу для трех дисков.

Выражено в виде повторения:

= 2 × (Время решения для двух дисков) + постоянное время перемещения диска 3

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

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

Для n дисков это выглядит так:

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

Сумма этой геометрической прогрессии равна O(2).n – 1), что упрощается до O (2n), экспоненциальная временная сложность.

2) Пространственная сложность:

Пространственная сложность алгоритма «Ханойская башня» составляет O(n). Рекурсия использует стек вызовов, а максимальная глубина стека равна n, числу дисков. Именно поэтому пространственная сложность равна O(n).

Часто задаваемые вопросы (FAQ)

Алгоритм «Ханойская башня» — это рекурсивная процедура, которая перемещает 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Разработчикам по-прежнему следует проверять базовые случаи и порядок аргументов.

Подведем итог этой публикации следующим образом: