分而治之(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-2)a的b次方
給定一個整數a與b,輸出a的b次方除以1234的餘數。
輸入說明
輸入兩個正整數a與b,a會介於在1到100000之間,b會介於在0到100000之間。
輸出說明
輸出a的b次方除以1234的餘數。。
輸入範例
12321 9999
輸出範例
853
解題想法
本範例使用分而治之(Divide and Conquer)解題策略,有不錯的程式執行效率。分而治之(Divide and Conquer)演算法的解題步驟,如下。
Step1)Divide
自訂函式f(a,b)用於計算a的b次方,f(a,b)有以下關係
大問題f(a,b)可以切割成小問題f(a,b-1)或f(a,b/2),一直切割到f(a,0)回傳1,或f(a,1)回傳a,過程中要不斷除以1234求餘數。
Step2)Conquer 利用「f(a,b)=a*f(a,b-1)」或「tmp=f(a,b/2),f(a,b)=tmp*tmp」組合出大問題的答案,過程中要不斷除以1234求餘數。
程式碼
(1-3)合併排序(MergeSort)
詳細演算法與程式碼,請參閱排序。
解題想法
使用分而治之(Divide and Conquer)解題策略,分而治之(Divide and Conquer)演算法的解題步驟,如下。
Step1)Divide
自訂函式mergesort(a,L,R)用於將陣列a進行切割成索引值從L到R。M取(L+R)/2,可以將大問題利用mergesort(a,L,R)呼叫mergesort(a,L,M)與mergesort(a,M+1,R)不斷將陣列a分割成兩半,形成兩個小問題,直到mergesort(a,L,R),從L到R只剩一個元素為止,一個元素表示已經完成排序。
Step2)Conquer
自訂函式merge(a,L,M,R)將已排序的陣列a從L到M與已排序的陣列a從M+1到R,合併成一個更大的已排序陣列a從L到R。
範例練習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字串。
參考網頁:http://morris821028.github.io/2014/05/01/oj/uva/uva-1608/
利用map找出每個元素最近的相同元素的左邊索引值到L[],找出每個元素最近的相同元素的右邊索引值到R[],用於在O(1)時間內判斷是否在指定範圍內出現一次的元素,從左邊與右邊往中間找,第一個就找到演算法為O(n),中間才找到為O(n*log(n))