Description
Fibonacci数列，定义如下：
f(1)=f(2)=1
f(n)=f(n-1)+f(n-2) n>=3。
计算第n项Fibonacci数值。
Input
输入第一行为一个整数N，接下来N行为整数Pi（1<=Pi<=1000）。
Output
输出为N行，每行为对应的f(Pi)。
Sample Input
5
1
2
3
4
5
Sample Output
1
1
2
3
5
HINT
此题需要用大数处理(string 处理）
这里大致说一下解题思路： 这道题跟以往写过的 斐波那契数列题不一样，以前的大多都是要求结果对某个素数取余，这道题是直接让你输出，所以对于大数据的处理一般想到的就是用字符串来解决该问题了，这道题只有用到了大整数运算中的 正整数加法，另外，程序中，我还用了map打了一个大斐波数表。整体的思路很简单，代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;const int N = 1000;void Reverse(char *str)
{char temp[N];int len = strlen(str);int k = 0;strcpy(temp, str);for(int i = len-1; i >= 0; i--){str[k++] = temp[i];}str[k] = '\0';
}char * BIA(char * a, char *b)
{int a_len = strlen(a);int b_len = strlen(b);int maxlen = max(a_len, b_len);int m = 0, n = 0; //进位int c = 0, i;char *ans = new char[maxlen + 2];char *pa = a + a_len - 1;char *pb = b + b_len - 1;for(i = 0; i < maxlen; i++){m = n = 0;if(pa + 1 != a){m = *pa - 48;pa--;}if(pb + 1 != b){n = *pb - 48;pb--;}*(ans+i) = (m + n + c) % 10 + 48;c = (m + n + c) / 10;}if(c > 0){*(ans + i) = c + 48;*(ans + i + 1) = '\0';}else*(ans + i) = '\0';Reverse(ans);return ans;}int main()
{// 打表char s1[N] = "1";char s2[N] = "1";char *s3 = new char[N];map<int, string> sky;sky.clear();sky[1] = sky[2] = s1;for(int i = 3; i <= 1000; i++){s3 = BIA(s1, s2);sky[i] = s3;strcpy(s1, s2);strcpy(s2, s3);}int t;cin>>t;while(t--){int num;scanf("%d", &num);cout<<sky[num]<<endl;}return 0;
}