LikeWater - 1004: [递归]母牛的故事C++（曾经的你对我嗤之以鼻，现在的我你高攀不起(‾◡◝)）

857 阅读 5 评论 0 点赞

***—————依稀记得那是第一次使用dotcpp来学习c++提升直接的编程能力，当时第一个遇到的第一个题目就是这个母牛的故事，当时仗着自己的学过递归，感觉能做出来，但是是我小瞧递归了，时间超限是我永远的痛。今天偶然又看到这个题，居然看到它还没有通过，这是我不能容忍的，现在虽然轻松解决，也知道了递归为什么这么容易时间超限，但是过去再也回不去了。（强行感慨，能力增强肯定更开♥:bowtie:）***

**当时跟这个题目就杠上了，每次都时间超限说实话还是挺不舒服的，知道是递归的问题，但是也不知道怎么解决，后面就搁置了，现在王姐归来，再刷此题，倒是发现也是一个不错的题目，下面给出我的两种解法。**

*1、记忆递归法：采用递归形式，但是用全局数组变量记录递归结果，避免二次重复递归占用时间，这里的递归公式由下表推测而出。*

|年份|1|2|3|4|5|6|
|:------------:|
|数量|1|2|3|4|6|9|

**可以看到规律是很明显的，4=3+1；6=4+2；9=6+3；用公式来表示就是第n年的数量等于第n-1年的数量加上第n-3年的数量，即f(n)=f(n-1)+f(n-3);这就是递归的公式。**

***PS：推导递归公式的思想适用于几乎所有递归的情况，因为递归它比较死板，所以推到的过程也是死板的，虽然它比较好用，但是由于它每次递归都会占用新的空间，同时也会占用大量的时间，所以只适用于小数目的递归，一旦数量级上去了，递归的层次变深了，它的实用度就没有那么高了，反而容易成为累赘，所以我给出了第二种非递归的算法。***

记忆递归算法；C++；不超时
```cpp11
#include<iostream>
using namespace std;

int fn[55]={0,1,2,3,4};//全局变量记录母牛数量

int f(int n){//递归母牛
    if(n<=4)return n;
    else if(fn[n] == 0){
        fn[n] = f(n-1) + f(n-3);//数组记录递归结果，加快速度,记忆递归
        return fn[n];
    }
    else if(fn[n]!=0)return fn[n];
}

int main()
{
    int n=1;
    while(~scanf("%d",&n) && n!=0){//~按位取反
        printf("%d\n",f(n));
    }
    return 0;
}

```
运行结果如下：
![母牛的故事-递归](/image_editor_upload/20230305/20230305093733_52264.png "母牛的故事-递归")
*2、非递归法：采用循环来计算母牛数量，同样用全局变量记录年份的母牛数量，不用占用额外空间，效率更高。*
```cpp
#include<iostream>
using namespace std;
int fn[55]={0,1,2,3,4};//全局变量记录母牛数量

int main()
{
    int n=1;
    while(~scanf("%d",&n) && n!=0){//~按位取反
        if(n<=4)printf("%d\n",n);
        else if(fn[n] == 0){
            for(int i=5;i<=n;i++){
                fn[i] = fn[i-1] + fn[i-3];
            }
            printf("%d\n",fn[n]);
        }
        else if(fn[n]!=0)printf("%d\n",fn[n]);;
    }
    return 0;
}
```
运行结果如下：
![母牛的故事-非递归](/image_editor_upload/20230305/20230305094130_70761.png "母牛的故事-非递归")

***上面看起来两者内存，用时都差不多，但是如果直接用纯递归的形式一下子就能看出很大差别，即使是记忆递归，数量级上去了依然比不过非递归循环来的优势大，大家可以自行改写一些n的范围来测试时间和空间复杂度。但是递归和循环都是蓝桥杯必考的内容，大家两者都需要掌握，有什么问题欢迎大家留言:smile:***

0.0分

11 人评分

本文分类：题解列表
浏览次数：857 次浏览
发布日期：2023-03-05 21:44:16
本文链接：https://blog.dotcpp.com/a/94564

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表共有 5 条评论

Lingxici074 11月前回复TA

大佬你是我滴神，直接给我醍醐灌顶啊

LikeWater 1年前回复TA

@渚一叶 所以2、scanf返回值是int类型，如果不加~按位取反，那么当你输入出错的时候就不会执行循环，这里是为了格式规范，不加这个题是没有问题的。

LikeWater 1年前回复TA

@渚一叶 首先1、scanf函数返回成功读入的数据项数，读入数据时遇到了“文件结束”则返回EOF。  如：scanf("%d %d",&a,&b);  函数返回值为int型。如果a和b都被成功读入，那么scanf的返回值就是2；  如果只有a被成功读入，返回值为1；  如果a和b都未被成功读入，返回值为0；  如果遇到错误或遇到end of file，返回值为EOF。end of file为Ctrl+z 或者Ctrl+d。

渚一叶 1年前回复TA

请问为什么要加上这个~？

LikeWater 1年前回复TA

666666666666666666666666666666666

LikeWater - 1004: [递归]母牛的故事C++（曾经的你对我嗤之以鼻，现在的我你高攀不起~~(‾◡◝)~~）

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 5 条评论

发表评论 取消回复

LikeWater - 1004: [递归]母牛的故事C++（曾经的你对我嗤之以鼻，现在的我你高攀不起(‾◡◝)）

评论列表共有 5 条评论

发表评论取消回复