C 語言初學教材 - 第五章 迭代的方案

利用遞迴的計算方式解決問題比較直覺,但是當計算的值越大時,所需的時間也就越多。其實遞迴的方法都能夠用迭代的計算方式來代替,所謂的迭代類似公式解,利用一個迴圈進行計算工作,因此不會消耗太多的記憶體,得到結果的時間也會快很多。



迭代的方案雖然有其優點,問題是迭代並非顯而易見的,例如計算階層數,我們該怎麼把計算都濃縮在一個迴圈之中呢?


因為每一個階層數都是從 1 開始相乘,因此我們可以設定迴圈變數 i 從 1 開始遞增,然後另外用一個儲存算結果的變數 result ,把 result 乘上每一個遞增的 i 。


基於這個想法,程式如下
#include <stdio.h>

int factorial(int n);

int main(void)
{
    int i;
    
    for (i = 0; i < 10; i++) {
        printf("%d! = %d\n", i, factorial(i));
    }
    
    return 0;
}

int factorial(int n)
{
    int i, result;
    
    result = 1;
    for (i = 1; i <= n; i++) {
        result *= i;
    }
    
    return result; 
}

/* 《程式語言教學誌》的範例程式
    http://pydoing.blogspot.com/
    檔名:iterative1.c
    功能:計算階層
    作者:張凱慶
    時間:西元2010年7月 */


編譯後行,結果如下



結果符合預期,因此計算階層數可以用這個方法代替。


那計算費伯納西數可以用怎麼樣的迭代方法計算呢?由於每個費伯納西數都是前兩個數字相加,因此迴圈變數在實際計算過程就只代表要做幾次計算,這也是說,我們需要額外的兩個變數來儲存要進行相加的前兩個數字。


以下程式為計算費伯納西數的迭代版本,變數 a 及變數 b 分別儲存費伯納西數列的起始值 0 及 1 ,然後 result 儲存結果,初值設為 1 ,這樣的計算結果會跟遞迴版本相同
#include <stdio.h>

int fabonacii(int n);

int main(void)
{
    int i;
    
    for (i = 0; i < 16; i++) {
        printf("F%d\t= %d\n", i, fabonacii(i));
    }
    
    return 0;
}

int fabonacii(int n)
{
    int i, result, a, b;
    
    a = 0;
    b = 1;
    result = 1;
    for (i = 0; i < n; i++) {
        result = a + b;
        a = b;
        b = result;
    }
    
    return result;
}

/* 《程式語言教學誌》的範例程式
    http://pydoing.blogspot.com/
    檔名:iterative2.c
    功能:計算費伯納西數列
    作者:張凱慶
    時間:西元2010年7月 */


編譯後執行,結果如下



問題與討論
  1. 比較迭代跟遞迴的優劣。
  2. 計算階層數時,迴圈變數為什麼不從 0 開始遞增?
  3. 計算費伯納西數時,如果 result 的初值設為 0 ,會有什麼結果?




2 則留言:

Darkian 提到...

您好
這兩張圖似乎錯置了
第一張比較像費波納契數列
第二張是階乘數

Kaiching Chang 提到...

圖弄反了,已修改,感謝指正 ^_^