Algorytmy, które musisz znać (2026)

Algorytmy na maturę z informatyki 2026 – Kompendium: NWD, Sito, Horner

Algorytmiczne 'Must-Have' na maturze 2026:

✓Teoria liczb: Liczby pierwsze (Sito Eratostenesa), rozkład na czynniki (faktoryzacja), NWD i NWW.
✓Systemy liczbowe: Konwersja dowolny system -> dziesiętny (Schemat Hornera).
✓Ciągi: Ciąg Fibonacciego (iteracyjnie vs rekurencyjnie).
✓Analiza: Umiejętność określenia złożoności obliczeniowej (np. O(n) vs O(log n)).

Dlaczego algorytmy to klucz do wyniku 90%+?

Na maturze z informatyki zadania algorytmiczne pojawiają się zarówno w części teoretycznej (analiza pseudokodu, uzupełnianie luk), jak i praktycznej (plik z milionem liczb do przetworzenia). Nie wystarczy, że kod 'działa'. Musi działać szybko. Egzaminatorzy CKE premiują rozwiązania optymalne – dlatego zamiast sprawdzać dzielniki do n, musisz wiedzieć, kiedy przerwać pętlę przy pierwiastku z n. W tym kompendium przejdziemy przez najważniejsze algorytmy w języku Python.

1. Złożoność obliczeniowa – podstawa teorii

Zanim zaczniesz pisać kod, musisz wiedzieć, jak szybki on jest. Na maturze często pada pytanie: „Jaka jest złożoność tego algorytmu?”. Oto ściąga:

Typowe klasy złożoności na maturze

Złożoność	Nazwa	Przykład algorytmu
O(1)	Stała	Dostęp do elementu tablicy: tab[5].
O(log n)	Logarytmiczna	Algorytm Euklidesa, Wyszukiwanie binarne.
O(n)	Liniowa	Znalezienie minimum w nieposortowanej tablicy.
O(n log n)	Liniowo-logarytmiczna	Dobre sortowanie (Merge Sort, Quick Sort).
O(n²)	Kwadratowa	Sortowanie bąbelkowe, sprawdzanie par każdy z każdym.

Pamiętaj: Jeśli masz do przetworzenia plik z 100 000 wierszy, algorytm O(n²) prawdopodobnie przekroczy czas (Time Limit Exceeded).

2. Liczby pierwsze: Metoda naiwna vs Sito Eratostenesa

Badanie pierwszości to klasyk. Mamy dwie sytuacje: sprawdzasz jedną liczbę lub szukasz wszystkich liczb pierwszych w zakresie.

A. Sprawdzanie jednej liczby (Optymalne)

def is_prime(n):
    if n < 2:
        return False
    # Sprawdzamy dzielniki tylko do pierwiastka z n
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

Kluczowa optymalizacja: `range(2, int(n**0.5) + 1)`. Złożoność wynosi O(√n). Bez tego, dla dużych liczb, program będzie działał za wolno.

B. Sito Eratostenesa (Generowanie zakresu)

def sieve(n):
    primes = [True] * (n + 1)
    primes[0] = primes[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if primes[i]:
            # Wykreślamy wielokrotności liczby i
            for j in range(i * i, n + 1, i):
                primes[j] = False
    return [x for x in range(n + 1) if primes[x]]

print(sieve(30)) # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Jeśli zadanie brzmi 'Znajdź wszystkie liczby pierwsze mniejsze od miliona', Sito jest jedynym słusznym wyborem. Jest znacznie szybsze niż sprawdzanie `is_prime` dla każdej liczby z osobna.

3. NWD i NWW – Algorytm Euklidesa

Największy Wspólny Dzielnik (NWD) przydaje się przy skracaniu ułamków i zadaniach z teorią liczb. Algorytm Euklidesa jest jednym z najstarszych i najszybszych algorytmów świata.

Algorytm Euklidesa (Wersja iteracyjna)

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

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

Złożoność logarytmiczna O(log(min(a, b))). Wersja z modulo (`%`) jest znacznie szybsza niż wersja z odejmowaniem. Pamiętaj o wzorze na NWW – łączy się on bezpośrednio z NWD.

4. Rozkład na czynniki pierwsze (Faktoryzacja)

Częste zadanie maturalne: 'Dla każdej liczby z pliku wypisz jej czynniki pierwsze'. Tutaj również kluczowa jest pętla do pierwiastka z liczby.

Faktoryzacja liczby n

def get_prime_factors(n):
    factors = []
    d = 2
    temp = n
    while d * d <= temp:
        while temp % d == 0:
            factors.append(d)
            temp //= d
        d += 1
    if temp > 1:
        factors.append(temp)
    return factors

print(get_prime_factors(60)) # Wynik: [2, 2, 3, 5]

Algorytm dzieli liczbę przez najmniejszy możliwy dzielnik (2, potem 3, itd.) tak długo, jak się da. Warunek `if temp > 1` na końcu wyłapuje ostatni czynnik pierwszy, jeśli liczba nie zredukowała się do 1.

5. Systemy liczbowe i Schemat Hornera

Konwersja z systemu binarnego (lub dowolnego innego) na dziesiętny może być wykonana klasycznie (sumując potęgi) lub sprytniej – Schematem Hornera. CKE uwielbia Schemat Hornera w części teoretycznej.

Schemat Hornera (System X -> Dziesiętny)

def horner(liczba_str, system):
    wynik = 0
    for cyfra in liczba_str:
        wynik = wynik * system + int(cyfra)
    return wynik

# Binarny na dziesiętny
print(horner("1101", 2))  # 13
# Ósemkowy na dziesiętny
print(horner("17", 8))    # 15

Zamiast potęgować `cyfra * podstawa^k`, Horner wykorzystuje mnożenie i dodawanie: `((1*2 + 1)*2 + 0)*2 + 1`. Jest to bardziej efektywne i często wymagane w specyfikacji zadania.

6. Ciąg Fibonacciego – Pułapka rekurencji

Wyznaczanie n-tego wyrazu ciągu Fibonacciego to idealny przykład na pokazanie różnicy między rekurencją a iteracją. Na maturze unikaj czystej rekurencji dla dużych n!

Fibonacci Iteracyjnie (Bezpieczny)

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łożoność liniowa O(n). Działa błyskawicznie nawet dla n=1000.

Fibonacci Rekurencyjnie (Ryzykowny)

def fib_rec(n):
    if n <= 1: return n
    return fib_rec(n-1) + fib_rec(n-2)

Złożoność wykładnicza O(2^n). Dla n=40 program może działać kilka sekund, dla n=50 – 'zawiśnie'. Używaj tylko dla bardzo małych n lub z zapamiętywaniem (memoization).

Najczęściej zadawane pytania (FAQ) - Algorytmika

Wątpliwości przed egzaminem? Odpowiadamy.

Czy muszę pisać własną funkcję konwersji systemów, czy mogę użyć `int(x, base)`?

W części praktycznej (programowanie) MOŻESZ używać funkcji wbudowanych jak `int('101', 2)`, `bin()`, `hex()`. Oszczędzasz czas i minimalizujesz ryzyko błędu. Własne algorytmy (Horner) są wymagane głównie w części teoretycznej (zapisywanie algorytmu w pseudokodzie) lub gdy system jest nietypowy (np. podstawa ujemna).

Jaką metodę sortowania wybrać na maturze?

W Pythonie używaj wbudowanej metody `.sort()` lub funkcji `sorted()`. Działają one w oparciu o Timsort (O(n log n)) i są niezwykle szybkie. Nie ma sensu pisać ręcznie QuickSorta, chyba że treść zadania wyraźnie tego wymaga (bardzo rzadkie).

Czy Sito Eratostenesa jest konieczne?

Jeśli masz zadanie typu „znajdź liczby pierwsze w przedziale do 100 000”, Sito jest najlepszym wyborem. Sprawdzanie każdej liczby osobno funkcją `is_prime` może przekroczyć limit czasu, jeśli danych wejściowych jest dużo.

Podsumowanie

Opanowanie tych 6 algorytmów (Pierwszość, Sito, NWD, Faktoryzacja, Horner, Fibonacci) daje Ci solidną bazę na maturę z informatyki 2026. Pamiętaj, że w części praktycznej liczy się poprawny wynik i czas działania programu. Ćwicz implementację tych schematów, aż będziesz je pisać z pamięci. Potrzebujesz wsparcia w nauce algorytmiki? Sprawdź nasze kursy maturalne na PROkorepetycje.pl!

Podoba Ci się ten artykuł?

To tylko wycinek wiedzy! Na naszych korepetycjach omawiamy te tematy jeszcze dokładniej. Zapisz się na lekcję próbną i zdaj egzamin na 100%.

Umów darmową konsultację

Źródła:

https://cke.gov.pl/egzamin-maturalny/egzamin-maturalny-w-formule-2023/https://www.geeksforgeeks.org/maths/prime-numbers/https://eduinf.waw.pl/inf/alg/001_search/0009.php

Ostatnia aktualizacja: 2025-09-09