经典算法题：牛的繁衍问题

if(cow.it_can_be_a_Mother()){

cows.add(cow.generateChild());

}

}

}

return cows.size();

}

测试代码：

import java.util.Vector;

public class Test {

public static final int YEARS = 10;

public static void main(String args[]){

//面向对象的解法

System.out.println("牛的总数是："+ooCow());

//数组解法

System.out.println("牛的总数是："+funCow());

//回朔解法

System.out.println("牛的总数是："+generateCow(3));

}

public static int ooCow(){.....}

public static int funCow(){ ....}

public static int generateCow(int adult){ ....}

}

总结：

据测试，以上三种方法中，数组实现的方法是最高效率的，其空间复杂度为O(1),而时间复杂度为O(N),在效率上，是其他两种方法不可比拟的，其次是回溯法的解法，从逻辑设计上，面向对象的解法是最容易理解的。这道题相信还存在着多种更优秀解题思路，如果从数学角度上进行分析归纳，或许还有效率更优的算法。这是昨天在csdn论坛上看到的一道题，觉得比较有趣，这里把自己的几种做法写出来。

问题大概：

假设有一种牛，3岁成年，成年后具备自交能力，也就是说不用公牛帮忙，每年可以生产出一只同种类的牛，问如果一个农场有1只该品种0岁的 牛，不考虑牛的寿命问题，那么10年后农场总共 有多少只牛？

说明：

其实原问题没有这么复杂，但是考虑到一些不必要的争议，所以加了不少题设。从题面上看，头两年第一只牛只能孤独的度过，到了第三年开始，牛会诞下第一个孩子，接下来的每一年都会继续生育，而生下来的孩子三岁成年后也会加入生育大军，孩子的孩子也会陆续具备生育能力。。。

推算结果:

第1年生育有1只牛

第2年生育有1只牛

第3年生育有2只牛

第4年生育有3只牛

第5年生育有4只牛

第6年生育有6只牛

第7年生育有9只牛

第8年生育有13只牛

第9年生育有19只牛

第10年生育有28只牛

牛的总数是：28

算法:

1.回溯算法实现:

/**

* @param: adult 成年的年份

*/

public static int generateCow(int adult){

//孩子总数

int child = 0;

//计算从成年开始到第10个年头，每个年头诞生的孩子及其孩子们衍生出来的子孙的总数。

for(int i=adult;i<=YEARS;i++){
child += generateCow(i+3);

}

//加上本身

return child+1;

}

2.利用数组作为辅助结构的解法(三种解法中最高效)：

public static int funCow(){

//各年龄段未成年牛的总数

int[] nonAge = new int[4];

//牛的总数

int total = 1;

//妈妈的数量

int mum = 0;

//当前0岁的牛的头数

nonAge[3] = 1;

//数组指针，用于实现环形顺序表

int point = 1;

for(int i=1;i<=YEARS;i++){
mum+=nonAge[point%4];

total+=mum;

nonAge[(point+3)%4] = mum;

point++;

}

return total;

}

3.面向对象的解法：

class Cow {

public int age=0; //年龄

//是否能成为妈妈

public boolean it_can_be_a_Mother(){

return age >= 3;

}

//生育

public Cow generateChild(){

return new Cow();

}

//长大一岁

public void Grow(){

age++;

}

}

(2)产牛流程

public static int ooCow(){

//牛的集合

Vector cows = new Vector();

//第一只牛

Cow firstCow = new Cow();

//加入集合

cows.add(firstCow);

for(int i=1;i<=YEARS;i++){
int cowSize = cows.size();

for(int j=0;j Cow cow = (Cow)cows.elementAt(j);

cow.Grow();

2009/11/3 0:18:09