Benutzer-Werkzeuge
ss14:rekursive_funktionen_fibonacci_decorators_sitzung_vom_22._mai
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen gezeigt.
| Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende Überarbeitung | ||
|
ss14:rekursive_funktionen_fibonacci_decorators_sitzung_vom_22._mai [2014/05/25 23:35] stefanborn |
ss14:rekursive_funktionen_fibonacci_decorators_sitzung_vom_22._mai [2016/05/10 14:46] (aktuell) |
||
|---|---|---|---|
| Zeile 27: | Zeile 27: | ||
| </code> | </code> | ||
| | | ||
| - | Diese Lösung hat einen Vorteil und einige Nachteile: Benötigt man die Werte der Folge immer wieder, so wird die Funktion, nachdem sie die Werte einmal berechnet hat, sehr schnell. Andererseits ist ihr Speicherverbrauch linear in n, auch wird der Python-Interpreter für große n die Funktion sich sehr oft selbst aufrufen lassen müssen, bevor sie auf bereits tabellierte Werte stößt. Trotz der Nachteile dieses Verfahrens ist es nützlich, ein automatisierters Verfahren zu haben, dass aus einer beliebigen Funktion eine macht, die sich ihre Werte merkt. Dazu findet ihr Material in diesem [[http://www.python-course.eu/python3_memoization.php | Artikel über Memoizing und Decorators]]. | + | Diese Lösung hat einen Vorteil und einige Nachteile: Benötigt man die Werte der Folge immer wieder, so wird die Funktion, nachdem sie die Werte einmal berechnet hat, sehr schnell. Andererseits ist ihr Speicherverbrauch linear in n, auch wird der Python-Interpreter für große n die Funktion sich sehr oft selbst aufrufen lassen müssen, bevor sie auf bereits tabellierte Werte stößt. Trotz der Nachteile dieses Verfahrens ist es nützlich, ein automatisierters Verfahren zu haben, dass aus einer beliebigen Funktion eine macht, die sich ihre Werte merkt. Dazu findet ihr Material in diesem [[http://www.python-course.eu/python3_memoization.php | Artikel über Memoizing und Decorators]] (hier besteht kein Unterschied zwischen Python 2.7 und Python 3). |
| Will man einfach nur eine Funktion, die für möglichst große Werte von n noch in der Lage ist, das n. Glied der Fibonacci-Folge zu berechnen, so kann man das in einer Schleife, die aus den ersten beiden Werten den dritten, aus dem zweiten und dritten, den vierten usw. bis zum n. berechnet: | Will man einfach nur eine Funktion, die für möglichst große Werte von n noch in der Lage ist, das n. Glied der Fibonacci-Folge zu berechnen, so kann man das in einer Schleife, die aus den ersten beiden Werten den dritten, aus dem zweiten und dritten, den vierten usw. bis zum n. berechnet: | ||
| <code python> | <code python> | ||
| + | def fibonacci(n): | ||
| + | if (n==1) or (n==2): | ||
| + | return 1 | ||
| + | else: | ||
| + | a=1 | ||
| + | b=1 | ||
| + | k=2 | ||
| + | while (k<n): | ||
| + | # Es gilt an dieser Stelle stets: a=fibonacci(k-1), b=fibonacci(k) | ||
| + | a,b=b,a+b | ||
| + | k=k+1 | ||
| + | return b | ||
| + | </code> | ||
| + | |||
| + | Dieses Programm liefert nun auch für sehr große Werte von $n$ den Wert der Fibonacci-Folge. Die Schleife muss zur Berechnung | ||
| + | von fibonacci(n) n-2 mal aufgerufen werden. Da Python mit fast beliebig großen ganzen Zahlen rechnen kann, lässt sich so etwa fibonacci(100000) im Bruchteil einer Sekunde berechnen. Es kann aber auch in dieser Variante praktisch sein, eine Merktabelle anzulegen, wenn dieselben Werte immer wieder benötigt werden. | ||
ss14/rekursive_funktionen_fibonacci_decorators_sitzung_vom_22._mai.1401053746.txt.gz · Zuletzt geändert: 2016/05/10 14:46 (Externe Bearbeitung)
Seiten-Werkzeuge
