本文共 4768 字,大约阅读时间需要 15 分钟。
Fibonacci斐波那契数列,很简单,就是一个递归嘛,学任何编程语言可能都会做一下这个。
最近在玩Python,在粗略的看了一下Learning Python和Core Python之后,偶然发现网上有个帖子Python程序员的进化写的很有意思。于是打算仿照一篇,那篇帖子用了十余种方法完成一个阶乘函数,我在这里会用九种不同的风格写出一个Fibonacci函数。
要求很简单,输入n,输出第n个Fibonacci数,n为正整数
下面是这九种不同的风格:
1)第一次写程序的Python程序员:
?12def fib(n): returnnth fibonacci number
说明:
第一次写程序的人往往遵循人类语言的语法而不是编程语言的语法,就拿我一个编程很猛的哥们来说,他写的第一个判断闰年的程序,里面直接是这么写的:如果year是闰年,输出year是闰年,否则year不是闰年。2)刚学Python不久的的C程序员:
?def fib(n):#{ ifn<=2: return1; else: returnfib(n-1)+fib(n-2);#}
说明:
在刚接触Python时,用缩进而非大括号的方式来划分程序块这种方式我是很不适应的,而且每个语句后面没有结束符,所以每次写完一个Python函数之后干的第一件事一般就是一边注释大括号,一边添加漏掉的冒号。3)懒散的Python程序员:
def fib(n): return1 and n<=2 or fib(n-1)+fib(n-2)
说明:
看了Learning Python之后,才知道Python没有三元操作符?,不过鉴于Python里bool值比较特殊(有点像C,非零即真,非空即真),再加上Python的逻辑语句也是支持短路求值(Short-Circuit Evaluation)的,这就可以写出一个仿?语句出来。4)更懒的Python程序员:
?fib=lambdan:1 if n<=2else fib(n-1)+fib(n-2)
说明:
lambda关键字我曾在C#和Scheme里面用过,Python里面的lambda比C#里简便,并很像Scheme里的用法,所以很快就适应了。在用Python Shell声明一些小函数时经常用这种写法。5)刚学完数据结构的Python程序员:
def fib(n): x,y=0,1 while(n): x,y,n=y,x+y,n-1 returnx
说明:
前面的Fibonacci函数都是树形递归的实现,哪怕是学一点算法就应该知道这种递归的低效了。在这里从树形递归改为对应的迭代可以把效率提升不少。 Python的元组赋值特性是我很喜欢的一个东东,这玩意可以把代码简化不少。举个例子,以前的tmp=a;a=b;b=tmp;可以直接用一句a,b=b,a实现,既简洁又明了。6)正在修SICP课程的Python程序员:
def fib(n): deffib_iter(n,x,y): ifn==0: return x else: return fib_iter(n-1,y,x+y) returnfib_iter(n,0,1)
|
说明:
在这里我使用了Scheme语言中很常见的尾递归(Tail-recursion)写法。Scheme里面没有迭代,但可以用不变量和尾递归来模拟迭代,从而实现相同的效果。不过我还不清楚Python有没有对尾递归做相应的优化,回头查一查。 PS:看过SICP的同学,一眼就能看出,这个程序其实就是SICP第一章里的一个例子。7)好耍小聪明的Python程序员:
fib=lambdan,x=0,y=1:xif not n else f(n-1,y,x+y)
说明:
基本的逻辑和上面的例子一样,都是尾递归写法。主要的区别就是利用了Python提供的默认参数和三元操作符,从而把代码简化至一行。至于默认参数,学过C++的同学都知道这玩意,至于C#4.0也引入了这东东。8)刚修完线性代数的Python程序员:
def fib(n): defm1(a,b): m=[[],[]] m[0].append(a[0][0]*b[0][0]+a[0][1]*b[1][0]) m[0].append(a[0][0]*b[0][1]+a[0][1]*b[1][1]) m[1].append(a[1][0]*b[0][0]+a[1][1]*b[1][0]) m[1].append(a[1][0]*b[1][0]+a[1][1]*b[1][1]) returnm defm2(a,b): m=[] m.append(a[0][0]*b[0][0]+a[0][1]*b[1][0]) m.append(a[1][0]*b[0][0]+a[1][1]*b[1][0]) returnm returnm2(reduce(m1,[[[0,1],[1,1]]for i inrange(n)]),[[0],[1]])[0]
|
说明:
这段代码就不像之前的代码那样清晰了,所以先介绍下原理(需要一点线性代数知识): 首先看一下之前的迭代版本的Fibonacci函数,很容易可以发现存在一个变换:y->x, x+y->y。换一个角度,就是[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 ……………… 以此类推,可以得到: 1 | 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程序员:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | def fib(n): lhm=[[0,1],[1,1]] rhm=[[0],[1]] em=[[1,0],[0,1]] #multiply two matrixes defmatrix_mul(lhm,rhm): #initialize an empty matrix filled with zero result=[[0for i inrange(len(rhm[0]))]for j inrange(len(rhm))] #multiply loop fori in range(len(lhm)): forj in range(len(rhm[0])): fork in range(len(rhm)): result[i][j]+=lhm[i][k]*rhm[k][j] returnresult defmatrix_square(mat): returnmatrix_mul(mat,mat) #quick transform deffib_iter(mat,n): ifnot n: returnem elif(n%2): returnmatrix_mul(mat,fib_iter(mat,n-1)) else: returnmatrix_square(fib_iter(mat,n/2)) returnmatrix_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时,输出如下: 1 2 3 4 5 6 | 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数列的函数,如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | import datetime def fib1(n): ifn ==0: return0 elifn ==1: return1 else: returnfib1(n - 1) + fib1(n - 2) known ={0:0, 1:1} def fib2(n): ifn in known: returnknown[n] res= fib2(n -1) +fib2(n - 2) known[n]= res returnres 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的计算机编程入门语言。转载地址:http://yithj.baihongyu.com/