Hanoin torni
Hanoin torni-nimellä tunnettuun lautapeliin kuuluu kahdeksan erikokoista kiekkoa, joissa
kaikissa on reikä keskellä sekä lauta, johon on kiinnitetty kolme tappia. Aluksi kiekot ovat
yhdessä tapissa järjestettyinä koon mukaan siten, että niistä muodostuu kartio. Suurin
kiekko on alimmaisena.
Pelissä kartio pitää siirtää toiseen tappiin samanlaiseksi kartioksi. Vain yhden kiekon saa
siirtää kerrallaan. Pienemmän kiekon päälle ei saa koskaan panna isompaa
kiekkoa. Kuinka monta siirtoa pitää tehdä, jotta kartio saadaan rakennettua toiseen
tappiin?
Vihje 1
Mieti ensin tapaukset, joissa kiekkoja on vain 1, 2 ja 3. Kun kiekkoja on neljä,
pitää kolme ylimmäistä kiekkoa siirtää ensin, jotta neljäs kiekko voidaan siirtää. Tämän
jälkeen kolme kiekkoa on vielä siirrettävä neljännen päälle.
Laske n + 1 kiekon siirtämiseen tarvittavien siirtojen määrä, kun n kiekon siirtämiseen
tarvittavien siirtojen määrä tiedetään.
Vihje 2
Kun kiekkoja on (n + 1) kappaletta, voidaan alimmaista siirtää vasta, kun
n ylimmäistä on siirretty. Näiden n ylimmäisen kiekon siirtämiseen tarvitaan
s(n) siirtoa. Vasta tämän jälkeen voidaan siirtää (n + 1). kiekko. Muut kiekot
on vielä siirrettävä suurimman kiekon päälle eli tarvitaan vielä s(n) siirtoa.
Vihje 3
Määrittele s(n + 1) funktion s(n) avulla. Laske tämän rekursiivisen
yhtälön avulla s(8), kun tiedetään, että s(1) = 1. Voit myös määritellä s(n):lle
eksplisiittisen lausekkeen ja laskea s(8).