Алгоритъм на Ханойската кула: Python, C++ код

Какво представлява кулата на Ханой?

Ханойската кула е математически пъзел, състоящ се от три пръта и множество дискове, поставени един върху друг. Известен е още като Кулата на Брама или кулата на Лукас, както я представя френският математик Едуард Лукас през 1883 г. Този пъзел се основава на легенди за преместване на златни дискове между три пръта.

Този пъзел има три пръчки и променлив брой подредени дискове. Тези пръчки са проектирани като циклични кули. Така че дисковете с по-голям диаметър са подредени отдолу, а дисковете с по-малък диаметър са подредени отгоре.

Първоначално ни се дават три колчета или пръти. И един от тях (A, показан в примера) има всички дискове подредени. Имаме за цел да преместим цял куп дискове от един прът (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 дискове от помощното колче към целевото колче.

Забележка: Ако имаме един диск, можем директно да го преместим от източника към местоназначението.

Как да решите пъзела на Ханойската кула

Нека да илюстрираме алгоритъма за три диска и да разгледаме peg A като източник, peg B като помощник и peg C като дестинация

Стъпка 1) Първоначално всички дискове ще бъдат подредени върху колче A.

На този етап:

Източник = Peg A
Дестинация = Peg C
Помощник = Peg B

Сега трябва да преместим горните n-1 диска от източника към помощника.

Забележка: Въпреки че можем да преместваме само един диск наведнъж, това пречупва нашия проблем от проблем с 3 диска на проблем с 2 диска, което е рекурсивно извикване.

Стъпка 2) Тъй като извикваме рекурсивно повикване от peg A и дестинацията е peg B, ще използваме peg C като помощник.

Забележете, че отново сме на етап едно за същия проблем с кулата на Ханой за два диска.

Сега трябва да преместим n-1 или един диск от източник към помощник, като преместим най-малкия диск от кол A към C.

На този етап:

Източник = кол A
Дестинация = колче B
Помощник = колче C

Стъпка 3) След това, според нашия алгоритъм, необходимият n-ти или 2-ри диск трябва да бъде прехвърлен в дестинацията или peg B.

На този етап:

Източник = кол A
Дестинация = колче B
Помощник = колче C

Стъпка 4) Сега ще преместим n-1 диска или диск едно от помощния или кол C до дестинацията или peg B според третия етап на нашия алгоритъм.

На този етап:

Източник = кол A
Дестинация = колче B
Помощник = колче C

Стъпка 5) След завършване на рекурсивното повикване, ние ще се върнем към предишната си настройка, когато първият етап от алгоритъма.

Стъпка 6) Сега, във втория етап, ще преместим нашия източник до нашата дестинация, която е преместване на диск 3 към кол С от кол А.

На този етап:

Източник = кол A
Дестинация = колче C
Помощник = колче B

Стъпка 7) Сега можем да видим това

d е да преместите оставащите дискове от помощния (колон B) до дестинацията (колан C). Ще използваме първоначалния източник или peg A като помощник в този случай.

Стъпка 8) Тъй като не можем да преместим два диска едновременно, ще извикаме рекурсивно повикване за диск 1. Според последната стъпка и нашата алгоритъм, дестинация в тази стъпка е кол A.

На този етап:

Източник = peg B
Дестинация = колче A
Помощник = колче C

Стъпка 9) Нашето рекурсивно повикване вече е завършено. След това преместваме диск 2 от неговия източник до местоназначението му.

На този етап:

Източник = peg 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

Сложност на Ханойската кула

Регистрирайте се за бюлетина