Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Rekursion (Türme von Hanoi)
F34r0fTh3D4rk - Sa 07.05.05 15:50
Titel: Rekursion (Türme von Hanoi)
hallo, ich möchte gerne etwas mit Rekursion machen, weiß aber nicht was ?
Ich wollte des nämlich etwas üben, bevor ich wieder was größeres damit mache.
Die "Rekursiv"-Suche die keine war hab ich dann mal gelöscht :mrgreen:
GTA-Place - Sa 07.05.05 16:47
Wie Fear gerade festgestellt hat, braucht er gar keine Rekursion, da er ja die Schleife hat ^^
Damit wäre dieses Problem gelöst. :D
F34r0fTh3D4rk - Sa 07.05.05 16:47
jo ^^ man ich will aber was mit rekursion machen :D
GTA-Place - Sa 07.05.05 16:51
Dann programmier einen Routenplaner 8)
F34r0fTh3D4rk - Sa 07.05.05 16:57
nee lassma stecken, ich brauch was praktischeres (obwohl sone eigene stadt entwerfen und dafür nen routenplaner basteln, wäre geil) :wink:
alzaimar - So 08.05.05 09:33
Rekursion üben: Türme von Hanoi.
feuerwaran - So 08.05.05 09:42
Die Türme von Hanoi kann man auch iterativ lösen :oops:
alzaimar - So 08.05.05 12:03
Ach was (stand da nicht: "Rekursion üben:..."?)
Man kann *Alles* iterativ lösen, und Rekursion ist eigentlich überflüssig.
Aber die rekursive Lösung ist i.a. 'eleganter', weil sie direkt den Lösungsansatz implementiert. Hier ging es ums 'Üben', und die Türme von Hanoi sind (für mich) das schönste Beispiel für die Eleganz von Rekursion.
feuerwaran - So 08.05.05 12:12
jo :) Er könnte auch die Festplatte rekursiv durchsuchen oder sowas. Da hat er bestimmt auch seinen Spaß dran.
F34r0fTh3D4rk - So 08.05.05 13:44
die türme von hanoi kenn ich garnet, hab des sierpinski dreieck mal gemacht, die türme von hanoi, wo kann ich dazu was finden ? klingt interessant :roll:
Die letzte Tröte - So 08.05.05 13:47
Man kann alles Iterative Rekursiv lösen, aber nicht alles Rekursive Iterativ...oder versuch ma die Koch Kurve Iterativ auf die beine zu stellen :D
F34r0fTh3D4rk - So 08.05.05 13:53
man kann rekursion eigentlich doch so gut wie immer durch schleifen ersetzen oder nicht ? mich interessieren jetzt aber mal die türme von hanoi :idea:
EDIT: Man kann alles rekursive iterativ lösen, da es immer eine maximale anzahl von iterationen in einer rekursion gibt, beschränkt durch die hardware. (endlosschleifen gibt es nur in der theorie)
alzaimar - So 08.05.05 14:18
Türme von Hanoi:
Stell Dir drei Felder vor. A B und C.
Auf A steht ein Stapel mit N sich noch oben verkleinernden Scheiben.
Aufgabe: Verschiebe den Stapel von A nach C.
Regel 1: Du darfst immer nur eine Scheibe bewegen.
Regel 2: Eine Scheibe darf nicht auf einer kleineren Scheibe liegen.
Lösungstipp:
Um alle Scheiben von A nach C zu verschieben, verschiebe einfach (unter Beibehaltung der Regeln) irgendwie den Stapel (bis auf die unterste Scheibe) von A nach B, dann bewege die unterste Scheibe von A nach C und abschließend den Stapel, der jetzt auf B liegt, von B nach C.
F34r0fTh3D4rk - So 08.05.05 14:28
ach das teil ^^ :D ich überleg grad wie ich das mache, hmm schwiegrig, ich glaub ich probier des erstmal mit geldstücken auf meinem schreibtisch :lol:
auf meinem schreibttisch bin ich jetzt so weit:
Quelltext
1:
2:
3:
4:
5:
| ------1------
------2------
5-----3-----4
A-----B-----C |
ok jetzt ist es so:
Quelltext
1:
2:
3:
4:
5:
6:
| -----1-----
-----2-----
-----3-----
-----4-----
-----5-----
A----B----B |
naja sagen wir geschaft ^^
Das System ist etwas kompliziert, das muss ich in meinem
Kopf noch in Code umwandeln, aber es ist lustig ^^ :D
F34r0fTh3D4rk - So 08.05.05 14:44
ich kriegs auch in 30 sekunden hin, das system ist in mir drin, ich versteh auch wie ichs machen muss, aber in code .... ??? muss ich wohl noch etwas denken :lol: aber so schwer ist es glaube ich net
GTA-Place - So 08.05.05 14:49
1. Scheibe 1 auf B
2. Prüfen wo Scheibe 2 hin darf -> auf C
3. Prüfen wo Scheibe 3 hin darf -> nicht bei B und nicht bei C -> Kleinste Scheibe bei B oder C suchen -> B auf C
...
alzaimar - So 08.05.05 15:28
Achtung, hier ist eine Lösung...
Wie war das?
Um N Scheiben zu verschieben:
Verschiebe erstmal N-1 Scheiben woandershin
Dann die unterste zum Ziel
Und dann die N-1 Scheiben von woandershin zum Ziel.
Aha. 'woanders' ist interessant. Wir haben ja drei Felder. A, B und C (oder 1,2 und 3). Wenn wir von A nach C wollen, ist 'B' eben das 'woanders'. Gut. Nochmal:
Verschiebe Scheiben von A über B nach C:
1. Verschiebe N-1 Scheiben von A über C nach B.
2. Bewege die verbliebene Scheibe von A nach C.
3. Verschiebe N-1 Scheiben von B über C nach A.
Oha. Das riecht nach Rekursion ('Verschiebe X Scheiben von ....'). Das passt. Also:
Delphi-Quelltext
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:
| Program TowersOfHanoi;
Procedure MoveTower (N : Integer; aFromField, aToField, aUsingField : Integer);
Begin
If N>1 Then
MoveTower (N - 1, aFromField, aUsingField, aToField);
Writeln(aFromField,'->',aToField);
If N>1 Then
MoveTower (N - 1, aUsingField, aToField, aFromField);
End;
Procedure Main;
Var
N : Integer;
Begin
Write ('Türme von Hanoi. Wie hoch ist der Turm [1-100] ? > '); ReadLn(N);
MoveTower (N,1,3,2); End. |
F34r0fTh3D4rk - So 08.05.05 15:41
ja danke :D
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
| Procedure MoveTower(N : Integer; aFromField, aToField, aUsingField : Integer);
Begin
If N > 1 Then
MoveTower (N - 1, aFromField, aUsingField, aToField);
Form1.ListBox1.Items.add(inttostr(aFromField) + ' nach Feld ' + inttostr(aToField) + ' bewegen');
If N > 1 Then
MoveTower (N - 1, aUsingField, aToField, aFromField);
End;
procedure TForm1.Button1Click(Sender: TObject);
begin
form1.ListBox1.clear;
MoveTower(strtoint(edit1.text), 1, 3, 2);
end; |
Die Macht von Rekursion ist gewaltig.
Iterativ ist das schon ne ganz schöne arbeit mehr (hatte des gerade mit nem 2d array und dann würde erst immer geprüft)
GTA-Place - So 08.05.05 15:49
Für 20 Scheiben braucht er 1.048.000 Runden.
Für 30 Scheiben braucht er 1.070.000.000 Runden.
alzaimar - So 08.05.05 15:58
@F34r0fTh3D4rk: Deine Lösung ist aber falsch (auch wenn sie ein 'IF' weniger hat)!
Denn ich kann ja nicht erst den Turm von A nach B, dann von B nach C und zum Schluss die Scheibe oben drauf packen!
Schau Dir mal die ausgegebene Lösung (bei N=2) an.
Meine Lösung
1->2
1->3
2->3
Deine Lösung
1->2
2->3
1->3 <-- Regelverstoss weil eine größere über einer kleineren Scheibe liegt.
F34r0fTh3D4rk - So 08.05.05 17:58
ich weiß, hatte mich auch vertan, weil ich zuerst keine befehlszeile fürs speichern drin hatte die dazwischen musste, ist aber inzwischen längst behoben :D
wäre auch dumm ((1 nach 2) und (2 nach 3)) ist das gleiche wie (1 nach 3) ^^
GTA-Place - So 08.05.05 18:07
So meine Version ist fertig.
F34r0fTh3D4rk - So 08.05.05 19:22
ich habs jetzt angefangen mit nem stringgrid Grafisch zu machen, aber bei mir tut sich garnischt:
Delphi-Quelltext
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:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
| unit UMain;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, Grids, StdCtrls;
type
TForm1 = class(TForm)
StringGrid1: TStringGrid;
Button1: TButton;
Edit1: TEdit;
Button2: TButton;
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
private
public
end;
var
Form1: TForm1;
implementation
{$R *.dfm}
procedure Init(N: integer);
var
i: integer;
begin
Form1.StringGrid1.RowCount := N;
for i := 0 to N - 1 do
Form1.StringGrid1.Cells[0, i] := inttostr(i + 1);
end;
procedure MoveDisc(aFromField, aToField: integer);
var
i, j: integer;
begin
for i := Form1.StringGrid1.RowCount - 1 downto 0 do if Form1.StringGrid1.Cells[atofield, i] = '' then
begin
for j := 0 to Form1.StringGrid1.RowCount - 1 do if Form1.StringGrid1.Cells[afromfield, j] <> '' then
begin
Form1.StringGrid1.Cells[atofield, i] := Form1.StringGrid1.Cells[afromfield, j];
Form1.StringGrid1.Cells[afromfield, j] := '';
break;
end;
break;
end;
end;
procedure Hanoi(N : Integer; aFromField, aToField, aUsingField : Integer);
begin
if N > 1 then
Hanoi(N - 1, aFromField, aUsingField, aToField);
MoveDisc(aFromField, aToField);
Application.ProcessMessages;
if N > 1 then
Hanoi(N - 1, aUsingField, aToField, aFromField);
end;
procedure TForm1.Button1Click(Sender: TObject);
begin
Init(strtoint(edit1.text));
end;
procedure TForm1.Button2Click(Sender: TObject);
begin
Hanoi(strtoint(edit1.text), 1, 3, 2)
end;
end. |
:(
kannst ja vielleicht mal deinen code zeigen GTA
GTA-Place - So 08.05.05 19:32
Neue Version von meiner Simulation.
Ihr könnt jetzt einstellen, wie viele Scheiben ihr wollt (3 - 15).
Delphi-Quelltext
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:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
| procedure MoveTower (N: Integer; aFromField, aToField, aUsingField: Integer);
begin
If N > 1 Then
MoveTower (N - 1, aFromField, aUsingField, aToField);
Form1.HinwMemo.Lines.Add('-> Scheibe ' + IntToStr(N) + ' von Feld ' +
IntToStr(aFromField) + ' nach Feld ' + IntToStr(aToField));
inc(Runde);
if aFromField = 1 then
begin
TLabel(Form1.FindComponent('A' + IntToStr(BelA))).Caption := 'II';
TLabel(Form1.FindComponent('A' + IntToStr(BelA))).Left := 144;
dec(BelA);
end;
if aFromField = 2 then
begin
TLabel(Form1.FindComponent('B' + IntToStr(BelB))).Caption := 'II';
TLabel(Form1.FindComponent('B' + IntToStr(BelB))).Left := 144;
dec(BelB);
end;
if aFromField = 3 then
begin
TLabel(Form1.FindComponent('C' + IntToStr(BelC))).Caption := 'II';
TLabel(Form1.FindComponent('C' + IntToStr(BelC))).Left := 144;
dec(BelC);
end;
if aToField = 1 then
begin
inc(BelA);
TLabel(Form1.FindComponent('A' + IntToStr(BelA))).Caption := ScheibArray[N];
TLabel(Form1.FindComponent('A' + IntToStr(BelA))).Left := 150 -
TLabel(Form1.FindComponent('A' + IntToStr(BelA))).Width div 2;
end;
if aToField = 2 then
begin
inc(BelB);
TLabel(Form1.FindComponent('B' + IntToStr(BelB))).Caption := ScheibArray[N];
TLabel(Form1.FindComponent('B' + IntToStr(BelB))).Left := 150 -
TLabel(Form1.FindComponent('B' + IntToStr(BelB))).Width div 2;
end;
if aToField = 3 then
begin
inc(BelC);
TLabel(Form1.FindComponent('C' + IntToStr(BelC))).Caption := ScheibArray[N];
TLabel(Form1.FindComponent('C' + IntToStr(BelC))).Left := 150 -
TLabel(Form1.FindComponent('C' + IntToStr(BelC))).Width div 2;
end;
Application.ProcessMessages;
Sleep(StrToInt(Form1.GeschwEdit.Text));
If N > 1 Then
MoveTower (N - 1, aUsingField, aToField, aFromField);
end; |
F34r0fTh3D4rk - So 08.05.05 20:02
warum tut sich aber bei meinem code nischt ? Bin aus deinem Code net schlauer geworden (weil mein system anders funzt)
GTA-Place - Mo 09.05.05 16:23
Hab meinen Source optimiert:
Delphi-Quelltext
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:
| procedure MoveTower (N: Integer; aFromField, aToField, aUsingField: Integer);
begin
If N > 1 Then
MoveTower (N - 1, aFromField, aUsingField, aToField);
Form1.HinwMemo.Lines.Add('-> Scheibe ' + IntToStr(N) + ' von Feld ' +
IntToStr(aFromField) + ' nach Feld ' + IntToStr(aToField));
inc(Runde);
TLabel(Form1.FindComponent(FeldArray[aFromField] +
IntToStr(BelArray[aFromField]))).Caption := 'II';
TLabel(Form1.FindComponent(FeldArray[aFromField] +
IntToStr(BelArray[aFromField]))).Left := 144;
BelArray[aFromField] := BelArray[aFromField] - 1;
BelArray[aToField] := BelArray[aToField] + 1;
TLabel(Form1.FindComponent(FeldArray[aToField] +
IntToStr(BelArray[aToField]))).Caption := ScheibArray[N];
TLabel(Form1.FindComponent(FeldArray[aToField] +
IntToStr(BelArray[aToField]))).Left := 150 -
TLabel(Form1.FindComponent(FeldArray[aToField] +
IntToStr(BelArray[aToField]))).Width div 2;
Application.ProcessMessages;
Sleep(StrToInt(Form1.GeschwEdit.Text));
If N > 1 Then
MoveTower (N - 1, aUsingField, aToField, aFromField);
end; |
Larus - So 15.05.05 14:30
Rofl: 33791 Schritte um 15 Scheiben zu bewegen! Wozu braucht man so ne Berechnung denn bitteschön! Es wird keiner so Lebensmüde sein diese Anzahl an schritten per Hand durchzuführen oder?
F34r0fTh3D4rk - So 15.05.05 14:51
| Zitat: |
Wozu braucht man so ne Berechnung denn bitteschön!
|
braucht man nicht, außerdem kann man es ja grafisch darstellen 8)
Micho - So 15.05.05 19:43
 Die letzte Tröte hat folgendes geschrieben: |
| Man kann alles Iterative Rekursiv lösen, aber nicht alles Rekursive Iterativ...oder versuch ma die Koch Kurve Iterativ auf die beine zu stellen :D |
Die Koch-Kurve kann man iterativ mit dem L-System erzeugen. Sind nur zwei Schleifen ...
Außerdem kann man jedes rekursive Programm auch iterativ lösen, wenn man z.B. einen Stapel oder eine Schlange (stack bzw. queue) benutzt.
_________________
www.michael-kreil.de [
http://www.michael-kreil.de]
F34r0fTh3D4rk - Di 14.03.06 16:48
so ich hab mich nochmal dran gemacht, dieses mal mit grafischer umsetzung, jedoch habe ich probleme, da zwischendurch einige teile nicht dargestellt sind, ich weiß einfach nicht, wo die hin sind Oo
EDIT: habs musste nur 3 highs durch lenghts ersetzen ^^
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!