Trzy losowe pytania z bazy — analiza kodu, algorytmy, SQL.
Algorytmy zaawansowane to absolutny rdzeń egzaminu maturalnego z informatyki — pojawiają się w KAŻDYM arkuszu i są warte najwięcej punktów. CKE konsekwentnie sprawdza umiejętność stosowania rekurencji (procedury sortowania, parsery wyrażeń), programowania dynamicznego (najdłuższy podciąg rosnący, segment o największej sumie, łańcuchy przedziałów), metody dziel-i-zwyciężaj (sortowanie szybkie, wyszukiwanie połówkowe) oraz strategii zachłannej (problem plecakowy w wersji ciągłej, harmonogramowanie zadań). Najczęstsze typy zadań to: zapisanie nierekurencyjnej wersji procedury rekurencyjnej (4-5 pkt), znalezienie segmentu/podciągu o zadanych własnościach (3-4 pkt), analiza złożoności podanego algorytmu oraz porównanie dwóch wariantów. Kluczem jest umiejętność rozumienia pseudokodu i przekładania go na C++/Python (lub odwrotnie) oraz świadome dobranie struktury danych do problemu — tablicy zwykłej, stosu, kolejki, listy dynamicznej.
Filtruj zadania po typie (kod, SQL, pseudokod, ABCD), trudności i pochodzeniu — wszystko widoczne przed rozpoczęciem.
Lista zgodna z wymaganiami podstawy programowej PR i Informatorem CKE.
Identyfikacja przypadku bazowego (warunek stopu) oraz kroku rekurencyjnego (wywołanie z mniejszymi danymi). Klasyczne przykłady: silnia, Fibonacci, NWD Euklidesa, wieże Hanoi, sortowanie przez wstawianie rekurencyjnie. Świadomość kosztu pamięci (stos wywołań).
Przekształcanie procedury rekurencyjnej w wersję pętlową przy użyciu stosu lub akumulatora. To częste polecenie maturalne (4-5 pkt). Wzorzec: identyfikuj parametry zmienne, zastąp wywołanie pętlą while/for, kontroluj warunek zakończenia.
Klasyczne problemy: maksymalny segment (Kadane O(n)), najdłuższy podciąg rosnący O(n²) lub O(n log n), najdłuższy wspólny podciąg, problem plecakowy 0-1, łańcuchy przedziałów. Kluczowa idea: wynik[i] zależy od wynik[<i], unikamy ponownego liczenia.
Liniowe O(n) rozwiązanie: utrzymuj sumę bieżącą; jeśli zejdzie poniżej 0 — zacznij od nowa. Pamiętaj o wariantach: segment niepusty, najdłuższy taki segment, segment o sumie ≤ K, dwuwymiarowy odpowiednik na macierzy.
Podział problemu na ~równe podproblemy, rekurencyjne rozwiązanie, scalenie wyników. Sortowanie przez scalanie O(n log n), sortowanie szybkie (quicksort) ze średnim O(n log n), wyszukiwanie połówkowe O(log n), potęgowanie szybkie O(log n).
Wybór lokalnie najlepszej opcji w każdym kroku. Działa, gdy problem ma własność wyboru zachłannego. Klasyka: wydawanie reszty (dla "porządnych" nominałów), problem plecakowy ciągły (ułamkowy), harmonogramowanie zadań — sortowanie po czasie zakończenia.
Tablica MUSI być posortowana. Algorytm: lewy=0, prawy=n-1; dopóki lewy ≤ prawy: środek = (l+p)/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.
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. Świadomość, że trzy zagnieżdżone pętle = O(n³) (nie do zaakceptowania dla n=10⁵).
Operacje dozwolone w zadaniach "kartka": +, -, *, /, div (dzielenie całkowite), mod (reszta), porównania, instrukcje sterujące. ZABRONIONE: funkcje biblioteczne typu sort(), reverse(), str.upper(), Math.pow(). Musisz wszystko zaimplementować ręcznie.
Dla zbioru przedziałów [a,b] — znajdź najdłuższy łańcuch zagnieżdżeń. Wzorzec: posortuj przedziały po długości rosnąco; dla każdego przedziału licz dl[i] = max(dl[j])+1 po wszystkich j zawartych w i. Analogiczne do najdłuższego podciągu rosnącego — O(n²).
Najczęstsze błędy obserwowane przez CKE — i jak ich unikać.
Rekurencja bez warunku stopu lub z błędnym warunkiem.
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) + ...".
Trzy zagnieżdżone pętle dla zadania z n=100000.
Sprawdź rozmiar danych! Dla n=100000 musisz mieć co najwyżej O(n²) ale lepiej O(n log n) lub O(n). Użyj Kadane, programowania dynamicznego, sortowania + przejścia.
Dla najdłuższego podciągu rosnącego (LIS) używanie warunku t[j] ≤ t[i].
Dla podciągu ROSNĄCEGO: t[j] < t[i] (ściśle). Dla NIEMALEJĄCEGO: t[j] ≤ t[i].
Algorytm zachłanny zastosowany do problemu plecakowego 0-1.
Greedy działa tylko dla problemu plecakowego CIĄGŁEGO (możemy brać ułamki). Dla 0-1 (przedmiot bierzemy w całości lub wcale) — programowanie dynamiczne.
Bisection na tablicy nieposortowanej.
Wyszukiwanie połówkowe DZIAŁA tylko na danych posortowanych. Jeśli nie są — najpierw posortuj O(n log n), potem szukaj O(log n).
Implementacja Kadane bez obsługi tablicy z wszystkimi liczbami ujemnymi.
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ą).
Próba zapisania funkcji rekurencyjnej z parametrem licznika "ile wywołań".
Licznik wywołań zwykle utrzymuj jako zmienną GLOBALNĄ albo PRZEKAZUJ przez referencję/wskaźnik. Inaczej każde wywołanie zaczyna od 0.
Programowanie dynamiczne bez sortowania danych wejściowych.
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[].
Spaced Repetition przypomina te pojęcia i wzorce algorytmiczne dokładnie wtedy, kiedy zaczynasz je zapominać.
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)
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
Liniowy O(n) algorytm znajdowania spójnego podciągu o największej sumie.
ost = max(t[i], ost+t[i]); maks = max(maks, ost)
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]
Strategia: dziel problem na ~równe części, rozwiąż rekurencyjnie, scal wyniki.
Merge sort, quicksort, binary search, potęgowanie szybkie
Strategia: w każdym kroku wybieraj lokalnie najlepszą opcję.
Działa dla: harmonogramowanie, plecakowy ciągły, Huffman, MST
Algorytm O(log n) szukania elementu w POSORTOWANEJ tablicy.
l=0, p=n-1; dopóki l≤p: m=(l+p)/2, porównaj t[m] z x
Asymptotyczne oszacowanie liczby operacji w funkcji rozmiaru danych n.
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
Najprostszy przypadek w rekurencji, dla którego znamy odpowiedź bez dalszych wywołań.
Bez niego = nieskończona rekursja = Stack Overflow
Struktura pamięci przechowująca aktywne wywołania funkcji. Każda rekurencja zużywa stos.
Głębokość rekurencji > 10⁵ często powoduje przepełnienie
Wariant PD: pamiętamy wyniki funkcji rekurencyjnej w słowniku/tablicy i nie liczymy dwukrotnie.
Top-down PD vs bottom-up PD
Ciąg przedziałów P₁, P₂, ..., Pₖ taki, że każdy następny zawiera poprzedni.
Znajdowane przez sortowanie + PD analogiczne do LIS
Czytaj polecenie 2-3 razy. CKE celowo używa precyzyjnych słów: "rosnący" ≠ "niemalejący", "spójny podciąg" ≠ "podciąg", "ściśle większy" ≠ "większy lub równy". Każde słowo zmienia algorytm.
Sprawdź rozmiar danych PRZED napisaniem kodu. n=100 → możesz O(n³). n=10000 → max O(n²). n=10⁵ → musisz O(n log n) lub O(n). To determinuje wybór algorytmu.
Zawsze napisz przypadek bazowy rekurencji JAKO PIERWSZY. Potem dopisuj krok rekurencyjny. Po napisaniu — przetestuj na ręcznie obliczonym przykładzie z polecenia.
Dla zadań z plikiem dane.txt: najpierw policz ręcznie wynik dla przykładu z polecenia (1-2 wiersze). Dopiero potem skaluj na cały plik. Jeśli twój kod nie daje dobrego wyniku dla przykładu — nie ma sensu uruchamiać na 100000 elementach.
Ucz się 4 wzorców programowania dynamicznego: (1) maksymalny segment Kadane, (2) najdłuższy podciąg rosnący LIS, (3) najdłuższy wspólny podciąg LCS, (4) problem plecakowy 0-1. To 80% zadań PD na maturze.
Pseudokod CKE używa: dla i od a do b wykonaj / dopóki / jeśli ... w przeciwnym razie / ← (przypisanie) / div, mod (operacje całkowite). Naucz się tej składni — w zadaniach "kartka" musisz pisać w niej, nie w C++.
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ę.
Każdy typ wymaga innej strategii rozwiązywania.
Najczęstsze pytania o ten dział
Naturalne kontynuacje tematu
Pełen dostęp do 300 zadań z tego działu (PR), edytora kodu C++/Python/Java, klienta SQL, oceny AI z punktacją CKE, Spaced Repetition wzorców algorytmicznych.
Od 49 zł / miesiąc. Anulujesz kiedy chcesz.
Rozpocznij ćwiczenieWybierz, które kategorie plików cookies akceptujesz. Zgodę możesz zmienić w dowolnym momencie.
Sesja, bezpieczeństwo, podstawowa funkcjonalność (logowanie, koszyk subskrypcji, zabezpieczenia reCAPTCHA). Bez nich serwis nie działa.
Google Analytics 4 — anonimowe statystyki użycia serwisu. Pomaga nam poprawiać aplikację na podstawie tego, które funkcje są faktycznie używane.
Google Ads — remarketing i pomiar skuteczności reklam. Dzięki temu możemy pokazywać Ci trafniejsze reklamy i finansować rozwój darmowej wersji.
Zapamiętywanie preferencji (motyw ciemny/jasny, wybrane przedmioty, ustawienia sesji).
Dopasowywanie treści do Twoich zainteresowań (rekomendacje pytań, spersonalizowane powiadomienia o powtórkach).