一对成熟的兔子每月能且只能产下一对小兔子，每次都生一公一母，每只小兔子的成熟期是一个月，而成熟后的第二个月才开始生小兔。某人领养了一对小兔子，一公一母，请问第N个月以后，他将会得到多少对兔子。

输入

测试数据包括多组，每组一行，为整数n(1≤n≤90)。
输入以0结束。

输出

对应输出第n个月有几对兔子(假设没有兔子死亡现象，而且是一夫一妻制)。

样例输入
1
2
0
样例输出
1
2

#include<iostream>
using namespace std;
int main()
{

 long long int a,b,c[1000],i;

 while( cin>>a&&a!=0)

 {

 c[1]=1;

 c[2]=2;

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

 {

 c[i]=c[i-1]+c[i-2];

 }

 cout<<c[a]<<endl;

 }
}

首先应当能看出这是个 斐波那契数列，于是有代码

unsigned fs( unsigned n )
{
    unsigned a=0, b=1;
    for( unsigned i=0; i!=n; ++i )
    {
        b = b + a;
        a = b - a;
    }
    return b;
}

然后，题目要求 1≤n≤90，那么当n==90时上面的代码 b = b + a 会不会有溢出呢？只能测试一下

#include <stdio.h>
#include <stdlib.h>

unsigned fs( unsigned n )
{
    unsigned a=0, b=1;
    for( unsigned i=0; i!=n; ++i )
    {
        if( b+a<a )
        {
            printf( "当 n == %u 时结果溢出\n", n );
            exit( 1 );
        }

        b = b + a;
        a = b - a;
    }
    return b;
}

int main( void )
{
    for( unsigned n=0; n<=90; ++n )
    {
        printf( "%u - %u\n", n, fs(n) );
    }
}

运行后发现当 n==47 时就发生溢出了。于是将类型改大后再测试

#include <stdio.h>
#include <stdlib.h>

unsigned long long fs( unsigned n )
{
    unsigned long long a=0, b=1;
    for( unsigned i=0; i!=n; ++i )
    {
        if( b+a<a )
        {
            printf( "当 n == %u 时结果溢出\n", n );
            exit( 1 );
        }

        b = b + a;
        a = b - a;
    }
    return b;
}

int main( void )
{
    for( unsigned n=0; n<=90; ++n )
    {
        printf( "%u - %llu\n", n, fs(n) );
    }
}

这回没溢出了，很好，于是你有了第一份可提交的代码

#include <stdio.h>

unsigned long long fs( unsigned n )
{
    unsigned long long a=0, b=1;
    for( unsigned i=0; i!=n; ++i )
    {
        b = b + a;
        a = b - a;
    }
    return b;
}

int main( void )
{
    for( unsigned n=0; scanf("%u",&n)==1 && n!=0; )
        printf( "%llu\n", fs(n) );
}

然后题目要求多次输入，你一想，这会不会导致fs重复计算呢？比如先输入40再输入50，当计算f(50)时其实前面的f(40)已经算过了，可是改一改有了第二份可提交的代码

#include <stdio.h>

int main( void )
{
    unsigned long long fs[91] = { 1, 1 };
    for( unsigned i=2; i!=sizeof(fs)/sizeof(*fs); ++i )
        fs[i] = fs[i-2] + fs[i-1];

    for( unsigned n=0; scanf("%u",&n)==1 && n!=0; )
        printf( "%llu\n", fs[n] );
}

那有没有可能出题者很狡诈，说是n<=90，但他给出的测试用例不是每次都有n==90，没有的话，f(90)就白算了，浪费了运行时间。于是改为只结算到最大的输入数

#include <stdio.h>

int main( void )
{
    unsigned long long fs[91] = { 1, 1 };
    unsigned m = 2;

    for( unsigned n=0; scanf("%u",&n)==1 && n!=0; )
    {
        for( ; m<=n; ++m )
            fs[m] = fs[m-2] + fs[m-1];

        printf( "%llu\n", fs[n] );
    }
}