MÁRTON Gyöngyvér

Vissza

Labor 3, haladóknak

Hanoi tornyai

Adott három rúd, jelöljük őket a, b, c-vel. Az a rúdra különböző átmérőjű korongok vannak felhúzva, méretük szerint csökkenő sorrendben, legalul a legnagyobb átmérőjű korong. Írjunk programot, mely megadja a korongok áthelyezési sorrendjét az a rúdról a c rúdra figyelembe véve a következő szabályokat:

egy lépésben egy korongot lehet elmozdítani
kisebb korongra nem helyezhető nagyobb korong.

Oldjuk meg a feladatot rekurzívan és adjunk egy iteratív megoldást is, majd hasonlítsuk össze a két algoritmus időigényét, táblázatban feltüntetve a különböző számú korongokra mért időigényt, másodpercben.

Példa időmérésre:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define M 70000000

int main(){
    clock_t start, finish;
    int i;
    start = clock();
    for(i=0; i<M; ++i);
    finish = clock();
    printf("ido: %f\n\n", (float)(finish - start)/CLOCKS_PER_SEC);
    system("pause");
    return 0;
}

Rekurzív megoldás:
n korong áthelyezése az a rúdról a c rúdra, a b segítségével visszavezethető a következő lépésekre:

n-1 korong áthelyezése az a rúdról a b rúdra, a c segítségével
az a rúdon maradt legnagyobb korongot a c rúdra helyezzük
n-1 korong áthelyezése az b rúdról a c rúdra, az a segítségével

Iteratív megoldás:
1..2ⁿ-1 lépésben vizsgáljuk a következőket:

meghatározzuk, hogy melyik rúdon levő koronggal lépünk:

ha a páros lépés számnál tartunk, akkor arról a rúdról lépünk ahol az abszolút legkisebb korong van
másképp arról a rúdról lépünk, ahol az a legkisebb korong van, mely ugyanakkor nincs egy rúdon az abszolút legkisebb koronggal

meghatározzuk, hogy melyik rúdra lépünk:

ha páros sorszámú korongnál tartunk "előre" lépünk
másképp "hátra" lépünk

5 korongra az első pár lépés a következő, szükség lesz egy 5 elemű poz tömbre.
Legyen 5 korongunk, akkor:
a poz tömb, kezdetben: poz = [0, 0, 0, 0, 0]. Ez azt jelenti, hogy
    a 0-ás korong (a legnagyobb) a 0-ás rúdon,
    az 1-es korong az 0-ás rúdon,
    a 2-es korong a 0-ás rúdon van.
    a 3-as korong (a legkisebb) a 0-ás rúdon van,
    a 4-es korong (az abszolút legkisebb) is a 0-ás rúdon van.

0. lépés (páros):
honnan: a poz[4]-el lépünk (az abszolút-legkisebbel)
hova: előre lépünk egyet, mert 4 páros:   p[4] = (p[4] + 1) % 3;
    0 -> 1
    poz = [0, 0, 0, 0, 1], ez azt jelenti, hogy:
    a 0-ás korong a 0-ás rúdon,
    az 1-es korong az 0-ás rúdon,
    a 2-es korong a 0-ás rúdon van.
    a 3-as korong (a legkisebb) is a 0-ás rúdon van,
    a 4-es korong (az abszolút legkisebb) az 1-es rúdon van,

1. lépés:
honnan: a poz[3]-al lépünk (a legkisebbel)
hova: hátra lépünk egyet, mert 3 páratlan:   p[3] = (p[3] + 2) % 3;
    0 -> 2
    poz = [0, 0, 0, 2, 1], ez azt jelenti, hogy:
    a 0-ás korong a 0-ás rúdon,
    az 1-es korong az 0-ás rúdon,
    a 2-es korong a 0-ás rúdon van.
    a 3-as korong (a legkisebb) is a 2-es rúdon van,
    a 4-es korong (az abszolút legkisebb) az 1-es rúdon van,

2. lépés
honnan: a poz[4]-el lépünk (az abszolút-legkisebbel)
hova: előre lépünk egyet, mert 4 páros:   p[4] = (p[4] + 1) % 3;
    1 -> 2
    poz = [0, 0, 0, 2, 2]

3. lépés
honnan: a poz[2]-el lépünk (a legkisebbel)
hova: előre lépünk egyet, mert 2 páros:   p[2] = (p[2] + 1) % 3;
    0 -> 1
    poz = [0, 0, 1, 2, 2]

4. lépés
honnan: a poz[4]-el lépünk (az abszolút-legkisebbel)
hova: előre lépünk egyet, mert 4 páros:   p[4] = (p[4] + 1) % 3;
    2 -> 0
    poz = [0, 0, 1, 2, 0]

5. lépés
honnan: a poz[3]-el lépünk (a legkisebbel)
hova: hátra lépünk egyet, mert 3 páratlan:   p[3] = (p[3] + 2) % 3;
    2 -> 1
    poz = [0, 0, 1, 1, 0]