Obliczanie wartosci elementow ciagu Fibonacciego metoda iteracyjna w Pythonie
ð Podstawa programowa: I.2dCiag Fibonacciego to jeden z najslynniejszych ciagow liczbowych w matematyce i informatyce. Zostal opisany przez wloskiego matematyka Leonarda z Pizy (zwanego Fibonacci) w 1202 roku w ksiazce Liber Abaci.
Kazdy kolejny wyraz ciagu jest suma dwoch poprzednich wyrazow. Ta prosta regula generuje ciag o niezwyklych wlasnosciach matematycznych.
Istnieja dwa glowne podejscia do obliczania wartosci ciagu Fibonacciego:
# Metoda iteracyjna - obliczanie n-tego wyrazu ciagu Fibonacciego
def fibonacci(n):
if n == 0:
return 0
if n == 1:
return 1
a = 0 # F(0)
b = 1 # F(1)
for i in range(2, n + 1):
c = a + b # F(i) = F(i-1) + F(i-2)
a = b # przesuwamy wartosci
b = c
return b
# Test
for i in range(15):
print(f"F({i}) = {fibonacci(i)}")# Wypisanie pierwszych n wyrazow ciagu Fibonacciego
def fibonacci_ciag(n):
if n <= 0:
return []
if n == 1:
return [0]
ciag = [0, 1]
for i in range(2, n):
ciag.append(ciag[i-1] + ciag[i-2])
return ciag
# Wypisz pierwsze 20 wyrazow
wynik = fibonacci_ciag(20)
print("Pierwsze 20 wyrazow ciagu Fibonacciego:")
print(wynik)Ciag Fibonacciego pojawia sie zaskakujaco czesto w przyrodzie:
print(fibonacci(30) / fibonacci(29))
import time
# Metoda rekurencyjna (WOLNA!)
def fib_rek(n):
if n <= 1:
return n
return fib_rek(n-1) + fib_rek(n-2)
# Metoda iteracyjna (SZYBKA!)
def fib_iter(n):
if n <= 1:
return n
a, b = 0, 1
for i in range(2, n + 1):
a, b = b, a + b
return b
# Porownanie czasu dla n = 35
start = time.time()
print(f"Rekurencja: F(35) = {fib_rek(35)}")
print(f"Czas: {time.time() - start:.4f} s")
start = time.time()
print(f"Iteracja: F(35) = {fib_iter(35)}")
print(f"Czas: {time.time() - start:.6f} s")Napisz program, ktory pyta uzytkownika o numer wyrazu ciagu Fibonacciego (n), a nastepnie oblicza i wypisuje wartosc F(n) metoda iteracyjna.
def fibonacci(n):
if n == 0:
return 0
if n == 1:
return 1
a, b = 0, 1
for i in range(2, n + 1):
a, b = b, a + b
return b
n = int(input("Podaj numer wyrazu ciagu: "))
if n < 0:
print("Numer musi byc nieujemny!")
else:
print(f"F({n}) = {fibonacci(n)}")Napisz program, ktory oblicza sume pierwszych n wyrazow ciagu Fibonacciego. Na przyklad dla n=7 (wyrazy: 0, 1, 1, 2, 3, 5, 8) suma = 20.
def suma_fibonacci(n):
if n <= 0:
return 0
suma = 0
a, b = 0, 1
for i in range(n):
suma += a
a, b = b, a + b
return suma
n = int(input("Ile wyrazow zsumowac? "))
print(f"Suma pierwszych {n} wyrazow = {suma_fibonacci(n)}")
# Wypisz tez same wyrazy:
a, b = 0, 1
wyrazy = []
for i in range(n):
wyrazy.append(str(a))
a, b = b, a + b
print(f"Wyrazy: {', '.join(wyrazy)}")Napisz program, ktory oblicza stosunek F(n+1)/F(n) dla kolejnych n od 2 do 20 i wypisuje wyniki. Zaobserwuj, jak stosunek zbliza sie do zlotego podzialu (phi ≈ 1.618).
import math
def fibonacci(n):
if n <= 1:
return n
a, b = 0, 1
for i in range(2, n + 1):
a, b = b, a + b
return b
phi = (1 + math.sqrt(5)) / 2
print(f"Zloty podzial phi = {phi:.10f}")
print(f"{'n':>3} | {'F(n+1)/F(n)':>15} | {'Roznica od phi':>15}")
print("-" * 40)
for n in range(2, 21):
stosunek = fibonacci(n + 1) / fibonacci(n)
roznica = abs(stosunek - phi)
print(f"{n:>3} | {stosunek:>15.10f} | {roznica:>15.10f}")Napisz program, ktory sprawdza, czy podana przez uzytkownika liczba jest elementem ciagu Fibonacciego. Wskazowka: generuj kolejne wyrazy ciagu dopoki nie osiagniesz lub przekroczysz podanej liczby.
def czy_fibonacci(liczba):
if liczba < 0:
return False
if liczba == 0 or liczba == 1:
return True
a, b = 0, 1
while b < liczba:
a, b = b, a + b
return b == liczba
# Test
liczba = int(input("Podaj liczbe: "))
if czy_fibonacci(liczba):
print(f"{liczba} JEST liczba Fibonacciego!")
else:
print(f"{liczba} NIE jest liczba Fibonacciego.")
# Bonus: pokaz najblizsze liczby Fibonacciego
a, b = 0, 1
while b < liczba:
a, b = b, a + b
if b != liczba:
print(f"Najblizsze liczby Fibonacciego: {a} i {b}")