分治与递归-Fibonacci数列兔子问题

裴波那契(Fibonacci leonardo,约1170-1250)是意大利著名数学家。在他的著作《算盘书》中许多有趣的问题,最富成功的问题是著名的“兔子繁殖问题”: 如果每对兔子每月繁殖一对子兔,而子兔在出生后第二个月就有生殖能力,试问一对兔子一年能繁殖多少对兔子?

这个问题会构成一个斐波那契数列

月份 已有兔子数 新增兔子数 兔子总数 兔子对数 新增兔子对数
1 2 0 2 1 0
2 2 2 4 2 1
3 4 2 6 3 1
4 6 4 10 5 2
5 10 6 16 8 3
6 16 10 26 13 5
7 26 16 42 21 8

因此兔子对数为:1,2,3,5,8,13,21,...在其前加1是斐波那契数列

每次新增兔子数为:0,1,1,2,3,5,8,...,在其前删除0也是斐波那契数列

兔子总对数的斐波那契数列:1,1,2,3,5,8,13,21,...

分治与递归-Fibonacci数列兔子问题

 

 

 其中n为月份。

 

上一篇:Problem 2


下一篇:【Java】剑指Offer_编程题01 斐波那契数列