递归的应用-经典的“汉诺塔”演示

作者： /

“汉诺塔”是一个由数学家爱德华·卢卡斯于1883年发明的一个非常著名的游戏。游戏的内容是，有三根细柱（A,B,C)，A柱上套着6个圆盘。这些圆盘大小各异，按从大到小的顺序自下而上摆放。如下图所示。

0001

（图上白色黑框的代表圆盘）

现在要把套在A住上的6个圆盘全部移到B柱上。并且在移动圆盘时须遵守下述规则：

  1.  一次只能移动柱子最上端的一个圆盘。
  2.  小圆盘上不能放大圆盘。

将1个圆盘从一根柱子移到另一根柱子，算移动“1次”。那么，将6个圆盘全部从A移到B需要移动几次呢？（大家可以先默想一下）

 

让我们来看看C语言编写的解法程序吧，这是一个递归的调用：

void hanoi(int n, char x, char y, char z) {
  if (n == 0) {
    /* 什么也不做 */
   } else {
    hanoi(n-1, x, z, y);
    printf("%c->%c, ", x, y);
    hanoi(n-1, z, y, x);
   }
}

int main(void) {
  hanoi(6, 'A', 'B', 'C');
  return EXIT_SUCCESS;
}

上面的程序会正确的输出“6层汉诺塔”的解决步骤。hanoi 就是核心了，不过上面的C代码并不能直观的显示移动的过程，所以我特别用delphi写了一个小程序，用来做演示。

type
  // 用于存放指定轴上第n次移动时圆盘的数量与编号
  THanoiValue = record
    Start: Integer;
    procedure Push(V: Byte);
    function Pop(): Byte;
    function Count: Integer;
    function Get(Index: Integer): Byte;
  end;

  // 记录每次移动后的状态，以便动画显示
  THanoiList = array of THanoiValue;

  // 汉诺塔模拟移动
  THanoi = class(TObject)
  const
    SPACE = 24;
  private
    FCS: TCanvas;
    FTimer: TTimer;
    FIndex: Integer;
    FLayerCount: Integer;
    FAxis: array of THanoiList;
    FLayerWidth: array of Integer;
    FW, FH: Integer;
    FXx, FYx, FZx, FIW: Integer;
    function GetInterval: Cardinal;
    procedure SetInterval(const Value: Cardinal);
  protected
    procedure Init();
    procedure Hanoi(n: Integer; X, Y, Z: Integer);
    procedure DoTimer(Sender: TObject);

    procedure DoDrawBackground();
    procedure DoDrawItem(AIndex: Integer);
    procedure DoDraw();
  public
    constructor Create(CS: TCanvas);
    destructor Destroy; override;
    procedure Start;  // 开始演示
    procedure Stop;   // 停止演示
    // 演示速度
    property Interval: Cardinal read GetInterval write SetInterval;
    // 几层圆盘？ 本示例最多支持7层，受限于THanoiValue的定义，需要更多的话请你改进它
    property LayerCount: Integer read FLayerCount write FLayerCount;
  end;


{ THanoi }

constructor THanoi.Create(CS: TCanvas);
begin
  FCS := CS;
  FTimer := TTimer.Create(frmMathTool);
  FTimer.Enabled := False;
  FTimer.Interval := 1000;
  FTimer.OnTimer := DoTimer;
end;

destructor THanoi.Destroy;
begin
  Stop();
  FreeAndNil(FTimer);
  inherited;
end;

procedure THanoi.DoDraw;
begin
  DoDrawBackground();
  DoDrawItem(0);
  DoDrawItem(1);
  DoDrawItem(2);
  FCS.Font.Size := 14;
  FCS.Brush.Color := clWhite;
  FCS.TextOut(10, 6, Format('%d/%d', [FIndex, High(FAxis[0])]));
end;

procedure THanoi.DoDrawBackground;
var
  R: TRect;

  procedure DrawAxis(AOffset: Integer; const AName: string);
  begin
    FCS.Brush.Color := clMaroon;
    R.Left := AOffset + (FIW - 12) shr 1;
    R.Right := R.Left + 12;
    R.Top := 40;
    R.Bottom := FH - SPACE;
    FCS.FillRect(R);
    FCS.Brush.Color := clWhite;
    FCS.TextOut(R.Left, 6, AName);
  end;
  
begin
  FCS.Brush.Color := clWhite;
  FCS.FillRect(FCS.ClipRect);
  
  FCS.Brush.Color := clDkGray;
  SetRect(R, FXx, FH - SPACE, FXx + FIW, FH - 6);
  FCS.FillRect(R);
  SetRect(R, FYx, FH - SPACE, FYx + FIW, FH - 6);
  FCS.FillRect(R);
  SetRect(R, FZx, FH - SPACE, FZx + FIW, FH - 6);
  FCS.FillRect(R);

  FCS.Font.Size := 16;
  DrawAxis(FXx, 'A');
  DrawAxis(FYx, 'B');
  DrawAxis(Fzx, 'C');  
end;

procedure THanoi.DoDrawItem(AIndex: Integer);
const
  LH = 24;
var
  X, Y, I, W: Integer;
  V: THanoiValue;
  R: TRect;
begin
  V := FAxis[AIndex][FIndex];
  if V.Count = 0 then Exit;  
  case AIndex of
    0: X := FXx;
    1: X := FYx;
    2: X := FZx;
  else
    Exit;
  end;
  Y := FH - SPACE;
  FCS.Brush.Color := clWhite;
  for I := 0 to V.Count - 1 do begin
    W := FlayerWidth[V.Get(i) - 1];
    R.Left := X + (FIW - W) div 2;
    R.Right := R.Left + W;
    R.Top := Y - LH;
    R.Bottom := Y;
    Dec(Y, LH);
    FCS.Rectangle(R);
  end;
end;

procedure THanoi.DoTimer(Sender: TObject);
begin
  if FIndex > High(FAxis[0]) then
    FTimer.Enabled := False
  else begin
    DoDraw();
    Inc(FIndex);
  end;
end;

function THanoi.GetInterval: Cardinal;
begin
  Result := FTimer.Interval;
end;

procedure THanoi.Hanoi(n, X, Y, Z: Integer);
begin
  if n > 0 then begin
    Hanoi(n - 1, x, z, y);

    FAxis[y][FIndex].Start := FAxis[y][FIndex - 1].Start;  
    FAxis[x][FIndex].Start := FAxis[x][FIndex - 1].Start;
    FAxis[z][FIndex].Start := FAxis[z][FIndex - 1].Start;   

    FAxis[y][FIndex].Push(FAxis[x][FIndex].Pop);

    Inc(FIndex);
    Hanoi(n - 1, z, y, x);
  end;
end;

procedure THanoi.Init;
var
  I, J: Integer;
begin
  I := (2 shl (FLayerCount - 1));
  if Length(FAxis) < 3 then begin
    SetLength(FAxis, 3);
    SetLength(FAxis[0], I);
    SetLength(FAxis[1], I);
    SetLength(FAxis[2], I);
    FillChar(FAxis[0][0], i * 4, 0);
    FillChar(FAxis[1][0], i * 4, 0);
    FillChar(FAxis[2][0], i * 4, 0);
    for i := 1 to FLayerCount do        
      FAxis[0][0].Push(I);
    FIndex := 1;
    Hanoi(FLayerCount, 0, 1, 2);
  end;
  FIndex := 0;

  FW := FCS.ClipRect.Right - FCS.ClipRect.Left;
  FH := FCS.ClipRect.Bottom - FCS.ClipRect.Top;

  FIW := Round((FW - SPACE * 4) / 3);
  SetLength(FLayerWidth, FLayerCount);
  J := Round(FIW * 0.8 / FLayerCount);
  for I := 0 to FLayerCount - 1 do
    FLayerWidth[i] := FIW - (I + 1) * J;
  FXx := SPACE;
  FYx := FXx + FIW + SPACE;
  FZx := FYx + FIW + SPACE;
  DoDrawBackground();
end;

procedure THanoi.SetInterval(const Value: Cardinal);
begin
  FTimer.Interval := Value;
end;

procedure THanoi.Start;
begin
  Init;
  FTimer.Enabled := True;
end;

procedure THanoi.Stop;
begin
  FTimer.Enabled := False;
  Init;
end;

{ THanoiValue }

function THanoiValue.Count: Integer;
var
  I: Integer;
begin
  Result := 0;
  I := Start;
  while (Result < 10) and (I and $7 > 0) do begin
    Inc(Result);
    I := I shr 3;
  end; 
end;

function THanoiValue.Get(Index: Integer): Byte;
var
  I, K: Integer;
begin
  Result := 0;
  I := Start;
  K := 0;
  while K < 8 do begin
    Result := I and $7;
    if Result > 0 then begin
      if K = Index then
        Break;
      I := I shr 3;
      Inc(K);
    end else 
      Break;
  end;   
end;

function THanoiValue.Pop: Byte;
var
  I, J, K: Integer;
begin
  Result := 0;
  I := Start;
  K := 0;
  while K < 8 do begin
    J := I and $7;
    if J > 0 then begin
      Result := J;
      I := I shr 3;
      Inc(K);
    end else begin
      if Result > 0 then        
        Start := Start and (not ($7 shl ((K - 1) * 3)));
      Break;
    end;
  end;
end;

procedure THanoiValue.Push(V: Byte);
var
  I, K, L: Integer;
begin
  I := Start;
  L := V;
  K := 0;
  while K < 8 do begin
    if (I and $7) > 0 then begin
      I := I shr 3;
      L := L shl 3;
      Inc(K);
    end else begin
      Start := Start or L;
      Break;
    end;
  end;
end;

使用 THanoi 可以动态的演示移动过程，我的程序运行效果如下：

0002

0003

0004

0005

在上面的演示程序中，是先将整个移动过程计算好后保存起来，然后用定时器动画显示的。THanoiValue 的作用很关键，它记录了每次移动后在一个轴上的圆盘数量和大小（编号），这样才可以准确的画图展示移动过程。

 

滚动至顶部