[数据结构——递归]母牛的故事（蓝桥杯1004）

本文主要是介绍[数据结构——递归]母牛的故事（蓝桥杯1004），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

[数据结构——递归]母牛的故事（蓝桥杯1004）

一、题目内容

题目描述：

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

输入格式：

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

n=0表示输入数据的结束，不做处理。

输出格式：

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

每个输入占一行。

样例输入：

样例输出：

二、思路分析

首先进行输入数据的判断，使用while循环最方便，会一直等到用户输入0，才会停止。因此，在写判断的时候一定要放在调用方法的前面。

我定义了一个方法productOx对母牛的数量进行判断。

根据样例发现，初始的这一头母牛在第一年不生母牛，第二年才生一头母牛，并且出生的母牛，在它出生的第4年才会生母牛。

那么可以看作第一年初始母牛出生，第二年生母牛，并且这个母牛在它自己出生的第4年开始生母牛。

因此（关键），当第二年出生的母牛可以看作为，它自己在初始母牛母牛生它的第3年，它自己出生，并且第二年开始生母牛。这样逻辑变和初始母牛的逻辑一样，可以变成递归了。两头母牛都是在自己出生的第二年开始生母牛，并且两头牛的时间相差3年。

再次总结变成，初始母牛第二年开始生母牛，加上3年后的每一年加入一头相同的初始母牛开始生母牛。

三、代码实现

public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (true) {// 从用户输入读取年份int year = sc.nextInt();// 如果年份为0，则退出循环if (year == 0) {break;}// 调用productOx方法计算并打印出年份的乘积int productOx = productOx(year);System.out.println(productOx);}
}// 计算年份的乘积
private static int productOx(int year) {if (year <= 3) {return year;}// 递归调用productOx方法，并将结果相加return productOx(year - 1) + productOx(year - 3);
}