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

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

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

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

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

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

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

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

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

У початковому стані цієї головоломки всі диски будуть складені в один стрижень.
Остаточним станом є те, що всі ці диски зі стрижня один будуть укладені на стрижень два або стрижень три.
Ми можемо перемістити диск з одного стержня на інший у будь-який момент часу.
Ми можемо лише відсунути верхній диск від стрижня.
Диск не може бути розміщений поверх іншого диска, який є меншим.

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

На цій стадії:

Джерело = Peg A
Пункт призначення = Peg C
Помічник = Peg 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

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