kowala's home

kowala's home
這裡是我的學習筆記,陸續增加中。
http://kowala21.blogspot.com

2011-10-25

Dev C++ 有趣的遞迴函數-費式數列(Fibonacci)

C 語言有個好玩的寫法,就是遞迴函數(Recursive call),遞迴函數有幾項特徵,就是


1.自己呼叫自己
2.必須存在終止條件

來找個例子,一般談到遞迴,總是喜歡拿費式數列(Fibonacci)來說明,這裡也簡單的介紹一下,詳細的資料可以在維基百科[1]找到。

費式數列(Fibonacci)
數列的前兩項為 1、1,之後的每一項為前兩項之和,
即 Fn=Fn-1+Fn-2,數列的前 10 項為:
1、1、2、3、5、8、13、21、34、55、89。

是使用一種線性遞迴關係式來定義:
F_{0} = 0 \,
F_{1} = 1 \,
F_{n} = F_{n-1}+F_{n-2} \,
 設若:F_{n} / F_{n-1}\, 當n趨於無限大之極限值存在,則其值為 1+\sqrt{5} \over 2\, = Φ 恰為黃金分割之ㄧ值,1.618....,另一值則為0.618....,兩值互為倒數,也就是說1.618....分之1=0.618....,反之亦然。

我們任意取兩個連續的數來除,很容易可以得到一比值

    89/55=1.618181818181...
    55/34=1.617647058823...
    34/21=1.619047619047...
    21/13=1.615384615384...
    13/8=1.625
    8/5=1.6
    5/3=1.66666666666666...

這就是有名的黃金比例 1.618...

好了,介紹到這裡,讓我們來看看如何在 C++ 中實現...

這是費式數列(Fibonacci)的寫法,C++可以很簡潔的表示出來[2].

double f(double n){
    if(n<=2)return 1;   
    return f(n-1)+f(n-2);
}

簡單說明一下遞迴函數的特徵

if(n<=2)return 1;          這是中止條件
return f(n-1)+f(n-2);     這是自己呼叫自己

來實做一下
//-----------------------------------------------------------
#include <cstdlib>
#include <iostream>
#include <iomanip.h>

using namespace std;

//費式數列(Fibonacci)
double f(double n){
    if(n<=2)return 1;  
    return f(n-1)+f(n-2);
}
int main(int argc, char *argv[]){
    int i,n;
    system("cls");
  
    cout << "遞迴測試 - 費式數列(Fibonacci)" << endl;
    cout << "------------------------------" << endl;
  
    n=30;
    for(int i=1;i<=n;i++){
        cout << "Loop " << setw(5) << setprecision(5) << setfill(' ') << i
        << setw(10) << setprecision(10) << setfill(' ')<< f(i) << "\n";
    }
  
    cout << "\n黃金比例 (f(9)/f(8)) = " << f(9)/f(8) << endl << endl;
  
    system("PAUSE");
    return EXIT_SUCCESS;
}

//-----------------------------------------------------------


結果如下


這個是為了對齊而對 cout 做了一些指定
cout << "Loop " << setw(5) << setprecision(5) << setfill(' ') << i

setw(5)  設定5個字組寬
setprecision(5)  設定5個數字
setfill(' ')  空格補 space

為了觀察遞迴函數的運作,我們在裏頭加一行顯示其值,如下

double fi(double n){
    cout << n << " ";   
    if(n<=2)return 1;   
    return fi(n-1)+fi(n-2);
}

再把 n 改小一點,n=10,再跑看看

    n=10;
    for(int i=1;i<=n;i++){
        cout << "Loop " << setw(5) << setprecision(5) << setfill(' ') << i
        << setw(10) << setprecision(10) << setfill(' ')<< fi(i) << "\n";
    }
這次就可以清楚看到它被執行幾次了。

參考資料:
1.遞迴關係式
http://zh.wikipedia.org/wiki/%E9%81%9E%E8%BF%B4%E9%97%9C%E4%BF%82%E5%BC%8F

2.費式(Fibonacci)數列  
http://dhcp.tcgs.tc.edu.tw/c/p014.htm

沒有留言:

張貼留言

請提供您的寶貴意見 ;-)