Grafische Lösung der Türme von Hanoi (Rekursion)

[Mavarik]

So würde ich das machen...

[Hanoi1]

Wie rufe ich den Code dafür ab?

[Mavarik]

Zitat von Hanoi1:

Wie rufe ich den Code dafür ab?

Die wesentlichen Teilen:

Delphi-Quellcode:

unit Main;


interface

uses
...

const
  Größe     = 250.0;
  MaxHeight = 240;
  Dauer     = 1;
  Dicke     = 25;

type
  TZug = record
    Von, Nach: integer;
    constructor Create( AVon, ANach: integer );
  end;

  TKindOfAnimation = ( Up, RightOrLeft, Down, Next );

  TForm128 = class( TForm )
..
  private
    { Private-Deklarationen }
    Scheiben    : array of TRectangle;
    Pole        : array [ 1 .. 3 ] of TPointF;
    Stange      : array [ 1 .. 3 ] of TStack<integer>;
    Colors      : array [ 0 .. 9 ] of TAlphaColor;
    Zugliste    : TQueue<TZug>;
    ScheibenNr  : integer;
    AktAnimation: TKindOfAnimation;
    AktZug      : TZug;

    procedure Init( const AAnzahl: integer );
    procedure DeInit;
    procedure dohanoi( Anzahl, AFrom, ATo, ASave: integer );
    procedure ShowZüge;
    function GetZug( out AZug: TZug ): boolean;
    procedure ShowZug( AZug: TZug );
    procedure Animation( AKind: TKindOfAnimation );
    function GetColor( A, B: integer ): TAlphaColor;
  public
    { Public-Deklarationen }
  end;

implementation

{$R *.fmx}

procedure TForm128.dohanoi( Anzahl, AFrom, ATo, ASave: integer );
begin
  if Anzahl > 0
  then
    begin
      dohanoi( Anzahl - 1, AFrom, ASave, ATo );
      Zugliste.Enqueue( TZug.Create( AFrom, ATo ) );
      dohanoi( Anzahl - 1, ASave, ATo, AFrom );
    end
end;

procedure TForm128.FloatAnimation1Finish( Sender: TObject );
begin
  AktAnimation := Succ( AktAnimation );
  if AktAnimation = Next
  then
    begin
      Application.ProcessMessages;
      ShowZüge;
    end
  else
    Animation( AktAnimation );
end;

procedure TForm128.FormCreate( Sender: TObject );
begin
  Colors[ 0 ] := TAlphaColorRec.Black;
  Colors[ 1 ] := TAlphaColorRec.Darkviolet;
  Colors[ 2 ] := TAlphaColorRec.Blue;
  Colors[ 3 ] := TAlphaColorRec.Deepskyblue;
  Colors[ 4 ] := TAlphaColorRec.Mediumseagreen;
  Colors[ 5 ] := TAlphaColorRec.Greenyellow;
  Colors[ 6 ] := TAlphaColorRec.Yellow;
  Colors[ 7 ] := TAlphaColorRec.Orange;
  Colors[ 8 ] := TAlphaColorRec.Orangered;
  Colors[ 9 ] := TAlphaColorRec.Red;

  Setlength( Scheiben, 0 );
  TrackBar1.Value := Dauer * 1000;

  Stange[ 1 ] := TStack<integer>.Create;
  Stange[ 2 ] := TStack<integer>.Create;
  Stange[ 3 ] := TStack<integer>.Create;

  Pole[ 1 ].X := Leftpole.Position.X + ( Leftpole.Width / 2 );
  Pole[ 2 ].X := MidPole.Position.X + ( MidPole.Width / 2 );
  Pole[ 3 ].X := RightPole.Position.X + ( RightPole.Width / 2 );

  Init( trunc( SpinBox1.Value ) );
end;


function TForm128.GetColor( A, B: integer ): TAlphaColor;
var
  M: Single;
begin
  if A = 0
  then
    Exit( Colors[ 0 ] );
  if A = B
  then
    Exit( Colors[ 9 ] );

  M := ( 9 / B ) * A;

  Result := Colors[ trunc( M ) ];
end;

function TForm128.GetZug( out AZug: TZug ): boolean;
begin
  if Zugliste.Count > 0
  then
    begin
      AZug   := Zugliste.Dequeue;
      Result := true;
    end
  else
    Result := false;
end;

procedure TForm128.Animation( AKind: TKindOfAnimation );
begin
  AktAnimation := AKind;

  case AKind of
    Up:
      begin
        FloatAnimation1.Stop;
        FloatAnimation1.Parent        := Scheiben[ ScheibenNr ];
        FloatAnimation1.StartValue    := Scheiben[ ScheibenNr ].Position.Y;
        FloatAnimation1.StopValue     := MaxHeight;
        FloatAnimation1.AnimationType := TAnimationType.&In;
        FloatAnimation1.Interpolation := TInterpolationType.Quadratic;
        FloatAnimation1.Start;
      end;
    RightOrLeft:
      begin
        FloatAnimation2.Stop;
        FloatAnimation2.Parent     := Scheiben[ ScheibenNr ];
        FloatAnimation2.StartValue := Scheiben[ ScheibenNr ].Position.X;
        FloatAnimation2.StopValue  := Pole[ AktZug.Nach ].X - ( Scheiben[ ScheibenNr ].Width / 2 );
        FloatAnimation2.Start;
      end;
    Down:
      begin
        FloatAnimation1.Stop;
        FloatAnimation1.Parent        := Scheiben[ ScheibenNr ];
        FloatAnimation1.StartValue    := MaxHeight;
        FloatAnimation1.StopValue     := Ground.Position.Y - ( Stange[ AktZug.Nach ].Count * Dicke );
        FloatAnimation1.AnimationType := TAnimationType.Out;
        FloatAnimation1.Interpolation := TInterpolationType.Bounce;
        FloatAnimation1.Start;
      end;
  end; // of case
end;

procedure TForm128.Button1Click( Sender: TObject );
begin
  Button1.Enabled  := false;
  SpinBox1.Enabled := false;
  Application.ProcessMessages;

  Init( trunc( SpinBox1.Value ) );

  Zugliste := TQueue<TZug>.Create;
  dohanoi( trunc( SpinBox1.Value ), 1, 3, 2 );

  ShowZüge;
end;

procedure TForm128.DeInit;
begin
  Zugliste.Free;
  FloatAnimation1.Parent := nil;
  FloatAnimation2.Parent := nil;
  Button1.Enabled        := true;
  SpinBox1.Enabled       := true;
end;

procedure TForm128.Init( const AAnzahl: integer );
var
  i                            : integer;
  StartSize, StartStack, DeltaW: Single;
begin
  Stange[ 1 ].Clear;
  Stange[ 2 ].Clear;
  Stange[ 3 ].Clear;

  for i := 0 to high( Scheiben ) do
    Scheiben[ i ].Free;

  StartSize  := Größe;
  StartStack := Ground.Position.Y - Dicke;
  Setlength( Scheiben, AAnzahl );

  FloatAnimation1.Duration := TrackBar1.Value / 1000;
  FloatAnimation2.Duration := TrackBar1.Value / 1000;

  DeltaW := 230 / AAnzahl;

  for i := 0 to AAnzahl - 1 do
    begin
      Scheiben[ i ]            := TRectangle.Create( Self );
      Scheiben[ i ].Parent     := Layout1;
      Scheiben[ i ].Height     := Dicke;
      Scheiben[ i ].Width      := StartSize;
      Scheiben[ i ].Position.X := Pole[ 1 ].X - ( StartSize / 2 );
      Scheiben[ i ].Position.Y := StartStack;
      Scheiben[ i ].Fill.Color := GetColor( i, AAnzahl - 1 );
      StartStack               := StartStack - Dicke;
      StartSize                := StartSize - DeltaW;
      Stange[ 1 ].Push( i );
    end;
end;

procedure TForm128.ShowZug( AZug: TZug );
begin
  ScheibenNr := Stange[ AZug.Von ].Pop;
  Stange[ AZug.Nach ].Push( ScheibenNr );

  AktZug := AZug;
  Animation( Up );
end;

procedure TForm128.ShowZüge;
var
  Zug: TZug;
begin
  if GetZug( Zug )
  then
    ShowZug( Zug )
  else
    DeInit;
end;


{ TZug }

constructor TZug.Create( AVon, ANach: integer );
begin
  Von  := AVon;
  Nach := ANach;
end;

end.

[Hanoi1]

Mein Programm funktioneirt jetzt endlich.
Ich habe auch die Oberfläche nochmal etwas abgeändert und besser gestaltet.

Hier also mein neuer Quellcode:

Delphi-Quellcode:

unit Unit1;

{$mode objfpc}{$H+}

interface

uses
  Classes, SysUtils, FileUtil, Forms, Controls, Graphics, Dialogs, StdCtrls,
  ExtCtrls;

type

  { TForm1 }

  TForm1 = class(TForm)
    Button1: TButton;
    Button2: TButton;
    Button3: TButton;
    Edit1: TEdit;
    Label1: TLabel;
    Panel1: TPanel;
    Panel2: TPanel;
    Panel3: TPanel;
    Rechts: TShape;
    Mitte: TShape;
    Links: TShape;
    StabRechts: TShape;
    StabMitte: TShape;
    StabLinks: TShape;
    ShapeMOVE: TShape;
    TA: TShape;
    TB: TShape;
    TC: TShape;
    ShapeMF: TShape;
    ShapeMT: TShape;
    ShapeT2: TShape;
    Timer1: TTimer;
    procedure Button1Click(Sender: TObject);
    procedure Button2Click(Sender: TObject);
    procedure Button3Click(Sender: TObject);
    procedure Timer1Timer(Sender: TObject);
  private
    { private declarations }
  public
    { public declarations }
  end;

var
  Form1: TForm1;
    z: integer;
    q: boolean;
    cL,cM,cR: integer;
    Scheibe: array[1..10] of TShape;
    index: integer;

implementation

{$R *.lfm}

{ TForm1 }

procedure draw(a,b,c,d: integer; n: string);
var Shape : TShape;
begin
 Shape := TShape.Create(Form1);
 With Shape do
  begin
   Parent := Form1;
   Left := a;
   Top := b;
   Width:= c;
   Height:=d;
   Name := n;
   Brush.Color:=clMaroon;
   Brush.Style:=bsSolid;
   Pen.Color:=clMaroon;
  end;
end;

procedure towerA(t: integer);
var i,z: integer;
begin
 i:=0;
 z:=t+1;
 repeat
  i:=i+1;
  z:=z-1;
  Scheibe[z] := TShape.Create(Form1);
 With Scheibe[z] do
  begin
   Parent := Form1;
   Left := 100+((i-1)*10);
   Top := 550-(i*50);
   Width:= 200-((i-1)*20);
   Height:=50;
   Name:= 'Scheibe'+IntToStr(z);
   Brush.Color:=clNavy;
   Shape:=stRoundRect;
  end;
 until i=t;
end;

procedure movetop(r: integer;ShapeMF,ShapeMT: TShape);
begin
 index:=r;
 Form1.ShapeT2:=ShapeMT;
 if ShapeMT.left=Form1.Mitte.left then
 begin
    cM:=cM+1;
    z:=550-(cM*50);
 end;
 if ShapeMT.left=Form1.Links.left then
 begin
    cL:=cL+1;
    z:=550-(cL*50);
 end;
 if ShapeMT.left=Form1.Rechts.left then
 begin
    cR:=cR+1;
    z:=550-(cR*50);
 end;
 if ShapeMF.left=Form1.Mitte.left then
 begin
    cM:=cM-1;
 end;
 if ShapeMF.left=Form1.Links.left then
 begin
    cL:=cL-1;
 end;
 if ShapeMF.left=Form1.Rechts.left then
 begin
    cR:=cR-1;
 end;
 Form1.Timer1.Enabled:=true;
 While Form1.Timer1.Enabled = true do
begin
  Application.Processmessages;
  Sleep(10);
end;
end;

procedure rec(r: integer;TA,TB,TC: TShape);
begin
 if r>0 then
 begin
   rec(r-1,TA,TC,TB);
   movetop(r,TA,TC);
   rec(r-1,TB,TA,TC);
 end;
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
 draw(100,550,200,50,'Links');
 draw(400,550,200,50,'Mitte');
 draw(700,550,200,50,'Rechts');
 draw(195,120,10,430,'StabLinks');
 draw(495,120,10,430,'StabMitte');
 draw(795,120,10,430,'StabRechts');
end;

procedure TForm1.Button2Click(Sender: TObject);
var k: Integer;
begin
 k:=StrToInt(Edit1.Text);
 if k > 10 then
    k:=10;
 if k < 3 then
    k:=3;
 q:=true;
 rec(k,Links,Mitte,Rechts);
end;

procedure TForm1.Button3Click(Sender: TObject);
var k: Integer;
begin
 k:=StrToInt(Edit1.Text);
 if k > 10 then
 begin
    k:=10;
    ShowMessage('Achtung: Da die gewünschte Anzahl an Scheiben über dem gültigen Maximalwert liegt, werden 10 Scheiben generiert.');
 end;
 if k < 3 then
 begin
    k:=3;
    ShowMessage('Achtung: Da die gewünschte Anzahl an Scheiben unter dem gültigen Minimalwert liegt, werden 3 Scheiben generiert.');
 end;
 cL:= k;
 cM:= 0;
 cR:= 0;
 towerA(k);
end;

procedure TForm1.Timer1Timer(Sender: TObject);
begin
 if q=true then
 begin
    if Scheibe[index].Top > 50 then
    Scheibe[index].Top:=Scheibe[index].Top-10;
 end;
 if Scheibe[index].Top=50 then
 begin
   if Scheibe[index].Left > ShapeT2.Left+((200-Scheibe[index].width)DIV 2)  then
      Scheibe[index].Left:=Scheibe[index].Left-10;
   if Scheibe[index].Left < ShapeT2.Left+((200-Scheibe[index].width)DIV 2)  then
      Scheibe[index].Left:=Scheibe[index].Left+10;
 end;
 if Scheibe[index].Left = ShapeT2.Left+((200-Scheibe[index].width)DIV 2)  then
 begin
   q:=false;
   if Scheibe[index].Top < z then
    Scheibe[index].Top:=Scheibe[index].Top +10;
   if Scheibe[index].Top = z then
   begin
    q:=true;
    Timer1.Enabled:=false;
   end;
 end;
end;

end.

An dieser Stelle möchte ich mich ganz sehr bei allen, die mir dabei geholfen haben, bedanken! Ohne euch hätte das sicher nicht geklappt!


LG

[stahli]

[Hanoi1]

Eine Kleinigkeit noch:
Durch

Delphi-Quellcode:

While Form1.Timer1.Enabled = true do
begin
  Application.Processmessages;
  Sleep(10);
end;

friere ich das Programm mit Ausnahme des Timers ein. Ohne das funktioniert der Algorithmus ja auch nicht.

Wenn ich jetzt aber beispielsweise 10 Scheiben generiere und die Lösung aktiviere, dauert das ja seine Zeit, bis das Programm "entfriert".

Darum wollte ich einen neuen Knopf einfügen, der den Timer anhält (z.B. close; ).
Das geht aber nun natürlich nicht...

Gibt es eine Möglichkeit das umzusetzen?

[Mavarik]

Zitat von Hanoi1:

Eine Kleinigkeit noch:
Durch

Delphi-Quellcode:

While Form1.Timer1.Enabled = true do
begin
  Application.Processmessages;
  Sleep(10);
end;

friere ich das Programm mit Ausnahme des Timers ein. Ohne das funktioniert der Algorithmus ja auch nicht.

Wenn ich jetzt aber beispielsweise 10 Scheiben generiere und die Lösung aktiviere, dauert das ja seine Zeit, bis das Programm "entfriert".

Nöö Nur bis der Timer auf false geht weil die Scheibenanimation beendet ist...
Dann geht es ganz normal weiter...

[stahli]

Ein grundsätzliches Problem ist, dass Du die GUI (Formular und Controls) mit der Businesslogik (Berechnung) verknüpfst.
Das ist anfänglich ganz normal, aber man sollte beide Ebenen etwas entkoppelt.

Ich gehe davon aus, dass Du an dem Projekt lernen möchtest.
Dann versuche mal folgenden Ansatz:

Erstelle eine neue Unit Hanoi.pas.
Dort legst Du Variablen für die Positionen Deiner Steine ab (z.B. in einem Array) und dazu Funktionen, die die Bewegungen berechnen.
In der Unit passiert nichts grafisches sondern nur reine (virtuelle) Berechnungen.
Dann brauchst Du eine Art Schrittzähler, damit Du weißt, wie viele Schritte schon berechnet sind.

Und jetzt das Wichtigeste:
Du brauchst eine Prozedur Init und eine NextStep.

Init setzt den Schrittzähler auf 0.
NextStep erhöht den Schrittzähler und berechnet den nächsten Schritt.

Das alles ist Deine Businesslogik.


Jetzt zur GUI (also dem Formular).

Du brauchst natürlich Deine Shapes wie gehabt.
Der Button ruft Init aus der anderen Unit auf und startet den Timer.

Der Timer veranlasst die Berechnung des nächsten Schrittes und korrigiert die Positionen der Shapes.
Wenn NextStep als Funktion ausgelegt wird kann diese sogar gleich mitteilen, dass keine weiteren Berechnungen notwendig sind (also das Ende erreicht ist).

Delphi-Quellcode:

procedure TForm1.Timer1Timer(Sender: TObject);
begin
  Timer1.Enabled := NextStep;
  ÜbertrageBerechnetePositionenInDiePositionenDerShapes;
end;

So muss das Formular sich nicht weiter drum kümmern, wie die Berechnung korrekt erfolgt und die Berechnung muss nicht die Shapes herum schieben.
Die Zuständigkeiten sind so übersichtlicher.
Natürlich muss man dann beide Ebenen aufeinander abstimmen.

Jetzt wird Dein Formular nicht einfrieren - bzw. immer nur ganz kurz, wenn Dein Timer die Änderungen berechnen lässt und zeichnet.
Während der anderen Zeit könntest Du sogar etwas in einem Edit schreiben - also quasi ohne Einschränkung.


Das ist natürlich auch alles keine endgültige Lösung, aber für den Anfang vielleicht mal interessant um eine Vorstellung von der Trennung von GUI und BL zu erhalten (wenngleich das noch keine richtige Trennung ist).

Um das noch ein wenig weiter zu treiben könntest Du die Positionsliste zur Berechnung übergeben und die Werte so zwischen den Units austauschen.
So muss Dein Formular nicht wissen, wie die Berechnungsunit die Positionen verwaltet.

Delphi-Quellcode:

procedure TForm1.Timer1Timer(Sender: TObject);
begin
  Timer1.Enabled := NextStep(Positionsliste);
  ÜbertrageFolgendePositionenInDiePositionenDerShapes(Positionsliste);
end;

Wenn Du Lust hast kannst Du Dich ja mal schrittweise dort heran tasten.
Als Testprojekt würde ich mal ein Programm schreiben, dass einen Ball (Panel) schrittweise bewegt, was durch einen Button gestartet und gestoppt wird.
Das klingt trivial und ist es auch. Aber so versteht man gut, welche Aufgaben in welche Unit gehören und wie beide Ebenen miteinander verbunden werden.

Wichtig dabei: Die Berechnungsunit soll NIE auf das Formular zugreifen sondern NUR das Formular auf die Berechnungsunit.


So, wenn der Kopf nicht mehr raucht, dann frisch ans Werk.