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

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:

1.5. Wyszukiwanie Binarne – Znajdź igłę w stogu siana

Jeśli masz posortowaną tablicę i musisz znaleźć w niej element, nigdy nie używaj zwykłej pętli for (O(n)). Wyszukiwanie binarne dzieli zakres na pół w każdym kroku, co daje złożoność O(log n). Dla miliona elementów potrzebuje tylko ok. 20 sprawdzeń!

def binary_search(arr, target):
  left, right = 0, len(arr) - 1
  while left <= right:
      mid = (left + right) // 2
      if arr[mid] == target:
          return mid  # Znaleziono indeks
      elif arr[mid] < target:
          left = mid + 1
      else:
          right = mid - 1
  return -1  # Nie znaleziono

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.

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

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]

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.

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)

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.

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]

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.

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

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!

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_rec(n):
  if n <= 1: return n
  return fib_rec(n-1) + fib_rec(n-2)

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!