java算法----农夫和牛

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

算法一：

package com.test;

public class AlgorithmOne {
	/**
	 * 动态规划算法
	 * @param args
	 * 数组num中存储的是新生的牛的数目，这里的新生表示除了最开始的一头牛外的所有其他牛
	 * 例如：num[3]表示到第3年来新生的牛的数目
	 * num[i] = num[i-1]+num[i-3]+1;
	 * 上面的式子表示：第i年的新牛数目为第i-1年的新牛数目加上第i-3年的新牛数目(因为第i-3年的牛仔第i年就会生小牛了),
	 * 再加上最开始的那头牛在第i年也会生出一头牛
	 */
	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]+num[i-3]+1;
			System.out.println("第"+i+"年，牛的数量:"+(num[i]+1));
		}
	}
}

算法二：

package com.bean;

public class Cow {
	
	private int age = 0;
	
	public void addAge(){
		age++;
	}

	public boolean isCreatCrow(){
		return (age>=3)? true:false;
	}
}

package com.test;

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

import com.bean.Cow;

public class AlgorithmTwo {

	public static void main(String[] args) {
		List<Cow> cowList = new ArrayList<Cow>();
		cowList.add(new Cow());
		int yearCount = 10;
		
		for(int i =1;i<=yearCount;i++){
			int cowNum = cowList.size();
			
			for(int j=0;j<cowNum;j++){
				Cow cow = cowList.get(j);
				cow.addAge();
				if(cow.isCreatCrow()){
					cowList.add(new Cow());
				}
			}
		}
		System.out.println(yearCount+"年后将有"+cowList.size()+"头牛");
	}
}

算法三：

package com.test;

public class AlgorthmThree {
	
	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 AlgorthmThree().feedCow(0, 0);
		System.out.println(count);
	}

}

算法四：

package com.bean;

public class CowBean {
	
	public static int count = 0;
	
	/**
	 * 算法核心：该算法计算每头牛包括其后代在这10年内能生了多少小牛
	 * @param year
	 * 每new一次CowBean就会执行count++
	 */
	public CowBean(int year){
		count ++;
		for(int i =3+year;i<=10;i++){
			new CowBean(i);
		}
	}
	
	public static void main(String[] args) {
		new CowBean(0);
		System.out.println(count);
	}

}

转载连接：http://hechuanzhen.iteye.com/blog/1845173

评论

2 楼 yangjianzhouctgu 2013-04-12  

中国凉茶 写道

恩，重构的很好，比我的方便简单。

这个程序就是您的，有些难懂得地方，我用自己的想法加了注释

1 楼 中国凉茶 2013-04-12  

恩，重构的很好，比我的方便简单。