- 分治算法的介绍
- 经典问题
- 基本步骤
- 汉诺塔
- 思路分析
- 代码实现
1.分治算法的介绍
- 分治算法。字面意思就是 “分而治之” 。 就是把一个复杂的问题分成多个相同或相似的子问题，再把子问题分成更小的子问题....直到最后的子问题可以简单的直接求解，原问题的解即子问题解的合并。
2. 分治算法的经典问题
- 二分搜索
- 大整数乘法
- 棋盘覆盖
- 合并排序
- 快速排序
- 线性时间选择
- 最接近点对问题
- 循环赛日程表
- 汉诺塔
3. 基本步骤
- 分治法在每层递归都有三个步骤
分解： 将原问题分解为若干个小规模的与原问题形式相同的子问题
解决： 若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
合并： 将各个子问题的解合并为原问题的解
4. 汉诺塔
-
思路分析：
(1)如果有一个盘，
A->C如果
n >= 2的情况，可以看作是两个盘，1.最下边的盘，2.上面的盘(2) 先把 最上面的盘 从 A移到B
(3) 把最下边的盘从 A 移到 C
(4) 把 B 的所有盘移到 C
代码实现
public class Hanoitower {
public static void main(String[] args) {
hanoiTower(5,'A','B','C');
}
//汉诺塔的移动方法
//使用分治算法
public static void hanoiTower(int num,char a,char b,char c){
//如果只有一个盘
if(num == 1){
System.out.println("第1个盘从" + a + "->" +c);
}else {
//如果n>=2情况，我们总是可以看作两个盘，1.最下面的盘，2.上面所有的盘
//1.先把最上面所有盘 A-> B,移动过程会使用到c
hanoiTower(num - 1,a,c,b);
//2.把最下边的盘 A->C
System.out.println("第" + num + "个盘从" + a + "->" + c);
//3.把B塔的所有盘从 B->C
hanoiTower(num - 1,b,a,c);
}
}
}
