递归求母牛个数（递归法和数组法）

末蓝、 2023-10-11 17:51 38阅读 0赞

**目录**

简介：

输入格式：

输出格式

样例输入

样例输出

解析

代码

改进代码

总结

--------------------

## 简介： ##

> 有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？

### 输入格式： ###

> 输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0<n<55)，n的含义如题目中描述。  
> n=0表示输入数据的结束，不做处理。

### 输出格式 ###

> 对于每个测试实例，输出在第n年的时候母牛的数量。  
> 每个输出占一行。

### 样例输入 ###

>     2
>     4
>     5
>     0

### 样例输出 ###

>     2
>     4
>     6

### 解析 ###

> 1.  题目很明显第一感觉你会想到用递归写，这是最简单并且最好想到的方法
> 2.  分析题目可知：第一年：1只、第二年：2只、第三年：3只、第四年：4只、第五年：6只，第七年：9只
> 3.  根据规律可知当从第五年开始之后，母牛个数等于前年母牛个数加上前三年母牛个数之和。
> 4.  ![f(n)=f(n-1)+f(n-3)(n>4)][f_n_f_n-1_f_n-3_n_4] 这就是递归式。

#### 代码 ####

def countcow(n):
        if n<= 4:
            return n
        else:
            return countcow(n-1)+countcow(n-3)
    s = [] #用来存储母牛数
    while(True):
        n = eval(input())
        if n <1 or n >55:
            break
        s.append(countcow(n))
    for i in s:
        if s !=0:
            print(i)

这样的时间复杂度太高，在有时间限制的情况下不推荐！

#### **改进代码** ####

s = []
    for i in range(1,56):
        if i<=4:
            s.append(i)
        else:
            n = s[i-2]+s[i-4]
            s.append(n)
    m = []
    while(True):
        n = int(input())
        if n == 0 or n==55:
            break
        m.append(n)
    for i in m:
        print(s[i-1])

这里采用数组，功能大同小异，可以自己看懂。

## 总结 ##

要理清楚递归的规律，虽然在有时间限制的情况下不推荐递归，可是递归这个概念对于理解某些题目有着很大的作用！！第三篇博客，加油！

[f_n_f_n-1_f_n-3_n_4]: https://latex.csdn.net/eq?f%28n%29%3Df%28n-1%29&plus;f%28n-3%29%28n%3E4%29