11 — Algorytmy: etap 2

def insertion_sort(lista):
    for i in range(1, len(lista)):
        klucz = lista[i]       # element do wstawienia
        j = i - 1
        # Przesuń elementy większe od klucza w prawo
        while j >= 0 and lista[j] > klucz:
            lista[j + 1] = lista[j]
            j -= 1
        lista[j + 1] = klucz   # wstaw klucz na miejsce

# Wersja z debugiem — pokazuje każde wstawienie
def insertion_sort_debug(lista):
    for i in range(1, len(lista)):
        klucz = lista[i]
        j = i - 1
        while j >= 0 and lista[j] > klucz:
            lista[j + 1] = lista[j]
            j -= 1
        lista[j + 1] = klucz
        print(f"Wstawiam {klucz:2}: {lista}")

# Test
dane = [12, 11, 13, 5, 6]
print("Przed:", dane)
insertion_sort_debug(dane)
print("Po:   ", dane)

# Wstawiam 11: [11, 12, 13,  5,  6]
# Wstawiam 13: [11, 12, 13,  5,  6]
# Wstawiam  5: [ 5, 11, 12, 13,  6]
# Wstawiam  6: [ 5,  6, 11, 12, 13]

def wyszukiwanie_binarne(lista, szukana):
    """Zwraca indeks elementu lub -1. Lista musi być posortowana."""
    lewy   = 0
    prawy  = len(lista) - 1
    kroki  = 0

    while lewy <= prawy:
        kroki += 1
        srodek = (lewy + prawy) // 2

        if lista[srodek] == szukana:
            print(f"Znaleziono po {kroki} krokach.")
            return srodek
        elif lista[srodek] < szukana:
            lewy = srodek + 1    # szukamy w prawej połowie
        else:
            prawy = srodek - 1   # szukamy w lewej połowie

    print(f"Nie znaleziono po {kroki} krokach.")
    return -1

# Test
posortowane = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91]

idx = wyszukiwanie_binarne(posortowane, 23)
print(f"23 → indeks: {idx}")   # indeks: 5

idx = wyszukiwanie_binarne(posortowane, 50)
print(f"50 → indeks: {idx}")   # -1

# Porównanie z liniowym — dla 11 elementów:
# Liniowe max 11 porównań
# Binarne max 4 porównania (log2(11) ≈ 3.5)

def binarne_rek(lista, szukana, lewy, prawy):
    """Rekurencyjne wyszukiwanie binarne."""
    # Warunek bazowy — nie znaleziono
    if lewy > prawy:
        return -1

    srodek = (lewy + prawy) // 2

    # Warunek bazowy — znaleziono
    if lista[srodek] == szukana:
        return srodek
    # Szukaj w prawej połowie
    elif lista[srodek] < szukana:
        return binarne_rek(lista, szukana, srodek + 1, prawy)
    # Szukaj w lewej połowie
    else:
        return binarne_rek(lista, szukana, lewy, srodek - 1)

# Wygodny wrapper
def wyszukaj(lista, szukana):
    return binarne_rek(lista, szukana, 0, len(lista) - 1)

# Test
dane = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
print(wyszukaj(dane, 7))    # 3
print(wyszukaj(dane, 13))   # 6
print(wyszukaj(dane, 4))    # -1

# Wizualizacja kroków rekurencji dla szukanej=7:
# binarne_rek([1..19], 7, 0, 9)  → srodek=4, lista[4]=9 > 7
# binarne_rek([1..19], 7, 0, 3)  → srodek=1, lista[1]=3 < 7
# binarne_rek([1..19], 7, 2, 3)  → srodek=2, lista[2]=5 < 7
# binarne_rek([1..19], 7, 3, 3)  → srodek=3, lista[3]=7 == 7 ✓

# NWD — iteracyjnie (Euklides)
def nwd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# NWW ze wzoru
def nww(a, b):
    return a * b // nwd(a, b)

print(f"NWD(48, 18) = {nwd(48, 18)}")   # 6
print(f"NWW(4, 6)   = {nww(4, 6)}")     # 12

# Dzielniki liczby
def dzielniki(n):
    wynik = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            wynik.append(i)
            if i != n // i:
                wynik.append(n // i)
    return sorted(wynik)

print(dzielniki(36))  # [1, 2, 3, 4, 6, 9, 12, 18, 36]

# Rozkład na czynniki pierwsze
def czynniki_pierwsze(n):
    wynik = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            wynik.append(d)
            n //= d
        d += 1
    if n > 1:
        wynik.append(n)
    return wynik

print(czynniki_pierwsze(360))  # [2, 2, 2, 3, 3, 5]

# Palindrom — bez slice
def czy_palindrom(s):
    s = s.lower().replace(" ", "")
    n = len(s)
    for i in range(n // 2):
        if s[i] != s[n - 1 - i]:
            return False
    return True

print(czy_palindrom("kajak"))        # True
print(czy_palindrom("Kobyła ma mały bok"))  # True
print(czy_palindrom("Python"))       # False

# Anagram — przez sortowanie
def czy_anagram(s1, s2):
    s1 = s1.lower().replace(" ", "")
    s2 = s2.lower().replace(" ", "")
    return sorted(s1) == sorted(s2)

print(czy_anagram("listen", "silent"))  # True
print(czy_anagram("hello", "world"))    # False

# Zliczanie liter (bez Counter)
def zlicz_litery(tekst):
    licznik = {}
    for znak in tekst.lower():
        if znak.isalpha():
            licznik[znak] = licznik.get(znak, 0) + 1
    return dict(sorted(licznik.items()))

print(zlicz_litery("Python"))
# {'h': 1, 'n': 1, 'o': 1, 'p': 1, 't': 1, 'y': 1}

def nwd_debug(a, b):
    """NWD z wypisaniem każdego kroku."""
    krok = 0
    print(f"nwd({a}, {b})")
    while b != 0:
        krok += 1
        r    = a % b
        print(f"  krok {krok}: nwd({b}, {a}%{b}={r})")
        a, b = b, r
    print(f"  wynik: {a}")
    return a

nwd_debug(48, 18)
# nwd(48, 18)
#   krok 1: nwd(18, 48%18=12)
#   krok 2: nwd(12, 18%12=6)
#   krok 3: nwd(6,  12%6=0)
#   wynik: 6

# NWD wielu liczb — przez reduce
from functools import reduce
def nwd_wielu(*liczby):
    return reduce(nwd, liczby)

print(nwd_wielu(12, 18, 24))    # 6
print(nwd_wielu(100, 75, 50))   # 25

# NWW wielu liczb
def nww_wielu(*liczby):
    return reduce(nww, liczby)

print(nww_wielu(4, 6, 10))      # 60