大菲波数
问题描述 :
Fibonacci数列，定义如下： f(1)=f(2)=1 f(n)=f(n-1)+f(n-2) n>=3。 计算第n项Fibonacci数值。
输入:
输入第一行为一个整数N，接下来N行为整数Pi（1<=Pi<=1000）。
输出:
输出为N行，每行为对应的f(Pi)。
样例输入:
5
1
2
3
4
5
样例输出:
1
1
2
3
5
思路同博客中上一道题1042 N！ 均是大数加法原则，考虑到位数较多，所以采用数组。一维数组可以么？可以，但考虑到较为繁琐。所以采用二维数组，a[i][j] 其中i 表示 整数pi ， j表示求得结果的位数。本题同样采用10进制，逢十进一。（有的程序可能去除以自己定义的数100,1000,10000等等）。
#include<iostream>
#include<cstring>
using namespace std;
int f[][];
int main()
{
int m;
int n;
cin>>n;
memset(f,,sizeof(f));
f[][]=;
f[][]=;
for(int i=;i<;i++)
{
for(int j=;j<;j++)
{
f[i][j]+=f[i-][j]+f[i-][j];//+=号别错了 因为考虑到f[i][j]可能是之前计算的进位
if(f[i][j]>=)
{
f[i][j+]=f[i][j]/;//注意此处不要颠倒
f[i][j]=f[i][j]%;
}
}
}
while(n--)
{
cin>>m;
int flag=;//控制输出的
for(int i=;i>=;i--)//考虑到进位可能比较多所以稍大点
{
if(flag==&&f[m][i]!=)
flag=;
if(flag)
cout<<f[m][i];
}
cout<<endl;
} return ;
}