Kuidas lahendada Hanoi torni probleem - illustreeritud algoritmide juhend

Enne alustamist räägime sellest, mis on Hanoi torni probleem. Noh, see on lõbus mõistatusmäng, kus eesmärk on viia terve hunnik kettaid lähtepositsioonilt teisele. Järgitakse kolme lihtsat reeglit:

  1. Korraga saab liigutada ainult ühte ketast.
  2. Iga käik koosneb ülemise ketta võtmisest ühest korstnast ja teise virna kohale asetamisest. Teisisõnu saab ketast teisaldada ainult siis, kui see on virna pealmine ketas.
  3. Väiksema ketta peale ei tohi panna suuremat ketast.

Proovime nüüd stsenaariumi ette kujutada. Oletame, et meil on virn kolmest kettast. Meie ülesanne on liigutada virn allika et sihtkoha C . Kuidas me seda teeme?

Enne kui me saame sinna, olgem kujutada seal on vahe punkti B .

Selle töö lõpetamiseks saame kasutada abistajat B. Nüüd oleme valmis edasi liikuma. Vaatame läbi kõik etapid:

  1. Teisaldage esimene ketas A-lt C-le
  2. Teisaldage esimene ketas A-lt B-le
  3. Teisaldage esimene ketas C-lt B-le
  4. Teisaldage esimene ketas A-lt C-le
  5. Teisaldage esimene ketas B-lt A-le
  6. Teisaldage esimene ketas B-lt C-le
  7. Teisaldage esimene ketas A-lt C-le

Boom! Oleme oma probleemi lahendanud.

Parema mõistmise huvides näete ülaltoodud animeeritud pilti.

Proovime nüüd probleemi lahendamiseks luua algoritmi. Oota, meil on siin uus sõna: “ Algoritm ”. Mis see on? Kas teil on mõni idee? Pole probleemi, vaatame.

Mis on algoritm?

Algoritm on tarkvaraarendaja jaoks üks olulisemaid mõisteid. Tegelikult arvan, et see pole oluline mitte ainult tarkvaraarenduse või programmeerimise jaoks, vaid kõigile. Algoritmid mõjutavad meid meie igapäevaelus. Vaatame kuidas.

Oletame, et töötate kontoris. Nii et teete igal hommikul järjestikku mitu ülesannet: kõigepealt ärkate, siis lähete pesuruumi, sööte hommikusööki, valmistute kontoriks ette, lahkute kodust, siis võite võtta takso või bussi või hakata kõndima kontorisse ja teatud aja möödudes jõuate oma kontorisse. Võite öelda, et kõik need sammud moodustavad algoritmi .

Lihtsamalt öeldes on algoritm ülesannete kogum. Loodan, et te pole unustanud neid samme, mida tegime kolme kettahunniku teisaldamiseks A-st C. Võite ka öelda, et need sammud on Hanoi torni probleemi lahendamise algoritm.

Matemaatikas ja arvutiteaduses on algoritm ühemõtteline spetsifikatsioon selle kohta, kuidas lahendada klassi probleem. Algoritmidega saab täita arvutus-, andmetöötlus- ja automatiseeritud arutlusülesandeid. - Vikipeedia

Kui vaatate neid samme, näete, et tegime sama ülesannet mitu korda - liigutasime kettaid ühest virnast teise. Neid samme sees olevaid samme võime nimetada rekursiooniks .

Rekursioon

Rekursioonkutsub sama tegevust sellest tegevusest. Täpselt nagu ülaltoodud pilt.

Seega on rekursiivse töö tegemisel üks reegel: selle toimingu täitmise peatamiseks peab olema tingimus. Loodan, et saate rekursiooni põhitõdedest aru.

Proovime nüüd luua protseduuri, mis aitab meil lahendada Hanoi torni probleem. Püüame lahendust üles ehitada pseudokoodi abil . Pseudokood on meetod arvutikoodi välja kirjutamiseks inglise keeles.

tower(disk, source, intermediate, destination) { }

See on meie lahenduse skelett. Võtame argumendina ketaste koguarvu. Siis peame läbima allika, vahekoha ja sihtkoha, et saaksime aru kaardist, mida kasutame töö lõpetamiseks.

Nüüd peame leidma terminali oleku . Terminal on riik, kus me ei hakka seda funktsiooni enam nimetama.

IF disk is equal 1

Meie puhul oleks see meie lõppseisund. Sest kui meie korstnas on üks ketas, on seda viimast sammu lihtsalt teha ja pärast seda on meie ülesanne täidetud. Ärge muretsege, kui see pole teile selge. Kui jõuame lõpuni, on see mõiste selgem.

Hästi, oleme leidnud oma terminali olekupunkti, kus liigutame oma ketta sihtkohta järgmiselt:

move disk from source to destination

Nüüd nimetame need argumendid edasi oma funktsiooniks. Sel juhul jagame kettade virna kaheks osaks. Suurim ketas ( n-s ketas) on ühes osas ja kõik ülejäänud ( n-1 ) kettad teises osas. Seal kutsume meetodit kaks korda - (n-1).

tower(disk - 1, source, destination, intermediate)

Nagu me ütlesime, edastame argumendina total_disks_on_stack - 1 . Ja siis jälle liigutame oma ketast nii:

move disk from source to destination

Pärast seda nimetame oma meetodit uuesti järgmiselt:

tower(disk - 1, intermediate, source, destination)

Vaatame oma täielikku pseudokoodi:

tower(disk, source, inter, dest) IF disk is equal 1, THEN move disk from source to destination ELSE tower(disk - 1, source, destination, intermediate) // Step 1 move disk from source to destination // Step 2 tower(disk - 1, intermediate, source, destination) // Step 3 END IF END

See on kolme ketta puu:

See on rubiinis täielik kood:

def tower(disk_numbers, source, auxilary, destination) if disk_numbers == 1 puts "#{source} -> #{destination}" return end tower(disk_numbers - 1, source, destination, auxilary) puts "#{source} -> #{destination}" tower(disk_numbers - 1, auxilary, source, destination) nil end

Helistama tower(3, 'source','aux','dest')

Väljund:

source -> dest source -> aux dest -> aux source -> dest aux -> source aux -> dest source -> dest

Kolme ketta sihtkohta jõudmiseks kulus seitse sammu. Nimetame seda rekursiivseks meetodiks .

Aja keerukuse ja ruumi keerukuse arvutused

Aja keerukus

Kui käivitame oma masinas koodi või rakenduse, võtab see aega - protsessori tsüklid. Kuid see pole iga arvuti puhul sama. Näiteks pole tuuma i7 ja kahetuumalise töötlemise aeg sama. Selle probleemi lahendamiseks on arvutiteaduses kasutatud mõistet, mida nimetatakse aja keerukuseks .

Aja keerukus on arvutiteaduse mõiste, mis käsitleb koodi või algoritmi töötlemiseks või töötamiseks kuluva aja hulga kvantifitseerimist sisendi hulga funktsioonina.

In other words, time complexity is essentially efficiency, or how long a program function takes to process a given input. — techopedia

The time complexity of algorithms is most commonly expressed using big O notation. It’s an asymptotic notation to represent the time complexity.

Now, the time required to move n disks is T(n). There are two recursive calls for (n-1). There is one constant time operation to move a disk from source to the destination, let this be m1. Therefore:

T(n) = 2T(n-1) + m1 ..... eq(1)

And

T(0) = m2, a constant ...... eq(2) From eq (1) T(1) = 2T(1-1) + m1 = 2T(0)+m1 = 2m2 + m1 ..... eq(3) [From eq 2] T(2) = 2T(2-1) + m1 = 2T(1) + m1 = 4m2 + 2m1 + m1 .... eq(4) [From eq(3)] T(3) = 2T(3-1) + m1 = 2T(2) + m1 = 8m2 + 4m1 + 2m1 + m1 [From eq(4)]

From these patterns — eq(2) to the last one — we can say that the time complexity of this algorithm is O(2^n) or O(a^n) where a is a constant greater than 1. So it has exponential time complexity. For the single increase in problem size, the time required is double the previous one. This is computationally very expensive. Most of the recursive programs take exponential time, and that is why it is very hard to write them iteratively.

Space complexity

After the explanation of time complexity analysis, I think you can guess now what this is…This is the calculation of space required in ram for running a code or application.

In our case, the space for the parameter for each call is independent of n,meaning it is constant. Let it be J. When we do the second recursive call, the first one is over. That means that we can reuse the space after finishing the first one. Hence:

T(n) = T(n-1) + k .... eq(1) T(0) = k, [constant] .... eq(2) T(1) = T(1-1) + k = T(0) + k = 2K T(2) = 3k T(3) = 4k

So the space complexity is O(n).

After these analyses, we can see that time complexity of this algorithm is exponential but space complexity is linear.

Conclusion

From this article, I hope you can now understand the Tower of Hanoi puzzle and how to solve it. Also, I tried to give you some basic understanding about algorithms, their importance, recursion, pseudocode, time complexity, and space complexity. If you want to learn these topics in detail, here are some well-known online courses links:

  1. Algorithms, Part I
  2. Algorithms, Part II
  3. Google'i kursus Udacity kohta
  4. Javascripti algoritmide ja andmestruktuuride sertifitseerimine (300 tundi)

Võite külastada minu andmestruktuure ja algoritmeminu muude probleemide lahenduste nägemiseks.

Olen GitHubi | Twitter | LinkedIn