Algorytmy — Python

Po co się tego uczymy?

Uczeń ma dostać algorytm w małych porcjach: nazwa, zastosowanie, sposób działania i kod. Dzięki temu materiał nadaje się do samodzielnej nauki, a nie tylko do kopiowania.

Teoria

Algorytmy poniżej są ułożone w osobnych kartach. Każda karta wyjaśnia problem prostym językiem, pokazuje kroki działania i daje krótki przykład kodu z polskimi nazwami zmiennych.

Przykład z życia

Ta wersja jest przygotowana dla języka Python. Każdy algorytm ma osobną kartę: nazwę po polsku, proste wyjaśnienie, kroki działania i krótki kod z polskimi nazwami zmiennych.

Ucz się aktywnie: najpierw przeczytaj opis, potem przejdź kod linijka po linijce, a na końcu zmień dane wejściowe i sprawdź wynik.

Badanie podzielności i operator modulo

liczbymod

Modulo zwraca resztę z dzielenia. Jeżeli reszta z dzielenia przez dzielnik wynosi 0, liczba jest przez niego podzielna.

oblicz resztę z dzielenia
porównaj resztę z zerem
zwróć odpowiedź logiczną

def czy_podzielna(liczba, dzielnik):
    return dzielnik != 0 and liczba % dzielnik == 0

print(czy_podzielna(24, 6))

# Przykład użycia
print(czy_podzielna(24, 6))

Przykład uruchomienia: print(czy_podzielna(24, 6))

NWD — algorytm Euklidesa przez odejmowanie

liczbyNWD

Największy wspólny dzielnik nie zmienia się, gdy od większej liczby odejmujemy mniejszą. Powtarzamy to, aż obie liczby będą równe.

porównaj dwie liczby
od większej odejmij mniejszą
zatrzymaj się, gdy liczby są równe

def nwd_odejmowanie(a, b):
    a, b = abs(a), abs(b)
    while a != b:
        if a > b:
            a -= b
        else:
            b -= a
    return a

# Przykład użycia
print(nwd_odejmowanie(48, 18))

Przykład uruchomienia: print(nwd_odejmowanie(48, 18))

NWD modulo i NWW przez NWD

liczbyNWDNWW

Wersja modulo jest szybsza: zamiast odejmować wiele razy, od razu bierzemy resztę z dzielenia. NWW liczymy ze wzoru: a razy b podzielone przez NWD.

zamień parę (a, b) na (b, a % b)
powtarzaj, aż b będzie zerem
NWW policz ze wzoru

def nwd(a, b):
    while b != 0:
        a, b = b, a % b
    return abs(a)

def nww(a, b):
    return abs(a * b) // nwd(a, b)

# Przykład użycia
print(nwd(48, 18)); print(nww(12, 18))

Przykład uruchomienia: print(nwd(48, 18)); print(nww(12, 18))

Liczba pierwsza i rozkład na czynniki

liczbypierwsze

Liczba pierwsza ma dokładnie dwa dzielniki: 1 i samą siebie. Wystarczy sprawdzać dzielniki do pierwiastka z liczby, bo większe dzielniki miałyby parę mniejszą od pierwiastka.

odrzuć liczby mniejsze od 2
sprawdzaj dzielniki od 2 do √n
przy rozkładzie dziel przez znaleziony czynnik tak długo, jak się da

def czy_pierwsza(liczba):
    if liczba < 2: return False
    dzielnik = 2
    while dzielnik * dzielnik <= liczba:
        if liczba % dzielnik == 0: return False
        dzielnik += 1
    return True

# Przykład użycia
print(czy_pierwsza(29))

Przykład uruchomienia: print(czy_pierwsza(29))

Sito Eratostenesa

liczbypierwsze

Sito tworzy listę kandydatów na liczby pierwsze i wykreśla wielokrotności kolejnych liczb pierwszych. To szybki sposób na wszystkie liczby pierwsze do n.

załóż, że liczby od 2 są pierwsze
dla kolejnej niewykreślonej liczby wykreśl jej wielokrotności
zostaw niewykreślone wartości

def sito(granica):
    pierwsza = [True] * (granica + 1)
    pierwsza[0:2] = [False, False]
    for liczba in range(2, int(granica ** 0.5) + 1):
        if pierwsza[liczba]:
            for wielokrotnosc in range(liczba * liczba, granica + 1, liczba):
                pierwsza[wielokrotnosc] = False
    return [i for i in range(granica + 1) if pierwsza[i]]

# Przykład użycia
print(sito(30))

Przykład uruchomienia: print(sito(30))

Szybkie potęgowanie

liczbydziel i zwyciężaj

Zamiast mnożyć podstawę tyle razy, ile wynosi wykładnik, rozbijamy wykładnik na połowy. Gdy wykładnik jest nieparzysty, dokładamy jedną podstawę do wyniku.

jeśli wykładnik jest nieparzysty, pomnóż wynik przez podstawę
podstawę podnieś do kwadratu
wykładnik podziel całkowicie przez 2

def szybka_potega(podstawa, wykladnik):
    wynik = 1
    while wykladnik > 0:
        if wykladnik % 2 == 1:
            wynik *= podstawa
        podstawa *= podstawa
        wykladnik //= 2
    return wynik

# Przykład użycia
print(szybka_potega(2, 10))

Przykład uruchomienia: print(szybka_potega(2, 10))

Schemat Hornera

liczbywielomiany

Horner pozwala obliczyć wartość wielomianu bez osobnego liczenia kolejnych potęg. Wynik budujemy od lewej: mnożymy przez x i dodajemy następny współczynnik.

zacznij od wyniku 0
dla każdego współczynnika wykonaj: wynik = wynik * x + współczynnik
po ostatnim współczynniku masz wartość wielomianu

def horner(wspolczynniki, x):
    wynik = 0
    for wspolczynnik in wspolczynniki:
        wynik = wynik * x + wspolczynnik
    return wynik

# Przykład użycia
print(horner([2, 3, 1], 2))

Przykład uruchomienia: print(horner([2, 3, 1], 2))

Fibonacci iteracyjnie i rekurencyjnie

rekurencjaiteracja

Ciąg Fibonacciego zaczyna się od 0 i 1, a każdy następny wyraz jest sumą dwóch poprzednich. Wersja iteracyjna jest szybka, rekurencyjna dobrze pokazuje ideę, ale dla dużych n jest wolna.

iteracyjnie trzymaj dwie ostatnie wartości
rekurencyjnie użyj wzoru F(n)=F(n-1)+F(n-2)
pamiętaj o warunku stopu dla 0 i 1

def fib_iteracyjnie(n):
    poprzedni, aktualny = 0, 1
    for _ in range(n):
        poprzedni, aktualny = aktualny, poprzedni + aktualny
    return poprzedni

def fib_rekurencyjnie(n):
    return n if n < 2 else fib_rekurencyjnie(n-1) + fib_rekurencyjnie(n-2)

# Przykład użycia
print(fib_iteracyjnie(10)); print(fib_rekurencyjnie(10))

Przykład uruchomienia: print(fib_iteracyjnie(10)); print(fib_rekurencyjnie(10))

Silnia i wydawanie reszty zachłannie

liczbyzachłanny

Silnia mnoży kolejne liczby od 1 do n. Wydawanie reszty zachłannie zawsze wybiera największy nominał, który mieści się w pozostałej kwocie.

silnia: mnoż wynik przez kolejne i
reszta: wybierz największy możliwy nominał
odejmij jego wielokrotność od kwoty

def silnia(n):
    wynik = 1
    for liczba in range(2, n + 1):
        wynik *= liczba
    return wynik

def wydaj_reszte(kwota, nominaly=[500,200,100,50,20,10,5,2,1]):
    wynik = []
    for nominal in nominaly:
        ile = kwota // nominal
        if ile > 0:
            wynik.append((nominal, ile))
            kwota %= nominal
    return wynik

# Przykład użycia
print(silnia(5)); print(wydaj_reszte(289))

Przykład uruchomienia: print(silnia(5)); print(wydaj_reszte(289))

Sortowanie bąbelkowe

sortowanieO(n²)

Porównujemy sąsiednie elementy i zamieniamy je miejscami, jeśli są w złej kolejności. Największe wartości „wypływają” na koniec tablicy.

przechodź po parach sąsiadów
zamień, jeśli lewy jest większy od prawego
po każdej rundzie ostatni element jest już na miejscu

def sortowanie_babelkowe(tablica):
    tablica = tablica[:]
    for koniec in range(len(tablica) - 1, 0, -1):
        for i in range(koniec):
            if tablica[i] > tablica[i + 1]:
                tablica[i], tablica[i + 1] = tablica[i + 1], tablica[i]
    return tablica

# Przykład użycia
print(sortowanie_babelkowe([5, 2, 8, 1]))

Przykład uruchomienia: print(sortowanie_babelkowe([5, 2, 8, 1]))

Sortowanie przez wybór

sortowanieO(n²)

W każdej rundzie szukamy najmniejszego elementu w nieposortowanej części i przenosimy go na początek tej części.

ustaw pozycję początku nieposortowanej części
znajdź indeks minimum
zamień minimum z początkiem

def sortowanie_wybor(tablica):
    tablica = tablica[:]
    for poczatek in range(len(tablica)):
        minimum = min(range(poczatek, len(tablica)), key=lambda i: tablica[i])
        tablica[poczatek], tablica[minimum] = tablica[minimum], tablica[poczatek]
    return tablica

# Przykład użycia
print(sortowanie_wybor([5, 2, 8, 1]))

Przykład uruchomienia: print(sortowanie_wybor([5, 2, 8, 1]))

Sortowanie przez wstawianie

sortowanieO(n²)

Bierzemy kolejny element i wstawiamy go w odpowiednie miejsce w już posortowanej lewej części tablicy. Działa podobnie do układania kart w ręce.

weź element z nieposortowanej części
przesuwaj większe elementy w prawo
wstaw element w powstałe miejsce

def sortowanie_wstawianie(tablica):
    tablica = tablica[:]
    for i in range(1, len(tablica)):
        element = tablica[i]
        j = i - 1
        while j >= 0 and tablica[j] > element:
            tablica[j + 1] = tablica[j]; j -= 1
        tablica[j + 1] = element
    return tablica

# Przykład użycia
print(sortowanie_wstawianie([5, 2, 8, 1]))

Przykład uruchomienia: print(sortowanie_wstawianie([5, 2, 8, 1]))

Sortowanie przez scalanie

sortowaniedziel i zwyciężaj

Dzielimy tablicę na połowy, sortujemy połówki, a potem scalamy dwie posortowane listy w jedną. To klasyczne „dziel i zwyciężaj”.

podziel tablicę na dwie części
posortuj każdą część rekurencyjnie
scal dwie posortowane części

def sortowanie_scalanie(tablica):
    if len(tablica) <= 1: return tablica
    srodek = len(tablica) // 2
    lewa = sortowanie_scalanie(tablica[:srodek])
    prawa = sortowanie_scalanie(tablica[srodek:])
    wynik = []
    while lewa and prawa:
        wynik.append((lewa if lewa[0] <= prawa[0] else prawa).pop(0))
    return wynik + lewa + prawa

# Przykład użycia
print(sortowanie_scalanie([5, 2, 8, 1]))

Przykład uruchomienia: print(sortowanie_scalanie([5, 2, 8, 1]))

Quicksort — sortowanie szybkie

sortowaniedziel i zwyciężaj

Wybieramy element osiowy, dzielimy dane na mniejsze, równe i większe od niego, a potem sortujemy części rekurencyjnie.

wybierz pivot
podziel elementy względem pivota
posortuj rekurencyjnie lewą i prawą część

def quicksort(tablica):
    if len(tablica) <= 1: return tablica
    pivot = tablica[len(tablica) // 2]
    mniejsze = [x for x in tablica if x < pivot]
    rowne = [x for x in tablica if x == pivot]
    wieksze = [x for x in tablica if x > pivot]
    return quicksort(mniejsze) + rowne + quicksort(wieksze)

# Przykład użycia
print(quicksort([5, 2, 8, 1]))

Przykład uruchomienia: print(quicksort([5, 2, 8, 1]))

Sortowanie przez zliczanie

sortowaniekubełkowe

Działa dobrze, gdy wartości są liczbami całkowitymi z niedużego zakresu. Zliczamy, ile razy występuje każda wartość, a potem odtwarzamy posortowaną tablicę.

utwórz tablicę liczników
zwiększ licznik dla każdej wartości
wypisz wartości tyle razy, ile wynosi licznik

def sortowanie_zliczanie(tablica, maksimum):
    liczniki = [0] * (maksimum + 1)
    for liczba in tablica:
        liczniki[liczba] += 1
    return [wartosc for wartosc, ile in enumerate(liczniki) for _ in range(ile)]

# Przykład użycia
print(sortowanie_zliczanie([3, 1, 2, 3, 0], 3))

Przykład uruchomienia: print(sortowanie_zliczanie([3, 1, 2, 3, 0], 3))

Wyszukiwanie liniowe i binarne

wyszukiwanie

Liniowe sprawdza element po elemencie i działa zawsze. Binarne działa tylko na danych posortowanych, ale za każdym krokiem odrzuca połowę zakresu.

liniowe: idź od początku do końca
binarne: sprawdź środek
przesuń lewy lub prawy koniec zakresu

def szukaj_liniowo(tablica, szukana):
    for indeks, wartosc in enumerate(tablica):
        if wartosc == szukana: return indeks
    return -1

def szukaj_binarnie(tablica, szukana):
    lewy, prawy = 0, len(tablica) - 1
    while lewy <= prawy:
        srodek = (lewy + prawy) // 2
        if tablica[srodek] == szukana: return srodek
        if tablica[srodek] < szukana: lewy = srodek + 1
        else: prawy = srodek - 1
    return -1

# Przykład użycia
print(szukaj_liniowo([4, 7, 9], 7)); print(szukaj_binarnie([1, 4, 7, 9], 7))

Przykład uruchomienia: print(szukaj_liniowo([4, 7, 9], 7)); print(szukaj_binarnie([1, 4, 7, 9], 7))

Minimum, maksimum i lider

wyszukiwanielider

Minimum i maksimum znajdujemy jednym przejściem po tablicy. Lider to wartość, która występuje częściej niż połowa elementów; algorytm Boyera-Moore’a wybiera kandydata i potem go sprawdza.

przechodź po danych raz
aktualizuj minimum i maksimum
dla lidera kasuj pary różnych wartości

def minimum_maksimum(tablica):
    return min(tablica), max(tablica)

def lider(tablica):
    kandydat, glosy = None, 0
    for liczba in tablica:
        if glosy == 0: kandydat, glosy = liczba, 1
        elif liczba == kandydat: glosy += 1
        else: glosy -= 1
    return kandydat if tablica.count(kandydat) > len(tablica)//2 else None

# Przykład użycia
print(minimum_maksimum([3, 8, 1])); print(lider([2, 2, 1, 2]))

Przykład uruchomienia: print(minimum_maksimum([3, 8, 1])); print(lider([2, 2, 1, 2]))

Palindrom i zliczanie znaków

tekst

Palindrom czyta się tak samo od lewej i od prawej. Zliczanie znaków polega na przejściu po tekście i zwiększaniu licznika dla każdego znaku.

porównaj tekst z jego odwróceniem
dla zliczania użyj słownika/mapy
zwiększ licznik znaku

def czy_palindrom(tekst):
    tekst = tekst.lower().replace(' ', '')
    return tekst == tekst[::-1]

def zlicz_znaki(tekst):
    wynik = {}
    for znak in tekst:
        wynik[znak] = wynik.get(znak, 0) + 1
    return wynik

# Przykład użycia
print(czy_palindrom('kajak')); print(zlicz_znaki('ala'))

Przykład uruchomienia: print(czy_palindrom('kajak')); print(zlicz_znaki('ala'))

Wyszukiwanie wzorca w tekście

tekst

W wersji naiwnej przykładamy wzorzec do każdego miejsca w tekście i sprawdzamy zgodność znak po znaku. KMP i Rabin-Karp robią to szybciej, ale idea nadal zaczyna się od pojęcia wzorca.

wybierz pozycję startową
porównaj fragment tekstu ze wzorcem
zapisz pozycję, jeśli pasuje

def znajdz_wzorzec(tekst, wzorzec):
    pozycje = []
    for i in range(len(tekst) - len(wzorzec) + 1):
        if tekst[i:i+len(wzorzec)] == wzorzec:
            pozycje.append(i)
    return pozycje

# Przykład użycia
print(znajdz_wzorzec('abrakadabra', 'abra'))

Przykład uruchomienia: print(znajdz_wzorzec('abrakadabra', 'abra'))

Porządkowanie leksykograficzne i szyfry

tekstszyfry

Porządkowanie leksykograficzne to sortowanie tekstów jak w słowniku. Szyfr Cezara przesuwa litery, GADERYPOLUKI podmienia pary liter, a RSA pokazuje ideę klucza jawnego i prywatnego.

dla sortowania porównuj napisy
dla Cezara przesuń literę w alfabecie
dla RSA pamiętaj: to demonstracja matematyczna na małych liczbach

def cezar(tekst, przesuniecie):
    wynik = ''
    for znak in tekst:
        if znak.isalpha():
            baza = ord('A') if znak.isupper() else ord('a')
            wynik += chr((ord(znak) - baza + przesuniecie) % 26 + baza)
        else:
            wynik += znak
    return wynik

def rsa_demo(wiadomosc, e=7, n=187):
    return pow(wiadomosc, e, n)

# Przykład użycia
print(cezar('Ala ma kota', 3)); print(rsa_demo(12))

Przykład uruchomienia: print(cezar('Ala ma kota', 3)); print(rsa_demo(12))

Metoda bisekcji

numeryczne

Bisekcja szuka miejsca zerowego funkcji w przedziale. Jeśli funkcja zmienia znak między końcami przedziału, dzielimy przedział na pół i zostawiamy tę połowę, gdzie nadal jest zmiana znaku.

policz środek przedziału
sprawdź znak funkcji na końcu i w środku
zawęź przedział

def bisekcja(funkcja, lewy, prawy, dokladnosc=1e-6):
    while prawy - lewy > dokladnosc:
        srodek = (lewy + prawy) / 2
        if funkcja(lewy) * funkcja(srodek) <= 0:
            prawy = srodek
        else:
            lewy = srodek
    return (lewy + prawy) / 2

# Przykład użycia
print(bisekcja(lambda x: x*x - 2, 0, 2))

Przykład uruchomienia: print(bisekcja(lambda x: x*x - 2, 0, 2))

Pole pod wykresem i metoda Newtona

numeryczne

Pole pod wykresem można przybliżyć prostokątami albo trapezami. Metoda Newtona/Herona poprawia przybliżenie pierwiastka, uśredniając wynik z ilorazem liczby przez wynik.

podziel przedział na małe części
zsumuj pola prostokątów lub trapezów
dla pierwiastka poprawiaj przybliżenie aż do wymaganej dokładności

def prostokaty(f, a, b, n):
    szerokosc = (b - a) / n
    return sum(f(a + i * szerokosc) * szerokosc for i in range(n))

def pierwiastek_newtona(liczba):
    wynik = liczba
    while abs(wynik * wynik - liczba) > 1e-6:
        wynik = (wynik + liczba / wynik) / 2
    return wynik

# Przykład użycia
print(prostokaty(lambda x: x*x, 0, 1, 100)); print(pierwiastek_newtona(9))

Przykład uruchomienia: print(prostokaty(lambda x: x*x, 0, 1, 100)); print(pierwiastek_newtona(9))

Rekurencja — wieże Hanoi

rekurencja

Rekurencja oznacza, że funkcja wywołuje samą siebie dla mniejszego problemu. W Hanoi najpierw przenosimy n-1 krążków, potem największy, potem znów n-1.

ustal warunek stopu
rozwiąż mniejszy problem
wykonaj jeden ruch główny
rozwiąż drugi mniejszy problem

def hanoi(ile, zrodlo='A', pomoc='B', cel='C'):
    if ile == 0: return []
    return hanoi(ile-1, zrodlo, cel, pomoc) + [(zrodlo, cel)] + hanoi(ile-1, pomoc, zrodlo, cel)

# Przykład użycia
print(hanoi(3))

Przykład uruchomienia: print(hanoi(3))

Algorytm zachłanny — plecak ułamkowy

zachłanny

Algorytm zachłanny podejmuje lokalnie najlepszą decyzję. W plecaku ułamkowym bierzemy przedmioty według największej wartości na jednostkę wagi.

policz wartość na kilogram
posortuj malejąco
bierz cały przedmiot albo jego część

def plecak_ulamkowy(przedmioty, pojemnosc):
    wartosc = 0
    for cena, waga in sorted(przedmioty, key=lambda x: x[0]/x[1], reverse=True):
        biore = min(waga, pojemnosc)
        wartosc += biore * cena / waga
        pojemnosc -= biore
        if pojemnosc == 0: break
    return wartosc

# Przykład użycia
print(plecak_ulamkowy([(60, 10), (100, 20), (120, 30)], 50))

Przykład uruchomienia: print(plecak_ulamkowy([(60, 10), (100, 20), (120, 30)], 50))

Programowanie dynamiczne — monety i LCS

dynamiczne

Programowanie dynamiczne zapamiętuje wyniki mniejszych podproblemów. Dzięki temu nie liczymy wielokrotnie tego samego, jak w naiwnej rekurencji.

zdefiniuj małe podproblemy
zapisuj ich wyniki w tablicy
buduj odpowiedź od prostych przypadków do trudniejszych

def najmniej_monet(kwota, monety):
    dp = [0] + [10**9] * kwota
    for suma in range(1, kwota + 1):
        dp[suma] = min((dp[suma-m] + 1 for m in monety if m <= suma), default=10**9)
    return dp[kwota]

def lcs(a, b):
    dp = [[0]*(len(b)+1) for _ in range(len(a)+1)]
    for i in range(1, len(a)+1):
        for j in range(1, len(b)+1):
            dp[i][j] = dp[i-1][j-1]+1 if a[i-1] == b[j-1] else max(dp[i-1][j], dp[i][j-1])
    return dp[-1][-1]

# Przykład użycia
print(najmniej_monet(11, [1, 5, 7])); print(lcs('informatyka', 'format'))

Przykład uruchomienia: print(najmniej_monet(11, [1, 5, 7])); print(lcs('informatyka', 'format'))

Backtracking — hetmany i labirynt

backtracking

Backtracking próbuje kolejnych decyzji, a gdy ścieżka prowadzi do błędu, cofa się i sprawdza następną możliwość. To metoda „spróbuj, sprawdź, cofnij”.

wybierz możliwy ruch
sprawdź, czy jest poprawny
idź głębiej rekurencyjnie
jeśli się nie uda, cofnij wybór

def hetmany(n):
    rozwiazania, kolumny = [], []
    def poprawne(wiersz, kolumna):
        return all(kolumna != k and abs(kolumna-k) != wiersz-i for i, k in enumerate(kolumny))
    def szukaj(wiersz=0):
        if wiersz == n: rozwiazania.append(kolumny[:]); return
        for kolumna in range(n):
            if poprawne(wiersz, kolumna):
                kolumny.append(kolumna); szukaj(wiersz+1); kolumny.pop()
    szukaj(); return rozwiazania

# Przykład użycia
print(hetmany(4))

Przykład uruchomienia: print(hetmany(4))

Struktury danych: tablica, stos, kolejka, drzewo, kopiec, graf

struktury danych

Struktura danych decyduje, jak przechowujesz informacje. Tablica daje szybki dostęp po indeksie, stos działa LIFO, kolejka FIFO, kopiec szybko zwraca minimum/maksimum, a graf opisuje połączenia.

dobierz strukturę do operacji
stos: ostatni wchodzi, pierwszy wychodzi
kolejka: pierwszy wchodzi, pierwszy wychodzi
graf zapisz jako listę sąsiedztwa albo macierz

from collections import deque

stos = []
stos.append('A'); stos.append('B')
ostatni = stos.pop()

kolejka = deque(['A', 'B'])
pierwszy = kolejka.popleft()

graf = {'A': ['B', 'C'], 'B': ['A'], 'C': ['A']}

# Przykład użycia
print(stos, list(kolejka), graf)

Przykład uruchomienia: print(stos, list(kolejka), graf)

BFS i DFS

grafy

BFS przeszukuje graf wszerz, poziomami, używając kolejki. DFS idzie jak najgłębiej, używając rekurencji albo stosu.

zaznacz start jako odwiedzony
BFS: zdejmuj z kolejki
DFS: odwiedzaj rekurencyjnie sąsiadów

from collections import deque

def bfs(graf, start):
    odwiedzone, kolejka = {start}, deque([start])
    while kolejka:
        wierzcholek = kolejka.popleft()
        for sasiad in graf[wierzcholek]:
            if sasiad not in odwiedzone:
                odwiedzone.add(sasiad); kolejka.append(sasiad)
    return odwiedzone

# Przykład użycia
print(bfs({'A': ['B', 'C'], 'B': [], 'C': []}, 'A'))

Przykład uruchomienia: print(bfs({'A': ['B', 'C'], 'B': [], 'C': []}, 'A'))

Dijkstra — najkrótsza ścieżka

grafyścieżki

Dijkstra znajduje najkrótsze odległości od startu w grafie z nieujemnymi wagami. Zawsze wybiera jeszcze nieprzetworzony wierzchołek o najmniejszym znanym koszcie.

ustaw odległość startu na 0
wybierz najbliższy wierzchołek z kolejki priorytetowej
popraw odległości sąsiadów

import heapq

def dijkstra(graf, start):
    odleglosc = {start: 0}
    kolejka = [(0, start)]
    while kolejka:
        koszt, v = heapq.heappop(kolejka)
        for sasiad, waga in graf[v]:
            nowy = koszt + waga
            if nowy < odleglosc.get(sasiad, 10**9):
                odleglosc[sasiad] = nowy
                heapq.heappush(kolejka, (nowy, sasiad))
    return odleglosc

# Przykład użycia
print(dijkstra({'A': [('B', 3), ('C', 1)], 'B': [], 'C': [('B', 1)]}, 'A'))

Przykład uruchomienia: print(dijkstra({'A': [('B', 3), ('C', 1)], 'B': [], 'C': [('B', 1)]}, 'A'))

Minimalne drzewo rozpinające — Prim i Kruskal

grafyMST

Minimalne drzewo rozpinające łączy wszystkie wierzchołki najtańszym zestawem krawędzi. Prim rozbudowuje jedno drzewo, a Kruskal bierze krawędzie od najlżejszej i pilnuje, żeby nie zrobić cyklu.

Prim: zacznij od dowolnego wierzchołka
Kruskal: posortuj krawędzie rosnąco
dodawaj krawędź tylko, gdy łączy różne składowe

def kruskal(wierzcholki, krawedzie):
    rodzic = {v: v for v in wierzcholki}
    def znajdz(x):
        while rodzic[x] != x: x = rodzic[x]
        return x
    wynik = []
    for waga, a, b in sorted(krawedzie):
        ra, rb = znajdz(a), znajdz(b)
        if ra != rb:
            rodzic[ra] = rb
            wynik.append((a, b, waga))
    return wynik

# Przykład użycia
print(kruskal(['A','B','C'], [(1,'A','B'), (3,'A','C'), (2,'B','C')]))

Przykład uruchomienia: print(kruskal(['A','B','C'], [(1,'A','B'), (3,'A','C'), (2,'B','C')]))

Analiza złożoności Big-O

Big-O

Big-O mówi, jak rośnie czas lub pamięć algorytmu, gdy rośnie liczba danych. Nie mierzy sekund, tylko tempo wzrostu: O(n) rośnie liniowo, O(log n) bardzo wolno, O(n²) szybko robi się kosztowne.

policz dominującą pętlę lub rekurencję
pomijaj stałe
porównuj algorytmy dla dużych danych

tablica = [1, 2, 3]

# O(n) - jedna pętla po tablicy
for liczba in tablica:
    print(liczba)

# O(n^2) - pętla w pętli
for a in tablica:
    for b in tablica:
        print(a, b)

# Przykład użycia
tablica = [1, 2, 3]
for liczba in tablica:
    print(liczba)

Przykład uruchomienia: tablica = [1, 2, 3] for liczba in tablica: print(liczba)

Komentarz i wyjaśnienie kodu

Nie trzeba uczyć się wszystkich przykładów naraz. Najpierw wybierz algorytmy liczbowe i wyszukiwanie, potem sortowanie, a na końcu rekurencję, programowanie dynamiczne i grafy.

Ćwiczenie samodzielne

Wybierz trzy karty. Dla każdej: przepisz kod ręcznie, uruchom go dla innych danych i dopisz komentarz własnymi słowami, co robi każda ważna linia.

Zadania do pracy własnej

Wybierz 5 algorytmów i przygotuj do każdego po dwa testy danych wejściowych.
Porównaj dwa algorytmy rozwiązujące podobny problem, np. wyszukiwanie liniowe i binarne albo sortowanie bąbelkowe i szybkie.
Wybierz jeden trudniejszy algorytm: Dijkstra, Kruskal, LCS albo hetmany. Narysuj dane wejściowe i opisz działanie krok po kroku.

Typowe błędy

Uruchamianie wyszukiwania binarnego na nieposortowanej tablicy.
Brak warunku stopu w rekurencji.
Mylenie liczby wierzchołków z liczbą krawędzi przy złożoności grafów.

Nawiązanie do egzaminu zawodowego

Algorytmy wspierają programowanie konsolowe, desktopowe i mobilne w INF.04. To fundament do pisania kodu, który nie tylko działa, ale działa przewidywalnie i wydajnie.