目录

题目：[递归]母牛的故事

思路：设求第 n 年的母牛数目为f(n)。

代码实现：动态规划

题目：[递归]母牛的故事

• 题目描述：有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？
• 输入：输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0<n<55)，n的含义如题目中描述。n=0表示输入数据的结束，不做处理。

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

• 样例输入

  2
  4
  5
  0

  样例输出

  2
  4
  6

思路：设求第 n 年的母牛数目为f(n)。

           n<=4时：第 n 年母牛总数为f(n) =  n 。

          n>4：第n 年母牛总数为第n-1年总数+第n年新出生的母牛数目。在第 n-3年 之前的母牛都会新生出母牛，每一头母牛生出一头新的小牛，则第 n -3 年有多少母牛，第n 年便会新增加多少头母牛。f(n) = f(n-1)+f(n-3)

代码实现：动态规划

package day1_19;

import java.util.Scanner;
//思路：
/*
 * 创建一个数组，用来存放从1-n每天的母牛数目
 * 在循环中读取n,判断如果n==0，则退出循环
 * 不为0，则for循环，i:1-n,i<=4时，则arr[i] = i,否则为arr[i] = arr[i-1]+arr[i-3]
 * 输出
 */
public class Main1 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] arr = new int[55];
		while(true) {
			int n = sc.nextInt();
			if(n==0) {
				break;
			}
			for(int i =1;i<=n;i++) {
				if(i<=4) {
					arr[i] = i;
				}
				else {
					arr[i] = arr[i-1]+arr[i-3];
				}
			}
			System.out.println(arr[n]);
		}
	}
}