2021蓝桥备战

题目 1004: [递归] 母牛的故事

题目

时间限制: 1Sec 内存限制: 128MB

题目描述

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

输入

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

输出

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

样例输入

2
4
5
0

样例输出

2
4
6

题解

思路

蓝桥杯 JAVA 需要注意几个地方：

• 类命名：public class Main
• 方法命名：public static void main(String[] args) {}
• int的取值范围为（ -2147483648 ~ 2147483647），20 亿，占用 4 个字节（ \(-2^{31}\) ~ \(2^{31}-1\) ），一个字节占 8 位，也就是 32 位。
• 蓝桥杯的输入为键盘输入，输出结果为打印到控制台。
• 不要package字段。
• import包导入要包含。

然后就是本题的思路吧，递归基本不要想了，大概率会超时，也可以给个代码：

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      while (n!=0) {//不为0时可以继续输入
		System.out.println(tou(n));
		n=sc.nextInt();
		if (n==0) {//关闭资源
			sc.close();
			break;
		}
	}
    }
    static int tou(int n){
    	//牛的头数  1 2 3 4 6 9 13 19 28....
    	//从上面我们可以看出来从第四年开始 牛的头数等于前一年加上三年前
    	if (n<=4) 
			return n;
    	else
    	return tou(n-1)+tou(n-3);
    	
    }
}

接下来就是不递归的做法：

先列个表观察一下母牛的数量

年份	1	2	3	4	5	6	7	8	9	…
母牛数量（S）	1	2	3	4	6	9	13	19	28	…

那么其实可以看出来，从第五年开始，是有迹可循的。具体如下： \[ S(n) = S(n - 1) + S(n - 3) \qquad n ≥ 5 \] 既然如此，就可以写非递归程序了：

• 新建数组int num[] = new int[n + 1]，存放每年牛的数量，每个数组元素为一年的数量；
• num[i] = num[i - 1] + num[i - 3]

参考：

蓝桥杯（Java）注意事项_哈哈er的博客-CSDN博客_蓝桥杯java

蓝桥杯java组注意事项 - 臭蛋1999 - 博客园 (cnblogs.com)

代码

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		while (n != 0) {

			int num[] = new int[n + 1];
			for (int i = 1; i <= n; i++) {
				if (i <= 3) {
					num[i] = i;
				} else {
					num[i] = num[i - 3] + num[i - 1];
				}
			}
			System.out.println(num[num.length - 1]);
			n = sc.nextInt();
		}
	}
}