【題目描述】

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

給出一個正整數a，要求菲波那契數列中第a個數對1000取模的結果是多少。

【輸入】

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

【輸出】

n行，每行輸出對應一個輸入。輸出應是一個正整數，為菲波那契數列中第a個數對1000取模得到的結果。

【輸入樣例】

4
5
2
19
1

【輸出樣例】

?5
1
181
1

【源程序】

#include<iostream> using namespace std; int a[1000100]; int main() {int n,x,i;a[1]=1;a[2]=1;for(i=3;i<=1000000;i++)a[i]=(a[i-1]+a[i-2])%1000;cin>>n;for(i=1;i<=n;i++){cin>>x;cout<<a[x]<<endl;}return 0; }

?

總結

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

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