汉诺塔问题（递归思想）

淡淡的烟草味﹌ 2023-07-13 08:18 96阅读 0赞

# 问题描述： 有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆： 每次只能移动一个圆盘； 大盘不能叠在小盘上面。 提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须遵循上述两条规则。问：如何移？最少要移动多少次？ #

![在这里插入图片描述][20200311105021967.png]

# 解决思路： #

将A中的盘按要求移到C盘，分解为，将C中的n-1个移到B盘，再将A的最后一个盘移到C盘，最后将B中的n-1个盘按要求借助A盘移动到C盘。  
上源码：

#include<stdio.h>
    #define N 3
    int count=1;
    void move(char ch1,char ch2)
    { 
    	printf("第%d次移动：%c ---> %c\n",count++,ch1,ch2);
    }
    void han_ta(int n ,char A,char B, char C)//n为圆盘的个数
    { 
    	if(n==1)//递归出口
    	{ 
    		move(A,C);//将A盘移动到C盘
    	}
    	else
    	{ 
    		han_ta(n-1,A,C,B);//将A上方的n-1个盘通过C移动到B
    		move(A,C);//将A中的最后一个原盘放到C
    		han_ta(n-1,B,A,C);//将B中的n-1个圆盘通过A移动到C
    	}
    }
    int main()
    { 
    	han_ta(N,'A','B','C');
    	return 0;
    }

核心代码：

void han_ta(int n ,char A,char B, char C)//n为圆盘的个数
    { 
    	if(n==1)//递归出口
    	{ 
    		move(A,C);//将A盘移动到C盘
    	}
    	else
    	{ 
    		han_ta(n-1,A,C,B);//将A上方的n-1个盘通过C移动到B
    		move(A,C);//将A中的最后一个原盘放到C
    		han_ta(n-1,B,A,C);//将B中的n-1个圆盘通过A移动到C
    	}
    }

思考：递归是内部是怎么实现的？这是我们要思考的问题，我们知道递归算法，我们可以通过栈替换，递归的过程就是一个出入栈的过程。我敢肯定遇到递归算法，你肯定会根据代码，代数进去验证结果，结果一头雾水，越想越懵。这边建议去思考[递归内部实现][Link 1]。

[20200311105021967.png]: /images/20230529/7aa2d38de8c74853a3f791a64f61c8c7.png
[Link 1]: https://blog.csdn.net/Butterfly_resting/article/details/79827893?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task