分治算法

分治算法

分治算法，其实就是把一个大问题看成若干个小问题，解决了所有的小问题，那么大问题就解决了，原问题的解就是子问题解的合并，之前说的归并排序、快速排序，都用到了分治思想。

1.基本步骤

• 分解：将原问题分解成若干个相互独立的、规模较小的、容易求解的、与原问题形式相同的子问题；
• 解决：直接求解子问题或者递归求解子问题；
• 合并：将各个子问题的解合并为原问题的解。

2.经典应用：汉诺塔问题

问题介绍

2. 怎么玩？

3. 思路分析：

我们先给3根针标上号，左边的是A，中间的是B，右边的是C。

• 假如只有一个盘，那就直接从A移动到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");
 }
}