母牛繁殖问题
程序员文章站
2022-04-10 18:36:50
母牛的故事 有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？ Input 输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0
input
母牛的故事
有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？
input
输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0<n<55)，n的含义如题目中描述。
n=0表示输入数据的结束，不做处理。output对于每个测试实例，输出在第n年的时候母牛的数量。
每个输出占一行。
n=0表示输入数据的结束，不做处理。output对于每个测试实例，输出在第n年的时候母牛的数量。
每个输出占一行。
sample input
2 4 5 0sample output
2 4 6
1 #include <iostream>
2
3 using namespace std;
4
5 int sum(int n) //sum(n)表示第n年年初（第n年的母牛还没出生）母牛的数量
6 {
7 if (n <= 4)
8 return n;
9 return sum(n-3)+sum(n-1); //sum(n-3)表示3年前的母牛数量，这些母牛在第n-1年都能繁殖一倍
//sum(n-1)表示前一年年初的母牛数量
//所以第n-1年年初的母牛+在第n-1年出生的母牛 = 第n年年初的母牛
10 }
11
12 int main()
13 {
14 int n;
15 while (1){
16 cin >> n;
17 if (n == 0)
18 break;
19 int num = sum(n);
20 cout << num << endl;
21 }
22 }
感悟
运用递归方法：f(n)=f(n-1)+f(n-3)
递归就是把一个复杂的问题，分解成能用同一种方法解决的若干个小问题。