--- # System prepended metadata title: 分治法 tags: [Algorithm] --- 分治法 === ###### tags: `Algorithm` >分治法:分而治之 分: 切分問題 治: 解決、合併問題 很多時候大的問題很難解決，但是當規模較小的時候我們能直接知道答案。 那我們何不嘗先解決小的問題，在解決大的呢? :::info 分治步驟: 我有一個問題 -> 如果小到我們知道答案直接回答 否則繼續問更小的問題 -> 想辦法用兩個小問題的答案湊出原本問題的答案。 ::: 或許這樣講有點抽象，我們用範例來讓大家體會分治的強大。 ## 例一. 區間最小值 >給你 n 個數字, 請輸出其中的最小值。 用單純的分治解最小值看起來或許很蠢，不過我認為他是夠簡單且能體會分治的問題。 試著套用上面剛剛學到的步驟，嘗試以分治解決。 1. 問題: `int query(int l, int r)` 我們希望這個函式能回傳`[l,r)`區間的最小值。 2. 什麼時候可以直接回答? 當 `r-l==1` 時, 只有一個元素, 最小值就是他自己 3. 當不能直接回答，問更小的問題 我們把詢問 `[l,r)` 切成兩半 變成 `[l,m)` 和 `[m,r)`，其中 `m = (l+r)/2` 4. 當我們有了小問題的答案，該如何回答原問題? 整個區間的最小值 = min( 左半最小, 右半最小) 因此 `return min( query(l,m), query(r,m) );` :::warning 呼叫遞迴時有個要點，你要先假設你的下一層會好好地把事情做完。 不要擔心下一層怎麼運作，你只要確保: 1. 如果下一層是對的我能算對這一層 2. 遞迴直到某一層能直接停下來(直接取得答案) 類似數學歸納法的感覺 ::: ### Code 寫成程式碼會長成: ```cpp int arr[100]; int query (int l, int r) { if (r-l == 1) return arr[l]; else { int m = (l+r)/2; return min( query(l,m), query(m,r) ); } } ``` ## 例二. 合併排序 >給你 n 個數字, 請你由小到大排序。 這個問題看起來有點難，至少我們不能很直覺的解決他。 我們再度嘗試以分治解決。 1. 問題: msort(l,r) 我們希望把 `[l,r)` 排序 2. 什麼時候可以直接回答? 當 `r-l == 1` ，也就是只有一個元素時，我們不用排序。 3. 當不能直接回答，問更小的問題 我們把它切成兩半 設 `m = (l+r)/2` ，然後 `msort(l,m); msort(m,r);` 4. 用兩個小問題的答案湊出原本問題的答案 這部分稍微難一點 當我們有 `左:(1,3,6,7)` 和 `右:(2,4,5,8)` 兩個序列 要如何推出 `答:(1,2,3,5,7,8,10)`? 我們從左右兩邊各自拿最小的出來比較 1比較小先排入答案 因此有: ``` 左:(3,6,7) 右(2,4,5,8) 答:(1, ...) ``` 接下來繼續，這次最小的是右邊頭的 2, 那也把它丟進答案: ``` 左:(3,6,7) 右(4,5,8) 答:(1,2, ...) ``` 接下來可以試著自己推演。 示意圖: ![](https://i.imgur.com/rW3T4E6.png) ### Code ```cpp int arr[N], n, tmp[N]; inline void merge (int l, int r) // 合併答案 { // tmp 拿來存合併時的答案 // i 為左半邊頭, j 為右半邊頭, k 為放進答案的位置 int m = (l+r)>>1; for (int i=l,j=m,k=l; k=r || arr[i]>1; merge_sort(l,m); merge_sort(m,r); // 現在, 陣列的左半和右半都是分別排序好的。 merge(l,r); } ```