汉诺塔（河内塔）问题
最后更新于：2022-04-01 10:11:34
汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着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](#)