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

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

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

В этой головоломке есть три стержня и переменное количество сложенных друг на друга дисков. Эти стержни выполнены в виде циклических башен. Так, диски большего диаметра укладываются внизу, а диски меньшего диаметра – сверху.

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

Вот первоначальная настройка головоломки:

И это конечная цель-

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

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

В исходном состоянии этой головоломки все диски будут сложены в один стержень.
В конечном итоге все диски первого стержня будут сложены на второй или третий стержень.
Мы можем переместить диск с одного стержня на другой в любой момент времени.
Нам остается только сдвинуть со стержня самый верхний диск.
Диск не может быть помещен поверх другого диска меньшего размера.

Оригинальная легенда касалась перемещения 64 дисков. Согласно правилам, жрецы могли перемещать по одному диску за раз. Согласно легенде, было пророчество, что наступит конец света, если они смогут совершить это действие. В разделе временной сложности мы покажем, что установка Ханойской башни из n дисков будет стоить 2^n – 1 ход.

Итак, если бы священникам потребовалась 1 секунда, чтобы переместить диски, общее время, которое им потребовалось бы для решения головоломки, составило бы 2^64 – 1 секунда или 584,942,417,356 26 7 15 лет, XNUMX дней, XNUMX часов и XNUMX секунд.

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

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

Вот шаги для решения головоломки Ханойской башни:

Переместите верхние n-1 дисков с исходной привязки на вспомогательную.
После этого переместите n-й диск с исходной привязки на целевую.
Наконец, переместите оставшиеся n-1 дисков со вспомогательной привязки на целевую.

Внимание: Если у нас есть один диск, мы можем напрямую переместить его из источника в пункт назначения.

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

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

Шаг 1) Первоначально все диски будут сложены на колышке A.

На этом этапе:

Источник = привязка 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 на привязку C с привязки A.

На этом этапе:

Источник = привязка A
Пункт назначения = привязка C
Помощник = колышек B

Шаг 7) Теперь мы можем видеть, что

d — переместить оставшиеся диски из вспомогательного (привязка B) в пункт назначения (привязка C). В этом случае мы будем использовать первоначальный источник или привязку A в качестве помощника.

Шаг 8) Поскольку мы не можем перемещать два диска одновременно, мы вызовем рекурсивный вызов для диска 1. Согласно последнему шагу и нашему алгоритм, пунктом назначения на этом этапе является привязка A.

На этом этапе:

Источник = привязка B
Пункт назначения = привязка A
Помощник = привязка C

Шаг 9) Наш рекурсивный вызов завершен. Затем мы перемещаем диск 2 из источника в пункт назначения.

На этом этапе:

Источник = привязка B
Пункт назначения = привязка C
Помощник = привязка A

Шаг 10) Затем мы перемещаем оставшийся n-1 или диск 1 от помощника к месту назначения.

На этом этапе:

Источник = привязка A
Пункт назначения = привязка C
Помощник = колышек B

Псевдокод Ханойской башни

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 дважды вызывает рекурсивную функцию для первого диска.
Диск 1 может двигаться в пределах постоянного Времени, а Время решать за три диска.

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

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

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

Для n дисков это можно записать как –

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

Эта геометрическая прогрессия приведет к O(2^п-1) Или O (2ⁿ), что является экспоненциальным.

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

Пространственная сложность Ханойской башни равна 0(n). Это потому, что нам нужно сохранить последовательность пластин. Когда мы используем рекурсию, она использует стек. А максимальный размер стека может быть «n». Вот почему пространственная сложность становится O(n).

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

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

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

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

СТАТЬИ ПО ТЕМЕ

Псевдокод Ханойской башни

Код программы в C++

Код программы в Python

Сложность Ханойской башни

Подпишитесь на рассылку