最近在玩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<=2 : return 1; else: return fib(n-1)+fib(n-2);#}
说明：
在刚接触python时，用缩进而非大括号的方式来划分程序块这种方式我是很不适应的，而且每个语句后面没有结束符，所以每次写完一个python函数之后干的第一件事一般就是一边注释大括号，一边添加漏掉的冒号。
3）懒散的python程序员：
def fib(n): return 1 and ny。换一个角度，就是[x,y]->[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.176396fib1(40)=1023341552014-10-16 16:29:10.479953fib2(40)=1023341552014-10-16 16:29:10.480035
这两个计算fibonacci数列的函数，如下：https://github.com/smilejay/python/blob/master/py2014/fibonacci.py
import datetimedef 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 resif __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的计算机编程入门语言。