牛的问题

 http://blog.csdn.net/zhong317/archive/2009/11/02/4757827.aspx

问题大概：

 假设有一种牛，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年生育有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;


    }

/** * @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;
  }

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.面向对象的解法：

 

 (1)牛的类

  

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++;
    }


}

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();
          if(cow.it_can_be_a_Mother()){
             cows.add(cow.generateChild());
          }

        }


        }
        return cows.size();


   }

public static int ooCow(){ //牛的集合 Vector<Cow> cows = new Vector<Cow>(); //第一只牛 Cow firstCow = new Cow(); //加入集合 cows.add(firstCow); for(int i=1;i<=YEARS;i++){ int cowSize = cows.size(); for(int j=0;j<cowSize;j++){ Cow cow = (Cow)cows.elementAt(j); cow.Grow(); 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));
   }

}

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)); } }

总结：

据测试，以上三种方法中，数组实现的方法是最高效率的，其空间复杂度为O(1),而时间复杂度为O(N),在效率上，是其他两种方法不可比拟的，其 次是回溯法的解法，从逻辑设计上，面向对象的解法是最容易理解的。这道题相信还存在着多种更优秀解题思路，如果从数学角度上进行分析归纳，或许还有效率更 优的算法，有待日后探究，如有更好的思路，望不吝赐教！