用python实现斐波那契(fibonacci)函数

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的计算机编程入门语言。

Posted in 未分类