常用十大演算法（二）— 分治演算法
博客說明
文章所涉及的資料來自互聯網整理和個人總結，意在于個人學習和經驗匯總，如有什么地方侵權，請聯系本人洗掉，謝謝！
介紹
分治法是一種很重要的演算法，字面上的解釋是“分而治之”，就是把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并，這個技巧是很多高效演算法的基礎，如排序演算法(快速排序，歸并排序)，傅立葉變換(快速傅立葉變換)
分治演算法實踐
- 二分搜索
- 大整數乘法
- 棋盤覆寫
- 合并排序
- 快速排序
- 線性時間選擇
- 最接近點對問題
- 回圈賽日程表
- 漢諾塔
分治演算法的步驟
分治法在每一層遞回上都有三個步驟：
- 分解：將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題
- 解決：若子問題規模較小而容易被解決則直接解，否則遞回地解各個子問題
- 合并：將各個子問題的解合并為原問題的解，
分治(Divide-and-Conquer(P))演算法設計模式
if |P|≤n0
then return(ADHOC(P))
//將P分解為較小的子問題 P1 ,P2 ,…,Pk
for i←1 to k
do yi ← Divide-and-Conquer(Pi) 遞回解決Pi
T ← MERGE(y1,y2,…,yk) 合并子問題
return(T)
- 其中|P|表示問題P的規模；
- n0為一閾值，表示當問題P的規模不超過n0時，問題已容易直接解出，不必再繼續分解，
- ADHOC(P)是該分治法中的基本子演算法，用于直接解小規模的問題P，因此，當P的規模不超過n0時直接用演算法ADHOC(P)求解，
- 演算法MERGE(y1,y2,…,yk)是該分治法中的合并子演算法，用于將P的子問題P1 ,P2 ,…,Pk的相應的解y1,y2,…,yk合并為P的解，
漢諾塔代碼實作
package com.guizimo;
public class Hanoitower {
public static void main(String[] args) {
hanoiTower(10, '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 {
//1. 把上面的A->B
hanoiTower(num - 1, a, c, b);
//2. 把下面的A->C
System.out.println("第" + num + "個盤從" + a + "->" + c);
//3. 把B->C
hanoiTower(num - 1, b, a, c);
}
}
}
感謝
尚硅谷
以及勤勞的自己，個人博客，GitHub
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/5032.html
標籤：Java
下一篇：Arthas線上監控及問題定位