分而治之(Divide And Conquer)

分而治之(Divide and Conquer)

將大問題不斷切割成兩個或多個小問題，這樣的過程稱作「Divide」，當切割到最後的小問題，若簡單到可以直接解決，就直接使用程式解決，根據問題的需求決定是否要將小問題的解合併或組合成大問題的解，這樣的過程稱作「Conquer」，這是一種演算法解題策略，屬於由上而下(top-down)的解題策略。

(1-1)求n階乘

給定一個正整數n，輸出該正整數n的階乘。

輸入說明

輸入一個正整數，正整數字介於在1到20之間。

輸出說明

輸出該正整數的階乘值。

輸入範例

10

輸出範例

3628800

解題想法

本範例可以使用迴圈，也可以使用分而治之(Divide and Conquer)解題策略。

Step1)Divide

自訂函式f(n)用於計算n階乘，f(n)與f(n-1)的關係為「f(n)=n*f(n-1)」，大問題f(n)可以切割成小問題f(n-1)，一直切割到f(1)為止，f(1)答案就是1。

Step2)Conquer

利用「f(n)=n*f(n-1)」，將f(n-1)的結果乘以n就可以獲得f(n)的結果。

範例練習1 uva374 - Big Mod   

出處 ： https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=310

b的p次方%m

解題策略

Divide-and-Conquer

範例練習2  APCS201806第4題反序數量

考慮一個數列 A[1:n]。如果 A 中兩個數字 A[i] 和 A[j] 滿足 i<j AND A[j]<A[i]，也就是在前面的比較大，則我們說 (A[i],A[j]) 是一個反序對 (inversion)。 

定義 W(A)為數列 A 中反序對數量。例如，在數列 A=(3,1,9,8,9,2) 中，一共有(3,1)、(3,2)、(9,8)、(9,2)、(8,2)、(9,2) 一共 6 個反序對，所以 W(A)=6。

請注意到序列中有兩個 9 都在 2 之前，因此有兩個(9,2)反序對，也就是說，不同位置的反序對都要計算，不管兩對的內容是否一樣。 請撰寫一個程式，計算一個數列 A 的反序數量 W(A)。

輸入說明

第一行是一個正整數 n ，代表數列長度， 第二行有 n 個非負整數，是依序數列內容，數字間以空白隔開。 n 不超過 1e5 數列內容不超過 1e6 。

輸出說明

輸出反序對數量。

輸入範例1

6

3 1 9 8 9 2

輸出範例1

6

解題策略

分而治之

修改mergesort，當右半陣列元素merge到tmp陣列時，左半部剩餘元素個數就是逆序個數，累加這些個數就是答案

範例練習3  uva1608 - Non-boring sequences

所有子字串至少有一個只出現一次的元素，稱作Non-boring字串。

出處 ： https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=4483

參考網頁：http://morris821028.github.io/2014/05/01/oj/uva/uva-1608/

利用map找出每個元素最近的相同元素的左邊索引值到L[]，找出每個元素最近的相同元素的右邊索引值到R[]，用於在O(1)時間內判斷是否在指定範圍內出現一次的元素，從左邊與右邊往中間找，第一個就找到演算法為O(n)，中間才找到為O(n*log(n))