欢迎前往个人博客 驽马点滴 和视频空间 哔哩哔哩-《挨踢日志》
【问题】
a,b,c是三个塔座。开始时，在a上共有n个圆盘，自上而下，圆盘由小到大。编号分别为1,2,...,n. 现在要通过b塔把圆盘从a塔移动到c塔.试写出移动过程hanoi(n,a,b,c).
【解答】
建模
我们记录每一次转移为 x -> y 其中 x~=y， x, y从{a, b, c}中取值
那么问题就是要给出一些列的转移的有序集合，使得按照集合中的步骤，能够将n个盘从a移动到c
这里有3个塔： a、b、c，由于a是起始塔，而c是目标塔，b就是辅助塔，于是需要引入3个变量：起始塔、目标塔、辅助塔
同时还有一个由圆盘组成的堆的概念。有一个变量n用于描述这个堆的大小，因为我们不希望打乱堆的从上到下的圆盘是由小到大的布局，所以，n就唯一决定了这个堆的特性。
显然，我们接触到n这个变量，自然希望使用数学归纳法来解决这样的问题，于是问题，应当考虑将n的情形转化为n-1的情形，从而通过递归完成我们的解决方案。
首先我们假定解决方案是一个关于 n 和 起始塔、辅助塔、目标塔 的函数 hanoi(n, 起始塔, 辅助塔, 目标塔)
表示n个圆盘，从起始塔，通过辅助塔移动到目标塔的解决方案。
那么我们需要求解的问题就是：hanoi(n, a, b, c)
而 hanoi(n, a, b, c)的解决方案是一个步骤方案，于是我们又可以将这个过程视为3大步骤：
- 先将a上面的n-1个盘组成的堆从a，借助辅助塔c，转移到b的解决方案hanoi(n-1, a, c, b)
- 将第n个盘移动到c： hanoi(1, a, b, c)
- 再将b上面的n-1个盘组成的堆从b，借助辅助塔a，转移到c的解决方案hanoi(n-1, b, a, c)
于是递归算法如下：
void LankeHelper::hanoi(int n, char a, char b, char c){
if(n==1)
{
cout<<a<<"->"<<c<<"\n";
}
else {
hanoi(n-1,a,c,b);
hanoi(1, a, b, c);
hanoi(n-1,b,a,c);
}
}
int _tmain(int argc, _TCHAR* argv[]){
LankeHelper lh;
lh.hanoi(2,'a','b','c');
system("pause");
return 0;
}
欢迎前往个人博客 驽马点滴 和视频空间 哔哩哔哩-《挨踢日志》
