How to implement the Fibonacci function using Python

This article mainly introduces how to use Python to implement Fibonacci function related information. Friends who need it can refer to

Fibonacci Fibonacci sequence. It is very simple. It is just a recursion. Learn Any programming language can probably do this.

I have been playing Python recently. After a cursory look at Learning Python and Core Python, I accidentally found a post on the Internet about the evolution of Python programmers. It was very interesting. So I plan to imitate a post that uses more than ten methods to complete a factorial function. Here I will write a Fibonacci function in nine different styles.

The requirements are very simple, input n, output the nth Fibonacci number, n is a positive integer

The following are the nine different styles:

1) Python programmers who write programs for the first time:

def fib(n):
  return nth fibonacci number

Explanation:
People who write programs for the first time tend to follow human The syntax of a language rather than the syntax of a programming language. Take a buddy of mine who is very good at programming as an example. The first program he wrote to determine a leap year directly stated this: If year is a leap year, the output year is a leap year. Otherwise year is not a leap year.

2) C programmers who have just learned Python:

def fib(n):#{
 if n<=2 :
  return 1;
 else:
  return fib(n-1)+fib(n-2);
#}

Explanation:
When I first came into contact with Python , I am very uncomfortable with using indentation instead of braces to divide program blocks, and there is no terminator after each statement, so the first thing I do after writing a Python function is usually to Comment out the braces and add missing colons.

3) Lazy Python programmer:

def fib(n):
  return 1 and n<=2 or fib(n-1)+fib(n-2)

Explanation:
I didn’t know Python until I watched Learning Python No ternary operator? , but given that the bool value in Python is quite special (a bit like C, non-zero means true, non-empty means true), and Python's logical statements also support short-circuit evaluation (Short-Circuit Evaluation), this can be written An imitation? statement comes out.

4) Lazier Python programmers:

 fib=lambda n:1 if n<=2 else fib(n-1)+fib(n-2)

Description:
lambda keyword I have used in C# and Scheme However, lambda in Python is simpler than in C# and is very similar to the usage in Scheme, so I quickly adapted to it. This way of writing is often used when declaring some small functions in the Python Shell.

5) Python programmers who have just learned data structures:

def fib(n):
 x,y=0,1
 while(n):
  x,y,n=y,x+y,n-1
 return x

Explanation:
The previous Fibonacci functions are all It is an implementation of tree recursion. Even if you learn a little algorithm, you should know the inefficiency of this kind of recursion. Here, changing from tree recursion to corresponding iteration can improve the efficiency a lot.
Python's tuple assignment feature is something I like very much. This thing can simplify the code a lot. For example, the previous tmp=a;a=b;b=tmp; can be directly implemented with the sentence a,b=b,a, which is both concise and clear.

6) Python programmers who are taking SICP courses:

def fib(n):
  def fib_iter(n,x,y):
   if n==0 : return x
   else : return fib_iter(n-1,y,x+y)

  return fib_iter(n,0,1)

Note:
Here I used Scheme Tail-recursion is a very common writing method in languages. There is no iteration in Scheme, but invariants and tail recursion can be used to simulate iteration to achieve the same effect. However, I still don’t know if Python has made corresponding optimizations for tail recursion. I will check back.
PS: Students who have read SICP can tell at a glance that this program is actually an example in Chapter 1 of SICP.

7) A clever Python programmer:

fib=lambda n,x=0,y=1:x if not n else f(n-1,y,x+y)

Instructions:
Basic logic and the above example The same, both are written in tail recursive way. The main difference is that it uses the default parameters and ternary operator provided by Python, thereby simplifying the code to one line. As for default parameters, students who have studied C++ all know this stuff, and C# 4.0 has also introduced this stuff.

8) Python programmers who have just completed linear algebra:

def fib(n):
 def m1(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])
  return m
 def m2(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])
  return m
 return m2(reduce(m1,[[[0,1],[1,1]] for i in range(n)]),[[0],[1]])[0]

Explanation:
This code is not It is as clear as the previous code, so I will introduce the principle first (requiring a little knowledge of linear algebra):
First look at the previous iterative version of the Fibonacci function, it is easy to find that there is a transformation: y->x, x +y->y. From another angle, it is [x,y]->[y,x+y].
Here, I declare a binary vector [x,y]T, which obtains [y,x+y]T through a transformation. It can be easily obtained that the transformation matrix is ​​[[1,0],[1, 1]], that is to say: [[1,0],[1,1]]*[x,y]T=[y,x+y]T
Let the binary matrix A=[[1, 0],[1,1]], binary vector x=[0,1]T, it is easy to know that the result of Ax is the next Fibonacci value, that is:
Ax=[fib(1),fib(2) ]T
also has:
Ax=[fib(2),fib(3)]T
………………
By analogy, we can get:

Aⁿx=[fib(n),fib(n-1)]T

That is to say, you can perform n A transformations on the binary vector [0,1]T to get [fib(n),fib(n+1 )]T, thus obtaining fib(n).

Here I define a binary matrix multiplication function m1, and a transformation m2 on a binary vector, and then use the reduce operation to complete a continuous multiplication operation to get Aⁿx, and finally get fib (n).

9) Python programmers preparing to participate in the ACM competition:

 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]

Instructions:

看过上一个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的计算机编程入门语言。

The above is the detailed content of How to implement the Fibonacci function using Python. For more information, please follow other related articles on the PHP Chinese website!