【写在后面】

“Java算法系列”目录如下（更新ing）：

  • 数据结构相干算法
  • 八大排序算法：冒泡排序、抉择排序、插入排序、希尔排序、疾速排序、归并排序、基数排序、堆排序
  • 四大查找算法：线性查找、二分查找、插值查找、斐波那契查找
  • 九大罕用算法：分治算法、动静布局算法、KMP算法、贪婪算法、Prim算法、Kruskal算法、Dijkstra算法、Floyd算法、骑士环游回溯算法

本篇为九大罕用算法之分治算法。

分治算法的步骤

分治算法在每一层递归上都有三个步骤：

  1. 合成：将原问题合成为若干个规模较小、互相独立、与原问题模式雷同的子问题。
  2. 解决：若子问题规模较小而容易被解决则间接解决，否则递归地求解各个子问题。
  3. 合并：将各个子问题的解合并为原问题的解。

分治算法的经典例题

分治算法能够求解的经典问题包含：

  1. 二分搜寻（待补充）
  2. 大整数乘法
  3. Strassen矩阵乘法
  4. 棋盘笼罩
  5. 合并排序（待补充）
  6. 疾速排序（待补充）
  7. 线性工夫抉择
  8. 最靠近点对问题
  9. 循环赛日程表
  10. 汉诺塔

上面以“汉诺塔问题”为例阐明分治算法的思维。

汉诺塔问题

有三根杆子A、B、C。A杆上有若干盘子。每次挪动一块盘子，小的只能叠在大的下面。把所有盘子从A杆全副移到C杆上。

设n为盘子的数量。

  • 对于 n=1 的状况，间接将盘子从A杆挪动到C杆。

  • 对于 n≥2 的状况，能够将问题合成为：

    • 把 n-1 个盘子从A挪动到B；
    • 把第 n 个盘子从A挪动到C；
    • 把 n-1 个盘子从B挪动到C。

    那么，怎么把 n-1 个盘子从一根杆子挪动到另一根杆子上呢？能够先把 n-2 个盘子先挪动，再挪动第 n-1 个盘子……这就是分治法的思维。

因而能够很容易地写出汉诺塔问题的算法：

public class HanoiTower {    public static void main(String[] args) {        int n = 5;        hanoiTower(n, 'A', 'B', 'C');    }    public static void hanoiTower(int num, char a, char b, char c) {        // 对于 n = 1 的状况，间接将盘子从A杆挪动到C杆。        if (num == 1) {            System.out.println("第" + num + "个盘: " + a + " -> " + c);        }        // 对于 n ≥ 2 的状况        else {            // 把 n - 1 个盘子从A挪动到B；            hanoiTower(num - 1, a, c, b);            // 把第 n 个盘子从A挪动到C；            System.out.println("第" + num + "个盘: " + a + " -> " + c);            // 把 n - 1 个盘子从B挪动到C。            hanoiTower(num - 1, b, a, c);        }    }}

参考资料

  1. 尚硅谷：Java数据结构与算法
  2. 分治算法详解及经典例题