Feladat

Adott három rúd, ezekre felfűzve n korong az átmérők (szigorúan) csökkenő sorrendjében. Át kell jutattni a korongokat az elsőről a harmadik rúdra.

Szabályok:

1. Minden lépésben pontosan egy korongot mozgatunk egy rúdról egy másikra.
2. Minden rúdról csak a legfelsőt lehet levenni.
3. Sosem kerülhet nagyobb korong kisebbre.

Lásd még:

• https://hu.wikipedia.org/wiki/Hanoi_tornyai
• https://en.wikipedia.org/wiki/Tower_of_Hanoi
• https://www.mathsisfun.com/games/towerofhanoi.html

Megoldási ötlet: ahhoz, hogy a nagy korongot mozgatni lehessen, először az első (n-1)-et a segédrúdra kell tegyük (rekurzív hívással). Ez után jöhet a nagy korong mozgatása.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <iostream>
using namespace std;

int hanoi(int n, int honnan, int hova, int seged)
{
    if (n == 1)
        cout << honnan << " -> " << hova << endl;
    else {
        hanoi(n-1, honnan, seged, hova);

        cout << honnan << " -> " << hova << endl;

        hanoi(n-1, seged, hova, honnan);
    }
}


int main()
{
    hanoi(8, 1, 3, 2);
    return 0;
}

Pluszfeladatok:

1. Írjunk programot, mely adott n-re és adott lépéssorra (számpárok listája a fenti kimenetben szereplő nyilak nélkül) megmondja, hogy az helyesen megoldja-e a Hanoi tornyos feladatot n korongra (vagyis ellenőriz minden lépést, hogy megfelel-e a szabályoknak, illetve eljutunk-e a végállapotba)!
2. Írjunk programot, amely a szöveges konzolablakban szemlélteti adott n-re a megoldás lépéseit (rajz karakterekből, ASCII-art)!