Przejdź do treści

Zrozum algorytmy maturalne: złożoność, sortowanie, zachłanność i rekurencję

Prześledź na kartce i w kodzie wyszukiwanie binarne, sito Eratostenesa, algorytm Euklidesa, szybkie potęgowanie, programowanie dynamiczne oraz zadania pseudokodowe.

Jak bezbłędnie rozwiązywać zadania algorytmiczne na kartce i przy komputerze

  1. 01

    Zwróć uwagę na indeksowanie tablicy od 1 w arkuszach CKE

    W części teoretycznej matury CKE tablice w pseudokodzie są zazwyczaj indeksowane od 1 do n (a nie od 0 jak w Pythonie i C++) – zawsze sprawdź założenia na początku zadania.

  2. 02

    Rozpisz tabelkę wykonania pętli dla małego przykładu (n = 4 lub n = 5)

    Nie zgaduj wzoru rekurencyjnego w głowie – rozrysuj drzewo wywołań albo kolejne wiersze wartości zmiennych krok po kroku, aż dostrzeżesz prawidłowość.

  3. 03

    Szukaj niezmiennika lub optymalizacji z O(n^2) do O(n) / O(n log n)

    Gdy polecenie zabrania zagnieżdżania dwóch pełnych pętli po n elementach, rozważ sumy prefiksowe, dwa wskaźniki (gąsienicę), sortowanie lub tablicę zliczającą.

  4. 04

    Zawsze przetestuj warunki brzegowe algorytmu

    Sprawdź ręcznie, jak Twój algorytm zachowa się dla n = 1, dla tablicy posortowanej malejąco, dla wszystkich równych elementów oraz dla liczb pierwszych.

Najczęściej zadawane pytania

Czym w pseudokodzie maturalnym różnią się operatory div i mod od zwykłego dzielenia?

Operator div oznacza dzielenie całkowitoliczbowe z odrzuceniem części ułamkowej (17 div 5 = 3, w Pythonie //), a mod zwraca resztę z dzielenia całkowitego (17 mod 5 = 2, w Pythonie %).

Kiedy algorytm zachłanny NIE daje optymalnego wyniku (np. wydawanie reszty lub plecak)?

Zachłanność wybiera lokalnie najlepszy ruch w danej chwili: dla standardowych polskich monet działa, ale dla nominałów [1, 3, 4] kwotę 6 wyda jako 4+1+1 (3 monety) zamiast optymalnego 3+3 (2 monety) – wtedy trzeba użyć programowania dynamicznego.

Dlaczego funkcja rekurencyjna bez warunku stopu zawiesza program błędem przepełnienia stosu?

Każde wywołanie odkłada nową ramkę na stosie pamięci; brak warunku bazowego (np. dla n <= 1) lub niezmniejszanie argumentu sprawia, że wywołania nigdy się nie kończą (RecursionError).

Dowiedz się więcej

Powiązane poradniki i wyjaśnienia do tego zadania