杭电acm 1715 大菲波数

2010-08-26 13:58

ps:痛苦的大数啊,用的是纯int数组来做,低级的指针的交替搞错了,折磨了我n个小时…郁闷啊

思路:大于100000000的数,分段保存在int数组里,可以参考另一篇大数的文章,思路差不多

</pre>
#include<iostream>
using namespace std;
const int MAX = 100000000 ; 

int add(constint*b,constint*c,int*t)
{
     int k=0,m=0;
     while(1)
     {
        t[k] = b[k]+c[k]+m;
        
         if(t[k]>MAX)
         {
             m= t[k]/MAX;
             t[k] %= MAX;
         }
         else
            m=0;
            
         if(t[k]>0)   
            ++k;
         else
            break;      
     }
     
     return k-1;   
}              

void fenduan(long long s,int*c)
{
    //将a[91]和a[92]用数组分段保存 
    int i=0;    
    while(s>MAX)
    {
       c[i] = s%MAX;
       i++;
       s/= MAX;     
    }
    c[i]= s;
}


intmain()
{
    int n,pi;
    long long a[1001]={0,1};
    for(int i=2;i<93;++i)
        a[i]=a[i-1]+a[i-2];

    
    cin>> n;
    while(n--)
    {
        
        int b[1000]={0};
        int c[1000]={0};
        int t[1000]={0};
        fenduan(a[91],b);
        fenduan(a[92],c);
        
        int* t1=t;
        int* b1=b;
        int* c1=c;
        int l;

        cin>>pi;
        if(pi<=92)
        {
           cout<<a[pi]<<endl;
           continue;
        }
            
        else
        {
            
            for(int k=93; k<= pi; ++k)
            {     
               l= add(b1,c1,t1);
     
               if(k!=pi)
               {    
                  int*temp= b1;
                  b1= c1;  
                  c1= t1;   
                  t1= temp;   
               }
            }
                      
        }
               
       cout<<t1[l];
       while(--l,l>-1)
          printf("%08d",t1[l]);
       cout<<"\n";    
               
    }
    
    return0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注