So implementieren Sie die Fibonacci-Funktion mit Python

In diesem Artikel wird hauptsächlich die Verwendung von Python zur Implementierung von Fibonacci-Funktionsinformationen beschrieben.

Fibonacci-Fibonacci-Sequenz ist nur eine Rekursion kann das wahrscheinlich machen.

Ich habe kürzlich Python gespielt und bin zufällig auf einen Beitrag im Internet über die Entwicklung von Python-Programmierern gestoßen. Deshalb habe ich vor, einen Beitrag zu imitieren, der mehr als zehn Methoden zur Vervollständigung einer Fakultätsfunktion verwendet. Hier werde ich eine Fibonacci-Funktion in neun verschiedenen Stilen schreiben.

Die Anforderungen sind sehr einfach: Geben Sie n ein, geben Sie die n-te Fibonacci-Zahl aus, n ist eine positive ganze Zahl

Im Folgenden sind die neun verschiedenen Stile aufgeführt:

1) Python-Programmierer, die zum ersten Mal Programme schreiben:

def fib(n):
  return nth fibonacci number

Erklärung:
Menschen, die zum ersten Mal Programme schreiben Folgen Sie oft der Syntax der menschlichen Sprache und nicht der Syntax der Programmiersprache. Nehmen Sie als Beispiel das erste Programm, das er geschrieben hat, um Schaltjahre direkt zu bestimmen: Wenn das Jahr ein Schaltjahr ist , das Ausgabejahr ist ein Schaltjahr, andernfalls ist das Jahr kein Schaltjahr.

2) C-Programmierer, die gerade Python gelernt haben:

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

Hinweis:
Ich bin neu darin In Python bin ich es nicht gewohnt, zum Teilen von Programmblöcken Einrückungen anstelle von geschweiften Klammern zu verwenden, und nach jeder Anweisung steht kein Abschlusszeichen. Daher ist das erste, was ich nach dem Schreiben einer Python-Funktion normalerweise mache, einfach die geschweiften Klammern auskommentieren und die fehlenden Doppelpunkte hinzufügen .

3) Faule Python-Programmierer:

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

Erklärung:
Wussten Sie das, nachdem Sie „Learning Python“ gesehen haben? Python hat keinen ternären Operator? , aber angesichts der Tatsache, dass der Bool-Wert in Python etwas ganz Besonderes ist (ein bisschen wie in C, bedeutet ungleich Null wahr, nicht leer bedeutet wahr) und die logischen Anweisungen von Python auch die Kurzschlussauswertung (Short-Circuit Evaluation) unterstützen, ist dies möglich geschrieben werden Eine Nachahmung? Aussage kommt heraus.

4) Faule Python-Programmierer:

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

Hinweis:
Lambda-Schlüsselwort, das ich in C# und Scheme verwendet habe Da Lambda in Python einfacher ist als in C# und der Verwendung in Scheme sehr ähnlich ist, habe ich mich schnell daran gewöhnt. Diese Schreibweise wird häufig verwendet, wenn einige kleine Funktionen in der Python-Shell deklariert werden.

5) Python-Programmierer, die gerade mit dem Erlernen von Datenstrukturen fertig sind:

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

Erklärung:
Fibonacci vorne Funktionen sind alle Implementierungen der Baumrekursion. Selbst wenn Sie einen kleinen Algorithmus lernen, sollten Sie die Ineffizienz dieser Art der Rekursion kennen. Hier kann der Wechsel von der Baumrekursion zur entsprechenden Iteration die Effizienz erheblich verbessern.
Die Tupelzuweisungsfunktion von Python gefällt mir sehr gut. Sie kann den Code erheblich vereinfachen. Beispielsweise kann das vorherige tmp=a;a=b;b=tmp; direkt mit dem Satz a,b=b,a implementiert werden, was sowohl prägnant als auch klar ist.

6) Python-Programmierer, die SICP-Kurse belegen:

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)

Hinweis:
Hier verwende ich The very Die allgemeine Tail-Recursion-Schreibmethode (Tail-Recursion) in der Scheme-Sprache wird eingeführt. In Scheme gibt es keine Iteration, aber Invarianten und Schwanzrekursion können zur Simulation der Iteration verwendet werden, um den gleichen Effekt zu erzielen. Allerdings weiß ich immer noch nicht, ob Python entsprechende Optimierungen für die Tail-Rekursion vorgenommen hat, also schaue ich noch einmal nach.
PS: Studierende, die SICP gelesen haben, können auf einen Blick erkennen, dass es sich bei diesem Programm tatsächlich um ein Beispiel aus Kapitel 1 von SICP handelt.

7) Clevere Python-Programmierer:

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

Erklärung:
Grundlegende Logik und die oben genannten Beispiele sind die Das Gleiche, alles in rekursiver Weise geschrieben. Der Hauptunterschied besteht darin, dass die von Python bereitgestellten Standardparameter und der ternäre Operator verwendet werden, wodurch der Code auf eine Zeile vereinfacht wird. Was die Standardparameter betrifft, wissen alle Studenten, die C++ studiert haben, diese Dinge, und C# 4.0 hat diese Dinge auch eingeführt.

8) Python-Programmierer, die gerade die lineare Algebra abgeschlossen haben:

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]

Erklärung:
Dieser Code ist es nicht So klar wie der vorherige Code, also stellen wir zunächst das Prinzip vor (erfordert ein wenig Kenntnisse der linearen Algebra):
Schauen Sie sich zunächst die vorherige iterative Version der Fibonacci-Funktion an. Es ist leicht festzustellen, dass es eine Transformation gibt: y ->x , x+y->y. Aus einem anderen Blickwinkel ist es [x,y]->[y,x+y].
Hier deklariere ich einen binären Vektor [x,y]T, der durch eine Transformation [y,x+y]T erhält. Es kann leicht erhalten werden, dass die Transformationsmatrix [[1,0] ist. [1, 1]], das heißt: [[1,0],[1,1]]*[x,y]T=[y,x+y]T
Die Binärmatrix A= [[1, 0],[1,1]], binärer Vektor x=[0,1]T, es ist leicht zu erkennen, dass das Ergebnis von Ax der nächste Fibonacci-Wert ist, das heißt:
Ax=[ fib(1),fib(2) ]T
hat auch:
Ax=[fib(2),fib(3)]T
………………
Analog dazu haben wir kann erhalten:

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

Das heißt, Sie können n A-Transformationen für den binären Vektor [0,1]T durchführen, um ihn zu erhalten [fib(n),fib(n +1)]T, wodurch fib(n) erhalten wird.

Hier definiere ich eine binäre Matrixmultiplikationsfunktion m1 und eine Transformation m2 für einen binären Vektor und verwende dann die Reduktionsoperation, um eine kontinuierliche Multiplikationsoperation abzuschließen, um Aⁿx zu erhalten und schließlich fib (n ).

9) Python-Programmierer, die sich auf die Teilnahme am ACM-Wettbewerb vorbereiten:

 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]

Anleitung:

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

Das obige ist der detaillierte Inhalt vonSo implementieren Sie die Fibonacci-Funktion mit Python. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!