漢諾塔問題的算法分析及C++實現

江蘇灌南縣  孫小慧

   摘要：該文對經典的漢諾塔問題進行了詳細的分析，給出了遞歸的和非遞歸的算法，并用c++語言對這兩種算法進行了實現與比較。

    關鍵字：　漢諾塔，遞歸算法，非遞歸算法

Algorithm Analysis and C++ Realization of Hanio Issue

Sun Xiaohui

      Abstract: This text carries on detailed analysis about classical Hanio issue ,then describe it with both Recursive algorithm and Non-recursive algorithm, provides realization of algorithm in C++.

Keywords：Tower of hanoi，Recursive algorithm，Non-recursive algorithm

      一、 問題描述

問題提出：

設有三個塔柱（分別為A號，B號和C號）。初始時，有n 個圓盤按自下向上、從大到小的次序疊置在A 塔上。現要將A 塔上的所有圓盤，借助于B塔，全部移動到C塔上，且仍按照原來的次序疊置。移動的規則如下：這些圓形盤只能在個塔間進行移動，一次只能移動一個盤子，且任何時候都不允許將較大的盤子壓在比它小的盤子的上面。要求如下：從鍵盤輸入初始圓形盤子個數n，用C 語言實現n 個盤子最佳移動的全過程[1]。

本題的目的是設計一個盤子移動的方案，使得A 號塔上的所有盤子借助于B塔按照原來的次序移動到C塔上，并且，要給出完整的盤子移動的方案。下面我們從遞歸和非遞歸兩種方面進行考慮[2]。

       二、 遞歸解法及其C++實現

我們先來考慮下遞歸求解這個問題的情況：

假設共有n個盤子，無論n是多少，也不管怎么去移動盤子（當然是按規則來移動），但在移動的過程中，將始終會出現這樣的狀態情況：（n－1）個盤子將會以自下向上、從大到小的次序疊置在B 塔上，這時，A塔上第n 個盤子就能被輕而易舉地疊放到C 塔上；接著，再把B 塔上的共（n－1）個盤子移動到C 塔上，問題好像已經解決。但，B 塔上（n－1）個盤子怎么移動到C 塔上呢芽這是要解決的第二個問題。同樣，不管我們怎么移動，也將會出現這樣的狀態情況：（n－2） 個盤子將會以從上到下、從大到小的次序疊置在A 塔上，這時，B 塔上第（n－1） 個盤子就能被輕而易舉放到C 塔上；接著，把A 塔上的共（n－2）個盤子移動到C 塔上。這樣，不斷深入，不斷細小化，最終，將到達僅有一個盤的情形，這時，遞歸也就終止了，問題也得到了解決。通過以上分析，這里有很明顯的遞歸關系。

由此，可以給出漢諾塔問題的遞歸算法如下：

1. 當僅有1個盤子時，把這個盤子從A塔柱移動到C塔柱上

2. 當圓盤的個數多于1個時，如下解決：

（1） 先將A塔柱上的（n-1）個圓盤通過C塔柱移動到B塔柱上

（2） 再將A塔柱上的第n個圓盤直接移動到C塔柱上

（3） 最后B塔柱上的（n-1）個圓盤通過A塔柱移動到C塔柱上

該算法對應的代碼如下：

void hanoi(int n,char a,char b,char c)

{

if(n==1){

cout<<a<<"->"<<c<<endl;

}

else {

hanoi(n-1,a,c,b);

cout<<a<<"->"<<c<<endl;

hanoi(n-1,b,a,c);

}

}

        三、 非遞歸解法及其C++實現

首先把三根柱子按順序排成品字型，把所有的圓盤按從大到小的順序放在柱子A上。

根據圓盤的數量確定柱子的排放順序：若n為偶數，按順時針方向依次擺放 A B C；

（1）若n為奇數，按順時針方向依次擺放 A C B。

按順時針方向把圓盤1從現在的柱子移動到下一根柱子，即當n為偶數時，若圓盤1在柱子A，則把它移動到B；若圓盤1在柱子B，則把它移動到C；若圓盤1在柱子C，則把它移動到A。

（2）接著，把另外兩根柱子上可以移動的圓盤移動到新的柱子上。

即把非空柱子上的圓盤移動到空柱子上，當兩根柱子都非空時，移動較小的圓盤
這一步沒有明確規定移動哪個圓盤，你可能以為會有多種可能性，其實不然，可實施的行動是唯一的。

（3）反復進行（1）（2）操作，最后就能按規定完成漢諾塔的移動[3]。

C++代碼如下：

const int MAX = 64; //圓盤的個數最多為64

struct st{  //用來表示每根柱子的信息

      int s[MAX]; //柱子上的圓盤存儲情況

      int top; //棧頂，用來最上面的圓盤

      char name; //柱子的名字，可以是A，B，C中的一個

      int Top(){//取棧頂元素

            return s[top];

      }

      int Pop(){//出棧

            return s[top--];

      }

      void Push(int x){//入棧

            s[++top] = x;

      }

} ;

long Pow(int x, int y); //計算x^y
void Creat(st ta[], int n); //給結構數組設置初值
void Hannuota(st ta[], long max); //移動漢諾塔的主要函數

int main(void)
{

      int n;
      cin >> n; //輸入圓盤的個數      
      st ta[3]; //三根柱子的信息用結構數組存儲
      Creat(ta, n); //給結構數組設置初值

      long max = Pow(2, n) - 1;//動的次數應等于2^n - 1
      Hannuota(ta, max);//移動漢諾塔的主要函數

      system("pause");
      return 0;
}

void Creat(st ta[], int n)
{

      ta[0].name = 'A';

      ta[0].top = n-1;

      for (int i=0;i<n;i++)//把所有的圓盤按從大到小的順序放在柱子A上

            ta[0].s[i] = n - i;            
      ta[1].top = ta[2].top = 0;//柱子B，C上開始沒有沒有圓盤
      for (int i=0; i<n; i++)

            ta[1].s[i] = ta[2].s[i] = 0;

      if (n%2 == 0) //若n為偶數，按順時針方向依次擺放 A B C
      {
            ta[1].name = 'B';
            ta[2].name = 'C';
      }
      else  //若n為奇數，按順時針方向依次擺放 A C B
      {
            ta[1].name = 'C';
            ta[2].name = 'B';
      }
}

long Pow(int x, int y)
{
      long sum = 1;
      for (int i=0; i<y; i++)
            sum *= x;

      return sum;
}

void Hannuota(st ta[], long max)
{
      int k = 0; //累計移動的次數
      int i = 0;
      int ch;
      while (k < max)
      {
            //按順時針方向把圓盤1從現在的柱子移動到下一根柱子
            ch = ta[i%3].Pop();
            ta[(i+1)%3].Push(ch);
            cout << ++k << ": " << "Move disk " << ch << " from " << ta[i%3].name << " to " << ta[(i+1)%3].name << endl;
            i++;
            //把另外兩根柱子上可以移動的圓盤移動到新的柱子上
            if (k < max)
            {//把非空柱子上的圓盤移動到空柱子上，當兩根柱子都為空時，移動較小的圓盤
                  if (ta[(i+1)%3].Top() == 0 || ta[(i-1)%3].Top() > 0 && ta[(i+1)%3].Top() > ta[(i-1)%3].Top())
                  {
                        ch =  ta[(i-1)%3].Pop();
                        ta[(i+1)%3].Push(ch);
                        cout << ++k << ": " << "Move disk " << ch << " from " << ta[(i-1)%3].name << " to " << ta[(i+1)%3].name << endl;
                  }
                  else
                  {
                        ch =  ta[(i+1)%3].Pop();
                        ta[(i-1)%3].Push(ch);
                        cout << ++k << ": " << "Move disk " << ch << " from " << ta[(i+1)%3].name << " to " << ta[(i-1)%3].name << endl;
                  }
            }
      }
}

       四、 比較與總結

漢諾塔問題是經典的遞歸算法例子。本文給出了遞歸和非遞歸兩種解決漢諾塔問題的算法。遞歸的漢諾塔問題解法優點是邏輯清晰，易于理解，可讀性好，算法語句少，也有助于理解遞歸的思想，但需要大量的棧空間，運行效率不高。如果用非遞歸方法解決漢諾塔問題的算法，優點是僅用少量的存儲空間克服了遞歸算法的不足，兼顧了時間與空間的效率，缺點是理解起來可能比較困難，可讀性也不是很好，在實際中，可根據需要選擇一種進行解決。

   參考文獻

[1] 王春森．程序員教程[M]． 北京：清華大學出版社，2001-05．

[2] 周敏. 漢諾塔問題的算法分析及C語言實現[j].電腦學習，2009年10月

[3] 談祥柏 著.數學營養菜[M]. 中國少年兒童出版社,2004-5-1