3分鐘乾貨之迭代演算法
迭代法也稱輾轉法,是一種不斷用變數的舊值遞推新值的過程,在解決問題時總是重複利用一種方法。與迭代法相對應的是直接法(或者稱為一次解法),即一次性解決問題。迭代法又分為精確迭代和近似迭代。“二分法”和“牛頓迭代法”屬於近似迭代法,功能都比較類似。
迭代演算法基礎
迭代演算法是用計算機解決問題的一種基本方法。它利用計算機運算速度快、適合做重複性操作的特點,讓計算機對一組指令(或一定步驟)進行重複執行,在每次執行這組指令(或這些步驟)時,都從變數的原值推出它的一個新值。
在使用迭代演算法解決問題時,需要做好如下3個方面的工作。
(1)確定迭代變數
在可以使用迭代演算法解決的問題中,至少存在一個迭代變數,即直接或間接地不斷由舊值遞推出新值的變數。
(2)建立迭代關係式
迭代關係式是指如何從變數的前一個值推出其下一個值的公式或關係。通常可以使用遞推或倒推的方法來建立迭代關係式,迭代關係式的建立是解決迭代問題的關鍵。
(3)對迭代過程進行控制
在編寫迭代程式時,必須確定在什麼時候結束迭代過程,不能讓迭代過程無休止地重複執行下去。通常可分為如下兩種情況來控制迭代過程:
① 所需的迭代次數是個確定的值,可以計算出來,可以構建一個固定次數的迴圈來實現對迭代過程的控制;
② 所需的迭代次數無法確定,需要進一步分析出用來結束迭代過程的條件。