Embedded Files
本程式放置於Google Colab，共用連結如下：https://colab.research.google.com/drive/1-Y-YZ36xL3L2Tra8Zr-eAs-_FoTrDZR7?usp=sharing
(1)分而治之(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)的結果。
Python程式碼
(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求餘數。
Python程式碼
(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。
(2)循序搜尋與二分搜尋
搜尋前需要將資料進行排序才能使用二元搜尋。二元搜尋除了用於搜尋資料外，有時候也可以用於找出最佳解，例如：分配物品的最佳解，將n個大小不同的長方形蛋糕，分給m個人，不能將不同蛋糕的剩餘部分組合起來分給一個人，蛋糕若太小可以不分配，每個人都要獲得相同大小的蛋糕，每個人獲得的蛋糕大小可以是浮點數，此時需要使用二元搜尋加快逼近要分配的大小。
二元搜尋是對已排序資料進行尋找某筆資料是否存在，平均而言，二元搜尋比循序搜尋找到該資料的執行時間要短，也就是有較好的執行效率。使用「已排序成績陣列中是否包含成績為59分的學生」為例，進行二元搜尋概念的說明。 從頭到尾依序找尋稱作「循序搜尋」，但對已經由小到大排序好的資料可以使用「二分搜尋」方式加快找尋速度，因為已經排序可以從中間開始找，若要找的元素比中間元素值大，則往右邊找，若要找的元素比中間元素值小，則往左邊找，依此類推直到找到為止。
(2-1)循序搜尋
找出成績陣列中是否包含成績為59分的學生，找到第一個學生成績為59分為止。
舉例說明
(1) 第一個學生的成績(60) 是否為59分，若是則輸出「找到59分的學生」程式結束。
(2) 否則比較第二個學生的成績(90)是否為59分，若是則輸出「找到59分的學生」程式結束。
(3)否則比較第三個學生的成績(44)是否為59分，若是則輸出「找到59分的學生」程式結束。
(4)否則比較第四個學生的成績(98)是否為59分，若是則輸出「找到59分的學生」程式結束。
(5)否則比較第五個學生的成績(50)是否為59分，若是則輸出「找到59分的學生」程式結束。
(6)若全部都找不到成績59分的學生，則輸出「找不到59分的學生」。
解題想法
想要找出班上第一次段考成績是否有59分的學生，可能需要有全班成績單，從頭開始依序找，(1)第一個學生成績是否為59分，若是則輸出「找到59分的學生」程式結束，(2)否則比較第二個學生的成績是否為59分，若是則輸出「找到59分的學生」程式結束，(3)依此類推，直到比較到最後一個學生的成績為止，(4)若全部都找不到成績59分的學生，則輸出「找不到59分的學生」。
程式碼
程式碼效率
第5到11行要掃描成績陣列的每一個元素，所以程式碼效率為O(n)
程式執行
score[ 0 ]= 60
score[ 1 ]= 90
score[ 2 ]= 44
score[ 3 ]= 98
score[ 4 ]= 50
找不到59分
(2-2)使用二元搜尋搜尋值
假設已排序的十個學生的成績陣列，如下圖，以二分搜尋方式找尋成績為59分的學生。
Step1) 取第一個到第十個學生成績中間的那位學生，第六個學生的成績(78) 是否為59分，若是則輸出「找到59分的學生」程式結束。
Step2)因為59分小於78分，往左邊由第一到第五個學生成績中間的那位學生，第三個學生的成績(62)是否為59分，若是則輸出「找到59分的學生」程式結束。
Step3)因為59分小於62分，往左邊由第一到第二個學生成績中間的那位學生，第一個學生的成績(45)是否為59分，若是則輸出「找到59分的學生」程式結束。
Step4)因為59分大於45分，往右邊判斷第二個學生的成績(59)是否為59分，找到59分的學生，輸出「找到59分的學生」程式結束。
輸入說明
本題不需要輸入。
輸出說明
輸出是否找到成績為59分。
輸入範例
無
輸出範例
檢查score[ 5 ]= 78 是否等於59
right更新為 4
left更新為 0
mid更新為 2
找不到59分
檢查score[ 2 ]= 62 是否等於59
right更新為 1
left更新為 0
mid更新為 0
找不到59分
檢查score[ 0 ]= 45 是否等於59
right更新為 1
left更新為 1
mid更新為 1
找到59分
解題想法
這樣的演算法需要一個成績陣列，事先將成績陣列由小到大排序好，一個迴圈(while)用於檢查「目前成績」是否等於59分，若找到一個成績等於59分，則輸出「找到59分的學生」，否則若「目前成績」大於59分，59分可能在「目前成績」為左半部，「目前成績」為左半部陣列元素取位於中間元素的成績，若「目前成績」小於59分，59分可能在「目前成績」為右半部，「目前成績」為右半部成績陣列取位於中間元素的成績。若找不到可以比較的「目前成績」，則輸出「找不到59分的學生」。
Python程式碼
(2-3)整數平均分配
有n包不同口味的糖果要分給m個小朋友，每包糖果的個數不同，每個小朋友只接受同一口味的糖果，小朋友只在乎個數是否一樣，可以任意給同一口味的糖果，若某包糖果個數較多，就可以分給多個小朋友，多出的可以不分配，某包個數過少的糖果，導致不能分配出去，求每個小朋友最多可以拿幾顆糖果。
輸入說明
輸入n表示會輸入n包不同口味的糖果，接著輸入n行，每一行一個數字，表示該包糖果的個數，接著輸入m，表示有幾個小朋友，保證m小於n，且n小於1000。
輸出說明
每個小朋友最多可以拿幾顆糖果。
輸入範例
10
10
21
16
40
55
45
35
54
33
46
10
輸出範例
23
解題想法
本範例使用二分搜尋，不斷測試各種糖果顆數的分配是否足夠分給m個小朋友，使用二分搜尋不斷逼近解答，比循序搜尋逼近解答快。需要撰寫一個函式，可以不斷輸入糖果顆數，檢查是否可以分給m個小朋友，如果可以回傳true，否則回傳false，二分搜尋不斷依據此函式所回傳的結果，修正糖果顆數左邊界與右邊屆逼近正確答案。
Python程式碼
Page updated
Google Sites
Report abuse