母牛的故事（C++描述）

我就是我 2023-07-03 07:09 25阅读 0赞

# **题目：母牛的故事** #

## 题目描述： ##

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

### 输入 ###

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

### 输出 ###

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

### 样例输入 ###

2
    4
    5
    0

### 样例输出 ###

2
    4
    6

## 解析： ##

由于是多组输入输出，做过算法题的人都应该知道，在输入时用模板

while (cin >> n && n != 0)
    {
       /代码/
    }

拿到这题的时候第一反应是有可能这是一个递归题

我们先分析一下

<table style="width:480px;"> 
 <tbody> 
  <tr> 
   <td style="width:89px;">n</td> 
   <td style="width:38px;">1</td> 
   <td style="width:36px;">2</td> 
   <td style="width:44px;">3</td> 
   <td>4</td> 
   <td>5</td> 
   <td>6</td> 
   <td style="width:35px;">7&nbsp;</td> 
   <td style="width:126px;">................................</td> 
  </tr> 
  <tr> 
   <td style="width:89px;">母奶牛数量</td> 
   <td style="width:38px;">1</td> 
   <td style="width:36px;">2</td> 
   <td style="width:44px;">3</td> 
   <td>4</td> 
   <td>6</td> 
   <td>9</td> 
   <td style="width:35px;">12</td> 
   <td style="width:126px;">&nbsp;</td> 
  </tr> 
 </tbody> 
</table>

为了方便标记 将第n年的母奶牛数量设为num\[n\]

> ### 当n<=4时： ###
> 
> 由于每一个新生的母奶牛在第四年才能开始生新的小母奶牛，所以在 n<=4 的时候，数量并没有复利式的增长，全部都是由最初的母奶牛所生
> 
> 所以n<=4：num\[n\] = n;
> 
> ### 当n>4时： ###
> 
> 可以试想一下：
> 
> 第n年的奶牛的数量由什么组成？
> 
> 其中会有第n-1年的数量
> 
> 那么num\[n\]比num\[n-1\]多的因素是什么？
> 
> 就是因为三年前的num\[n-3\]中不能生奶牛的小奶牛已经全部成长为可以生新母奶牛的老母奶牛
> 
> 那么现在母奶牛里面可以生新奶牛的奶牛数量为num\[n-3\]
> 
> 所以，第n年的全部奶牛数量可以表示为：
> 
> num\[n\] = num\[n-1\] + num\[n-3\]

为了使得程序更加简洁

在代码里面设置一个数组num\[N\]

由于题目要求，其中N=55

数组设置初始值：num\[N\] = \{0, 1, 2, 3, 4\}

可以实现当n<=4时，num\[n\] = n

代码如下：

#include<iostream>
    using namespace std;
    #define N 55
    int main()
    {
        int n, i;
        int num[N] = {0,1,2,3,4};  //num[0]=0,num[1]=1,num[2]=2,num[3]=3,num[4]=4
        for (i = 5; i < 55; i++)
            num[i] = num[i - 1] + num[i - 3];
        while (cin >> n && n != 0)  //输入 n 的值，且 n 不等于0，则进入，否则退出
        {
            cout << num[n] << endl;
        }
        return 0;
    }