标题:!!养兔子问题!
只看楼主
Mrcui233
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2019-10-13
结帖率:0
已结贴  问题点数:20 回复次数:2 
!!养兔子问题!
一对成熟的兔子每月能且只能产下一对小兔子,每次都生一公一母,每只小兔子的成熟期是一个月,而成熟后的第二个月才开始生小兔。某人领养了一对小兔子,一公一母,请问第N个月以后,他将会得到多少对兔子。

输入

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

输出

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

样例输入
1
2
0
样例输出
1
2
搜索更多相关主题的帖子: 兔子 输出 输入 现象 对应 
2019-10-13 16:57
自学的数学
Rank: 13Rank: 13Rank: 13Rank: 13
等 级:贵宾
威 望:46
帖 子:967
专家分:4146
注 册:2017-11-15
得分:10 
程序代码:
#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;

 }
}
2019-10-13 17:45
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:507
帖 子:8890
专家分:53117
注 册:2011-1-18
得分:10 
首先应当能看出这是个 斐波那契数列,于是有代码
程序代码:
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] );
    }
}
2019-10-14 09:34



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-497240-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.119312 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved