12 — Algorytmy: etap 3

def silnia_debug(n, poziom=0):
    wciec = "  " * poziom
    print(f"{wciec}silnia({n}) wywołana")

    if n == 0:
        print(f"{wciec}silnia(0) → zwraca 1")
        return 1

    wynik = n * silnia_debug(n - 1, poziom + 1)
    print(f"{wciec}silnia({n}) → zwraca {wynik}")
    return wynik

silnia_debug(4)
# silnia(4) wywołana
#   silnia(3) wywołana
#     silnia(2) wywołana
#       silnia(1) wywołana
#         silnia(0) wywołana
#         silnia(0) → zwraca 1
#       silnia(1) → zwraca 1
#     silnia(2) → zwraca 2
#   silnia(3) → zwraca 6
# silnia(4) → zwraca 24

# Rekurencyjna
def silnia_rek(n):
    if n == 0:
        return 1
    return n * silnia_rek(n - 1)

# Iteracyjna — for
def silnia_for(n):
    wynik = 1
    for i in range(2, n + 1):
        wynik *= i
    return wynik

# Iteracyjna — while
def silnia_while(n):
    wynik = 1
    i     = 2
    while i <= n:
        wynik *= i
        i += 1
    return wynik

# Test wszystkich wersji
for n in range(8):
    r = silnia_rek(n)
    f = silnia_for(n)
    w = silnia_while(n)
    print(f"{n}! = {r:6}  "
          f"{'✓' if r==f==w else '✗'}")

# Tabela silni
print("\nTabela silni:")
for n in range(11):
    print(f"{n:2}! = {silnia_for(n):10}")

# Rekurencyjna — prosta (wolna dla dużych n)
def fib_rek(n):
    if n <= 1:
        return n
    return fib_rek(n-1) + fib_rek(n-2)

# Iteracyjna — szybka, O(n)
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

# Z memoizacją — słownik wyników
def fib_memo(n, pamiec={}):
    if n in pamiec:
        return pamiec[n]
    if n <= 1:
        return n
    pamiec[n] = fib_memo(n-1) + fib_memo(n-2)
    return pamiec[n]

# Wypisanie ciągu
def fib_ciag(ile):
    a, b = 0, 1
    for _ in range(ile):
        print(a, end=" ")
        a, b = b, a + b
    print()

print("Ciąg Fibonacciego (15 wyrazów):")
fib_ciag(15)
# 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377

print(f"\nfib(10)  = {fib_iter(10)}")    # 55
print(f"fib(30)  = {fib_iter(30)}")    # 832040
print(f"fib(100) = {fib_memo(100)}")   # ogromna liczba!

# Potęgowanie — O(n)
def potega(x, n):
    if n == 0:
        return 1
    return x * potega(x, n - 1)

# Szybkie potęgowanie — O(log n)
def potega_szybka(x, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        p = potega_szybka(x, n // 2)
        return p * p
    return x * potega_szybka(x, n - 1)

print(potega_szybka(2, 10))   # 1024

# Suma cyfr
def suma_cyfr(n):
    if n < 10:
        return n
    return n % 10 + suma_cyfr(n // 10)

print(suma_cyfr(12345))   # 15

# Odwracanie stringa
def odwroc(s):
    if len(s) <= 1:
        return s
    return odwroc(s[1:]) + s[0]

print(odwroc("Python"))   # nohtyP

# NWD rekurencyjnie
def nwd(a, b):
    if b == 0:
        return a
    return nwd(b, a % b)

print(nwd(48, 18))   # 6

# O(1) — stały czas
def pierwszy(lista):
    return lista[0]

# O(n) — jedna pętla
def suma(lista):
    wynik = 0
    for x in lista:       # n iteracji
        wynik += x
    return wynik

# O(n²) — dwie zagnieżdżone pętle
def wszystkie_pary(lista):
    pary = []
    for i in range(len(lista)):         # n razy
        for j in range(i+1, len(lista)):  # ~n/2 razy
            pary.append((lista[i], lista[j]))
    return pary   # łącznie: n*(n-1)/2 = O(n²)

# O(log n) — dzielenie zakresu na pół
def binarne(lista, x):
    l, p = 0, len(lista) - 1
    while l <= p:          # log2(n) iteracji
        s = (l + p) // 2
        if lista[s] == x: return s
        elif lista[s] < x: l = s + 1
        else: p = s - 1
    return -1

# O(n log n) — sortowanie z podziałem
def merge_sort(lista):
    if len(lista) <= 1:
        return lista
    srod  = len(lista) // 2
    lewo  = merge_sort(lista[:srod])    # log n poziomów
    prawo = merge_sort(lista[srod:])    # każdy poziom: O(n)
    return scal(lewo, prawo)

def scal(a, b):
    wynik = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            wynik.append(a[i]); i += 1
        else:
            wynik.append(b[j]); j += 1
    return wynik + a[i:] + b[j:]

import time
from functools import lru_cache

# Bez memoizacji — bardzo wolne dla dużych n
def fib_wolny(n):
    if n <= 1:
        return n
    return fib_wolny(n-1) + fib_wolny(n-2)

# Z lru_cache — bardzo szybkie
@lru_cache(maxsize=None)
def fib_szybki(n):
    if n <= 1:
        return n
    return fib_szybki(n-1) + fib_szybki(n-2)

# Ręczna memoizacja — słownik
cache = {}
def fib_cache(n):
    if n in cache:
        return cache[n]
    if n <= 1:
        return n
    cache[n] = fib_cache(n-1) + fib_cache(n-2)
    return cache[n]

# Porównanie czasu
n = 35

start = time.time()
print(f"fib_wolny({n})  = {fib_wolny(n)}")
print(f"Czas: {time.time()-start:.3f}s")

start = time.time()
print(f"fib_szybki({n}) = {fib_szybki(n)}")
print(f"Czas: {time.time()-start:.6f}s")

# fib_szybki działa błyskawicznie nawet dla n=500
print(f"fib_szybki(100) = {fib_szybki(100)}")