F



i



v



e



-



gr



ea



t
某种序列


某种序列

时间限制:3000 ms | 内存限制:65535 KB 难度:4

描述

数列A满足An = An-1 + An-2 + An-3, n >= 3 编写程序,给定A0, A1 和 A2, 计算A99

输入

输入包含多行数据 每行数据包含3个整数A0, A1, A2 (0 <= A0, A1, A2 <= 100000000)

数据以EOF结束

输出

对于输入的每一行输出A99的值

样例输入

1 1 1

样例输出

69087442470169316923566147


思路:数组存储,递推

#include<stdio.h>
#include<string.h>
#define M 100000
int sum[5][11];
void f(int x,int a)
{ int j=0;while(a)sum[x][j++]=a%M,a=a/M;}
int main()
{
    int a,b,c,i,j,n,k,adw;
    while(scanf("%d%d%d",&a,&b,&c)==3){
        memset(sum,0,sizeof(sum));
        if(a==0&&b==0&&c==0){printf("%d\n",0);continue;}
        f(0,a);f(1,b);f(2,c);int c1=0,c2=1,c3=2,c4=3;
        for(i=3;i<=99;++i){
            adw=0;//进位 
            for(j=0;j<=10;++j){
                sum[c4][j]=sum[c1][j]+sum[c2][j]+sum[c3][j]+adw;
                adw=sum[c4][j]/M;
                sum[c4][j]%=M;
            }
            c1=(c1+1)%4;c2=(c2+1)%4;c3=(c3+1)%4;c4=(c4+1)%4;//更新滚动 
        }
        for(i=10;i>=0;--i)if(sum[c3][i]!=0)break;
            for(j=i;j>=0;--j)
            if(j==i)printf("%d",sum[c3][j]);
            else printf("%05d",sum[c3][j]);
            printf("\n");}
    return 0;
}


  转载请注明: Five-great的博客 某种序列