2020牛客国庆集训派对day2 VIRUS OUTBREAK

VIRUS OUTBREAK
@[toc]

题目描述

The State Veterinary Services Department recently reported an outbreak of a newly found cow disease. All cows found to have affected by the disease have since euthanized because of the risk to the industry. Number of affected cows increased to 21, 34 and reached 55 after eight, nine and ten hours respectively.
You have been assigned by the authority to study the pattern of the outbreak and develop a program to predict the next number of affected cows so that the authorities could prepare and act accordingly.

输入描述:

Input will consist of a series of positive integer numbers no greater than 490 each on a separate line represent the hours. The input process will be terminated by a line containing -1.

输出描述:

For each input value, the output contains a line in the format: \text { Hour } \mathbf{X}: \mathbf{Y} \text { cow(s) affected } Hour X:Y cow(s) affected , where \mathbf{X}X is the hour, and \mathbf{Y}Y is the total affected cows that need to be euthanized based on the hour given by \mathbf{X}X.

输入

1
4
6
11
-1

输出

Hour: 1: 1 cow(s) affected
Hour: 4: 3 cow(s) affected
Hour: 6: 8 cow(s) affected
Hour: 11: 89 cow(s) affected

题解：

直接看样例就不难看出是求斐波那契数列，再一看数据范围，果然是大数的斐波那契数列，我拿出珍藏的java版的斐波那契数列，java对写大数加减等这方面有得天独厚的优势
但是爷就想用c++来写咋办？
要知道300的斐波那契数列是222232244629420445529739893461909967206666939096499764990979600
longlong也存不下，那怎么办？我们就用数组来存数，就是一位一位的存，然后我们手写模拟加法过程，前两位相加等于第三位，记得考虑进位情况

代码：

#include <stdio.h>
#include <string.h>
#include<bits/stdc++.h>
using namespace std; 
int a[1005][1005];
int main()
{
    int T;
    int n;
    while(cin>>n)
    {
        if(n==-1)break;
        int c;
    int d=0;
    memset(a,0,sizeof(a));
    a[1][0]=1;a[2][0]=1;//第一个和第二个数要先保存下来 
    for(int i=3;i<=n;i++)//从第三个数开始都是等于前两个数的和 
    {
        c=0;//保存余数 
        for(int j=0;j<=d;j++)
        {
            a[i][j]=a[i-1][j]+a[i-2][j]+c;//计算结果 
            c=a[i][j]/10;//将其他的数进位 
            a[i][j]%=10;//将大于10的数要余数 
        }
        while(c!=0)//最后一位要是大于10，需要进位，并且最高位也需要加1！ 
        {
            a[i][++d]=c%10;
            c/=10;
        }
    }
    printf("Hour: %d: ",n);
    for(int i=d;i>=0;i--)//输出需要求的数的所有的位所有的值！ 
    {

        printf("%d",a[n][i]);
    }
    printf(" cow(s) affected\n");
    }


    return 0;
}