漢諾塔問題的算法分析及C++實(shí)現(xiàn)

江蘇灌南縣  孫小慧

   摘要：該文對(duì)經(jīng)典的漢諾塔問題進(jìn)行了詳細(xì)的分析，給出了遞歸的和非遞歸的算法，并用c++語言對(duì)這兩種算法進(jìn)行了實(shí)現(xiàn)與比較。

    關(guān)鍵字：　漢諾塔，遞歸算法，非遞歸算法

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

      一、 問題描述

問題提出：

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

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

       二、 遞歸解法及其C++實(shí)現(xiàn)

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

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

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

1. 當(dāng)僅有1個(gè)盤子時(shí)，把這個(gè)盤子從A塔柱移動(dòng)到C塔柱上

2. 當(dāng)圓盤的個(gè)數(shù)多于1個(gè)時(shí)，如下解決：

（1） 先將A塔柱上的（n-1）個(gè)圓盤通過C塔柱移動(dòng)到B塔柱上

（2） 再將A塔柱上的第n個(gè)圓盤直接移動(dòng)到C塔柱上

（3） 最后B塔柱上的（n-1）個(gè)圓盤通過A塔柱移動(dòng)到C塔柱上

該算法對(duì)應(yīng)的代碼如下：

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++實(shí)現(xiàn)

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

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

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

按順時(shí)針方向把圓盤1從現(xiàn)在的柱子移動(dòng)到下一根柱子，即當(dāng)n為偶數(shù)時(shí)，若圓盤1在柱子A，則把它移動(dòng)到B；若圓盤1在柱子B，則把它移動(dòng)到C；若圓盤1在柱子C，則把它移動(dòng)到A。

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

即把非空柱子上的圓盤移動(dòng)到空柱子上，當(dāng)兩根柱子都非空時(shí)，移動(dòng)較小的圓盤
這一步?jīng)]有明確規(guī)定移動(dòng)哪個(gè)圓盤，你可能以為會(huì)有多種可能性，其實(shí)不然，可實(shí)施的行動(dòng)是唯一的。

（3）反復(fù)進(jìn)行（1）（2）操作，最后就能按規(guī)定完成漢諾塔的移動(dòng)[3]。

C++代碼如下：

const int MAX = 64; //圓盤的個(gè)數(shù)最多為64

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

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

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

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

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

            return s[top];

      }

      int Pop(){//出棧

            return s[top--];

      }

      void Push(int x){//入棧

            s[++top] = x;

      }

} ;

long Pow(int x, int y); //計(jì)算x^y
void Creat(st ta[], int n); //給結(jié)構(gòu)數(shù)組設(shè)置初值
void Hannuota(st ta[], long max); //移動(dòng)漢諾塔的主要函數(shù)

int main(void)
{

      int n;
      cin >> n; //輸入圓盤的個(gè)數(shù)      
      st ta[3]; //三根柱子的信息用結(jié)構(gòu)數(shù)組存儲(chǔ)
      Creat(ta, n); //給結(jié)構(gòu)數(shù)組設(shè)置初值

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

      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為偶數(shù)，按順時(shí)針方向依次擺放 A B C
      {
            ta[1].name = 'B';
            ta[2].name = 'C';
      }
      else  //若n為奇數(shù)，按順時(shí)針方向依次擺放 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; //累計(jì)移動(dòng)的次數(shù)
      int i = 0;
      int ch;
      while (k < max)
      {
            //按順時(shí)針方向把圓盤1從現(xiàn)在的柱子移動(dòng)到下一根柱子
            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++;
            //把另外兩根柱子上可以移動(dòng)的圓盤移動(dòng)到新的柱子上
            if (k < max)
            {//把非空柱子上的圓盤移動(dòng)到空柱子上，當(dāng)兩根柱子都為空時(shí)，移動(dòng)較小的圓盤
                  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;
                  }
            }
      }
}

       四、 比較與總結(jié)

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

   參考文獻(xiàn)

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

[2] 周敏. 漢諾塔問題的算法分析及C語言實(shí)現(xiàn)[j].電腦學(xué)習(xí)，2009年10月

[3] 談祥柏 著.數(shù)學(xué)營(yíng)養(yǎng)菜[M]. 中國少年兒童出版社,2004-5-1