計算機算法設計的基本方法(4)
作者:zhushican 丨 時間:2022年04月17日 丨 分類:六六互聯
分治法
定義:將問題分而治之,把一個復雜的問題分成兩個或更多的相同或相似的子問題,再把子問題分成更小的子問題,直到最后的子問題可以簡單的直接求解,原問題的解為子問題解的合并。
思想:常常要借助遞歸的結構,逐層求解,當問題規模達到某個簡單情況時,解容易直接得出,而不必繼續分解。
基本步驟:
第一步:判斷問題是否可分。如果可分,轉第二步;否則轉第三步。
第二步:將問題劃分為多個子問題,并分別遞歸調用分治法過程,求出多個解,并將多個子問題的解進行合并。
第三步:直接求解,并返回問題的解。
例3-7:識別假幣問題。一個袋子里裝有偶數枚硬幣,其中有一枚為假幣,而且假幣的重量比真幣的輕。假幣和真幣從外形看一模一樣,無法分辨出來。請從中找出這枚假幣。
分析:
例3-8:歸并排序。
某數列存儲在序列A[1],A[2],……,A[n],現采用歸并思想進行排序。
分析:
例3-8的N-S圖
序列(5,3,4,2,1,3,6,2)進行歸并排序的示例圖
上一篇
計算機數據庫之認識數據
2022年04月17日
2022年04月17日
下一篇