回分類題庫
b022: 費氏數列
關鍵字: 遞迴

測資點 : 5 | Time Limit : 1000 ms | Memory Limit : 32000 KB
Accepted : 2767 Times / 2387 Users | Submit : 4563 Times / 2501 Users | Accepted rate : 95%
題目加入時間 : 2011-10-14 00:08

Content: 简体中文

費波那西數列(Fibonacci Sequence)簡稱費氏數列,它的定義如下:

F0=0
F1=1
Fn=Fn-1+Fn-2

也就是說,它以 0,1 開頭,接下來的每一項都是前兩項的和,它的前10項為:0,1,1,2,3,5,8,13,21,34。

費氏數列是許多人接觸遞迴函數時的第一個例子,但事實上它不是一個適合使用遞迴的例子,因為隨著 N 的增加,底層函數的呼叫將會接近指數成長而導致效能過低,現在給你一個 N,請你以遞迴方式計算出 Fn的值,並統計執行了幾次函數的呼叫。

Input:

輸入一個正整數 N (2<=N<=35)。

Output:

請輸出 Fn 的值,以及執行了幾次函數的呼叫。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
輸入1:
4

輸入2:
10

Sample Output :

輸出1:
3 9

輸出2:
55 177

Hint :

PS.由於系統問題,如果你輸出的第二個數字為 0,請將該數字以另一行 cout 或 printf 輸出。

Author :

遞迴 (管理員:sagit)

  Solve it!   Status Forum