Eine Fibonacci-Sequenz ist "eine Sequenz, in der die ersten beiden Terme 0, 1 sind und jeder nachfolgende Term die Summe der beiden unmittelbar vorhergehenden Terme ist." ([Wikibedia](https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%9C%E3%83%8A%E3%83%83%E3% Von 83% 81% E6% 95% B0))
Fibonacci-Folge
0
1
1 （0 + 1）
2 （1 + 1）
3 （1 + 2）
5 （2 + 3）
8 （3 + 5）
13 （5 + 8）
Wenn der n-te Term dieser Zahlenfolge gefunden wird, wird er so implementiert, wenn er so implementiert ist, wie er ist.
def fib(n):
"""
Finden Sie die n-te Fibonacci-Zahl ab 0.
"""
if n == 0:
return 0
if n == 1:
return 1
return fib(n-1) + fib(n-2)
print(fib(7)) # -> 13
Wenn Sie es tatsächlich ausführen, können Sie sehen, dass es ** sehr langsam ** ist. Zum Beispiel nimmt sogar n = 100 eine beträchtliche Zeit in Anspruch.
Der Grund ist, dass, obwohl ich die Details weglassen werde, ** dieselbe Berechnung viele Male durchgeführt wird **. Zum Beispiel kann fib (8) erhalten werden, indem fib (7) und fib (6) gefunden und dann addiert werden. Um jedoch fib (7) zu finden, ist es notwendig, fib (6) erneut zu finden. Es gibt.
Beschleunigen wir mit dem Schlüsselwort ** "Führen Sie nicht zweimal dieselbe Berechnung durch" **. Ich werde zwei Algorithmen vorstellen, ** Memorandum ** und ** dynamische Planungsmethode **.
Speichern Sie das Ergebnis der Berechnung einmal. Wenn es funktioniert, verwenden Sie es, wenn nicht, berechnen Sie es erneut und speichern Sie das Ergebnis für die zukünftige Verwendung.
MAX_N = 100
MEMO = [None] * (MAX_N + 1) #Array zum Speichern des Berechnungsergebnisses
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
#Berechnet?
if MEMO[n]:
return MEMO[n]
r = fib(n-1) + fib(n-2)
MEMO[n] = r #Speichern Sie das Berechnungsergebnis
return r
print(fib(100))
Selbst wenn n = 100 war, kam das Ergebnis sofort zurück.
Selbst wenn Sie keine rekursive Funktion verwenden, können Sie die Fibonacci-Zahl ermitteln, indem Sie aus der mit dem kleinsten n berechnen.
MAX_N = 100
DP = [None] * (MAX_N + 1) #Array zum Speichern des Berechnungsergebnisses
DP[0] = 0 #Aus der Definition
DP[1] = 1 #Aus der Definition
def fib(n):
#Finden Sie die Anzahl der Fibonacci in der Reihenfolge von 2 bis n
for i in range(2, n + 1):
DP[i] = DP[i-1] + DP[i-2]
return DP[n]
print(fib(100))
Informationen zur dynamischen Planung finden Sie im Referenzmaterial.