### 八大算法思想 >[info]比較笨的枚舉算法思想 聰明一點的遞推算法思想 充分利用自己的遞歸算法思想 各個擊破的分治算法思想 貪心算法思想并不貪婪 試探性算法思想是一種委婉的做法 迭代算法 模擬算法思想 ### 枚舉算法 >將問題的所有可能的答案一一列舉，然后根據條件判斷此答案是否合適，合適則保留，不合適則丟棄。 C語言中，枚舉算法一般使用while循環實現。 使用枚舉算法解題的基本思路是： 1. 確定枚舉對象、枚舉范圍和判定條件 2. 逐一枚舉可能的解，驗證每個解是否是問題的解 枚舉算法一般按照如下三個步驟進行： 1. 題解的可能范圍，不能遺漏任何一個真正的解，也要避免重復 2. 判斷是否是真正解的方法 3. 使可能解的范圍降至最小，以便提高解決問題的效率  >缺點：當給定的范圍太大的時候，一般不選擇枚舉法，效率太低 >優點：而給定范圍比較小，且條件判斷清晰簡單，可以使用枚舉法，程序簡單，基本不用考慮效率問題 ### 遞推算法 >“穩扎穩打”的策略，不斷利用已有的信息導出新的東西。 日常應用中有如下兩種遞推算法： 1. 順推法：從已知條件觸出發，逐步推算出要解決問題的方法 2. 逆推法：從已知結果出發，用迭代表達式逐步推算出問題開始的條件，即順推法的逆過程 ### 遞歸算法 三個特點； 1. 遞歸過程一般通過函數或子過程來實現 2. 遞歸算法在函數或子過程的內部，直接或間接地調用自己的算法 3. 遞歸算法實際上是把問題轉化為規模縮小了的同類問題的子問題，然后再遞歸調用函數或過程來表示問題的解 使用遞歸算法的時候要注意如下4點： 1. 遞歸是在過程或函數中調用自身的過程 2. 在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱之為遞歸出口 3. 遞歸算法通常顯得很簡潔，但是運行效率較低，所以一般不提倡用遞歸算法設計程序 4. 在遞歸調用的過程中，系統用棧來存儲每一層的返回點和局部量，如果遞歸次數過多，則容易造成棧溢出，所以一般不提倡使用遞歸算法設計程序 ### 分治算法： >將問題分解為多個小的子問題，找到求出這幾個子問題的解法后，再找到合適的方法，把它們組合成求整個大問題的解法。如果這些子問題還是比較大，再次分解為更小的子問題，以此類推，直到找出求解方式為止。 使用分治算法解題的一般步驟如下： 1. 分解，將要解決的問題劃分為若干個規模較小的同類問題 2. 求解，當子問題劃分得足夠小的時候，用較簡單的方法解決 3. 合并，按原問題的要求，將子問題的解逐層合并構成原問題的解 ### 貪心算法 >從某一個初始解出發，逐步逼近給定的目標，當達到算法的某一步不能再繼續前進時，就停止算法，給定一個近似解。 貪心算法存在以下3個問題： 1. 不能保證最后的解是最優的 2. 不能用來求最大或最小解的問題 3. 只能求滿足某些約束條件的可行解的范圍 貪心算法的基本思路： 1. 建立數學模型來描述問題 2. 把求解的問題分成若干個子問題 3. 把每一個子問題求解，得到子問題的局部最優解 4. 把子問題的解局部最優解合并成原來解問題的一個解 實現貪心算法的基本過程如下所示： 1. 從問題的某一初始解出發 2. while能向給定總目標前進異步 3. 求出可行解的一個解元素 4. 由所有解元素組合成問題的一個可行解 ### 試探法算法 基本步驟： 1. 針對所給的問題，定義問題的解空間 2. 確定易于搜索的解空間結構 3. 以深度優先方式搜索解空間，并在搜索過程中用剪枝函數避免無效的搜索 ### 迭代算法 >用于計算機解決問題的一種基礎方法。利用計算機運算速度快、適合做重復性操作的特點，讓計算機對一組指令(或一定步驟)進行重復執行，在每次執行這組指令(或這些步驟)時，都從變量的原值推出它的一個新值。 使用迭代算法要注意的三個方面： 1. 確定迭代變量 在可以使用迭代算法解決的問題中，至少要存在一個迭代變量，即直接或間接地不斷由舊值遞推出新值的變量 2. 建立迭代關系式 迭代關系式是指如何從變量的前一個值退出其下一個值的公式或關系，通常可以使用遞推或倒推的方式來建立迭代關系式，迭代關系式的建立是解決迭代問題的關鍵 3. 對迭代過程進行控制 在編寫迭代程序時，必須確定在什么時候結束迭代過程，不能讓迭代過程無休止地重復執行下去，通常可分為如下兩種情況來控制迭代過程： ①所需的迭代次數是個確定值，可以計算出來，可以構建一個固定次數的循環來實現對迭代過程的控制 ②所需的迭代次數無法確定，需要進一步分析出用來結束迭代過程的條件 ### 模擬算法 >一種最基本的算法思想，解決方法是根據題目給定的規則對題目要求的相關過程進行編程模擬。 在解決模擬問題時，需要注意字符串處理，特殊情況處理和對題目意思的理解。