Hanoi tornyai

A Programozás Wiki wikiből

Egy egyszerű matematikai feladvány. A lényege, hogy van három rúd. Az elsőre rá van téve tetszőleges számú, különböző méretű korong, méret szerint rendezve, úgy hogy a legnagyobb van legalul. Feladat, hogy az összes korongot átrakjuk egy másik rúdra úgy, hogy egyszerre csak egyet mozgathatunk, és egy korong sem helyezhető nála kisebb korongra.

A feladatot jellemzően rekurzív algoritmussal oldják meg:

Hanoi(n,I,J,K) n számú korongot átrak az I rúdról a J-re, a K rúd felhasználásával.

Hanoi(n, I, J, K)
    if not n = 0
        Hanoi(n-1, I, K, J)
        Atrak(I,J)
        Hanoi(n-1, K, J, I)
    end if
end Hanoi

Az Atrak(A,B) eljárás az A rúdról áttesz egyetlen korongot a B rúdra.

Az algoritmus futásideje: Θ(2^n)

A nem-rekurzív megoldás alapgondolata az, hogy minden páratlan lépésben a legkisebb korong mozog, a maradék felében a második legkisebb, és így tovább; továbbá az egyes korongok mozgásának iránya is szabályosan váltakozik: 1->3, 3->2, 2->1 vagy 1->2, 2->3, 3->1.

static void Move (long long step, int n, int from, int to, int spare)
{
   long long s;
   int korong;
   int dir;
   int mfrom, mto;

   for (s=step, korong=1; s%2==0; ++korong) s/=2;
   dir= s%6;
   if ((n-korong)%2==0) {
       if      (dir==1) mfrom= from,  mto= to;
       else if (dir==3) mfrom= to,    mto= spare;
       else if (dir==5) mfrom= spare, mto= from;

   } else {
       if      (dir==1) mfrom= from,  mto= spare;
       else if (dir==3) mfrom= spare, mto= to;
       else if (dir==5) mfrom= to,    mto= from;
   }
   printf ("%lld korong #%d: %d->%d\n", step, korong, mfrom, mto);
}

static void Hanoi (int n, int from, int to, int spare)
{
   long long nstep, step;

   nstep= (1LL << n) - 1;

   for (step=1; step<=nstep; ++step) {
       Move (step, n, from, to, spare);
   }
}

Megvalósítása különböző nyelveken[szerkesztés]

Go[szerkesztés]

A rudakat int típusú változók fogják jelölni. Értékük a rajtuk lévő korongok száma. Ezen algoritmus implementációban azért nem kell foglalkozni a korongok méretével, mert a feladat ezen kitételét az algoritmus teljes körűen kezeli. A példában a rudak állapota indulásnál: I:10, J:0, K:0, és J rúdra fogjuk átpakolni a korongokat.

package main
import "fmt"

func Hanoi(n int, I, J, K *int) {
        if n != 0 {
                Hanoi(n-1, I, K, J)
                Atrak(I,J)
                fmt.Printf("%d\t%d\t%d\n",*I,*J,*K)    // minden áthelyezés után kiírjuk, hogy melyik tornyon hány korong található
                Hanoi(n-1, K, J, I)
        }
}

func Atrak(a, b *int) {
        *a--
        *b++
}

func main() {
        fmt.Println("I\tJ\tK\t")
        I := 10
        J,K := 0,0
        Hanoi(I,&I,&J,&K)
}


Haskell[szerkesztés]

Hasonlóan Go példához, a rudakat itt is egy szám típusú "változó" fogja jelölni. Ami lényeges eltérés az előbbihez (és minden imperatív nyelvben tapasztalthoz) képest, hogy Haskellben nincs általános értelemben vett állapottér (így változó sem). Ezért az algoritmus működése kicsit eltérő. A rudakon lévő korongok számának módosítása nem egy kijelölt memóriaterületen fog történni, hanem a hanoi függvény adja vissza az új állapotot.

Mivel tankönyvi leírás szerint nem csak állapottér nem létezik egy tisztán funkcionális nyelvben, hanem szekvencia sem, a szekvencia-szerű végrehajtásra értékhivatkozásokkal fogjuk rávenni a programot:

hanoi :: Num a=> a -> (a,a,a) -> (a,a,a)
hanoi n (i,j,k)         = if n /= 0 then (ri,rj,rk) else (i,j,k)
        where
        (i'',j'')       = atrak(i',j')
        (i',k',j')      = hanoi (n-1) (i,k,j)
        (rk,rj,ri)      = hanoi (n-1) (k',j'',i'')


atrak :: Num a=> (a,a) -> (a,a)
atrak (a,b)     = (a-1,b+1)

-- A rekurziót, I:10, J:0, K:0 esetén így kell indítani:
-- hanoi 10 (10,0,0)
-- Eredménye pedig, egy rendezett hármas lesz:
-- (0,10,0)