这是我参加“14天阅读挑战赛”第一周第二篇
点击查看“14天阅读挑战赛”详情，《趣学算法第二版》1.4 神奇的兔子数列。
假设第1个月有1对初生的兔子，第2个月进入成熟期，第3个月开始生育兔子，而1对成熟的兔子每月会生1对兔子，兔子永不死去……那么，由1对初生的兔子开始，12个月后会有多少对兔子呢？
兔子数列即斐波那契数列，它的发明者是意大利数学家莱奥纳尔多·斐波那契（Leonardo Fibonacci，1170—1250）。1202年，莱奥纳尔多撰写了《算盘全书》（Liber Abaci），该书是一部较全面的初等数学著作。书中系统地介绍了印度—阿拉伯数码及其演算法则，以及中国的“盈不足术”；此外还引入了负数，并研究了一些简单的一次同余式组。
根据分析第一、二个月没有兔子新增数量都是1；第三个月成熟期的兔子会生一只兔子，总数2；第四月成熟期的兔子会生兔子，上月生的兔子成熟，总数3；第五月两只成熟的兔子生小兔子，上月生的成熟，总数5；第五月三只成熟的兔子生小兔子，上月生的成熟，总数8；……兔子这样一直繁衍下去……
由兔子繁殖规律可见，每月新生兔子数都是上上个月的总数。
神奇的兔子数列公式图
根据从兔子繁殖分析出的事件特性，可以用递归算法编写代码实现任意项的数列项推演。
递归代码
def resursive_rabbit(n):
''' 递归兔子数列 '''
if n == 1 or n == 2:
return 1
else:
return resursive_rabbit(n-1) + resursive_rabbit(n-2)
运行效果截图
这？效率有点儿低啊😱能不能优化下哩？这主要是在递推和回归在计算和存储上费时费力。那就用列表和循环来试试。😄
代码
def for_rabbit(n):
''' for循环优化兔子数列 '''
fib = [1]*n
for i in range(2, n):
fib[i] = fib[i-1] + fib[i-2]
return fib[-1]
运行效果截图
这！🧐这么快？👀
只是用一个列表来存储前面的项而已哦。等等，来算个10000项。😎
耗时居然远远小于0.1秒。先不定义整个数列长度的列表，就第一、二项，后面的计算出来append到列表中，会不会更快？
代码
def for_rabbit_append(n):
''' for+append循环优化兔子数列 '''
fib = [1, 1]
for i in range(2, n):
fib.append(fib[i-1] + fib[i-2])
return fib[-1]
效果截屏图片
和直接先定义n个元素长度的列表，几无差异(还是计算第10000项)。还可以优化不？只计算第几项，用列表存储整个数列，是不是有点儿浪费？用两个变量暂存上一项、上上项何如？
代码
def for_rabbit_ab(n):
''' for + a,b循环优化兔子数列 '''
a, b = 1, 1
for i in range(2, n):
fib_new = b + a
b, a = fib_new, b
return b
代码运行效果截屏图片
还是讲得第10000项，时间又少了一半！🤗
这神奇的兔子数列，还没通项公式哩，用她来试试:
代码
def formula_rabbit(n):
''' 通项公式兔子数列 '''
from math import sqrt
a, b = ((1+sqrt(5))/2)**n, ((1-sqrt(5))/2)**n
return 1/sqrt(5) * ( a - b )
运行效果截图
计算第10000项数字表示溢出报错截屏图片
由试炼可见，通项公式不但有浮点数计算误差，还可以算太多的项。速度也比不上列表+循环。所以最好不好用通项公式来整。😜
试试用三个优化的循环都计算一遍第10000项：
耗时还是远远小于0.1秒。😎😎😎
一般来讲，同一需求都可以设计几种算法。当重复太多，递归费时费力，就要找出一个更优算法。我从优化算法的过程中，真切地体会到算法之美！