漢諾塔（又稱河內塔）問題是源于印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。
下圖分析了黃金圓盤數目分別為1、2、3時的情況，可通過其觀察移動的一般規律。
圖片來源：http://www.chiuchang.com.tw/toy/hanoi/hanoi.html
通過分析可知，題目要求是將所有圓盤最終從A號柱移動到C號柱，對于問題規模為n的情況，可將問題分解為三步：
**1.將頂上的n-1個黃金圓盤從A號柱通過C號柱移動到B號柱上。**
**2.將A號柱子上的最后一個圓盤移動到C號柱上。**
**3.將B號柱上的n-1個圓盤通過A移動到C號柱上。**
有此可知該問題可以用一遞歸的思想來解決，實現代碼如下：
~~~
//漢諾塔問題，遞歸
//時間復雜度，設有n個盤 f(n) = 2f(n-1)+1 = 4f(n-2) + 2 + 1 = pow(2, n-1) + pow(2, n-2) + `````+ 4 + 2 + 1
//等積數列 可知最后 f(n) = pow(2, n)-1;
#include <iostream>
using namespace std;
int g_nTimesUsed = 0;
void Hanoi(int nDisk, char A, char B, char C)
{
if (nDisk == 1)
{
cout<<"moved the "<<nDisk<< " Disk from "<<A <<" to "<<C<<endl;
g_nTimesUsed++;
return;
}
else
{
Hanoi(nDisk-1, A, C, B);
cout<<"moved the "<<nDisk<< " Disk from "<<A <<" to "<<C<<endl;
g_nTimesUsed++;
Hanoi(nDisk-1, B,A, C);
}
}
int main()
{
int nBow = 0;
cout<<"輸入塔A上的盤數目"<<endl;
cin>>nBow;
Hanoi(nBow, 'A','B','C');
cout<<endl<<"used "<<g_nTimesUsed<<" times"<<endl;
system("pause");
}
~~~
本系列(趣味算法系列)內的部分問題題目來自：經典算法大全 老奔整理? Email: [ben0133@163.com](#)
