Rekurzíó - Hanoi tornyai

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:

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.

Megoldás

Számozni fogjuk a rudakat (1, 2, 3) és írunk egy rekurzív függvényt, aminek paramétere az is, hogy mely rudak között kell mozgasson.

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

#include <iostream>
using namespace std;

void 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()
{
    int n;
    cout << "n = ";
    cin >> n;

    hanoi(n,  1, 3, 2);

    return 0;
}

+ pontért:

Módosítjuk a feladatot:

Adott még egy rúdpár (pl. 1,3) és a párban szereplő rudak között nem szabad közvetlenül átmozgatni korongot.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include <iostream>
using namespace std;

void hanoi(int n, int honnan, int hova, int seged, int a, int b)
{
    if (n == 1) {
        if((honnan == a && hova == b) || (honnan == b && hova == a)){
            cout << honnan << " -> " << seged << endl;
            cout << seged << " -> " << hova << endl;
        }
        else{
            cout << honnan << " -> " << hova << endl;
        }
    }
    else {
        if((honnan == a && hova == b) || (honnan == b && hova == a)){
            hanoi(n-1, honnan, hova, seged, a, b);
            cout << honnan << " -> " << seged << endl;
            hanoi(n-1, hova, honnan, seged, a, b);
            cout << seged << " -> " << hova << endl;
            hanoi(n-1, honnan, hova, seged, a, b);
        }
        else{
            hanoi(n-1, honnan, seged, hova, a, b);
            cout << honnan << " -> " << hova << endl;
            hanoi(n-1, seged, hova, honnan, a, b);
        }
    }
}


int main()
{
    int n, a, b;
    cout << "n = ";
    cin >> n;
    cout << "a rudpar: ";
    cin >> a >> b;

    hanoi(n,  1, 3, 2, a, b);

    return 0;
}