Divide and Conquer

Divide and conquer 是一種由上而下 ( top-down ) 的解題方式

• Def:
  • 可將母問題切割成較小的問題(切割)，使用相同的解決程序加以處理 (征服)。所有小問題的解可以成為母問題的最後解; 若有必要，則再將每個小問題的處理結果加以合併，就可以得到最後的答案。
    • 由於使用相同的解決程序處理每個小問題，這一個程序就會被遞迴呼叫，因此一個遞迴演算法則通常以一個副程式的型式出現，內部包含一個解決程序與遞迴呼叫。
    • 對於具有遞迴關係的問題，或是一些採用遞迴定義的資料結構，都適合採用 Divide and Conquer 演算法設計策略
  • 最簡潔、易懂
  • 效率差 ( ∵ 採用遞迴設計 )

Divide and Conquer 使用時機

下列兩種情況是適合使用 Divide and Conquer 設計策略(也是遞迴演算法的適用時機):

• 問題本身具有遞迴關係
  • 母問題可被切割成較小的“相同”問題
  • 如: 階乘問題、費氏數問題、河內塔問題、快速排序問題、二元搜尋問題… 等
• 資料結構屬於遞迴定義
  • 大量的 Data Set，在切割後仍為一組具“相同性質”的 Data Set
  • 如: 二元樹 ( Binary Tree )、鏈結串列 ( Link List )… 等

遞迴演算法則的設計

1. 找出問題的終止條件
2. 找出問題本身的遞迴關係 (遞迴呼叫)

• 技巧:
  • 思考遞迴呼叫需要哪些參數？
    • 外部副程式
    • 副程式本身
  • 遞迴呼叫的傳回值為何？
  • 遞迴呼叫的終止條件為何？終止時傳回何值？

Procedure Recursion_subroutine(Parameter);
{
    if ({% label danger@終止條件 %}) then Return( );
    else {% label info@Recursion_subroutine(New_parameter) %};
}

案例探討

Binary Search (二分搜尋)