Java算法—农夫和牛的问题

问题：一个农夫养了一头牛，三年后，这头牛每年会生出一头牛，生出来的牛三年后又可以内年生出一头牛....问农夫10年后有多少头牛，n年呢？

java面向对象方式解决：

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 问题：一个农夫养了一头牛，三年后，这头牛每年会生出一头牛，生出来的牛三年后又可以内年生出一头牛....问农夫10年后有多少头牛，n年呢？
 * 
 * @author liang
 */
public class Cow {// 定义牛类
	private int age = 0;// 定义牛的初始年龄

	// 记录牛的年龄，每过一年，牛的年龄加1
	public void addAge() {
		age++;
	}

	// 判断是否到了生育年龄
	public boolean isCreatCow() {
		return (age >= 3) ? true : false;
	}

	public static void main(String[] args) {
		List<Cow> cowList = new ArrayList<Cow>();
		// 农夫原有的第一头牛
		cowList.add(new Cow());
		int yearCount;// 年份
		// 提示用户输入年份
		Scanner scanner = new Scanner(System.in);
		System.out.print("请您输入牛生长了多少年,输入后按回车可看到牛的数量奥：\n");
		yearCount = scanner.nextInt();// 输入年份
		for (int i = 1; i <= yearCount; i++) {// 根据输入的年份对牛进行循环计算，每过一年，牛的年龄都增加一岁
			int cowNum = cowList.size();// list中有多少行数据，就有几头牛，定义变量，取得list中的行数，即牛的数量
			for (int j = 0; j < cowNum; j++) {
				Cow o = cowList.get(j);// 取出要进行生育的牛
				// 每重复取到一头牛时，都意味着根据年份进行了一次新的循环，也就是又过了一年，所以每次新取出一头牛进行生育判断时，都要将这头牛的年龄加1
				o.addAge();
				// 对牛进行生育判断
				if (o.isCreatCow()) {
					// 如果这头牛到了生育年龄，就让牛生小牛
					cowList.add(new Cow());
				}
			}
		}
		System.out.println(yearCount + "年后将有<--" + cowList.size() + "-->头牛。");
	}
}

 第二种方式：

public class Cow {
	public static int count = 0;

	public Cow(int year) {
		count++;
		for (int i = 3 + year; i <= 10; i++) {
			new Cow(i);
		}
	}

	public static void main(String[] args) {
		new Cow(0);
		System.out.println(count);
	}
}

 递归方式解决：

public class Cow {
	static int count = 1;

	private static void feedCow(int year, int age) {
		year++;
		age++;
		if (year <= 10) {
			if (age >= 3) {
				count++;
				feedCow(year, 0);
			}
			feedCow(year, age);
		}
	}

	public static void main(String[] args) {
		new Cow().feedCow(0, 0);
		System.out.println(count);
	}
}

 动态规划算法算法时间和空间复杂度均为O(n),n为年数：

<span style="font-size: 14px;">public class CowBreed {
	public static void main(String args[]) {
		final int size = 100; // 可以根据需要，设置为所需要计算的最大年限
		long[] num = new long[size + 1];
		num[0] = num[1] = num[2] = 0;
		for (int i = 3; i <= size; ++i) {
			num[i] = num[i - 1] + 1 + num[i - 3];
			System.out.println("第" + i + "年，牛的数量为：" + (num[i] + 1));
		}
	}
}</span>