fibonacci斐波那契数列，很简单，就是一个递归嘛，学任何编程语言可能都会做一下这个。
最近在玩python，在粗略的看了一下learning python和core python之后，偶然发现网上有个帖子python程序员的进化写的很有意思。于是打算仿照一篇，那篇帖子用了十余种方法完成一个阶乘函数，我在这里会用九种不同的风格写出一个fibonacci函数。
要求很简单，输入n，输出第n个fibonacci数，n为正整数
下面是这九种不同的风格：
1）第一次写程序的python程序员：
def fib(n):
return nth fibonacci number
说明：
第一次写程序的人往往遵循人类语言的语法而不是编程语言的语法，就拿我一个编程很猛的哥们来说，他写的第一个判断闰年的程序，里面直接是这么写的：如果year是闰年，输出year是闰年，否则year不是闰年。
2）刚学python不久的的c程序员：
def fib(n):#{
if n[y,x+y]。
在这里，我声明一个二元向量[x,y]t，它通过一个变换得到[y,x+y]t，可以很容易得到变换矩阵是[[1,0],[1,1]]，也就是说：[[1,0],[1,1]]*[x,y]t=[y,x+y]t
令二元矩阵a=[[1,0],[1,1]]，二元向量x=[0,1]t，容易知道ax的结果就是下一个fibonacci数值，即：
ax=[fib(1),fib(2)]t
亦有：
ax=[fib(2),fib(3)]t
………………
以此类推，可以得到：
aⁿx=[fib(n),fib(n-1)]t
也就是说可以通过对二元向量[0,1]t进行n次a变换，从而得到[fib(n),fib(n+1)]t，从而得到fib(n)。
在这里我定义了一个二元矩阵的相乘函数m1，以及一个在二元向量上的变换m2，然后利用reduce操作完成一个连乘操作得到aⁿx，最后得到fib(n)。
9）准备参加acm比赛的python程序员：
def fib(n):
lhm=[[0,1],[1,1]]
rhm=[[0],[1]]
em=[[1,0],[0,1]]
#multiply two matrixes
def matrix_mul(lhm,rhm):
#initialize an empty matrix filled with zero
result=[[0 for i in range(len(rhm[0]))] for j in range(len(rhm))]
#multiply loop
for i in range(len(lhm)):
for j in range(len(rhm[0])):
for k in range(len(rhm)):
result[i][j]+=lhm[i][k]*rhm[k][j]
return result
def matrix_square(mat):
return matrix_mul(mat,mat)
#quick transform
def fib_iter(mat,n):
if not n:
return em
elif(n%2):
return matrix_mul(mat,fib_iter(mat,n-1))
else:
return matrix_square(fib_iter(mat,n/2))
return matrix_mul(fib_iter(lhm,n),rhm)[0][0]
说明：
看过上一个fib函数就比较容易理解这一个版本了，这个版本同样采用了二元变换的方式求fib(n)。不过区别在于这个版本的复杂度是lgn，而上一个版本则是线性的。
这个版本的不同之处在于，它定义了一个矩阵的快速求幂操作fib_iter，原理很简单，可以类比自然数的快速求幂方法，所以这里就不多说了。
ps：虽然说是acm版本，不过说实话我从来没参加过那玩意，毕竟自己算法太水了，那玩意又太高端……只能在这里yy一下鸟~
python中，最基本的那种递归（如下fib1)效率太低了，只要n数字大了运算时间就会很长；而通过将计算的指保存到一个dict中，后面计算时直接拿来使用，这种方式成为备忘(memo)，如下面的fib2函数所示，则会发现效率大大提高。
在n=10以内时，fib1和fab2运行时间都很短看不出差异，但当n=40时，就太明显了，fib1运行花了35秒，fab2运行只花费了0.00001秒。
n=40时，输出如下：
jay@jay-linux:~/workspace/python.git/py2014$ python fibonacci.py
2014-10-16 16:28:35.176396
fib1(40)=102334155
2014-10-16 16:29:10.479953
fib2(40)=102334155
2014-10-16 16:29:10.480035
这两个计算fibonacci数列的函数，如下：https://github.com/smilejay/python/blob/master/py2014/fibonacci.py
import datetime
def fib1(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib1(n – 1) + fib1(n – 2)
known = {0: 0, 1: 1}
def fib2(n):
if n in known:
return known[n]
res = fib2(n – 1) + fib2(n – 2)
known[n] = res
return res
if __name__ == ‘__main__’:
n = 40
print(datetime.datetime.now())
print(‘fib1(%d)=%d’ % (n, fib1(n)))
print(datetime.datetime.now())
print(‘fib2(%d)=%d’ % (n, fib2(n)))
print(datetime.datetime.now())
后记：
由于刚学习python没多久，所以对其各种特性的掌握还不够熟练。与其说是我在用python写程序，倒不如说我是在用c，c++，c#或是scheme来写程序。至于传说中的pythonic way，我现在还没有什么体会，毕竟还没用python写过什么真正的程序。
learning python和core python都是不错的python入门书籍，前者更适合没有编程基础的人阅读。
python是最好的初学编程入门语言，没有之一。所以它可以取代scheme成为mit的计算机编程入门语言。