1.枚舉算法思想
將問題的所有可能的答案一一列舉,然後根據條件判斷此答案是否合適,保留合適的,丟棄不合適的。在C語言中,枚舉算法一般使用while 循環實現。枚舉算法的基本思路:
確定枚舉對象、枚舉範圍和判定條件。
逐一列舉可能的解,驗證每個解是否是問題的解。
枚舉算法一般步驟:
題解的可能範圍,不能遺漏任何一個真正解,也要避免重複解。
判斷是否是真正解的方法
使可能解的範圍降低至最新,以便提高解決問題的效率。
案例:百雞百錢問題等。
2.遞推算法思想
遞推算法的可以不斷利用已有的信息推導出新的東西,在日常應用中有如下兩種遞推算法。
順推法:從已知條件出發,逐步推出要解決問題的方法。例如斐波那契數列就可以通過順推法推算出新的數據
逆推法:從已知結果觸發,用迭代表達式逐步推算出問題開始的條件,即順推法的逆過程。
案例:斐波那契數列問題
3.遞歸算法思想
遞歸算法思想往往用函數的形式來體現,所以遞歸算法需要預先編寫功能函數。通過調用這些功能函數,可以實現問題的解決。
遞歸算法基礎,遞歸算法具有如下三個特點:
遞歸過程一般通過函數或子過程來實現。
遞歸算法在函數或子過程內部直接或者間接地調用自己的算法,
遞歸算法實際上是把問題轉化為規模縮小的同類問題的子問題,然後在遞歸調用函數或過程來表示問題的解。
在使用遞歸算法時,注意以下4點:
遞歸實在過程或函數中調用自身的過程。
在使用遞歸策略時,必須有一個明確的遞歸條件,這稱為遞歸出口。
遞歸算法通常顯得很簡潔,但是運行效率較低,所以一般不提倡用遞歸算法設計程序。
在遞歸調用過程中,系統用棧來存儲每一層的返回點和局部量。如果遞歸次數過多則容易造成棧溢出,所以一般不提倡遞歸算法設計程序。
實例:漢諾塔問題
4.分治算法的思想
將一個規模為N的問題分解為K個規模較小的子問題,這些子問題相互獨立且與原問題性質相同。只要求出子問題的解,就可得到原問題的解,循環這樣的模式知道解決問題為止。
分治算法的一般步驟:
分解,將要解決的問題劃分成若干個規模較小的同類問題。
求解,當子問題劃分得足夠小時,用比較簡單的方法解決。
合併,按原文的要求,將問題的解逐漸合併構成原問題的解。
實例:大數相乘問題、歐洲冠軍盃比賽日程安排
5.貪心算法的思想
貪心算法又稱貪婪算法,它在解決問題的時候總想用在當前看來是最好方法來實現。這種算法思想不從整體最優上考慮問題僅僅是在某種意義上的局部最優求解。雖然貪心算法並不能解決所有問題整體最優解,但是在面對範圍相當廣泛的許多問題時,能產生整體最優解或者是整體最優解的近似解。
貪心算法的基礎:貪心算法從問題的某一個初始解出發逐步逼近給定的目的,以便儘快求出更好的解。當達到算法中的某一步不能再繼續前進時,就停止算法,給出一個近似解。由於貪心算法的特點和思路可以看出,貪心算法存在以下三個問題:
不能保證最後的解是最優的。
不能用來求最大或者最小問題。
只能滿足求某些約束條件下的可行解的範圍。
基本思路:
建立數學模型來描述問題。
把求解的問題分成若干個子問題。
對每一個子問題的求解,得到子問題的局部最優解。
把子問題的局部最優解合併成原來問題的一個解。
基本步驟:
從問題的某一初始解出發
while能向給定總目標前進一步
求出可行解的一個解元素
由所有解元素組合成問題的一個可行解
實例:裝箱問題
閱讀更多 一兒口山石 的文章