LikeWater

用户名：dotcpp0632461

访问量：6950

签　名：

KaMi

等　　级
排　　名	455
经　　验	4782
参赛次数	0
文章发表	90
年　　龄	0
在职情况	学生
学　　校	长江大学
专　　业	电子信息

　　自我简介：

TA的其他文章

LikeWater - 1097: 蛇行矩阵
浏览：26

LikeWater - 2701: 蓝桥杯真题-取模（请问有谁知道看错题的痛！一直看成n mod x == m mod y 隔这儿一只写。。。）
浏览：298

你可能喜欢

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

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

　　作者: LikeWater　　　　发表时间：2023-03-05 21:44:16 浏览：753　|　评论：3　

原题链接：[递归]母牛的故事

***—————依稀记得那是第一次使用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分

15 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

Lingxici074

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

2024-02-13 17:52:30

渚一叶

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

2023-03-07 00:30:08

LikeWater

666666666666666666666666666666666

2023-03-05 21:48:55

LikeWater

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

用筛法求之N内的素数。（C语言代码）

明明的随机数（C++代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C二级辅导-等差数列（C语言代码）

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

评论区

精彩推荐

震宇大神的杀毒软件（C++代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

WU-蓝桥杯算法提高VIP-交换Easy （C++代码）

WU-陶陶摘苹果2 （C++代码）

简单的a+b （C语言代码）

用筛法求之N内的素数。（C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

LikeWater

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

用筛法求之N内的素数。 （C语言代码）

明明的随机数 （C++代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C二级辅导-等差数列 （C语言代码）

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

评论区

精彩推荐

震宇大神的杀毒软件 （C++代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

WU-蓝桥杯算法提高VIP-交换Easy （C++代码）

WU-陶陶摘苹果2 （C++代码）

简单的a+b （C语言代码）

用筛法求之N内的素数。 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

用筛法求之N内的素数。（C语言代码）

明明的随机数（C++代码）

C二级辅导-等差数列（C语言代码）

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

　　评论区

震宇大神的杀毒软件（C++代码）

用筛法求之N内的素数。（C语言代码）