-
推算法
鎖定
- 中文名
- 推算法
- 拼 音
- tuī suàn fǎ
- 類 別
- 一種簡單的算法
- 遞推算法
- 順推和逆推
分類
遞推算法分為
順推和逆推兩種。所謂順推法是從已知條件出發,逐步推算出要解決的問題的方法叫順推。如斐波拉契數列,設它的函數為f(n),已知f(1)=1,f(2)=1;f(n)=f(n-2)+f(n-1)(n>=3,n∈N)。則我們通過順推可以知道,f(3)=f(1)+f(2)=2,f(4)=f(2)+f(3)=3……直至要求的解。相對於遞歸算法,遞推算法免除了數據進出棧的過程,也就是説,不需要函數不斷的向邊界值靠攏,而直接從邊界出發,直到求出函數值.比如階乘函數:f(n)=n*f(n-1)在f(3)的運算過程中,遞歸的數據流動過程如下:f(3){f(i)=f(i-1)*i}-->f(2)-->f(1)-->f(0){f(0)=1}-->f(1)-->f(2)--f(3){f(3)=6}而遞推如下:f(0)-->f(1)-->f(2)-->f(3)由此可見,遞推的效率要高一些,在可能的情況下應儘量使用遞推.但是遞歸作為比較基礎的算法,它的作用不能忽視.所以,在把握這兩種算法的時候應該特別注意.
- 詞條統計
-
- 瀏覽次數:次
- 編輯次數:9次歷史版本
- 最近更新: 小胖_0216