nyoj--114--某种序列（滚动数组)

某种序列

时间限制：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>

#include<algorithm>

using namespace std;

#define N 110

int a[N];

int b[N];

int c[N];

int sum[N];

void init(int x,int a[])

{

	int i=0;

	while(x)

	{

		a[i++]=x%10;

		x/=10;

	}

}

int main()

{

	int aa,bb,cc;

	while(scanf("%d%d%d",&aa,&bb,&cc)!=EOF)

	{

		int i,j,t;

		memset(a,0,sizeof(a));

		memset(b,0,sizeof(b));

		memset(c,0,sizeof(c));

		init(aa,a);

		init(bb,b);

		init(cc,c);

		for(i=3;i<=99;i++)

		{

			memset(sum,0,sizeof(sum));

			for(j=0;j<N;j++)

			{

				sum[j]+=(a[j]+b[j]+c[j]);

				if(sum[j]>9)

				{

					t=sum[j];

					sum[j]=t%10;

					sum[j+1]=t/10;

				}

			}

			for(j=0;j<N;j++)

			{

				a[j]=b[j];

				b[j]=c[j];

				c[j]=sum[j];

			}

		}

		for(j=N-1;j>0&&sum[j]==0;j--);

		for(;j>=0;j--)

			printf("%d",sum[j]);

		printf("\n");

	}

	return 0;

}

巴特西

nyoj--114--某种序列（滚动数组)

某种序列

最新文章

热门文章