（如有冒犯可联系删图）   普通汉诺塔       欢迎点赞和收藏，有想法的小伙伴可以在评论区一起交流和探讨~       [达成共识]      汉诺塔（港台：河内塔）（Tower of Hanoi）是根据一个传说形成的数学问题：    有三根杆子A，B，C。A杆上有 N 个 (N>1) 穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：        每次只能移动一个圆盘；        大盘不能叠在小盘上面。       可以将圆盘临时置于 B 杆，也可将从 A 杆移出的圆盘重新移回 A 杆，但都必须遵循上述两条规则。     [抱大腿]         对于这个问题可以从简单的看起，然后发现规律。从规律中摸索出解决这个问题的办法。通常汉诺塔被作为学习递归的入门案例。一起吃透汉诺塔思想及其变形的题目！     我们从只有一个盘子的时候开始研究。很简单，直接把红色的盘子移到B上就可以了。          现在我们来研究两个盘子的情况：        我们的思路是先把最底下的大盘子放到B上，但是由于盘子大小不一样，所以我们得想办法先把上面的盘子放到C上，这样才可以把下面的大盘子放到B上，再把上面的小盘子放到B上           步骤：   1. 红色盘子移到C上2. 黄色盘子移到B上3. 红色盘子移到B上   此时两个盘子都在B上，并且红色盘子在黄色盘子上面     接下来再来看三个盘子的情况        要都放到B上，就必须先把蓝色上面的两个盘子想办法移到C 上，这样才能把蓝色的盘子移到B上。因此，先把红色和黄色移到C上，现在问题变成了只有两个盘子的情况，也就用到了上面的三步。然后再把蓝色盘子移到B上。最后把黄色和红色盘子移到B上，也就又回到了上面只有两个盘子的情况。           步骤：   1. 把红色盘子移到B上2. 把黄色盘子移到C上3. 把红色盘子移到C上4. 把蓝色盘子移到B上5. 把红色盘子移到A上6. 把黄色盘子移到B上7. 把红色盘子移到B上      可见，完全可以把三个盘子的情况转化成两个盘子的情况，然后得以解决。     根据上面的规律可以知道：    n盘子从A移动到B   =   先把 n - 1 个盘子从A移动到C   +  把最底下的盘子移动到B  + 最后把 n - 1个盘子从C移动到B上     即 ： 公式 H ( n ) = H ( n - 1 )  +  1  + H ( n - 1 )        数学方法适合计算移动的次数，递归法计算次数和显示移动路径均可，后同。     现在思路清楚了，它有两种解法：     解法一(数学方法)：   //换元法+数学归纳法H( n ) = H( n - 1 ) + 1 + H( n - 1 )       = 2 * H( n - 1 )  +  1//两边同时加1H( n ) + 1 = 2 * [ H( n - 1 ) + 1 ]//令U( n ) = H( n ) + 1H( n ) + 1 = 2 * [ H(n - 1 ) + 1 ]//则可变为U( n ) = 2 * U( n - 1 )           = 2^2 * U( n - 2 ) = ······       = 2^(n-1) * U(1) = 2^n//因此解得 H( n ) = 2^n - 1   解法二（递归法）：   unsigned int count = 0;void hanio(int n,char A,char B,char C){    if(n==1)       cout<<"Put "<<n<<" from "<<A<<" to "<<B<<endl;// 如果只有一个，那么把这个盘子直接放到B上就可以       count += 1;    else    {       hanio(n-1,A,C,B);    //借助B把前n-1个盘子从A移动到C上       cout<<"Put "<<n<<" from "<<A<<" to "<<B<<endl;    //把最下面的盘子从A移动到B上       count += 1;       hanio(n-1,C,B,A);   //借助A把刚才上面的n-1个盘子从C移动到B上}   变形题1（变化条件）：    假如有2N个盘子，盘子种类有N种，并且每种盘子有两个（这两个大小和颜色完全相同）        以前移动1个盘子：例如红色移动到C上，现在无非就是把两个红色的移动到C上，因为这两个盘子完全一样，所以只要把原来的移动一次，现在改成移动两次就可以了     新2n盘子从A移动到B   =   2 * 之前n个盘子移动次数     因此，依然有两种解法：     解法一(数学方法)：   //换元法+数学归纳法//G(n)代表新的规则下的移动次数G( n ) = 2 * H( n )       = 2 * ( 2^n - 1 )       = 2^(n + 1) - 2   解法二（递归法）：   unsigned int count = 0;void hanio(int n,char A,char B,char C){    if(n == 2 ){       cout<<"Put "<<n<<" from "<<A<<" to "<<B<<endl;// 如果只有两个，那么把这两个盘子直接放到B上就可以       cout<<"Put "<<n-1<<" from "<<A<<" to "<<B<<endl;       count += 2;    }    else    {       hanio(n-2,A,C,B);    //借助B把前n-2个盘子从A移动到C上       cout<<"Put "<<n - 1<<" from "<<A<<" to "<<B<<endl;    //把最下面的两个盘子从A移动到B上       cout<<"Put "<<n<<" from "<<A<<" to "<<B<<endl;    //       count += 2;       hanio(n-2,C,B,A);   //借助A把刚才上面的n-2个盘子从C移动到B上}   变形题2（变化条件）：    假如A和B直接不能直接移动，那么怎么解决？        既然不能直接在A和B直接移动，那么想从A移动到B，或者从B移动到A，都需要借助C来实现，先移动到C再移动到A或B     步骤：    1. 先把 n - 1 个通过C移动到B上  2. 把最底部的移动到C上 3. 再通过C把B上的n-1个移动到A上 4. 把底部的移动到B上 5. 最后把n - 1 个通过C移动到B上   移动n个盘子需要的次数 =  通过C移动n-1个盘子到B的次数  +  把最底部移动到C上的次数 + 通过C再次移动n-1个盘子到A的次数 + 把最底部盘子移动到B上次数 + 通过C把n-1个盘子移动回B的次数     因此，依然有两种解法：     解法一(数学方法)：   //为了区别此处改为G(n)G( n ) = G( n - 1 ) + 1 + G( n - 1 ) + 1 + G( n - 1 )// 同理,此次省略数学推导过程,证明思路和第一个一样,有兴趣可以联系作者       = 3^n - 1   解法二（递归法）：   unsigned int count = 0;void hanio(int n,char A,char B,char C){    if(n == 1 ){       cout<<"Put "<<n<<" from "<<A<<" to "<<B<<endl;// 如果只有一个，那么把这个盘子先放到C上       cout<<"Put "<<n<<" from "<<C<<" to "<<B<<endl;// 把这个盘子再放到B上       count += 2;    }    else    {       hanio(n-1,A,B,C);                                   //把n-1个通过C移动到B上        cout<<"Put "<<n<<" from "<<A<<" to "<<C<<endl;    //把最底部的移动到C上       count += 1;       hanio(n-1,B,A,C);                                //再通过C把B上的n-1个移动到A上       cout<<"Put "<<n<<" from "<<C<<" to "<<B<<endl;    //把底部的移动到B上       count += 1;               hanio(n-2,A,B,C);                                   //最后把n-1个通过C移动到B上}      [击掌]      一起在评论区交流和讨论吧~      往期精彩：   小白也能进大厂：希望我走过的路，你可以拥有捷径 面试高频考题TCP协议:理论+实践让你拿捏面试官（上）