母鸡算法

Question

有一道题：
有一只母鸡，每月生一只小母鸡，小母鸡长到每第四个月后每月又生一只小小母鸡，问20个月后母鸡的总数为多少？
写一个程程序解决这个问题 
刚遇到的难题， 求一个合适的解决方案， 附代码。

Answer 1

一般有两种方法：
1. 笨办法，计下所有的鸡
2. 找数学规律
[code=Jav]import java.util.ArrayList;
import java.util.List;public class HenGrow {
    public static void main(String[] args) {
        final int month = 20;
        // 方法1: 记录所有的鸡
        List<Integer> hen1 = new ArrayList<Integer>();
        hen1.add(100);        for (int i = 1; i <= month; ++i) {
            int size = hen1.size();
            for (int j = 0; j < size; ++j) {
                hen1.set(j, hen1.get(j) + 1);
                if (hen1.get(j) >= 4) {
                    hen1.add(0);
                }
            }
        }        System.out.println(hen1.size());        // 方法2: 本月的鸡数为上一个月的鸡数 + 前4个月的鸡数 (可以生小鸡了，不过鸡好像不是生出来的)
        List<Integer> hen2 = new ArrayList<Integer>();
        hen2.add(2); // 第一个月有2只鸡: 母鸡+生的一只小鸡
        hen2.add(3); // 第二个月有3只鸡
        hen2.add(4); // 第三个月有4只鸡
        hen2.add(5); // 第四个月有5只鸡        // 从第五个月开始，第一个月生的小鸡可以生小鸡鸡了
        for (int i = 5; i <= month; ++i) {
            hen2.add(hen2.get(i - 1 - 1) + hen2.get(i - 1 - 4));
        }
        System.out.println(hen2.get(month - 1));
    }
}[/code]

Answer 2

List <Integer> hen1 = new ArrayList <Integer>(); 
        hen1.add(100); 100代表着什么？  而且你没有考虑到， 小鸡长大生小鸡， 小鸡又长大， 再生。。 你没考虑这个问题

Answer 3

首先通过数学将公式推导出来，这里的问题和斐波那契数是类似的。
Fi代表第i月鸡的数量：
F1=2
F2=3
F3=4
Fi=F（i-1）+F（i-3），这里i>3这样，我们就得到了公式，然后通过编写算法来实现就行了，很简单。公式是关键。

Answer 4

这里有一个类似的：求Fibonacci数列的前20个数。该数列有如下特点: 第1, 2两个数为0,1。从第3个数开始，每个数等于前2个数之和。
生成方法为：
F1=1                  (n=1)
F2=1                  (n=2)
Fn=Fn-1+Fn-2           (n>=3)java 代码[code=Jav]
public class Fibonacci {   
    public static long fib(int n) {   
        if (n <= 1) return n;   
        else return fib(n-1) + fib(n-3);   
    }   
  
    public static void main(String[] args) {   
        int N = Integer.parseInt(args[0]);   
        for (int i = 1; i <= N; i++)   
            System.out.println(i + ": " + fib(i));   
    }   
  
}  
[/code]你稍微改一改就可以了。

Answer 5

给你一个有输出小鸡记录的，对比结果应该就很明显了
[code=Jav]import java.util.ArrayList;
import java.util.List;public class HenGrow {
    public static void main(String[] args) {
        final int month = 10;
        // 方法1: 记录所有的鸡
        List<Integer> hen1 = new ArrayList<Integer>(); // 保存每只小鸡的年龄，用于判断能否生小鸡鸡
        hen1.add(3);        for (int i = 1; i <= month; ++i) {
            int size = hen1.size();
            for (int j = 0; j < size; ++j) {
                hen1.set(j, hen1.get(j) + 1); // 增加一岁
            }            // 如果大于等于4岁，则生一只小鸡
            for (int j = 0; j < size; ++j) {
                if (hen1.get(j) >= 4) {
                    hen1.add(0);
                }
            }
            System.out.printf("第%d天:\n\t已有小鸡:%s\n\t刚生小鸡:%s\n",
                i,
                hen1.subList(0, size),
                hen1.subList(size, hen1.size()));
        }        System.out.println(hen1.size());        // 方法2: 本月的鸡数为上一个月的鸡数 + 前4个月的鸡数 (可以生小鸡了，不过鸡好像不是生出来的)
        List<Integer> hen2 = new ArrayList<Integer>();
        hen2.add(2); // 第一个月有2只鸡: 母鸡+生的一只小鸡
        hen2.add(3); // 第二个月有3只鸡
        hen2.add(4); // 第三个月有4只鸡
        hen2.add(5); // 第四个月有5只鸡        // 从第五个月开始，第一个月生的小鸡可以生小鸡鸡了
        for (int i = 5; i <= month; ++i) {
            hen2.add(hen2.get(i - 1 - 1) + hen2.get(i - 1 - 4));
        }
        System.out.println(hen2.get(month - 1));
    }
}[/code]输出：第1天:
    已有小鸡:[4]
    刚生小鸡:[0]
第2天:
    已有小鸡:[5, 1]
    刚生小鸡:[0]
第3天:
    已有小鸡:[6, 2, 1]
    刚生小鸡:[0]
第4天:
    已有小鸡:[7, 3, 2, 1]
    刚生小鸡:[0]
第5天:
    已有小鸡:[8, 4, 3, 2, 1]
    刚生小鸡:[0, 0]
第6天:
    已有小鸡:[9, 5, 4, 3, 2, 1, 1]
    刚生小鸡:[0, 0, 0]
第7天:
    已有小鸡:[10, 6, 5, 4, 3, 2, 2, 1, 1, 1]
    刚生小鸡:[0, 0, 0, 0]
第8天:
    已有小鸡:[11, 7, 6, 5, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1]
    刚生小鸡:[0, 0, 0, 0, 0]
第9天:
    已有小鸡:[12, 8, 7, 6, 5, 4, 4, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1]
    刚生小鸡:[0, 0, 0, 0, 0, 0, 0]
第10天:
    已有小鸡:[13, 9, 8, 7, 6, 5, 5, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1]
    刚生小鸡:[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
36
36 // 10天有36只

Answer 6

hen1.add(100);  
hen1.add(3); 
3 还是100都无所谓，第一只鸡的年龄，就是为了保证它能生

Answer 7

哎，没法跟你说，不知道你的脑子里想的是什么
List <Integer> hen1 = new ArrayList <Integer>(); // 保存每只小鸡的年龄，用于判断能否生小鸡鸡 
每个元素保存的是此鸡的年龄，不是鸡的数量，自己想去吧

Answer 8

我用了下面的方法 [code=Jav]public static void main(String[] args) {
for(int i = 1; i <= 20; i++){
int count = bigHen(i);
System.out.println(i + " 天:  " + count);
}
}

public static int bigHen(int endMonth){  
int count = 1;  // 只数
for(int i = 1; i <= endMonth; i++){
if(i >= 4){
count = count + bigHen(endMonth - i);  //计算每一只小鸡能生多少只
}
count++;
}
return count;
}[/code]
我算了下，感觉是对的。 但是考官就是说答案是 2745 。 我非常郁闷

Answer 9

“我算了下，感觉是对的。 但是考官就是说答案是 2745 。 我非常郁闷”
考官说的2745，是他把第四个月才开始生小鸡弄成了第三个月就开始生，
                if (hen1.get(j) >= 4) { // 把这里的4改成3你就知道问题出在哪了
                    hen1.add(0); 
                } 

Answer 10

final int month = 10; // 定义月数
哎，不知道要怎么说，只用10个月，是为了输出的内容少些，好比较，改成20不就好了？

Answer 11

菜鸟练手，用面向对象思想，不知对不对。[code=Jav]public class Cow {
private int age;
private static int counts = 0;

public Cow(int age, int years) {
this.age = age;
grow(years);
counts++;
} public void grow(int years) {
for(int i=0; i<years; i++) {
if(age++ >= 4) {
new Cow(0, years-i);
}
}
}

public static void main(String[] args) {
new Cow(4, 6);
System.out.println(Cow.counts);
}
}[/code]

Answer 12

上面代码搞错了，main方法里的6应该改为20，结果为907，测试了前几个月的，好像没问题。

Answer 13

答案就是 2745.。想起我以前做过的一道非常类似的，只是用C语言描述的：题目：
有一头母牛，从出生起第四个年头开始每年生一头母牛，第n年几头？[code=Jav]
#include<stdio.h>
void main()
{
/*y1表示1岁，y2...,y3..没有y4，是因为到了第四年，就可以生了，所以身份是母亲*/
int sum,mother=1,y1,y2,y3,n;
printf("Enter the Year(n)=: ");
scanf("%d",&n);
if(0<n&&n<4) sum=n;
if(n>=4)
{
for(y1=1,y2=1,y3=1;n>=4;n--)//第6年后，刚好y1,y2,y3都为1。此后每过一年...
{
mother=mother+y3; //三岁的变成母亲。
y3=y2; //2岁的成了三岁
y2=y1; //1岁的--->二岁
y1=mother; //所有的母亲每一年都生下小牛（y1）
sum=mother+y1+y2+y3; 
}
}
printf("Sum = %d\n",sum);
}[/code]09年前写的 母牛四年生一只...
几本都一样的。

Answer 14

[code=Jav]
public class Test {
public static void main(String[] args) {
/*y1表示1岁，y2...,y3..没有y4，是因为到了第四年，就可以生了，所以身份是母亲*/
int sum=0,mother=1,y1,y2,y3,n;
n=20;
if(0<n&&n<4) sum=n;
if(n>=4)
{
for(y1=1,y2=1,y3=1;n>=4;n--)//第6年后，刚好y1,y2,y3都为1。此后每过一年...
{
mother=mother+y3; //三岁的变成母亲。
y3=y2; //2岁的成了三岁
y2=y1; //1岁的--->二岁
y1=mother; //所有的母亲每一年都生下小牛（y1）
sum=mother+y1+y2+y3; 
}
}
System.out.println(sum);
}
}[/code]改成了JAVA.. 测试过了。 
不过编码规范不够好,那时候刚入门不久·· 可以看着改改。

Answer 15

[code=Jav]public class Test {
public static void main(String[] args) {
/*y1表示1岁，y2...,y3..没有y4，是因为到了第四年，就可以生了，所以身份是母亲*/
int sum=0,mother=1,y1,y2,y3,n;
n=20;
if(0<n&&n<4) sum=n;
if(n>=4)
{
for(y1=1,y2=1,y3=1;n>=4;n--)//第6年后，刚好y1,y2,y3都为1。此后每过一年...
{
mother=mother+y3; //三岁的变成母亲。
y3=y2; //2岁的成了三岁
y2=y1; //1岁的--->二岁
y1=mother; //所有的母亲每一年都生下小牛（y1）
sum=mother+y1+y2+y3; 
}
}
System.out.println(sum);
}
}
[/code]

Answer 16

public class App 
{

    public static void main( String[] args )
    {
     System.out.println(getbigHen(1,20)+1);//+1是因为包括母鸡自己！
    }
    public static int getbigHen(int xiaoji ,int month)
    {
     if(month!=20)
     {
     month = month-2;//第一只母鸡不需要4天，为什么这里是2天，因为调用的时候-1了
     }
     int total = 0;
     for(int i=month;i>0;i--)
     {
     total ++;
     total += getbigHen(1,i-1);
     }
     return total;
    }
}

Answer 17

我不会用数字计算，但是我会用面向对象的方法计算，也就是用现实生活中的逻辑让程序去模仿，这里只要给刚出去的每只鸡设定生日，然后每个月来催生就好了。最后来个人口普查。[code=Jav]import java.util.ArrayList;
import java.util.List;/**
 * 
 * 有一只母鸡，每月生一只小母鸡，小母鸡长到每第四个月后每月又生一只小小母鸡，问20个月后母鸡的总数为多少？ 写一个程程序解决这个问题
 */
public class 小鸡家族 {    public static class 小鸡 {
int 生日; 小鸡(int 鸡历月份) {
    this.生日 = 鸡历月份;
} public boolean 有娃么(int 世界月份) {
    return 世界月份 - this.生日 >= 3;
}
    }    private static List<小鸡> 族谱 = new ArrayList<小鸡>();    public static void main(String[] args) {
小鸡 小鸡世界的女娲 = new 小鸡(-3); // 浑沌初开 族谱.add(小鸡世界的女娲); for (int m = 1; m <= 20; m++) {     int 鸡口 = 族谱.size(); // 先记下鸡口，这月出生的小鸡在这个月的普查后再入家谱。     for (int index = 0; index < 鸡口; index++) {
小鸡 hen = (小鸡) 族谱.get(index); if (hen.有娃么(m)) {
    族谱.add(new 小鸡(m));
}
    }     System.out.println("第 " + m + " 月，鸡口 ：" + 族谱.size() + ", 鸡口自然增长：" + (族谱.size() - 鸡口));
} System.out.println("鸡口 :" + 族谱.size());
    }
}[/code]

Answer 18

为什么这个插入源代码时选择 java 最后变成了 lang=Jav
[code=Jav]
...
[/code]

Answer 19

我看到了，现在再试试[code=Jav]123123[/code]

Answer 20

[code=Jav]
int cal(int month, int num4, int num3, int num2, int num1, int num0) {
return cal(month-1, num4+num3, num2, num1, num4);
}
[/code]其中，month代表月数，num4代表4月后的小鸡数(也就是能生小鸡了)，num3是3月大的小鸡数，num2是2月大的小鸡数，num1是1月大的小鸡数，num0是刚出生的小鸡数。哈哈，我写的是不是最简单的啊！

Answer 21

void main(String[] args) {
    System.out.println(cal(20, 1, 0, 0, 0, 0));
}
就能得到20月后的母鸡数！

Answer 22

int cal(int month, int num4, int num3, int num2, int num1, int num0)
{
if (month == 0) {
return num4+num3+num2+num1+num0;
}
return cal(month-1, num4+num3, num2, num1, num0, num4)
}
代码贴错了， 不好意思， 哈哈！

Answer 23

递归算法处理public class feibonaqie {
public static int sum(int i){
if (i == 1 || i == 0){
return 1;
}else if (i == 2) {
return 2;
}else {
return sum(i-1) + sum(i-3);
}
}
public static void main(String[] args) {
int mon = feibonaqie.sum(10);

System.out.println(mon);
}}