Hanoin torni -algoritmi: Python, C++ Koodi

Mikä on Hanoin torni?

Hanoin torni on matemaattinen palapeli, joka koostuu kolmesta sauvasta ja lukuisista toistensa päälle asetettuista kiekoista. Se tunnetaan myös nimellä Brahman torni tai Lucas-torni, kuten ranskalainen matemaatikko Edouard Lucas esitteli sen vuonna 1883. Tämä palapeli perustuu legendoihin kultaisten kiekkojen siirtämisestä kolmen sauvan välillä.

Tässä palapelissä on kolme sauvaa ja vaihteleva määrä pinottuja kiekkoja. Nämä sauvat on suunniteltu syklisiksi torneiksi. Joten halkaisijaltaan suuremmat levyt pinotaan pohjalle ja pienemmät levyt päälle.

Aluksi meille annetaan kolme tappia tai sauvaa. Ja yhdessä niistä (A, esimerkki esimerkissä) on kaikki levyt pinottu. Pyrimme siirtämään koko pinon levyjä yhdestä tangosta (A) toiseen (C) noudattamalla tiettyjä sääntöjä.

Tässä on palapelin alkuasetukset -

Ja tämä on viimeinen tavoite -

Hanoin tornin säännöt

Tässä on joitain tärkeitä sääntöjä Hanoin tornille:

• Tämän palapelin alkutila, kaikki levyt pinotaan sauvaan yksi.
• Lopullinen tila on, että kaikki tangon 1 levyt pinotaan tangon 2 tai kolme päälle.
• Voimme siirtää levyllä olevan tangon toiselle milloin tahansa.
• Voimme siirtää vain ylimmän kiekon tangosta.
• Levyä ei voi asettaa toisen levyn päälle, joka on pienempi.

Alkuperäinen legenda kertoi 64 levyn siirtämisestä. Papit saivat siirtää levyä kerrallaan sääntöjen mukaan. Legendan mukaan oli profetia, että maailma loppuisi, jos he voisivat suorittaa teon. Aikamonimutkaisuuden osiossa näytämme, että n levyn Tower of Hanoi -asetus maksaisi 2^n – 1 siirto.

Joten jos papit voisivat vaatia 1 sekunnin levyjen siirtämiseen, kokonaisaika, jonka he tarvitsisivat pulman ratkaisemiseen, olisi 2^64 – 1 sekunti tai 584,942,417,356 26 7 15 vuotta, XNUMX päivää, XNUMX tuntia ja XNUMX sekuntia.

Algoritmi Tower of Hanoin

Yksi yleinen tapa ratkaista Hanoin torni on rekursiivinen algoritmi. Ensin meidän on päätettävä kahdesta sauvasta tai tapista lähteeksi ja määränpääksi, ja varatappi olisi apu- tai apuväline.

Tässä on vaiheet Hanoin tornin ratkaisemiseksi:

• Siirrä ylimmät n-1-levyt lähdenastasta aputappiin.
• Siirrä sen jälkeen n:s levy lähdeliittimestä kohdeliittimeen.
• Siirrä lopuksi loput n-1 levyä apupuomista kohdetappiin.

Huomautuksia: Jos meillä on yksi levy, voimme siirtää sen suoraan lähteestä kohteeseen.

Kuinka ratkaista Tower of Hanoi -pulma

Havainnollistetaan kolmen levyn algoritmi ja pidetään tappia A lähteenä, tappia B apuna ja tappia C määränpäänä

Vaihe 1) Aluksi kaikki levyt pinotaan tappiin A.

Tässä vaiheessa:

Lähde = Peg A
Kohde = Peg C
Apulainen = Peg B

Nyt meidän on siirrettävä parhaat n-1 levyt lähteestä avustajalle.

Huomautus: Vaikka voimme siirtää vain yhtä levyä kerrallaan, se katkaisee ongelmamme kolmen levyn ongelmasta 3 levyn ongelmaan, joka on rekursiivinen kutsu.

Vaihe 2) Koska kutsumme rekursiivista kutsua liittimestä A ja määränpää on tappi B, käytämme liitintä C apuna.

Huomaa, että olemme jälleen vaiheessa yksi saman Hanoin tornin ongelman osalta kahdelle levylle.

Nyt meidän on siirrettävä n-1 tai yksi levy lähteestä avustajalle, siirtämällä pienin levy tapista A tappiin C.

Tässä vaiheessa:

Lähde = tappi A
Kohde = tappi B
Apulainen = tappi C

Vaihe 3) Sitten algoritmimme mukaan n. tai 2. levytarpeet tulee siirtää kohde- tai tappiin B.

Tässä vaiheessa:

Lähde = tappi A
Kohde = tappi B
Apulainen = tappi C

Vaihe 4) Nyt siirrämme n-1 levyä tai levyn ykköstä avustajasta tai tapista C määränpäähän tai tappiin B algoritmimme kolmannen vaiheen mukaisesti.

Tässä vaiheessa:

Lähde = tappi A
Kohde = tappi B
Apulainen = tappi C

Vaihe 5) Rekursiivisen kutsun suorittamisen jälkeen palaamme aiempaan asetuksemme, kun algoritmin ensimmäinen vaihe.

Vaihe 6) Nyt, toisessa vaiheessa, siirrämme lähteemme määränpäähämme, joka siirtää levyn 3 tappiin C tapista A.

Tässä vaiheessa:

Lähde = tappi A
Kohde = tappi C
Apulainen = tappi B

Vaihe 7) Nyt voimme nähdä sen

d on siirtää jäljellä olevat levyt avustajasta (liitin B) kohteeseen (liitin C). Käytämme tässä tapauksessa alkulähdettä tai tappia A apuna.

Vaihe 8) Koska emme voi siirtää kahta levyä samanaikaisesti, kutsumme levyn 1 rekursiivisen kutsun. Viimeisen vaiheen ja meidän algoritmi, määränpää tässä vaiheessa on tappi A.

Tässä vaiheessa:

Lähde = tappi B
Kohde = tappi A
Apulainen = tappi C

Vaihe 9) Rekursiivinen puhelumme on nyt valmis. Sitten siirrämme levyn 2 lähteestään määränpäähänsä.

Tässä vaiheessa:

Lähde = tappi B
Kohde = tappi C
Apulainen = tappi A

Vaihe 10) Sitten siirrämme jäljellä olevan n-1:n tai levyn 1 avustajasta määränpäähän.

Tässä vaiheessa:

Lähde = tappi A
Kohde = tappi C
Apulainen = tappi B

Hanoin tornin pseudokoodi

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

Ohjelmakoodi sisään 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;
}

ulostulo

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

Ohjelmakoodi sisään 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')

lähtö:

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

Hanoin tornin monimutkaisuus

Tässä on Hanoin tornin aika ja tila monimutkaisuus:

1) Aika monimutkaisuus:

Jos katsomme taaksepäin algoritmimme, voimme nähdä, että otamme käyttöön rekursiivisen kutsun (n-1) levyille kahdesti. Nämä rekursiiviset kutsut (n-1) levyille voidaan jakaa muihin ((n-1)-1) ja niin edelleen, kunnes saamme vain yhden levyn siirrettäväksi.

Kolmelle levylle -

• Levy 3 kutsuu rekursiivisen funktion levylle kaksi kahdesti.
• Disk 2 kutsuu rekursiivisen funktion levylle yksi kahdesti.
• Levy 1 voi liikkua vakioajan sisällä ja kolmen levyn ratkaisemisaika.

= 2*(Ratkaisuaika kahdelle levylle) + vakio Aika siirtää levy 3

= 2*(2*ratkaisuaika yhdelle levylle + vakio Aika siirtää levyä 2) + vakio Aika siirtää levyä 3

= (2*2) (vakio aika levyn 1 siirtoon) + 2*vakio aika levyn 2 siirtoon + vakio aika levyn 3 siirtoon

n levylle se voidaan kirjoittaa muodossa -

(2^n-1 * jatkuva aika siirtää levy 1 + 2^n-2 * jatkuva aika siirtää levy 2 + ….

Tämä geometrinen eteneminen johtaa O(2^n-1) Tai O (2ⁿ), joka on eksponentiaalinen.

2) Tilan monimutkaisuus

Hanoin tornin avaruuden monimutkaisuus on 0(n). Tämä johtuu siitä, että meidän on tallennettava levyjen järjestys. Kun käytämme rekursiota, se käyttää pinoa. Ja pinon enimmäiskoko voi olla "n". Siksi avaruuden kompleksisuudesta tulee O(n).