杭电ACM 2020:母牛的故事|解决

418次阅读
没有评论

1、母牛的故事 原题展示:

杭电ACM

/>

2、题目讲解:

这个题还是递归和找规律的问题,做这种问题,就需要自己手动写一段排列,找其中的规律,无非就是递归问题。找到规律后就可以使用代码来实现这个功能即可。

这里面有一个坑,那就是题目说的是第四年年初的母牛会生一头小母牛,其实这头母牛才长了整三年,

第n年: n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9
fn头牛? f1=1 f2=2 f3=3 f4=4 f5=6 f6=9 f7=13 f8=19 f9=28

手动推导如上:

可以看出规律了,以n = 6年为例,f6=9=6+3=f5(6) + f3那一年的三头在 f3到f6 这三年生的母牛(三头母牛各生一个=3只),也可以再验证其他年。

好了,规律已经找到,那就开始 AC 代码吧!

3、AC代码讲解:

3.1、递归代码

简洁明了,但是运行效率很低。

#include<iostream>
using namespace std;

int loop(int x){
    if(x<4)
        return x;
    return loop(x-1)+loop(x-3);
}

int main(){
    int x;
    while(cin>>x, x){
        cout<<loop(x)<<endl;
    }

    return 1;
}

3.2、使用数组

#include<iostream>
#include<string>
using namespace std;

int main(){
    int x;
    int arr[56] = {0, 1, 2, 3};
    for(int i=0;i<=55;++i){
        arr[i] =arr[i-1] + arr[i-3];
    }
    while(cin>>x, x){
        cout<<arr[x]<<endl;

    }

    return 1;
}

总结

多动手找规律,有问题,多多记录。

参考文章:

https://blog.csdn.net/sxhelijian/article/details/42609353

3
西园公子
版权声明:本站原创文章,由西园公子2021-02-12发表,共计767字。
转载提示:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(没有评论)
载入中...