HDU1715（大肥婆数）

HD1715

题目

http://acm.hdu.edu.cn/showproblem.php?pid=1715；

大的fibonacci,用数组模拟，其实也不难，可是要优化就没那么容易了。以前做过大数加法，这一次用的是int二维数组，没有用难缠的字符数组了（字符数组好计算数的长度）。。所以还是贴过来了，，呵呵。

#include<iostream>
using namespace std;
int  fib[1000][1000];
int main(void)
{
 int n,m,i,j,k,carry;
 cin>>n;
 fib[1][1]=1;
 fib[2][1]=1;
 while(n--)
 {
  cin>>m;
  for(i=3,k=1;i<=m;i++)
  {
   for(j=1,carry=0;j<=k;j++)
   {
    fib[i][j]=fib[i-1][j]+fib[i-2][j]+carry;
    carry=fib[i][j]/10;
    fib[i][j]%=10;
   }
   while(carry)
   {
    fib[i][++k]=carry%10;//强烈注意下k,,,这个很重要，k用来计算数组的长度。乘法的同样也可以用这种模式去做，就像计算大数N！。
    carry/=10;
   }
  }
  for(i=k;i>=1;i--)
   cout<<fib[m][i];
  cout<<endl;
 }
 return 0;
}