Ciagi liczbowe, rekurencja vs iteracja, ciag Fibonacciego w Pythonie
ð Podstawa programowa: II.1+I.2dCiag Fibonacciego to jeden z najslynniejszych ciagow w matematyce. Kazdy wyraz (poczawszy od trzeciego) jest suma dwoch poprzednich:
F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)
Poczatkowe wyrazy: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
def fibonacci_iteracyjnie(n):
"""Zwraca n-ty wyraz ciagu Fibonacciego (iteracyjnie)."""
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
# Wyswietl pierwsze 15 wyrazow
for i in range(15):
print(fibonacci_iteracyjnie(i), end=" ")
# 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377Rekurencja = funkcja wywoluje sama siebie. Elegancka, ale nieefektywna dla duzych n:
def fibonacci_rekurencyjnie(n):
"""Zwraca n-ty wyraz ciagu Fibonacciego (rekurencyjnie)."""
if n <= 0:
return 0
if n == 1:
return 1
return fibonacci_rekurencyjnie(n - 1) + fibonacci_rekurencyjnie(n - 2)
# UWAGA: Dla n > 35 bedzie BARDZO wolno!
print(fibonacci_rekurencyjnie(10)) # 55# Ciag arytmetyczny: a(n) = a(0) + n * r
def ciag_arytmetyczny(a0, r, n):
return [a0 + i * r for i in range(n)]
print(ciag_arytmetyczny(2, 3, 8)) # [2, 5, 8, 11, 14, 17, 20, 23]
# Ciag geometryczny: a(n) = a(0) * q^n
def ciag_geometryczny(a0, q, n):
return [a0 * q**i for i in range(n)]
print(ciag_geometryczny(1, 2, 8)) # [1, 2, 4, 8, 16, 32, 64, 128]
# Silnia: n! = 1 * 2 * 3 * ... * n
def silnia(n):
wynik = 1
for i in range(1, n + 1):
wynik *= i
return wynik
# Ciag: 1!, 2!, 3!, ..., 10!
for i in range(1, 11):
print(f"{i}! = {silnia(i)}")def collatz(n):
"""Generuje ciag Collatza zaczynajacy od n."""
ciag = [n]
while n != 1:
if n % 2 == 0:
n = n // 2
else:
n = 3 * n + 1
ciag.append(n)
return ciag
print(collatz(27)) # [27, 82, 41, 124, 62, 31, ...]Napisz program, ktory wyswietla wszystkie wyrazy ciagu Fibonacciego mniejsze od podanej liczby n. Uzyj wersji iteracyjnej.
n = int(input("Podaj granice: "))
a, b = 0, 1
print("Wyrazy ciagu Fibonacciego mniejsze od", n, ":")
while a < n:
print(a, end=" ")
a, b = b, a + bNapisz program, ktory generuje: a) ciag arytmetyczny o podanym a0, roznicy r i n wyrazach, b) ciag geometryczny o podanym a0, ilorazie q i n wyrazach. Oblicz sume kazdego ciagu.
print("=== Ciag arytmetyczny ===")
a0 = float(input("Podaj a0: "))
r = float(input("Podaj roznice r: "))
n = int(input("Ile wyrazow? "))
ciag_a = [a0 + i * r for i in range(n)]
print(f"Ciag: {ciag_a}")
print(f"Suma: {sum(ciag_a)}")
print("\n=== Ciag geometryczny ===")
a0 = float(input("Podaj a0: "))
q = float(input("Podaj iloraz q: "))
n = int(input("Ile wyrazow? "))
ciag_g = [a0 * q**i for i in range(n)]
print(f"Ciag: {ciag_g}")
print(f"Suma: {sum(ciag_g)}")Napisz program, ktory oblicza stosunek kolejnych wyrazow Fibonacciego (F(n)/F(n-1)) dla n od 2 do 20. Pokaz, ze stosunek ten zbliza sie do zlotego podzialu (ok. 1.6180339...).
def fib(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
zloty = (1 + 5**0.5) / 2
print(f"Zloty podzial = {zloty:.10f}\n")
print(f"{'n':>4} | {'F(n)':>10} | {'F(n)/F(n-1)':>14} | {'Roznica':>12}")
print("-" * 48)
for n in range(2, 21):
stosunek = fib(n) / fib(n - 1)
roznica = abs(stosunek - zloty)
print(f"{n:>4} | {fib(n):>10} | {stosunek:>14.10f} | {roznica:>12.10f}")Zaimplementuj Fibonacciego iteracyjnie i rekurencyjnie. Zmierz czas wykonania obu wersji dla n = 10, 20, 30, 35. Wyswietl wyniki w tabeli i wyciagnij wnioski.
import time
def fib_iter(n):
if n <= 1: return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
def fib_rek(n):
if n <= 1: return n
return fib_rek(n-1) + fib_rek(n-2)
print(f"{'n':>4} | {'Wynik':>12} | {'Iteracja':>12} | {'Rekurencja':>12}")
print("-" * 50)
for n in [10, 20, 30, 35]:
start = time.time()
wynik_i = fib_iter(n)
czas_i = time.time() - start
start = time.time()
wynik_r = fib_rek(n)
czas_r = time.time() - start
print(f"{n:>4} | {wynik_i:>12} | {czas_i:>10.6f}s | {czas_r:>10.6f}s")
print("\nWniosek: Rekurencja jest wykladniczo wolniejsza!")