关于java:Java算法系列分治算法一

39次阅读

共计 1077 个字符，预计需要花费 3 分钟才能阅读完成。

【写在后面】

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

数据结构相干算法

八大排序算法：冒泡排序、抉择排序、插入排序、希尔排序、疾速排序、归并排序、基数排序、堆排序

四大查找算法：线性查找、二分查找、插值查找、斐波那契查找

九大罕用算法：分治算法、动静布局算法、KMP 算法、贪婪算法、Prim 算法、Kruskal 算法、Dijkstra 算法、Floyd 算法、骑士环游回溯算法

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

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

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

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

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

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

有三根杆子 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);
        }
    }
}