Gyakorlati alapok II.
Rekurzió
Hanoi tornyai
Hanoi tornyai egy érdekes elmejáték:
Adott 3 db rúd, a középső rúd csak segédeszközként szolgál ahhoz, hogy az egyik szélső rúdról a gúlába rakott korongokat átmozgassuk a másik szélső rúdra. Kikötések:
egyszerre csak 1 korong mozgatható,
átmozgatáskor nem lehet korong fölé a méreténél nagyobbat tenni.
Forrás - Source: Wikipédia
Ilyesféle feladvány zabolátlan matematikai megoldások özönét szokta indukálni. Programozási szempontból a Hanoi tornyai tipikus rekurziós művelet, mert műveleti megoldása kisebb, jól szegmentálható, iteráló egységekre bontható.
Nézzük meg 3 korongos, rekurzív megoldásának futtatható Java-kódját (Forrás - Source: https://www.tutorialspoint.com/javaexamples/method_tower.htm):
public class Main {
public static void rekurzio(int szam, String kezdoRud, String kozepsoRud,
String celRud) {
if (szam == 1) {
System.out.println("Korong 1 " + kezdoRud + "tól " + celRud +
"ig");
}
else {
rekurzio(szam - 1, kezdoRud, celRud, kozepsoRud);
System.out.println("Korong " + szam + " " + kezdoRud + "tól "
+ celRud + "ig");
rekurzio(szam - 1, kozepsoRud, kezdoRud, celRud);
}
}
public static void main(String[] args) {
int korongokSzama = 3;
rekurzio(korongokSzama, "kezdő rúd", "középső rúd",
"célrúd");
}
}
Végeredmény:
Korong 1 kezdő rúdtól célrúdig
Korong 2 kezdő rúdtól középső rúdig
Korong 1 célrúdtól középső rúdig
Korong 3 kezdő rúdtól célrúdig
Korong 1 középső rúdtól kezdő rúdig
Korong 2 középső rúdtól célrúdig
Korong 1 kezdő rúdtól célrúdig
Házi feladat - Írjuk át a rudak elnevezéseit A-B-C betűkre!
A megoldás fejezete a képre kattintva érhető el.
Pénzes László