【专题一 递归】面试题 08.06. 汉诺塔问题
1.题目解析
2.讲解算法原理
- 如何解决汉诺塔问题？
- 为什么可以用递归?
大问题 ->相同类型的子问题
子问题 -> 相同类型的子问题
- 如何编写递归代码？
- 重复子问题 ->函数头
- 将x柱子上的一堆珠子,借助y柱子，转移到z柱子上→void dfs(x,y,z,n)
- 只关心某一个子问题在做什么 ->函数体
- dfs(x，z，y,n-1)--> x.back()→ z -->dfs(y,x,z, n-1)
- 递归的出口
- N=1
- 重复子问题 ->函数头
3.编写代码
class Solution {
public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
dfs(A,B,C,A.size());
}
public void dfs(List<Integer> A, List<Integer> B, List<Integer> C,int n){
if(n==1){
C.add(A.remove(A.size()-1));
return;
}
dfs(A,C,B,n-1);
C.add(A.remove(A.size()-1));
dfs(B,A,C,n-1);
}
}