1201：菲波那契數列

時間限制: 1000 ms ??? ??? 內存限制: 65536 KB
提交數: 17460 ??? 通過數: 9993

【題目描述】

菲波那契數列是指這樣的數列: 數列的第一個和第二個數都為1，接下來每個數都等于前面2個數之和。

給出一個正整數a，要求菲波那契數列中第a個數是多少。

【輸入】

第1行是測試數據的組數n，后面跟著n行輸入。每組測試數據占1行，包括一個正整數a(1<=a<=20)。

【輸出】

輸出有n行，每行輸出對應一個輸入。輸出應是一個正整數，為菲波那契數列中第a個數的大小。

【輸入樣例】

4 5 2 19 1

【輸出樣例】

5 1 4181 1

【分析】

? ? ? ? Fibonacci數列是最經典的遞推題目，可以用遞歸實現、也可以用遞推實現。

【參考代碼】

方法1：遞推法

#include <stdio.h> #define N 25 long long a[N]={0,1,1}; int main() {int i,t,n;for(i=3;i<=20;i++)a[i]=a[i-1]+a[i-2];scanf("%d",&t);while(t--){scanf("%d",&n);printf("%lld\n",a[n]);}return 0; }

方法2：遞歸法

#include <stdio.h> long long fib(int n) {if(n==1 || n==2)return 1;elsereturn fib(n-1)+fib(n-2); } int main() {int t,n;scanf("%d",&t);while(t--){scanf("%d",&n);printf("%lld\n",fib(n));}return 0; }

http://ybt.ssoier.cn:8088/problem_show.php?pid=1201

?

總結

以上是生活随笔為你收集整理的信息学奥赛一本通（1201：菲波那契数列）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。