汉诺塔递归

虽然知道思路但是想知道代码的每一步是怎么搞

一、什么是汉诺塔

汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

汉诺塔问题的实质

• 汉诺塔问题的解决一般是用递归来实现的；
• 递归就是函数调用自己；
• 函数的调用一般是用栈来实现的；

所以要想从本质上了解汉诺塔问题的求解，一定要从“栈”的角度来看问题。

思路

首先假设只有一个圆盘，我们将其编号为1，那么这时候只需要将A直接移到C即可：

二个圆盘

步骤1：先将1号盘从A移动到B；

步骤2：再将2号盘从A移动到C；

步骤3：最后将1号盘从B移动到C，完成转移。

首先三个圆盘放在A柱上，按从上到下的顺序依次编号为1,2,3（最小的为1，最大的为3），我们先不考虑3号盘，而只考虑上面两个小一点的圆盘（编号1,2），而此前我们已经分析了两个圆盘的移动过程，那么这两个圆盘该移动到哪根柱子呢？目前只有B柱,C柱可选，而C柱肯定不行，因为C柱是目标柱，那么我们只能把1,2号盘从A柱移动到B柱，借助C柱，则移动过程为：A->C, A->B,C->B。此时，1,2号盘已经到达B柱，再把最大的三号盘，直接移到C柱。此时工作快要完成了，目前的状态为：1,2号盘在B柱，3号盘已到达目的柱C柱，再接下来，把1，2号盘将B柱移动到C柱，转移工作就彻底结束，借助A柱，转移过程为：B->A,B->C,A->C。

通过上面第一段加红的文字，我们可以知道，A是作为起始柱，B作为目标柱，C作为辅助柱，通过第二段加红文字，我们可以知道，B是作为起始柱，A作为辅助柱，C作为目标柱。

这样我自己觉得在脑袋里面还不清晰

代码：

#include <iostream>
using namespace std;

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

int main()
{

   hanoi(3,'A','B','C');
   return 0;

}
void Move_print(int h,char a,char c)
{
    cout << h << ":"<<a<<"->" <<c << endl;
}
void hanoi(int n,char a,char b,char c)
{
    if(n==1)
    {
        cout <<n <<":" << a << "->" << c << endl;


    }else
    {
        hanoi(n-1,a,c,b);
        Move_print(n,a,c);
        hanoi(n-1,b,c,a);
    }


}

详细图解分析

• 每次调用都会先把自己当前的参数和返回的地址（就是回来的时候回到哪）给push进栈来保存

• 当前运行函数的参数值总是保存在栈顶

• 大体上向左的箭头是函数的递归调用（编译系统是用栈来实现的）也就是一路向左

• 大体上向右的箭头是返回调用函数的下一句代码继续执行，也就是一路向右

参数是怎么变化的