A hanoi torony problémájának megoldása - illusztrált algoritmus útmutató

Programozás

Mielőtt elkezdenénk, beszéljünk arról, mi a Hanoi-torony problémája. Nos, ez egy szórakoztató kirakós játék, amelynek célja egy teljes lemezhalom áthelyezése a forrás helyéről egy másik helyre. Három egyszerű szabályt követünk:

  1. Egyszerre csak egy lemezt lehet mozgatni.
  2. Minden lépés abból áll, hogy a felső lemezt kiveszi az egyik rakatból, és egy másik verem tetejére helyezi. Más szavakkal, egy lemezt csak akkor lehet mozgatni, ha az a legfelső lemez a veremben.
  3. Nagyobb lemez nem helyezhető el egy kisebb lemez tetején.

Most próbáljunk elképzelni egy forgatókönyvet. Tegyük fel, hogy van egy halom három lemezünk. A mi feladatunk az, hogy ezt a verem az A forrásból a C célba kerüljön . Hogyan csináljuk ezt?

Mielőtt odaérnénk, képzeljük el, hogy van egy köztes B pont .

B-t használhatjuk segítőként ennek a munkának a befejezéséhez. Most már készen állunk a továbblépésre. Menjünk át az egyes lépéseken:

  1. Helyezze az első lemezt A-ból C-be
  2. Helyezze az első lemezt A-ból B-be
  3. Helyezze az első lemezt C-ről B-re
  4. Helyezze az első lemezt A-ból C-be
  5. Vigye az első lemezt B-ről A-ra
  6. Vigye az első lemezt B-ről C-re
  7. Helyezze az első lemezt A-ból C-be

Bumm! Megoldottuk a problémánkat.

A jobb megértés érdekében a fenti animációs képet láthatja.

Most próbáljuk meg felépíteni az algoritmust a probléma megoldására. Várjon, itt van egy új szavunk: „ Algoritmus ”. Mi az? Bármilyen ötlete? Semmi gond, nézzük meg.

Mi az algoritmus?

Az algoritmus az egyik legfontosabb fogalom egy szoftverfejlesztő számára. Valójában szerintem ez nemcsak a szoftverfejlesztés vagy a programozás szempontjából fontos, hanem mindenki számára. Az algoritmusok hatással vannak ránk a mindennapokban. Lássuk, hogyan.

Tegyük fel, hogy irodában dolgozik. Tehát minden reggel sorozatosan végez egy sor feladatot: először felébred, aztán elmegy a mosdóba, reggelizik, felkészül az irodára, elmegy otthonról, majd taxival vagy busszal indulhat, vagy elindulhat a irodába, és egy bizonyos idő után elérheti irodáját. Mondhatja, hogy ezek a lépések algoritmust alkotnak .

Egyszerűbben fogalmazva: az algoritmus feladatsor. Remélem, nem felejtette el azokat a lépéseket, amelyeket három lemezverem áthelyezéséről A-ról C-re tettünk. Azt is mondhatja, hogy ezek a lépések jelentik a Hanoi-torony problémájának megoldására szolgáló algoritmust.

A matematikában és az informatikában az algoritmus egyértelműen meghatározza, hogy miként lehet megoldani a feladatok osztályát. Az algoritmusok számítási, adatfeldolgozási és automatizált érvelési feladatokat hajthatnak végre. - Wikipédia

Ha megnézi ezeket a lépéseket, láthatja, hogy ugyanazt a feladatot többször is elvégeztük - lemezeket mozgattunk egyik veremből a másikba. Ezeket a lépéseket a rekurziónak nevezhetjük .

Rekurzió

Rekurzióugyanazon akciót hívja meg abból a cselekvésből. Akárcsak a fenti kép.

Tehát egy rekurzív munka elvégzésének egyetlen szabálya van: feltételnek kell lennie a művelet végrehajtásának leállítására. Remélem, megértette a rekurzió alapjait.

Most próbáljunk meg olyan eljárást létrehozni, amely segít megoldani a Hanoi-torony problémáját. Pszeudokód segítségével próbáljuk megépíteni a megoldást . Az álkód a számítógépes kód angol nyelvű kiírásának egyik módszere.

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

Ez a megoldás csontváza. Argumentumként a teljes lemezszámot vesszük. Ezután át kell adnunk a forrást, a köztes helyet és a célt, hogy megértsük a térképet, amelyet a munka elvégzéséhez használunk.

Most meg kell találnunk egy végállapotot . A terminál állapot az az állapot, ahol ezt a funkciót már nem fogjuk hívni.

IF disk is equal 1

Esetünkben ez lenne a végállapotunk. Mert amikor egy lemez lesz a veremben, akkor egyszerűen elvégezhetjük ezt az utolsó lépést, és ezt követően a feladatunk elvégzésre kerül. Ne aggódj, ha nem világos számodra. Amikor a végére érünk, ez a koncepció világosabb lesz.

Rendben, megtaláltuk a terminálállapotunkat, ahol a lemezt a következő helyre helyeztük:

move disk from source to destination

Ezeknek az érveknek a továbbadásával hívjuk újra a funkciónkat. Ebben az esetben a lemezek halmát két részre osztjuk. A legnagyobb lemez ( n-edik ) egy részben található, az összes többi ( n-1 ) lemez pedig a második részben található. Ott kétszer hívjuk meg a módszert - (n-1) -re.

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

Mint mondtuk, a total_disks_on_stack - 1 argumentumot adjuk át . És akkor ismét így mozgatjuk a lemezünket:

move disk from source to destination

Ezt követően ismét így hívjuk a módszerünket:

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

Lássuk a teljes álkódunkat:

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

Ez a fa három lemez számára:

Ez a Ruby teljes kódja:

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

Hívás tower(3, 'source','aux','dest')

Kimenet:

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

Hét lépés kellett ahhoz, hogy három lemez elérje a célt. Ezt rekurzív módszernek hívjuk .

Időkomplexum és térbonyolultság számítások

Az idő összetettsége

Amikor kódot vagy alkalmazást futtatunk a gépünkben, időbe telik - CPU-ciklusok. De ez nem minden számítógépen ugyanaz. Például az i7 mag és a kétmagos feldolgozási ideje nem azonos. Ennek a problémának a megoldására van egy, a számítástechnikában használt koncepció, az idő bonyolultsága .

Az idő bonyolultsága a számítástechnika olyan fogalma, amely a kód vagy algoritmus készletének feldolgozásához vagy futtatásához szükséges idő mennyiségének számszerűsítésével foglalkozik az input mennyiségének függvényében.

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. The Google course on Udacity
  4. Javascript Algorithms And Data Structures Certification (300 hours)

You can visit my data structures and algorithms repoto see my other problems solutions.

I am on GitHub | Twitter | LinkedIn