6
回答
古典算法【兔子生兔子】的疑问
终于搞明白,存储TCO原来是这样算的>>>   

最近面试了两家,感觉基础落下了。所以恶补基础。

古典算法兔子生兔子的问题,在下极为不解。

题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第3个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少?

所以在标准答案不懂,直接用list测试了下,实在不能理解到这个规律问题。求算法达人详解,谢谢!

我的测试代码是:


package java.algorithm;

import java.util.LinkedList;
import java.util.List;

public class BornRabitCountTest {
	static class RabitPair {
		private int bornMonth = 1;

		public RabitPair born() {
			return bornMonth > 2 ? new RabitPair() : null;
		}

		public void incrBornMonth() {
			this.bornMonth++;
		}
	}

	public static void main(String[] args) {
		List<RabitPair> rabitPairs = new LinkedList<RabitPair>();
		rabitPairs.add(new RabitPair());
		int month = 10;
		for (int m = 1; m <= month; m++) {
			List<RabitPair> bornRabitPairs = new LinkedList<RabitPair>();
			for (RabitPair rabitPair : rabitPairs) {
				RabitPair newRabitPair = rabitPair.born();
				rabitPair.incrBornMonth();
				if (newRabitPair != null)
					bornRabitPairs.add(newRabitPair);
			}
			rabitPairs.addAll(bornRabitPairs);
			System.out.println(rabitPairs.size());
		}
	}

	// 【程序1】
	// 题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第四个月后每个月又生一对兔子,
	// 假如兔子都不死,问每个月的兔子总数为多少?
	public static void mainAns(String[] args) {
		// 程序分析: 兔子的规律为数列1,1,2,3,5,8,13,21....
		// 1 1 2 3 5
		int month = 10;
		for (int m = 1; m <= month; m++) {
			System.out.println(f(m));
		}
	}

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

}
标准答案的结果是 :


1,1,2,3,5,8,13,21。。。

使用main方法跑出来的是:

1 1 2 3 4 6 9 13 19 28


谢谢各位大神!


举报
共有6个答案 最后回答: 1年前

因为你的第一只【兔子】生下第一只【子兔】是在第4个月。

问题出在你的【生兔子】、【进月】、【统计总数】的时序上。

错误的拆解步骤如下:

当m=3开始时,其实第一只兔子其实经过m=1,m=2两次,此时它的bornMonth=3。

接着他生下了【子兔】,这是【子兔】bornMonth=1,

然后【母兔】bornMonth = 4。

最后当m=3的循环结束。

本来母兔和子兔的月份应该是 3、1的。

但是循环过后是 4、1。

--- 共有 1 条评论 ---
奔驰的蜗牛谢谢! 找到自己的错误了,非常感谢! 1年前 回复

因为新出生的兔子没有加一个月。需改成:

if (newRabitPair != null) {
  newRabitPair.incrBornMonth();
  bornRabitPairs.add(newRabitPair);
}

先生小兔子,然后兔子加一个月,这种写法不好,逻辑上有点乱(这个月出生的兔子立即变成两个月大了)。好的写法是兔子先加一个月,然后再生小兔子,这样新出生的兔子在这个月就只有一个月大。

int month = 10;
System.out.println(rabitPairs.size());
for (int m = 2; m <= month; m++) {
  List<RabitPair> bornRabitPairs = new LinkedList<RabitPair>();
  for (RabitPair rabitPair : rabitPairs) {
    rabitPair.incrBornMonth();
    RabitPair newRabitPair = rabitPair.born();
    if (newRabitPair != null) {
      bornRabitPairs.add(newRabitPair);
    }
  }
  rabitPairs.addAll(bornRabitPairs);
  System.out.println(rabitPairs.size());
}



--- 共有 1 条评论 ---
奔驰的蜗牛谢谢分析。 -- 后面的确实有点逻辑混乱… -- 不过出生时,是默认值一月 private int bornMonth = 1; 所以bornRabitPair.incr这个不应该加的哈 1年前 回复

也可以说,当你

rabitPairs.add(newRabitPair());

也就是添加第一只兔子进【总数组】时,第一个月已经过去了。

循环应该从第二个月走起。

引用来自“士止刀口”的评论

因为你的第一只【兔子】生下第一只【子兔】是在第4个月。

问题出在你的【生兔子】、【进月】、【统计总数】的时序上。

错误的拆解步骤如下:

当m=3开始时,其实第一只兔子其实经过m=1,m=2两次,此时它的bornMonth=3。

接着他生下了【子兔】,这是【子兔】bornMonth=1,

然后【母兔】bornMonth = 4。

最后当m=3的循环结束。

本来母兔和子兔的月份应该是 3、1的。

但是循环过后是 4、1。

for (RabitPair rabitPair : rabitPairs) {
				rabitPair.incrBornMonth();
				RabitPair newRabitPair = rabitPair.born();
				if (newRabitPair != null)
					bornRabitPairs.add(newRabitPair);
			}



引用来自“士止刀口”的评论

也可以说,当你

rabitPairs.add(newRabitPair());

也就是添加第一只兔子进【总数组】时,第一个月已经过去了。

循环应该从第二个月走起。

每月应该先加月份,然后看兔子是否足月可生bb谢谢了
顶部