Comment implémenter la fonction Fibonacci en utilisant Python

Cet article explique principalement comment utiliser Python pour implémenter les informations relatives à la fonction Fibonacci. Les amis qui en ont besoin peuvent se référer à

Séquence de Fibonacci Fibonacci C'est très simple. peut probablement le faire.

J'ai joué à Python récemment. Après un rapide coup d'œil à Learning Python et Core Python, j'ai accidentellement trouvé un article sur Internet sur l'évolution des programmeurs Python. C'était très intéressant. Je prévois donc d'imiter un article qui utilise plus de dix méthodes pour compléter une fonction factorielle. Ici, je vais écrire une fonction de Fibonacci dans neuf styles différents.

Les exigences sont très simples, saisissez n, affichez le nième nombre de Fibonacci, n est un entier positif

Voici les neuf styles différents :

1) Programmeurs Python qui écrivent des programmes pour la première fois :

def fib(n):
  return nth fibonacci number

Explication :
Personnes qui écrivent des programmes pour la première fois temps souvent Suivez la syntaxe du langage humain plutôt que la syntaxe du langage de programmation. Prenons l'exemple d'un de mes amis qui est très doué en programmation. Le premier programme qu'il a écrit pour déterminer les années bissextiles indique directement ceci : Si l'année est une année bissextile. , l'année de sortie est une année bissextile, sinon l'année n'est pas une année bissextile.

2) Programmeurs C qui viennent d'apprendre Python :

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

Remarque :
Je suis nouveau dans ce domaine En Python, je n'ai pas l'habitude d'utiliser l'indentation au lieu d'accolades pour diviser les blocs de programme, et il n'y a pas de terminateur après chaque instruction, donc la première chose que je fais après avoir écrit une fonction Python est généralement de simplement commenter les accolades et d'ajouter les deux-points manquants. .

3) Programmeurs Python paresseux :

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

Explication :
Après avoir regardé Learning Python, saviez-vous que Python n'a pas d'opérateur ternaire ? , mais étant donné que la valeur bool en Python est assez spéciale (un peu comme C, non nul signifie vrai, non vide signifie vrai), et que les instructions logiques de Python prennent également en charge l'évaluation des courts-circuits (Short-Circuit Evaluation), cela peut être écrit Une imitation ? la déclaration sort.

4) Programmeurs Python paresseux :

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

Remarque :
mot-clé lambda que j'ai utilisé en C# et Scheme que j'ai utilisé avant. Lambda en Python est plus simple qu'en C# et est très similaire à l'utilisation dans Scheme, donc je m'y suis rapidement adapté. Cette façon d'écrire est souvent utilisée lors de la déclaration de certaines petites fonctions dans Python Shell.

5) Programmeurs Python qui viennent de finir d'apprendre les structures de données :

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

Explication :
Fibonacci devant Les fonctions sont toutes des implémentations de récursivité arborescente. Même si vous apprenez un peu d'algorithme, vous devriez connaître l'inefficacité de ce type de récursion. Ici, passer de la récursivité de l'arbre à l'itération correspondante peut améliorer considérablement l'efficacité.
La fonctionnalité d'affectation de tuples de Python est quelque chose que j'aime beaucoup. Elle peut beaucoup simplifier le code. Par exemple, le précédent tmp=a;a=b;b=tmp; peut être directement implémenté avec la phrase a,b=b,a, qui est à la fois concise et claire.

6) Programmeurs Python qui suivent des cours SICP :

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)

Remarque :
Ici, j'utilise le très La méthode d'écriture commune de récursion de queue (Tail-récursion) dans le langage Scheme est introduite. Il n'y a pas d'itération dans Scheme, mais les invariants et la récursion de queue peuvent être utilisés pour simuler l'itération afin d'obtenir le même effet. Cependant, je ne sais toujours pas si Python a effectué les optimisations correspondantes pour la récursion de queue, je reviendrai.
PS : Les étudiants qui ont lu le SICP peuvent voir en un coup d'œil que ce programme est en fait un exemple du chapitre 1 du SICP.

7) Programmeurs Python intelligents :

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

Explication :
Logique de base et ce qui précède Les exemples sont les pareil, tous écrits de manière récursive. La principale différence est qu'il utilise les paramètres par défaut et l'opérateur ternaire fournis par Python, simplifiant ainsi le code sur une seule ligne. En ce qui concerne les paramètres par défaut, les étudiants qui ont étudié le C le savent tous, et C# 4.0 les a également introduits.

8) Programmeurs Python qui viennent de terminer l'algèbre linéaire :

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]

Explication :
Ce code n'est pas aussi clair que le code précédent, introduisons donc d'abord le principe (nécessite un peu de connaissance en algèbre linéaire) :
Regardez d'abord la version itérative précédente de la fonction de Fibonacci, il est facile de constater qu'il y a une transformation : y ->x , x y->y. Sous un autre angle, c'est [x,y]->[y,x y].
Ici, je déclare un vecteur binaire [x,y]T, qui obtient [y,x y]T grâce à une transformation. On peut facilement obtenir que la matrice de transformation est [[1,0],[1. ,1] ], soit : [[1,0],[1,1]]*[x,y]T=[y,x y]T
Soit la matrice binaire A=[[1, 0],[ 1,1]], vecteur binaire x=[0,1]T, il est facile de savoir que le résultat de Ax est la prochaine valeur de Fibonacci, soit :
Ax=[fib(1) ,fib(2)]T
Aussi :
Ax=[fib(2),fib(3)]T
…………
Par analogie, on peut obtenir :

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

C'est-à-dire que vous pouvez effectuer n A transformations sur le vecteur binaire [0,1]T pour obtenir [fib(n),fib (n 1)]T , obtenant ainsi fib(n).

Ici, je définis une fonction de multiplication matricielle binaire m1, et une transformation m2 sur un vecteur binaire, puis j'utilise l'opération de réduction pour terminer une opération de multiplication continue pour obtenir Aⁿx, et enfin obtenir fib (n ).

9) Programmeurs Python se préparant à participer au concours ACM :

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!