|
一. 算法介绍： 分治算法，其实就是把一个大问题看成若干个小问题，解决了所有的小问题，那么大问题就解决了，原问题的解就是子问题解的合并，之前说的归并排序、快速排序，都用到了分治思想。 二. 分治算法的基本步骤： 分解：将原问题分解成若干个相互独立的、规模较小的、容易求解的、与原问题形式相同的子问题；
三. 分治算法经典应用：汉诺塔问题 1. 汉诺塔问题介绍：  汉诺塔 汉诺塔问题介绍2. 怎么玩？  玩法3. 思路分析： 我们先给3根针标上号，左边的是A，中间的是B，右边的是C。 假如有两个盘，那就把上面那个从A移动到B，把底下那个从A到C，再把B中的移到C； 假如有多个盘，我们也可以按照两个盘的方式处理。即把最下边的看成一个盘，其他所有的看成一个盘；当然这里其他所有的还可以按照这种方式再进行分治。
4. 代码实现： public class HanoiTower {
/**
* 汉诺塔问题
* @param plateNum 盘子的数量
* @param a 出发地，初始的时候是A
* @param b 中转地，初始的时候是B
* @param c 目的地，初始的时候是C
*/
public static void hanoiTower(int plateNum, String a, String b, String c) {
if (plateNum == 1) {
System.out.println("从 " + a + " 到 " + c);
} else { // 盘子数量大于等于2的情况
// 上面的从A到B
hanoiTower(plateNum - 1, a, c, b);
// 最下面那个从A到C
System.out.println("从 " + a + " 到 " + c);
// B针上的所有搬到C
hanoiTower(plateNum - 1, b, a, c);
}
}
public static void main(String[] args) {
hanoiTower(5, "A", "B", "C");
}
}
怎么验证对不对呢？打开4399或者7k7k，搜索汉诺塔，选择盘子的数量，运行代码，按照代码打印的结果去玩这个游戏，就知道对不对了。
|
