Временная сложность
O(2^n - 1)
Ханойская башня — это классическая рекурсивная головоломка. Необходимо переместить все диски с исходного стержня на целевой, по одному за раз, никогда не помещая больший диск поверх меньшего.
Как это работает (рекурсия):
1. Переместить верхние n-1 дисков с исходного стержня на вспомогательный
2. Переместить самый большой диск с исходного стержня на целевой
3. Переместить n-1 дисков со вспомогательного стержня на целевой
Временная сложность: O(2^n - 1) — ровно 2^n - 1 перемещений
Пространственная сложность: O(n) — стек рекурсивных вызовов
Свойства:
- Минимальное количество перемещений: 2^n - 1
- Классический пример метода «разделяй и властвуй»
- Демонстрирует возможности рекурсии
Головоломка была придумана математиком Эдуардом Люка в 1883 году. Согласно легенде, монахи в храме перемещают 64 золотых диска — завершение этой задачи ознаменует конец света (для этого потребуется 18 446 744 073 709 551 615 перемещений).
Похожие алгоритмы
Частые вопросы
- Что такое Ханойская башня?
- Ханойская башня — это классическая рекурсивная головоломка. Необходимо переместить все диски с исходного стержня на целевой, по одному за раз, никогда не помещая больший диск поверх меньшего.
- Какова сложность Ханойская башня?
- Время (среднее): O(2^n - 1) · Память: O(n)
- Для кого предназначена визуализация Ханойская башня?
- Визуализация Ханойская башня рассчитана на средний уровень в категории «Разделяй и властвуй». Полезна для студентов, подготовки к собеседованиям и практического изучения.
- Какие алгоритмы связаны с Ханойская башня?
- В той же категории (Разделяй и властвуй) вы можете изучить: Binary Exponentiation. Каждый из них имеет интерактивную визуализацию.