汉诺塔

淡淡的烟草味﹌ 2022-11-02 13:14 49阅读 0赞

### 汉诺塔 ###

*  1.目标
 *  2.思路（算法 ）
 *  3.实现
 *  4.总结（如何理解这个算法）
 *   *  注意：

# 1.目标 #

目标很明确就是将下图中A柱子上的盘子全部搬在C柱子上。小的盘子必须在大的盘子上面。  
![在这里插入图片描述][20210225143834607.png]

# 2.思路（算法 ） #

要将A中的所有盘子放在C上面，那么需要将A中除了最下面那个盘子的其他盘子都放在B上面才可以。最后再将A最下面的盘子放在C上面就完成一块了。

于是我们可以提炼上面的思路，每次都把除了最下面的盘子之外的其他盘子放在除了目标柱子（C）之外的另一个柱子（可能A可能B）上，然后在放最后一块盘子即可。于是就可以使用递归的思路实现。

重点思路：要把最下面盘子之外的其他盘子，都放在除了目标柱子的另一个柱子上，即可。

# 3.实现 #

void hanoi(int n, char one, char two,char three)
    { 
    	void move(char x,char y);
    	if(n== 1)
    	move( one, three) ;  //将第一个最下面的那块盘子放到第三个柱子上
    	else{ 
    		hanoi(n-1 ,one, three, two);  //将n-1块的盘子放到第二个柱子上
    		move( one, three);  //将第一个最下面的那块盘子放到第三个柱子上
    		hanoi( n一1，two, one, three) ;  //第二个柱子上的将n-1块盘子放到第三个柱子上。
    	}
    	
    }

# 4.总结（如何理解这个算法） #

如果读者还是不能够很好的理解这个算法，我觉得应该这样想。将思路变得整体起来，要目标变得很明确，它就是在重复一个事：即  
1.将n-1块放在一个柱子上。  
2.将最后的一块放在另一个柱子上。  
3.将刚才的n-1再次重复第1.2步。比如，又将n-2块放在一个柱子上，将第n-1块放在目标柱子上，再对刚才的n-2块进行重复的操作。

## 注意： ##

千万别把注意力放在`hanoi(n-1 ,one, three, two);`此类代码上，去纠结为什么要交换three，two的位置，或者去思考交换之后，接下来应该怎么做。这样容易陷入无限递归的情况，然后越想越乱。

面对递归我们应该注意的是递归出口（即什么时候结束递归），和递归中需要做的事（比如这里的`move( one, three) ;`）。时时刻刻记住递归函数的目标（比如`hanoi(n-1 ,one, three, two);`就是将n-1块放在two柱子上），保持整体的思路，别去纠结细节，这样更容易理解和运用。

[20210225143834607.png]: /images/20221024/875b9f6c38e34cf6bd2eaf400eeaefa7.png