Türme von Hanoi - Rekursive Algorithmen
| abgelegt unter: Flash-Beispiele, ActionScript 3Dieses Problem geht auf eine alte Sage zurück: Tief im Dschungel, im Verborgenen, sind seit Anbeginn der Zeit Mönche damit beschäftigt, einen Turm aus fünfzig goldenen übereinander gestapelten Scheiben, die von oben nach unten im Durchmesser zunehmen, von einer goldenen Stange auf eine andere goldene Stange umzuschichten. Dabei dürfen sie eine dritte Stange zur Hilfe nehmen; nur müssen Sie darauf achten, dass niemals eine grössere Scheibe auf einer kleineren zu liegen kommt. Wenn die Mönche den Turm komplett umgeschichtet haben, so die Sage, dann ist das Ende der Welt gekommen.
Die "Türme von Hanoi" sind das Standardbeispiel bei der Einführung rekursiver Algorithmen. Es ist verblüffend, mit wie wenigen Zeilen Programm-Code sich diese Problematik bewältigen lässt, wenn man sie rekursiv löst, also durch sukzessive Reduktion des Gesamtproblems "verschiebe 6 Scheiben von der linken Stange unter Zuhilfenahme der mittleren Stange auf die rechte Stange" auf das einfachst mögliche Problem "verschiebe 1 Scheibe von der linken Stange unter Zuhilfenahme der mittleren Stange auf die rechte Stange".
var n:uint=6;
function erzeugeDemoProgramm(n:uint,a:String="StangeLinks",m::String="StangeMitte",e:String="StangeRechts"):void
{
if(n==1){
trace("Verschiebe Scheibe von "+a+" nach " +e);
}
else{
//alle zu oberst liegende Scheiben von der linken Stange auf die mittlere Stange schieben
erzeugeDemoProgramm(n-1,a,e,m);
trace("Verschiebe Scheibe von "+a+" nach " +e);
//alle Scheiben von der mittleren Stange auf die rechte Stange schieben
erzeugeDemoProgramm(n-1,m,a,e);
};
}
Die Funktion "erzeugeDemoProgramm", das Herzstück des Beispielprogramms "Türme von Hanoi", liefert eine Liste der Zugfolge zur Lösung des Problems. Den Regeln gemäss kann stets nur die oberste Scheibe verschoben werden, so dass die erzeugte Liste entsprechend zu verstehen ist.
Es ist deutlich zu erkennen, dass die Funktion zweimal sich selbst aufruft; und deshalb der Name: "Rekursive Funktion". Jeder Aufruf erzeugt dabei eine um 1 erhöhte Verschachtelungstiefe, wobei gleichzeitig die Anzahl n der übereinander gestapelten Scheiben auf Stange a um 1 erniedrigt wird. Bei n==1 wird schliesslich die letzte Scheibe von Stange a auf die Stange e, das Ziel der jeweiligen Rekursionsebene, verschoben.
Die rekursive Denkweise stellt höhere Ansprüche an das Vorstellungsvermögen, als die iterative Denkweise, belohnt jedoch i.d.R. mit extrem reduzierter Programm-Code-Menge. Da sich jede rekursive Lösung auch in eine iterative Lösung überführen lässt, mag der Leser den oben angegebenen Programmausschnitt entsprechend umformulieren und das Resultat mit dem rekursiven Algorithmus vergleichen.
