In dem Python-Buch, das ich gelesen habe, habe ich etwas über die Fibonacci-Zahlenfolge herausgefunden, daher werde ich sie mit einem leichten Inhalt wie einem Memo zusammenfassen, während ich sie untersuche.
Bitte beachten Sie, dass ich einen Abschluss in Design habe. Wenn Sie Absolvent einer Universität in Mathematik oder Informatik sind, kann dies verschiedene Punkte haben.
Es ist eine Sequenz, die nach dem italienischen Mathematiker Leonardo Fibonacci (Fibonacci-Sequenz in Englisch) benannt ist.
Es ist eine Folge von Werten wie "0, 1, 1, 2, 3, 5, 8, 13, 21 ...".
Der erste (Index von 0) ist 0, der nächste (Index von 1) ist 1 und danach der vorherige und 2 In einem Ausdruck geschrieben sieht es wie folgt aus (vorausgesetzt, der $ n $ -te Wert in der Zahlenspalte ist $ F_n $).
F_0 = 0\\
F_1 = 1\\
F_n = F_{n - 1} + F_{n - 2}
Darüber hinaus ist diese Zahlenfolge eng mit der sogenannten Designrichtung verbunden, insbesondere mit dem Goldenen Schnitt (1: 1,618 ...), und erscheint in designbezogenen Büchern.
Sogar in der natürlichen Welt gibt es verschiedene Dinge wie Sonnenblumenkerne und Papageien, die nahe an den Werten in dieser Anzahl von Reihen liegen, und es wird gesagt, dass das Verhältnis Menschen das Gefühl gibt, natürlich und schön zu sein.
Wenn Sie ein Rechteck mit goldenem Schnitt in zwei Teile teilen, ein Quadrat und ein Rechteck, wird das Rechteck zu einem Rechteck, das den goldenen Schnitt wieder beibehält und verschiedene interessante Eigenschaften aufweist (Details werden in diesem Artikel weggelassen). Wenn Sie Artikel und Bücher zu Mathematik und Design nachschlagen, finden Sie verschiedene Dinge. Überprüfen Sie dies gegebenenfalls.
Lassen Sie uns zunächst, ohne über irgendetwas nachzudenken, einen Prozess schreiben, um den Wert der Position des Index n der Fibonacci-Sequenz in Python durch rekursives Aufrufen der Funktion zu erhalten.
def fib(n: int) -> int:
if n == 0:
return 0
if n == 1:
return 1
return fib(n - 1) + fib(n - 2)
Wie in der obigen Formel werden, wenn n 0 ist und n 1 ist, 0 bzw. 1 zurückgegeben, und danach wird die Summe der Werte in der Fibonacci-Sequenz an den Positionen n -1 und n -2 verwendet. Es gibt.
Lassen Sie es uns ausführen und das Ergebnis sehen.
if __name__ == '__main__':
for n in range(7):
print(f'n = {n}Im Falle von:', fib(n=n))
n =Wenn 0: 0
n =Im Falle von 1: 1
n =Im Falle von 2: 1
n =Im Falle von 3: 2
n =Im Falle von 4: 3
n =Im Falle von 5: 5
n =Im Falle von 6: 8
Sie können sehen, dass der erwartete Wert genommen wird.
Wenn bei dieser Rate n groß wird, dauert die Berechnung lange.
Um beispielsweise den Wert von n = 5 zu berechnen, müssen Sie die Werte von n = 4 und n = 3 berechnen, und um n = 4 zu berechnen, müssen Sie die Werte von n = 3 und n = 2 ermitteln. Jedes Mal, wenn n um eins zunimmt, nehmen die zu berechnenden Bedingungen wie bei einem Familiendiagramm exponentiell zu.
Lassen Sie uns herausfinden, wie oft die vorbereitete Funktion ausgeführt wurde. Ich habe eine Variable namens count als globale Variable vorbereitet.
from datetime import datetime
count: int = 0
def fib(n: int) -> int:
global count
count += 1
if n == 0:
return 0
if n == 1:
return 1
return fib(n - 1) + fib(n - 2)
Wenn Sie versuchen, es mit n = 34 und n = 35 auszuführen, können Sie sehen, dass die Anzahl der Funktionsausführungen nur durch Erhöhen von n um 1 signifikant zugenommen hat.
n=Probe auf 34 laufen lassen
if __name__ == '__main__':
print(datetime.now(), 'started')
fib(n=34)
print('Häufigkeit, mit der die Funktion ausgeführt wurde:', count)
print(datetime.now(), 'ended')
2020-08-30 15:45:15.097393 started
Häufigkeit, mit der die Funktion ausgeführt wurde: 18454929
2020-08-30 15:45:17.980419 ended
n=Probe bei 35 laufen lassen
if __name__ == '__main__':
print(datetime.now(), 'started')
fib(n=35)
print('Häufigkeit, mit der die Funktion ausgeführt wurde:', count)
print(datetime.now(), 'ended')
2020-08-30 15:49:25.628928 started
Häufigkeit, mit der die Funktion ausgeführt wurde: 29860703
2020-08-30 15:49:30.307930 ended
Wie oben erwähnt, gibt es verschiedene Methoden, um die Berechnung zu beschleunigen, wenn n groß wird, und eine davon besteht darin, das Ausführungsergebnis der Funktion zwischenzuspeichern.
Wenn beispielsweise der Wert von n gleich ist, ist der Rückgabewert derselbe, und bei der Berechnung des Werts von großem n kann der kleinere Wert immer wieder berechnet werden, sodass bereits ein bestimmtes n angegeben ist. Wenn der Fall des Werts von bereits aggregiert ist, kann er zwischengespeichert und die Berechnung übersprungen werden, so dass die Verarbeitung in kurzer Zeit abgeschlossen werden kann, selbst wenn n zunimmt.
Sie können es mit einem Wörterbuch zwischenspeichern, aber in Python können Sie die integrierten Modul-Funktools verwenden und den Dekorator für lru_cache angeben.
Es ist einfach zu bedienen, setzen Sie einfach die Funktion lru_cache als Dekorateur auf die Funktion, die Sie zwischenspeichern möchten. lru ist eine Abkürzung für Least Recent Used und eine Methode zum Zwischenspeichern in Form eines neuen Ausführungsergebnisses (in diesem Fall wird das Berechnungsergebnis von n gegen Ende zwischengespeichert).
Da diesmal der alte Cache nicht gelöscht wird, sondern alle zwischengespeichert werden, wird für das Argument maxsize None angegeben.
from datetime import datetime
from functools import lru_cache
count: int = 0
@lru_cache(maxsize=None)
def fib(n: int) -> int:
global count
count += 1
if n == 0:
return 0
if n == 1:
return 1
return fib(n - 1) + fib(n - 2)
Wenn Sie es ausführen, können Sie sehen, dass der Prozess sofort abgeschlossen ist und die Anzahl der Vorgänge innerhalb der Funktion gleichzeitig abgenommen hat.
if __name__ == '__main__':
print(datetime.now(), 'started')
fib(n=35)
print('Häufigkeit, mit der die Funktion ausgeführt wurde:', count)
print(datetime.now(), 'ended')
2020-08-30 16:39:49.109241 started
Häufigkeit, mit der die Funktion ausgeführt wurde: 36
2020-08-30 16:39:49.110240 ended
Recommended Posts