通过汉诺塔深入理解递归流程。

淡淡的烟草味﹌ 2022-05-28 23:52 182阅读 0赞

苦于复试的递归dfs问题，久久不得求解。最终决定重新来一遍大一的流程，重新了解学习递归。  
**目录**

*  汉诺塔问题简介：
 *  模型详细分析
    
     *  递归三要素：
     *  递归流程分析
 *  代码实现

# **汉诺塔问题简介：** #

在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片，1. 一次只移动一片； 2. 不管在哪根针上，小片必在大片上面。当所有的金片都从梵天穿好的那根针上移到另外一概针上时，世界就将在一声霹雳中消灭，梵塔、庙宇和众生都将同归于尽。  
我们来看下三层汉诺塔模型图解。  
![这里写图片描述][20180313111946655]

# **模型详细分析** #

![这里写图片描述][20180313112032811]  
**我们先给盘子编号，从上到下分别是1~n,盘子越大，编码越大。**  
我们首先假设要把n个金片从宝针‘A’移动宝针‘B’，还有有另外一根’V’可以借用。  
如果n = 1，那么直接从 A->B 即可。  
如果n = 2，那么先把A最上面（第一个）金片移动到V，暂且放一下，然后第二个金片移动到B目的地，接着再把V上面的移动到B目的地，所以移动的次序是 A->V, A->B, V-B。  
如果n = 3，可以这么考虑: 先不看出发地A最下面一个最大的金片，先解决怎么把上面两个移走，方法我们已经知道了，但是移到哪里呢？只有B, V可选，B肯定是不行，因为B是目的地，那么只能是通过B先把两个金片移动到V（A->B, A->V, B->V），然后最下面那个最大的金片移动到目的地B（A->B）。注意这时B上面仅有这个最大的金片，A上面空的，V上面有两个金片。接着把V上面两个金片借由A移动到B（V->A, V->B, A->B）。这个的具体步骤，我们可以看动态图。  
如果n = 4, 同样的不考虑最大的一个，先把前三个移动到V，使用上面介绍的移动次序。  
以此类推（其实 n = 2时，也可以看作是先解决最上面一个的问题，然后才是把最下面的金片移动到目的地）  
通过分析，发现解决n个金片的方法是先借由B,把n-1个移动到V，然后把A最下面一个移动到B，在然后借由A把V上面n-1移动到B。  
综上所述，我们得到了三个核心步骤。

*  那坨N-1个盘子从A针移动到V针（递归过程）
 *  将最大的盘子N号从A针移动到C针
 *  将那坨N-1个盘子从V针移动到C针（递归过程）

## **递归三要素：** ##

*  一定有一种可以退出程序的情况；
 *  总是在尝试将一个问题化简到更小的规模
 *  父问题与子问题不能有重叠的部分

## **递归流程分析** ##

*  要解决N个盘子的移动问题，我们无法解决，我们先要解决N-1个盘子的移动问题，要解决N-1个盘子的问题，我们又需要先解决N-2个盘子的问题，直到n=1。（我们不断地将一个复杂的问题化简到同类型的规模更小的问题）
 *  当n=1的时候，我们终于能够解决当下的问题了，不用再去解决其他的问题了（我们也叫这种情况叫做递归出口）
 *  我们知道了n=1的实现过程，然后我们开始尝试n=2的解决。然后开始N=3…直到最后我们解决了最开始的问题。不忘初心。

**知乎上有大神曾经说递归有时候更像去查字典，我们一开始想要知道这句话什么意思，里面有词语不认识，查字典，字典的解释又有新的我们不认识的词语，然后一直查找，直到我们弄懂了，我们开始回去理解上一层词语的意思，不断往上，直到最后我们理解了最初的那句话的意思。**

# **代码实现** #

#include<iostream>
    #include<string.h>
    #include<stdio.h>
    using namespace std;
    void solve(int n,char src,char dst,char temp){
        if(n==1){
        //递归出口 
            cout<<src<<"-->"<<dst<<endl;
            return ;
        }
        solve(n-1,src,temp,dst);//将n-1块盘从src盘移动到temp盘，依靠dst做中介 
        cout<<src<<"-->"<<dst<<endl;//将最大的盘从目标盘移动到dst盘
        solve(n-1,temp,dst,src);//将temp上的一坨盘移动到目标盘即可 
    }
    int main(){
        int num;//输入汉诺塔的数量 
        cin>>num;
        solve(num,'A','B','V');//解决从A移动到B的问题,V是中间盘 
    }

**对递归的理解，最好的方法就是放弃一部分理解，只考虑当下，比如我们要处理规模为n的问题的时候，完全把n-1的规模当成已解决的问题去看待会好很多。放弃理解全局，尝试着只去理解一部分。**

[20180313111946655]: /images/20220529/bfa6232a27a94881a60c9e473c9c1e48.png
[20180313112032811]: /images/20220529/7034a61890e745489d9ae4b313eb7ab1.png