💾 InformatykaAlgorytmika i programowaniePR

Algorytmy zaawansowane — zadania maturalne

Rekurencja, dziel i zwyciężaj, programowanie dynamiczne, podejście zachłanne i metoda połowienia — techniki algorytmiczne z zakresu rozszerzonego podstawy programowej.

Pytania z działów: Algorytmika i analiza algorytmów (172)

Rozwiązuj zadania z tego działu → Jak działa quiz ↓

Konto zakładasz w minutę · pełny dostęp od 49 zł/mies.

Sprawdzian z algorytmiki z odpowiedziami →

pytań w quizie
172
pytań w quizie
umiejętności
10
umiejętności
pułapek do unikania
8
pułapek do unikania
Quiz w Matury Online — pytanie z tematu „Algorytmy zaawansowane” (Informatyka) po sprawdzeniu odpowiedzi, z wynikiem i wyjaśnieniem

Quiz · Algorytmy zaawansowane

„Algorytmy zaawansowane” w Quizie — jak ćwiczysz

172 pytania z tej części materiału w jednym miejscu. Wybierasz je filtrem, po każdej odpowiedzi widzisz wyjaśnienie, a quiz sam dobiera trudność i wraca do Twoich błędów.

Quiz w Matury Online — panel „Filtruj” z zaznaczonym tematem „Algorytmy zaawansowane”, typy zadań i trudność 1–5, pod spodem pytanie z tego tematu

  • Filtrujesz, co chcesz ćwiczyć

    Wybierasz dział, typ zadania i trudność 1–5. Przy każdej opcji widzisz, ile pytań zostaje w puli.

  • Wyjaśnienie po każdej odpowiedzi

    Od razu wiesz, czy dobrze — i dlaczego. Zadania otwarte ocenia AI według zasad oceniania CKE, z punktacją częściową.

  • Powtórki pytań, na których się mylisz

    Pytanie z błędem wraca po kilku dniach z plakietką „Powtórka”. Powtórki zajmują najwyżej 30% sesji; wyłączasz je jednym przełącznikiem.

  • Trudność dobiera się do Ciebie

    Quiz liczy Twój poziom z ostatnich odpowiedzi i podsuwa pytania, przy których trafiasz ok. 70% — nie za łatwe, nie za trudne.

9 typów zadań — Algorytmy zaawansowane

z 19 typów w całym quizie · liczba pytań · filtr „Typ” w quizie
  • Zamknięte (A–D) 39
  • Otwarte 32
  • Obliczenia 17
  • Prawda/Fałsz 17
  • Wykres 17
  • Tabela danych 16
  • Dopasuj 13
  • Uzupełnij 12
  • Wielokrotny wybór 9

Po odpowiedzi — od razu wyjaśnienie

Zaznaczasz odpowiedź, klikasz „Sprawdź” i widzisz, która była poprawna i dlaczego. Możesz też odsłonić odpowiedź bez rozwiązywania albo pominąć pytanie.

Wypróbuj bez logowania

Kilka pytań z bazy z działu „Algorytmy zaawansowane” — kliknij odpowiedź i sprawdź.
Ćwicz dział „Algorytmy zaawansowane” w Quizie → darmowe konto: 5 pytań dziennie · bez dziennego limitu od 49 zł/mies.

Podstawa programowa (zakres rozszerzony) wymienia tu: rekurencję (generowanie ciągów, potęgowanie, sortowanie, fraktale), metodę dziel i zwyciężaj (jednoczesne znajdowanie minimum i maksimum, sortowanie przez scalanie i szybkie), podejście zachłanne (wydawanie reszty, szukanie najkrótszej drogi), programowanie dynamiczne (najdłuższy wspólny podciąg) oraz znajdowanie podciągów o zadanych własnościach, np. spójnego podciągu o największej sumie.

W Informatorze CKE są przykłady takich zadań:

  • Segment o największej sumie: zadanie 1
  • Łańcuchy przedziałów: zadanie 3
  • Nierekurencyjna wersja procedury rekurencyjnej: zadanie 5.4

Według Informatora do około 60% punktów w arkuszu można uzyskać za zadania z analizy algorytmów i programowania. Algorytm zapisuje się w pseudokodzie albo w języku wybranym na egzamin — w 2027 r. to C/C++, Java albo Python (komunikat dyrektora CKE z 20 sierpnia 2026 r.).

Przed maturą

Powtórka z algorytmów zaawansowanych krok po kroku

  1. 1

    Odśwież pojęcia

    Zacznij od: Rekurencja, Programowanie dynamiczne (PD), Algorytm Kadane i 9 kolejnych pozycji.

    Pełna lista
  2. 2

    Sprawdź, co umiesz

    10 umiejętności do odhaczenia, od „Rekurencja” po „Łańcuchy przedziałów i porządki”.

    Lista umiejętności
  3. 3

    Uważaj na typowe błędy

    8 pułapek, np. „Rekurencja bez warunku stopu lub z błędnym warunkiem”. Przy każdej jest poprawna wersja i wyjaśnienie.

    Typowe błędy
  4. 4

    Sprawdź się

    Najpierw krótki quiz, potem pełny sprawdzian z całego zakresu.

    Quiz z algorytmów zaawansowanych Sprawdzian z algorytmiki Rozwiąż zadania z bazy

Zakres materiału

Umiejętności sprawdzane w tym dziale

Lista zgodna z wymaganiami podstawy programowej PR i Informatorem CKE.

  1. 1

    Rekurencja — schemat i baza

    Identyfikacja przypadku bazowego (warunek stopu) oraz kroku rekurencyjnego (wywołanie z mniejszymi danymi). Przykłady: silnia, ciąg Fibonacciego, algorytm Euklidesa w wersji rekurencyjnej, szybkie potęgowanie, rekurencyjne wstawianie elementu przy sortowaniu (Informator CKE, zadanie 5). Każde wywołanie zajmuje miejsce na stosie wywołań.

  2. 2

    Eliminacja rekurencji — wersja iteracyjna

    Przekształcanie procedury rekurencyjnej w wersję pętlową przy użyciu stosu lub akumulatora. Wzorzec: identyfikuj parametry zmienne, zastąp wywołanie pętlą while/for, kontroluj warunek zakończenia.

  3. 3

    Programowanie dynamiczne — tablica wyników częściowych

    Podstawa programowa wymienia najdłuższy wspólny podciąg; tą samą metodą rozwiązuje się zadanie o łańcuchach przedziałów z Informatora CKE (zadanie 3.3) i zadanie o najdłuższym podciągu rosnącym w czasie O(n²). Idea: wynik[i] zależy od wcześniej obliczonych wyników, więc niczego nie liczymy drugi raz.

  4. 4

    Algorytm Kadane — segment o największej sumie

    Rozwiązanie liniowe O(n): pamiętaj najlepszą sumę segmentu kończącego się na bieżącym elemencie; gdy jest ujemna, nowy segment zacznij od bieżącego elementu. W Informatorze CKE (zadanie 1.4) trzeba dodatkowo podać indeksy początku i końca segmentu, więc zapamiętuj też początek bieżącego segmentu.

  5. 5

    Metoda dziel-i-zwyciężaj

    Podział problemu na mniejsze podproblemy, rozwiązanie każdego z nich i połączenie wyników. Przykłady z podstawy programowej: jednoczesne znajdowanie minimum i maksimum, sortowanie przez scalanie O(n log n), sortowanie szybkie (średnio O(n log n)). Na połowieniu opierają się też wyszukiwanie binarne O(log n) i szybkie potęgowanie O(log n).

  6. 6

    Algorytmy zachłanne (greedy)

    Wybór lokalnie najlepszej opcji w każdym kroku. Podstawa programowa podaje dwa zastosowania: wydawanie reszty i szukanie najkrótszej drogi. Metoda zachłanna nie zawsze daje wynik optymalny: dla nominałów 1, 3, 4 i kwoty 6 wyda trzy monety (4 + 1 + 1), a wystarczą dwie (3 + 3).

Pokaż pozostałe 4
  1. 7

    Wyszukiwanie połówkowe (bisection)

    Tablica musi być posortowana. Algorytm: lewy=0, prawy=n-1; dopóki lewy ≤ prawy: środek = (lewy+prawy) div 2, porównaj z szukaną wartością i zawęź przedział. Złożoność O(log n). Wariant: znajdź pierwsze/ostatnie wystąpienie, znajdź najmniejszy element ≥ x.

  2. 8

    Analiza złożoności obliczeniowej

    Notacja O(): O(1) — stała, O(log n) — logarytmiczna, O(n) — liniowa, O(n log n) — quasi-liniowa, O(n²) — kwadratowa, O(n³) — sześcienna, O(2ⁿ) — wykładnicza. Zadania CKE opisują złożoność słowami: logarytmiczna, liniowa, kwadratowa, sześcienna (Informator, zadanie 4.2). Trzy zagnieżdżone pętle po n elementach to O(n³) — dla n = 10⁵ daje to rząd 10¹⁵ operacji.

  3. 9

    Operacje arytmetyczne w pseudokodzie

    W zadaniach, w których algorytm zapisuje się w arkuszu, CKE zwykle ogranicza dozwolone operacje do: dodawania, odejmowania, mnożenia, dzielenia, dzielenia całkowitego (div), reszty z dzielenia (mod), porównań, instrukcji sterujących, przypisań i samodzielnie napisanych funkcji; funkcje wbudowane są wtedy zabronione (Informator, zadanie 5.4; arkusze 2023 zad. 2.1, 2024 zad. 3.1, 2025 zad. 1.3, 2026 zad. 2.2). Dokładną listę zawsze podaje uwaga w treści zadania.

  4. 10

    Łańcuchy przedziałów i porządki

    Zadanie 3 z Informatora CKE: łańcuch to ciąg przedziałów, w którym każdy kolejny zawiera poprzedni. Wzorzec: uporządkuj przedziały od najkrótszych do najdłuższych; dla każdego przedziału i licz dl[i] = max(dl[j]) + 1 po wszystkich przedziałach j zawartych w i (dl[i] = 1, gdy takich nie ma). Koszt O(n²).

Typowe błędy

Pułapki, w które wpadają maturzyści

Typowe błędy w zadaniach z tego działu — i jak ich unikać.

✗ Błąd

Rekurencja bez warunku stopu lub z błędnym warunkiem.

✓ Poprawnie

Zawsze sprawdź najpierw warunek bazowy, dopiero potem rób wywołanie rekurencyjne. Wzorzec: „jeśli n ≤ 0 zwróć ...; w przeciwnym razie zwróć f(n-1) + ...”.

Dlaczego: Bez warunku stopu wywołania nigdy się nie kończą i program przerywa błąd przepełnienia stosu. Pisz przypadek bazowy jako pierwszy.

✗ Błąd

Trzy zagnieżdżone pętle dla zadania z n=100000.

✓ Poprawnie

Sprawdź rozmiar danych. Dla n = 100 000 algorytm sześcienny to rząd 10¹⁵ operacji, a kwadratowy — 10¹⁰; szukaj rozwiązania liniowego albo O(n log n).

Dlaczego: W Informatorze CKE zadanie 1.3 ma 1000 liczb i — jak podaje komentarz do rozwiązania — program sześcienny jest dla tych danych wystarczająco szybki. Zadanie 1.4 ma 100 000 liczb, a przykładowe rozwiązanie jest liniowe.

✗ Błąd

Dla najdłuższego podciągu rosnącego (LIS) używanie warunku t[j] ≤ t[i].

✓ Poprawnie

Dla podciągu rosnącego: t[j] < t[i] (ściśle). Dla niemalejącego: t[j] ≤ t[i].

Dlaczego: Jedno słowo w treści zmienia wynik: „rosnący” oznacza nierówność ostrą, „niemalejący” — nieostrą. Podstawa programowa wymienia właśnie najdłuższy spójny podciąg niemalejący.

✗ Błąd

Założenie, że zachłanne wydawanie reszty zawsze daje najmniejszą liczbę monet.

✓ Poprawnie

Metoda zachłanna (zawsze największy możliwy nominał) jest optymalna tylko dla niektórych zestawów nominałów. Gdy nominały są nietypowe, sprawdź kontrprzykład albo użyj programowania dynamicznego.

Dlaczego: Dla nominałów 1, 3, 4 i kwoty 6 metoda zachłanna wyda 4 + 1 + 1 (trzy monety), a optymalnie jest 3 + 3 (dwie monety).

Pokaż pozostałe 4
✗ Błąd

Bisection na tablicy nieposortowanej.

✓ Poprawnie

Wyszukiwanie połówkowe działa tylko na danych posortowanych. Jeśli nie są — najpierw posortuj O(n log n), potem szukaj O(log n).

Dlaczego: Podstawa programowa mówi o wyszukiwaniu binarnym w zbiorze uporządkowanym. Na danych nieuporządkowanych algorytm może odrzucić połowę, w której leży szukany element.

✗ Błąd

Implementacja Kadane bez obsługi tablicy z wszystkimi liczbami ujemnymi.

✓ Poprawnie

Inicjalizuj maks = t[0] (NIE maks = 0!) i ost_suma = t[0]. Dzięki temu jeśli wszystkie liczby są ujemne, algorytm zwróci największą (najmniej ujemną).

Dlaczego: Maks = 0 daje wynik 0 dla tablicy [-5,-3,-1], a poprawny segment niepusty to [-1]. Tak samo (maks = ost_suma = t[0]) zaczyna przykładowe rozwiązanie zadania 1.4 w Informatorze CKE.

✗ Błąd

Licznik wywołań funkcji rekurencyjnej przekazywany jako zwykły parametr (przez wartość).

✓ Poprawnie

Licznik wywołań trzymaj w zmiennej globalnej, przekazuj przez referencję albo zwracaj jako wynik funkcji.

Dlaczego: Parametr przekazany przez wartość jest w każdym wywołaniu osobną kopią, więc jego zmiana nie wraca do funkcji wywołującej.

✗ Błąd

Programowanie dynamiczne bez sortowania danych wejściowych.

✓ Poprawnie

Dla łańcuchów przedziałów / problemów z zawieraniem — pierwszy krok to sortowanie (po długości, po końcu, po początku). Dopiero potem buduj tablicę dl[].

Dlaczego: Wskazówka do zadania 3.3 w Informatorze CKE: długości łańcuchów oblicza się w kolejności od przedziałów najkrótszych do najdłuższych. Bez tego porządku komórka dl[i] bywa liczona, zanim znane są wartości, od których zależy.

Do zapamiętania

Definicje, wzory i pojęcia do powtórzenia

Rekurencja
Technika, w której funkcja wywołuje samą siebie z mniejszymi/prostszymi argumentami, aż osiągnie przypadek bazowy.
silnia(n) = jeśli n≤1 zwróć 1; w przeciwnym razie zwróć n * silnia(n-1)
Programowanie dynamiczne (PD)
Strategia, w której zapamiętujemy wyniki podproblemów w tablicy/słowniku, aby unikać ponownego obliczania.
fib[i] = fib[i-1] + fib[i-2], buduj od fib[0]=fib[1]=1
Algorytm Kadane
Liniowy O(n) algorytm znajdowania spójnego podciągu o największej sumie.
ost = max(t[i], ost+t[i]); maks = max(maks, ost)
Najdłuższy podciąg rosnący (LIS)
Problem znalezienia najdłuższego (niekoniecznie spójnego) podciągu ściśle rosnącego.
O(n²) z dl[i]=max(dl[j])+1 dla j<i z t[j]<t[i]
Dziel-i-zwyciężaj
Strategia: podziel problem na mniejsze części, rozwiąż je rekurencyjnie, połącz wyniki.
Sortowanie przez scalanie i szybkie, jednoczesne minimum i maksimum
Algorytm zachłanny (greedy)
Strategia: w każdym kroku wybieraj lokalnie najlepszą opcję.
W podstawie programowej: wydawanie reszty, szukanie najkrótszej drogi
Wyszukiwanie połówkowe
Algorytm O(log n) szukania elementu w posortowanej tablicy.
l=0, p=n-1; dopóki l≤p: m=(l+p) div 2, porównaj t[m] z x
Złożoność O()
Asymptotyczne oszacowanie liczby operacji w funkcji rozmiaru danych n.
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
Przypadek bazowy
Najprostszy przypadek w rekurencji, dla którego znamy odpowiedź bez dalszych wywołań.
Bez niego rekurencja się nie kończy i dochodzi do przepełnienia stosu
Stos wywołań
Struktura pamięci przechowująca aktywne wywołania funkcji. Każda rekurencja zużywa stos.
W Pythonie domyślny limit głębokości rekurencji to 1000 wywołań (sys.getrecursionlimit())
Memoizacja
Wariant PD: pamiętamy wyniki funkcji rekurencyjnej w słowniku/tablicy i nie liczymy dwukrotnie.
Top-down PD vs bottom-up PD
Łańcuch przedziałów
Ciąg przedziałów P₁, P₂, ..., Pₖ taki, że każdy następny zawiera poprzedni.
Informator CKE, zadanie 3; rozwiązanie: uporządkowanie po długości i programowanie dynamiczne

Jak się uczyć

Jak skutecznie uczyć się tego działu

  1. 1

    Czytaj polecenie uważnie: „rosnący” to nie „niemalejący”, „spójny podciąg” to nie „podciąg”, „większy” to nie „większy lub równy”. Każde z tych słów zmienia algorytm.

  2. 2

    Sprawdź rozmiar danych przed napisaniem kodu. Dla 1000 liczb wystarczy nawet rozwiązanie sześcienne (Informator CKE, zadanie 1.3), dla 100 000 potrzebne jest liniowe albo O(n log n) (zadanie 1.4).

  3. 3

    Zawsze napisz przypadek bazowy rekurencji jako pierwszy. Potem dopisuj krok rekurencyjny. Po napisaniu — przetestuj na ręcznie obliczonym przykładzie z polecenia.

  4. 4

    W zadaniach z plikiem danych najpierw sprawdź program na przykładzie z polecenia, dla którego znasz wynik. Dopiero potem uruchom go na całym pliku.

  5. 5

    Przećwicz problemy wymienione w podstawie programowej: spójny podciąg o największej sumie, najdłuższy spójny podciąg niemalejący, najdłuższy wspólny podciąg — oraz łańcuchy przedziałów z Informatora CKE.

  6. 6

    W pseudokodzie CKE spotkasz zapisy: „dla i = 2, 3, …, n wykonaj”, „dopóki … wykonaj”, strzałkę ← jako przypisanie oraz operatory div i mod (Informator, zadanie 4; arkusz 2025, zadanie 1). Gdy zadanie każe zapisać algorytm w arkuszu, możesz użyć pseudokodu albo języka programowania wybranego na egzamin.

  7. 7

    Algorytm w pseudokodzie zawsze testuj na przykładzie z polecenia ręcznie (krok po kroku, prowadząc kolumny stanu zmiennych). Często wykrywasz off-by-one, zły warunek pętli czy złą inicjalizację.

Typy zadań w tym dziale

Każdy typ wymaga innej strategii rozwiązywania.

FAQ

FAQ — Algorytmy zaawansowane

Czy mogę użyć C++, Pythona czy musi być pseudokod?
Program piszesz w języku, który wybrałeś na egzamin z listy ogłoszonej przez dyrektora CKE. W 2027 r. są na niej C/C++, Java i Python (komunikat z 20 sierpnia 2026 r.); wybrać można tylko oprogramowanie, które ma szkoła. Gdy zadanie każe zapisać algorytm w arkuszu, polecenie brzmi zwykle „w pseudokodzie lub w wybranym języku programowania” — jeśli wybierasz język, musi to być ten zadeklarowany na egzamin (instrukcja w arkuszu).
Czy mogę używać bibliotek typu sort() w Pythonie albo std::sort w C++?
W zadaniach praktycznych oceniane są wyniki działania programu (Informator CKE, zasady oceniania), a podstawa programowa przewiduje korzystanie z dostępnych bibliotek. Nie można natomiast doinstalować na egzaminie dodatkowych modułów. Gdy algorytm zapisujesz w arkuszu, uwaga w zadaniu zwykle zabrania funkcji wbudowanych i dopuszcza tylko operacje arytmetyczne, porównania, instrukcje sterujące, przypisania i własne funkcje (np. Informator, zadanie 5.4).
Czemu mój algorytm O(n³) wystarcza dla n=1000, a dla n=100000 nie kończy pracy?
n³ dla n = 1000 to 10⁹ operacji, a dla n = 100 000 już 10¹⁵ — milion razy więcej. Na egzaminie nie ma limitu czasu działania programu, ale wynik musisz mieć przed końcem egzaminu. W Informatorze CKE zadanie 1.3 (1000 liczb) ma przykładowe rozwiązanie sześcienne, a zadanie 1.4 (100 000 liczb) — liniowe.
Kiedy algorytm zachłanny daje poprawny wynik, a kiedy nie?
Zachłanny działa, gdy lokalnie najlepsza decyzja prowadzi do najlepszego rozwiązania całości. Przy wydawaniu reszty tak jest dla nominałów 1, 2, 5, 10, 20, 50, 100, 200, 500, ale nie dla każdego zestawu: dla nominałów 1, 3, 4 i kwoty 6 metoda zachłanna daje trzy monety (4 + 1 + 1), a wystarczą dwie (3 + 3). Dlatego wynik metody zachłannej warto sprawdzić na małym przykładzie.
Jak zacząć rozwiązywanie zadania algorytmicznego na maturze?
Trzy kroki: (1) Przeczytaj polecenie i zaznacz rozmiar danych, ograniczenia i dokładne zwroty („spójny”, „rosnący”, „różnych”). (2) Rozwiąż ręcznie przykład z polecenia — to sprawdzian, czy rozumiesz zadanie. (3) Dobierz algorytm do rozmiaru danych: dla małych plików wystarczy rozwiązanie wprost z definicji, dla dużych szukaj liniowego albo O(n log n). Dopiero potem pisz kod.
Jak zrobić powtórkę z algorytmów zaawansowanych przed maturą?
Sprawdza się taka kolejność. 1) Czytaj polecenie uważnie: „rosnący” to nie „niemalejący”, „spójny podciąg” to nie „podciąg”, „większy” to nie „większy lub równy”. 2) Sprawdź rozmiar danych przed napisaniem kodu. 3) Zawsze napisz przypadek bazowy rekurencji jako pierwszy. Na koniec sprawdź się w quizie z algorytmów zaawansowanych, a potem w pełnym sprawdzianie.

Powiązane działy

Naturalne kontynuacje tematu

Algorytmy podstawoweAnaliza algorytmówProgramowanie strukturalne

← Wszystkie działy

Zacznij rozwiązywać zadania z algorytmów zaawansowanych

Pełen dostęp do 172 zadań z tego działu (PR), edytora kodu z podświetlaniem składni (C++, Python, SQL) i oceny AI z punktacją CKE. Anulujesz kiedy chcesz.

Rozpocznij ćwiczenie

Pełny dostęp od 49 zł/mies. · jednorazowo 59 zł na 30 dni (BLIK / Przelewy24 / Google Pay / Apple Pay / Revolut / Karta) · subskrypcję anulujesz w 1 kliknięciu