[Python] Ein Programm zum Finden einer Fibonacci-Zahlenfolge (rekursive Funktion, Divisions-Governance-Methode, dynamische Planungsmethode)

Programm zum Auffinden der Fibonacci-Sequenz

Schreiben Sie ein Programm, das n Elemente in der Fibonacci-Zahlenfolge mit mehreren Beschreibungen findet.

Was ist die Fibonacci-Sequenz?

Eine Folge von Zahlen, die durch Hinzufügen des vorherigen und des vorherigen Begriffs erstellt wurden.

1,1,2,3,5,8,13,21,34,55,,,,,,

Wenn Sie sie addieren, wird ein großes Rechteck erstellt.

Die Fibonacci-Sequenz ist ein Wirbel aus Ammonit und Wirbeln, die im Raum größer werden.

Das goldene Rechteck von Steel Ball Run ist ebenfalls eine Fibonacci-Sequenz.

python

def fib(n):
  arr = [1,1]
  for j in range(n-1):
    val = arr[j] + arr[j+1] 
    arr.append(val) 

  return (arr[len(arr)-1])

Bestätigung

n=35
for i in range(1, n):
  print(fib(i))

Es ähnelt dem Wiederholen, bis die angegebene Bedingung erfüllt ist, und der gleiche Vorgang wird wiederholt, bis die Rückgabebedingung erfüllt ist.

python

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

python

#Bestätigung
n=35
for i in range(1, n):
  print(fib(i))

Dieser Vorgang ist relativ zeitaufwändig. Dies liegt daran, dass dieselbe Berechnung ** einzeln in fib (n-1) bzw. fib (n-2) berechnet wird.

Da fib (n-2) früher berechnet, kann die Berechnungszeit stark reduziert werden, wenn die Lösung auf fib (n-1) aufgetragen wird.

Diese epochale Methode wird als ** dynamische Planungsmethode ** bezeichnet.

python

#Wenn nur Variablen vorhanden sind, wird memo zu einer globalen Variablen. Fügen Sie es daher in def ein und machen Sie es zu einer lokalen Variablen.
def fib_memo(n):
  #Fib, so dass der Wert auch nach Abschluss der Funktionsverarbeitung erhalten bleibt(n)Raus aus
  memo = [None]*(n+1)  #n+Bereiten Sie ein Array mit einem leeren Element vor

  def _fib(n):
    if n==0 or n==1:
      return 1
    if memo[n] != None:  #Wenn das Element des angegebenen Werts nicht None ist, verwenden Sie diesen Wert (* Anfangswerte sind alle None)
      return memo[n]
    memo[n] = _fib(n-1) + _fib(n-2) #Wenn Keine, ersetzen Sie die hinzugefügten Werte
    return memo[n]
  
  return _fib(n)

Bestätigung

n=40
for i in range(0, n):
  print(fib_memo(i))

-Keine: Geben Sie explizit an, dass es leer ist (kein Objekt) -_Funktionsname: Schlägt eine Funktion vor, die nur lokal verwendet werden soll

Der Berechnungsprozess ist erheblich schneller.

Es ist auch möglich, die Memo-Methode anstelle der rekursiven Methode zu verwenden, um nacheinander aus kleinen Zahlen zu berechnen.

python

def fib_dp(n):
  memo = [None]*n
  memo[0] = 1
  memo[1] = 1
  for i in range(2, n):
    memo[i] = memo[i-1] + memo[i-2]
  return memo