汉罗塔问题 (递归分治篇)------- 算法笔记016

旧城等待， 2023-07-04 14:21 24阅读 0赞

## 概念解读 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz_size_16_color_FFFFFF_t_70]

> 其实汉罗塔问题的实质就是利用眼前的这三根柱子，一次只能移动一个圆盘，其中一根作为中介柱，使一根柱子上的圆盘移到另一根上。在移动的过程中不能出现大的圆盘套在小的圆盘的上面。  
> 其实这个问题体现了递归的思想，上面的三种情况列举出来以体现问题的递归性。

上面图片的解释并不完备!  
以三个汉罗塔举例：我们要将a柱上的汉罗塔全部移到c上，b柱为中转柱

> 第一步：我们要设法将a柱上前两个移到b上，再将a柱上最后一个移到c上  
> 第二步：如何将a柱上的前两个移到b上？就是将第一个移到c上将第二个移到b上  
> 第三步: 现在思考如何将c柱上的移到b上？很显然就是一个我们直接一上去。这样就完成了我们第一步的前两个移到b上的步骤。再将a柱上最后一个移到c上。  
> 递归步：现在思考的就是如何将b上的两个，或者是N-1个移到c上的操作。继续重复的操作

以此思想我们可以设计递归算法算法：

void Hanoi(int n,char a,char b,char c){ 
    	
    	//判断条件当只剩一个汉罗塔的时候执行参数a这个柱子->参数b这个柱子
    	//初始传值A,B,C对于a,b,c这三个参数，所以当A柱只有一个汉罗塔时就是A->C的操作
    	if(n==1){ 
    		printf("%c->%c\n",a,c); 
    		return; 
    	}
    	//底下就是递归的操作了
    	//如果不止一个汉罗塔，就开始将前n-1个汉罗塔执行a->b的操作
    	Hanoi(n-1,a,c,b);
    	//如果完成了前n-1个汉罗塔从a->b的操作，我们就将a上的最后一个移到c上
    	printf("%c->%c\n",a,c);
    	//这时候再执行b上汉罗塔，到c上的操作
    	Hanoi(n-1,b,a,c);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200211231935319.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz,size_16,color_FFFFFF,t_70