Python :: Aufgabe #258
5 Lösungen
Fibonacci-Folge - Berechnung der ersten 100 Zahlen (mit Schleife oder rekursiver Funktion)
Anfänger - Python
von Gnom
- 31.03.2020 um 00:35 Uhr
Berechne die ersten 100 Zahlen der Fibonacci-Folge (0, 1, 1, 2, 3, 5, 8, 13, ... vgl.: Fibonacci-Folge (Wikipedia))
Die Fibonacci-Folge beginnt mit den Zahen 0 und 1. Jede weitere Zahl der Folge wird durch Addition der beiden Vorhergehenden gebildet.
0
1
1 (=0+1)
2 (=1+1)
3 (=1+2)
5 (=2+3)
8 (=3+5)
13 (=5+8)
...
Die Aufgabe lässt sich mit einer relativ einfachen Schleife lösen.
Fortgeschrittene können sie auch mit einer rekursiven Funktion lösen.
Viel Erfolg!
Die Fibonacci-Folge beginnt mit den Zahen 0 und 1. Jede weitere Zahl der Folge wird durch Addition der beiden Vorhergehenden gebildet.
0
1
1 (=0+1)
2 (=1+1)
3 (=1+2)
5 (=2+3)
8 (=3+5)
13 (=5+8)
...
Die Aufgabe lässt sich mit einer relativ einfachen Schleife lösen.
Fortgeschrittene können sie auch mit einer rekursiven Funktion lösen.
Viel Erfolg!
Lösungen:
Python-Code
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# inspiriert durch Youtube: https://www.youtube.com/watch?v=Qk0zUZW-U_M
fibonacci_cache = {}
def fibonacci(n):
#Eingabeprüfung
if type(n) != int:
raise TypeError('n muss eine positive ganze Zahl sein')
if n < 1:
raise ValueError('n muss eine positive ganze Zahl sein')
#Wenn der Wert im Cache ist, dann diesen zurückgeben
if n in fibonacci_cache:
return fibonacci_cache[n]
if n == 1:
wert = 1
elif n == 2:
wert = 1
elif n > 2:
#Rekursiver Aufruf
wert = fibonacci(n-1) + fibonacci(n-2)
fibonacci_cache[n] = wert
return wert
Ausgabe von:
fibonacci(100) = 354224848179261915075
fibonacci(1.2): TypeError: n muss eine positive ganze Zahl sein
fibonacci(-3): ValueError: n muss eine positive ganze Zahl sein
Python-Code
a=0
b=1
print(a)
print(b)
for i in range(1,99):
c=a+b
print(c)
a=b
b=c
Python-Codeende = int(input("Bis wohin möchten Sie die Fibonaccifolge angezeigt bekommen?"))
n_0 = 0
n_1 = 1
n_2 = 1
print(n_0)
print(n_1)
for i in range(0, ende):
print(n_2)
n_0 = n_1
n_1 = n_2
n_2 = n_1 + n_0 Python-Codedef Fibonacci(i):
if i == 0:
return 0
elif i == 1:
return 1
elif i<0:
return Fibonacci(-i)
else:
return (Fibonacci(i-1)+Fibonacci(i-2))
print("Hinweis: Negative Zahlen werden vernachlaessigt")
i = int(input("Bitte geben Sie eine ganze Zahl ein, von welcher die Fibonacci-Folge berechnet werden soll: "))
print(f"Fibonacci-Folge: {Fibonacci(i)}") Python-Code
# Rekursive Berechnung der 100. Fibonacci-Zahl
from typing import Dict
memo: Dict[int, int] = {0: 0, 1: 1} #Abbruchbedingung
def fib(n: int) -> int:
if n not in memo:
memo[n] = fib(n-1) + fib(n-2) #Memoisation
return memo[n]
if __name__ == "__main__":
print(fib(100))