- 面试题 08.06. 汉诺塔问题
- 确定大致思路
- 递归三部曲
- 递归终止条件
- 确定传入参数
- 确定完成递归的步骤
- 整体代码
此题是一道经典的递归问题
递归的原理就是需要将问题的规模缩小，直到最简的情况，此题便是只有一个盘的情况。
动画演示思路：链接: 图解汉诺塔的故事
遵循递归的思路，由结果推过程。
首先我们看最简单的情况，就是只有一个汉诺塔。毫无疑问，只需将A处的盘挪到C即可。
然后再是两个塔的情况：
就是先将最后一个盘上的那个盘移动到B，再将底盘移动到C，最后将上面那个盘移动到C即可
再推广，解决5个汉诺塔问题，可以将上面四个盘视为一个整体，像两个盘的情况一样，先将4个盘挪到B，将红色盘挪到C，再进行一系列操作将四个盘挪到C，图解如下：
至此，我们便大致分析出了递归思路：
- 将移n个塔问题简化为将n-1个塔挪到B
- 再将第n个盘挪到C
- 再经过一系列操作将n-1个塔挪到C
此时，看似又有一个新问题出现了：一系列操作又是什么？
很简单，我们不需要仔细分析这一系列操作的步骤，只需关注它实现的功能即可。将n-1个盘挪到B，这个步骤是不是有些眼熟？没错，就和问题开始将A处的盘挪到C一摸一样，这个操作就是将我们原本的递归函数又调用了一遍。至此我们完全找到了递归的思路。
递归三部曲 递归终止条件注意：递归问题中尤其要注意递归方法本身的含义。
- 递归函数本身就是一个功能完善的方法，此题递归函数的作用就是解决n个塔从A移动到C的问题。
- 即这个函数的功能就是将给定的n个盘从指定位置挪到目标位置
- 我们通过上述分析简化了问题，让问题规模越来越小，试想一下，将盘移动到最后，是不是就是将最上面的小盘放到C？这一步的操作我们肯定会写。至此我们便完成了递归的全过程。
上面我们分析到简化为只有一个盘的情况，再把那一个盘挪到C，我们便解决了整个问题。
所以，我们的递归终止条件就是：只有一个盘的情况
再进一步思考，我们该如何知晓只剩一个盘的情况呢？ 很简单，我们只需设置一个参数size表示需要挪动的塔的数量即可
if(size==1){
target.add(start.remove(start.size()-1));
return ;
}
确定传入参数
- size：上面我们已经分析到，我们需要知道要移动的汉诺塔的个数
- A B C ：通过上面的过程分析，我们每次需要将塔移动到不同的柱子中，我们就自然要根据移动汉诺塔到不同的位置这一动作，用三个不同的参数表示
根据分析，我们确定最后的参数如下：
private void remove(int size,List确定完成递归的步骤start,List auxiliary,List target)
将最底下的一个盘挪到目标位置，需要进行三个步骤：
- 将上面n-1个盘挪到中间柱子
- 将最后一个盘挪到目标柱子
- 再将n-1个盘挪到目标柱子
根据上述三个步骤，挪动过程代码如下：
//先把第一根柱子上size-1个盘移到第二根柱子上
remove(size-1,start,target,auxiliary);
//再把第一根柱子上的最后一个盘放到第三根柱子中
target.add(start.remove(start.size()-1));
remove(size-1,auxiliary,start,target);
整体代码
class Solution {
public void hanota(List A, List B, List C) {
remove(A.size(),A,B,C);
}
private void remove(int size,List start,List auxiliary,List target){
//递归终止条件
if(size==1){
target.add(start.remove(start.size()-1));
return ;
}
//单层中进行的操作
//先把第一根柱子上size-1个盘移到第二根柱子上
remove(size-1,start,target,auxiliary);
//再把第一根柱子上的最后一个盘放到第三根柱子中
target.add(start.remove(start.size()-1));
remove(size-1,auxiliary,start,target);
}
}
总结：
- 想要理清递归的思路，需要找到将问题规模化小且重复同一个动作的方法
- 找出递归过程后，分析递归三部曲，可以更好地理清思路，写出最终的代码
