Türme von Hanoi < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:50 Fr 16.04.2010 | | Autor: | matheja |
| Aufgabe | Hallo Leute, ich beschäftige mich grad mit den Türmen von Harnoi und ich hab das Prinzip auch verstanden.
Nur ich hab trotzdem Probleme bei dieser Aufgabe einen Anfang zu finden:
Aufgabe:
Zeichnen Sie den gesamten Programmstack jeweils an der mit Start von rekhanoi bezeichneten Programmstelle. Verwenden Sie zur Bezeichnung der Rückkehrpunkte die im unteren Programm angegebenen Kommentare.
Java Code:
public static void rekhanoi(int start, int ziel, int hilf, int hoehe){
/* Start von rekhanoi */
if (hoehe>0) {
rekhanoi(start, hilf, ziel, hoehe-1) /* nach 1. Rekursion */;
zug(start, ziel);
rekhanoi(hilf, ziel, start, hoehe-1) /* nach 2. Rekursion */;
}
}
public static void main(String[] args){
rekhanoi(1,2,3,2) /* nach Aufruf in main */;
} |
Ich schreib erstmal ein bisschen was zum Prinzip:
siehe link -> http://www.saar.de/~awa/jrekursion.htm
Ich hab das Prinzip verstanden es hapert jedoch daran das ich das obige Programm nicht wirklich umsetzen kann
Ich versuch mal zu visualsieren wie ich mir das vorstelle:
Dabei sein --- die stacks
_________ ___________ ____________
Start Ziel Hilf
Wie sehen diese am Start von Rekanoi aus
---
------- => Die sei ein Turm mit drei Stacks der höhe drei :)
-----------
________
Start
In der Main methode steht ja:
rekhanoi(1,2,3,2) /* nach Aufruf in main
geh ich dann recht der annahme das start=1; ziel=2; hilf=3; höhe=2
Was hab ich mir darunter vorzustellen ist der Start=1
--------- => ein Stack ?
________
start
Es wär toll wenn ihr mir helfen könnt
beste grüße
matheja
|
|
| |
|
Hallo matheja,
> Zeichnen Sie den gesamten Programmstack jeweils an der mit
> Start von rekhanoi bezeichneten Programmstelle. Verwenden
> Sie zur Bezeichnung der Rückkehrpunkte die im unteren
> Programm angegebenen Kommentare.
Da du die Methode zug() nicht weiter beschrieben hast, bin ich im weiteren davon ausgegangen, daß sie für die Rekursion selbst nicht weiter relevant ist. Unter dieser Annahme kann man dein Programm so modifizieren, daß es dir deine Aufgabe von selbst löst. Dazu platziert man im Programm an den benötigten Stellen println()-Anweisungen. Um an die Stacktiefe zu kommen, erweitert man den Funktionskopf von rekhanoi() um den Parameter rekursionstiefe, den man bei weiteren Aufrufen von rekhanoi() übergibt und dabei um 1 erhöht:
| 1: | import java.io.FileNotFoundException;
| | 2: | import java.io.FileOutputStream;
| | 3: | import java.io.PrintWriter;
| | 4: |
| | 5: | public class HanoiTest {
| | 6: |
| | 7: | private static PrintWriter logstack;
| | 8: |
| | 9: | private static void rekhanoi(int start, int ziel, int hilf, int hoehe, int rekursionstiefe) {
| | 10: | logstack.println("Start von rekhanoi: start: "+start+", ziel: "+ziel+", hilf: "+
| | 11: | hilf+", hoehe: "+hoehe+"; rekursionstiefe: "+rekursionstiefe);
| | 12: |
| | 13: | if (hoehe > 0) {
| | 14: | rekhanoi(start, hilf, ziel, hoehe - 1, rekursionstiefe+1);
| | 15: | logstack.println("nach 1. Rekursion");
| | 16: | logstack.println("´´´´´´´´´´´´´´´´´");
| | 17: | logstack.println("Start von rekhanoi: start: "+start+", ziel: "+ziel+", hilf: "+
| | 18: | hilf+", hoehe: "+hoehe+"; rekursionstiefe: "+rekursionstiefe);
| | 19: | logstack.println("'''''''''''''''''");
| | 20: |
| | 21: | rekhanoi(hilf, ziel, start, hoehe - 1, rekursionstiefe+1);
| | 22: | logstack.println("nach 2. Rekursion");
| | 23: | logstack.println("´´´´´´´´´´´´´´´´´");
| | 24: | logstack.println("Start von rekhanoi: start: "+start+", ziel: "+ziel+", hilf: "+
| | 25: | hilf+", hoehe: "+hoehe+"; rekursionstiefe: "+rekursionstiefe);
| | 26: | logstack.println("'''''''''''''''''");
| | 27: | }
| | 28: | }
| | 29: |
| | 30: | public static void main(String[] args) throws FileNotFoundException {
| | 31: | PrintWriter logstack_ = new PrintWriter(new FileOutputStream("stack_state.txt"));
| | 32: | logstack = logstack_;
| | 33: | rekhanoi(1, 2, 3, 2, 0) /* nach Aufruf in main */;
| | 34: | logstack_.close();
| | 35: | }
| | 36: | } |
und die Ausgabe lautet:
| 1: | Start von rekhanoi: start: 1, ziel: 2, hilf: 3, hoehe: 2; rekursionstiefe: 0
| | 2: | Start von rekhanoi: start: 1, ziel: 3, hilf: 2, hoehe: 1; rekursionstiefe: 1
| | 3: | Start von rekhanoi: start: 1, ziel: 2, hilf: 3, hoehe: 0; rekursionstiefe: 2
| | 4: | nach 1. Rekursion
| | 5: | ´´´´´´´´´´´´´´´´´
| | 6: | Start von rekhanoi: start: 1, ziel: 3, hilf: 2, hoehe: 1; rekursionstiefe: 1
| | 7: | '''''''''''''''''
| | 8: | Start von rekhanoi: start: 2, ziel: 3, hilf: 1, hoehe: 0; rekursionstiefe: 2
| | 9: | nach 2. Rekursion
| | 10: | ´´´´´´´´´´´´´´´´´
| | 11: | Start von rekhanoi: start: 1, ziel: 3, hilf: 2, hoehe: 1; rekursionstiefe: 1
| | 12: | '''''''''''''''''
| | 13: | nach 1. Rekursion
| | 14: | ´´´´´´´´´´´´´´´´´
| | 15: | Start von rekhanoi: start: 1, ziel: 2, hilf: 3, hoehe: 2; rekursionstiefe: 0
| | 16: | '''''''''''''''''
| | 17: | Start von rekhanoi: start: 3, ziel: 2, hilf: 1, hoehe: 1; rekursionstiefe: 1
| | 18: | Start von rekhanoi: start: 3, ziel: 1, hilf: 2, hoehe: 0; rekursionstiefe: 2
| | 19: | nach 1. Rekursion
| | 20: | ´´´´´´´´´´´´´´´´´
| | 21: | Start von rekhanoi: start: 3, ziel: 2, hilf: 1, hoehe: 1; rekursionstiefe: 1
| | 22: | '''''''''''''''''
| | 23: | Start von rekhanoi: start: 1, ziel: 2, hilf: 3, hoehe: 0; rekursionstiefe: 2
| | 24: | nach 2. Rekursion
| | 25: | ´´´´´´´´´´´´´´´´´
| | 26: | Start von rekhanoi: start: 3, ziel: 2, hilf: 1, hoehe: 1; rekursionstiefe: 1
| | 27: | '''''''''''''''''
| | 28: | nach 2. Rekursion
| | 29: | ´´´´´´´´´´´´´´´´´
| | 30: | Start von rekhanoi: start: 1, ziel: 2, hilf: 3, hoehe: 2; rekursionstiefe: 0
| | 31: | ''''''''''''''''' |
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 16:36 Mo 19.04.2010 | | Autor: | matheja |
| Aufgabe | Hi Karl,
danke für deine Superlösung :)
Ich denke, dass ich den Algorithmus prinzipiell verstanden habe
Ich versuch mir das Grad zu zeichnen aber so ganz blick ich da noch nicht durch.
Wie sieht der Pyramidenstack aus?
wir haben drei (Pyramiden)-Stacks (Start, hilfe Ziel)
So soll eine Pyramide mit drei scheiben aussehen
---
-------
-----------
|
Meine Frage ist nun
Wie sieht diese Pyramide für Start , Ziel, Hilfe und Höhe
1.Beim Start von rekanoi
2.Nach der 1.Rekursion
3.Nach der 2.Rekursion
Wieviel scheiben hat die Pyramide?
Ich versuch das grad nachdem Prinzip zu lösen:
Nehmen wir an wir haben eine Pyramide mit drei Scheiben
Start: Hilfe: Ziel:
---
-------
-----------
Um die Pyramide von Start zu Ziel zu transportieren brauchen wir minimal
[mm] 2^{n}-1 [/mm] züge - also 7
1.Zug:
Start: Hilfe: Ziel:
-------
----------- --
siehe: http://www.mathematik.ch/spiele/hanoi_mit_grafik/
beste grüße
danke für hilfe
matheja
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:20 Mi 21.04.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
