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>

 

评论

16 楼 samkifeng 2013-04-16  

牛的规律是：1，1，2，3，5，8，...

public static void main(String[] args) {
// TODO Auto-generated method stub
int i;
for(i = 1;i<=10;i++){
System.out.println(fun(i));
}

}

public static int fun(int x){
if(x==1 || x==2){
return 1;
}else{
return fun(x-2)+fun(x-1);
}
}

结果：
1
1
2
3
5
8
13
21
34
55

不知道对不对。

15 楼 lispnet 2013-04-12  

别看14楼，错了，题目没看清

14 楼 lispnet 2013-04-12  

public int Getcow(int n){     
     if(n>=3)
      return 2*(n/3);
     else
      return 1;
}

13 楼 jaketyao 2013-04-12  

这是Fibonacci数列！

12 楼 中国凉茶 2013-04-12  

45088648 写道

DxcLove_Java 写道

一头牛自己怎么生？？？

是印度神牛啊

最后还是牛肉干

11 楼 45088648 2013-04-12  

DxcLove_Java 写道

一头牛自己怎么生？？？

是印度神牛啊

10 楼 yangjianzhouctgu 2013-04-11  

我想我已经知道这个公式的意思了，我转载了你的这篇文章，里面有我的想法，你可以看看我对式子的理解是否正确

9 楼 vawe666 2013-04-11  

8 楼 kuyefeiwu0 2013-04-11  

额 我没验证算法的正确性，我想说的是 数量的累计方式 1 1 2 3 5 8 13 21 累计上去的，第八年的时候你要新增21个对象，我想如果输入100年，那你不是要弄出许多的对象，我是半路出家的程序员，我的前辈跟我说：算法要尽量减少资源的损耗。貌似你这样对资源的损耗比较大把

7 楼 yangjianzhouctgu 2013-04-11  

楼主，请问个问题啊： num[i] = num[i - 1] + 1 + num[i - 3]; 这里为什么要加1啊？

6 楼 QuarterLifeForJava 2013-04-11  

根据楼主的算法七年后有9头牛？难道我对题目的意思理解错误了？看下：
第1年
第1年
第1年
第1年
第1年
第1年

5 楼 DxcLove_Java 2013-04-11  

一头牛自己怎么生？？？

4 楼 45088648 2013-04-11  

难道这就是传说中的印度神牛

3 楼 中国凉茶 2013-04-11  

Michael.L 写道

十年后第一头牛死了没。

十年之后，牛不在是牛，牛已变成牛肉干。

2 楼 MrLee23 2013-04-11  

Michael.L 写道

十年后第一头牛死了没。

当然没死，题目里没说就是没死

1 楼 Michael.L 2013-04-11  

十年后第一头牛死了没。