不同的角度，不同的玩法——用Python实现Fibonacci函数

yxixi

关于Fibonacci函数的100种写法  最近在玩Python，在粗略的看了一下LearningPython和CorePython之后，发现网上有个帖子写的很有意思。于是打算仿照一篇，那篇帖子用了十余种方法完成一个阶乘函数，我在这里会用九种不同的风格写出一个Fibonacci函数。  要求很简单，输入n，输出第n个Fibonacci数，n为正整数  下面是这九种不同的风格：  第一次写程序的Python程序员：  01 def fib(n): 02 return nth fibonacci number 说明： 第一次写程序的人往往遵循人类语言的语法而不是编程语言的语法，就拿我一个编程很猛的哥们来说，他写的第一个判断闰年的程序，里面直接是这么写的：如果year是闰年，输出闰年，否这不是闰年。  刚学Python不久的的C程序员：  01 def fib(n):#{ 02 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)。  准备参加ACM比赛的Python程序员：  01 def fib(n): 02 lhm=[[0,1],[1,1]] 03 rhm=[[0],[1]] 04 em=[[1,0],[0,1]] 05 #multiply two matrixes 06 def matrix_mul(lhm,rhm): 07 #initialize an empty matrix filled with zero 08 result=[[0 for i in range(len(rhm[0]))] for j in range(len(rhm))] 09 #multiply loop 10 for i in range(len(lhm)): 11 for j in range(len(rhm[0])): 12 for k in range(len(rhm)): 13 result[j]+=lhm[k]*rhm[k][j] 14 return result 15 16 def matrix_square(mat): 17 return matrix_mul(mat,mat) 18 #quick transform 19 def fib_iter(mat,n): 20 if not n: 21 return em 22 elif(n%2): 23 return matrix_mul(mat,fib_iter(mat,n-1)) 24 else: 25 return matrix_square(fib_iter(mat,n/2)) 26 return matrix_mul(fib_iter(lhm,n),rhm)[0][0] 说明： 看过上一个fib函数就比较容易理解这一个版本了，这个版本同样采用了二元变换的方式求fib(n)。不过区别在于这个版本的复杂度是lgn，而上一个版本则是线性的。 这个版本的不同之处在于，它定义了一个矩阵的快速求幂操作fib_iter，原理很简单，可以类比自然数的快速求幂方法，所以这里就不多说了。 PS：虽然说是ACM版本，不过其实我从来没参加过那玩意，毕竟自己算法太水了，那玩意又太高端……只能在这里YY一下鸟~  后记： 由于刚学习Python没多久，所以对其各种特性的掌握还不够熟练。与其说是我在用Python写程序，倒不如说我是在用C，C++，C#或是Scheme来写程序。至于传说中的Pythonic way，我现在还没有什么体会，毕竟还没用Python写过什么真正的程序。 非常喜欢Python的理念，在这里贴出来：  Beautiful is better than ugly. Explicit is better than implicit. Simple is better than complex. Complex is better than complicated. Flat is better than nested. Sparse is better than dense. Readability counts. Special cases aren't special enough to break the rules. Although practicality beats purity. Errors should never pass silently. Unless explicitly silenced. In the face of ambiguity, refuse the temptation to guess. There should be one-- and preferably only one --obvious way to do it. Although that way may not be obvious at first unless you're Dutch. Now is better than never. Although never is often better than *right* now. If the implementation is hard to explain, it's a bad idea. If the implementation is easy to explain, it may be a good idea. Namespaces are one honking great idea -- let's do more of those!　　不同的角度，不同的玩法——在Python上实现Fibonacci函数
　　
　　最近在玩Python，在粗略的看了一下Learning Python和Core Python之后，偶然发现网上有个帖子Python程序员的进化写的很有意思。于是打算仿照一篇，那篇帖子用了十余种方法完成一个阶乘函数，我在这里会用九种不同的风格写出一个Fibonacci函数。
　　
　　要求很简单，输入n，输出第n个Fibonacci数，n为正整数
　　
　　下面是这九种不同的风格：
　　
　　
　　
　　1）第一次写程序的Python程序员：
　　
　　01 def  fib(n):
　　02     return nth fibonacci number
　　
　　说明：
　　第一次写程序的人往往遵循人类语言的语法而不是编程语言的语法，就拿我一个编程很猛的哥们来说，他写的第一个判断闰年的程序，里面直接是这么写的：如果year是闰年，输出year是闰年，否则year不是闰年。
　　
　　
　　
　　2）刚学Python不久的的C程序员：
　　
　　01 def  fib(n):#{
　　02     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程序员：
　　
　　01 def  fib(n):
　　02     lhm=[[0,1],[1,1]]
　　03     rhm=[[0],[1]]
　　04     em=[[1,0],[0,1]]
　　05     #multiply two matrixes
　　06     def matrix_mul(lhm,rhm):
　　07         #initialize  an empty matrix filled with zero
　　08         result=[[0 for i in range(len(rhm[0]))] for j in range(len(rhm))]
　　09         #multiply  loop
　　10         for  i in range(len(lhm)):
　　11             for j in range(len(rhm[0])):
　　12                 for k in range(len(rhm)):
　　13                     result[j]+=lhm[k]*rhm[k][j]
　　14         return result
　　15     
　　16     def matrix_square(mat):
　　17         return matrix_mul(mat,mat)
　　18     #quick transform
　　19     def fib_iter(mat,n):
　　20         if  not n:
　　21             return em
　　22         elif(n%2):
　　23             return matrix_mul(mat,fib_iter(mat,n-1))
　　24         else:
　　25             return matrix_square(fib_iter(mat,n/2))
　　26     return matrix_mul(fib_iter(lhm,n),rhm)[0][0]
　　
　　说明：
　　看过上一个fib函数就比较容易理解这一个版本了，这个版本同样采用了二元变换的方式求fib(n)。不过区别在于这个版本的复杂度是lgn，而上一个版本则是线性的。
　　这个版本的不同之处在于，它定义了一个矩阵的快速求幂操作fib_iter，原理很简单，可以类比自然数的快速求幂方法，所以这里就不多说了。
　　PS：虽然说是ACM版本，不过说实话我从来没参加过那玩意，毕竟自己算法太水了，那玩意又太高端……只能在这里YY一下鸟~
　　
　　后记：
　　由于刚学习Python没多久，所以对其各种特性的掌握还不够熟练。与其说是我在用Python写程序，倒不如说我是在用C，C++，C#或是Scheme来写程序。至于传说中的Pythonic  way，我现在还没有什么体会，毕竟还没用Python写过什么真正的程序。
　　Learning Python和Core Python都是不错的Python入门书籍，前者更适合没有编程基础的人阅读。
　　Python是最好的初学编程入门语言，没有之一。所以它可以取代Scheme成为MIT的计算机编程入门语言。
　　
　　
　　
　　非常喜欢Python的理念（Zen of  python），在这里贴出来（import  this）：
　　
　　Beautiful is better than ugly.
　　Explicit is better than implicit.
　　Simple is better than complex.
　　Complex is better than complicated.
　　Flat is better than nested.
　　Sparse is better than dense.
　　Readability counts.
　　Special cases aren't special enough to break the rules.
　　Although practicality beats purity.
　　Errors should never pass silently.
　　Unless explicitly silenced.
　　In the face of ambiguity, refuse the temptation to  guess.
　　There should be one-- and preferably only one --obvious way to do  it.
　　Although that way may not be obvious at first unless you're  Dutch.
　　Now is better than never.
　　Although never is often better than *right* now.
　　If the implementation is hard to explain, it's a bad  idea.
　　If the implementation is easy to explain, it may be a good  idea.
　　Namespaces are one honking great idea -- let's do more of  those!
　　
　　
　　

figure9原创，2010-8-30  19:25:21，转帖请注明，错误请指正，Thanks~