Jak czytać pseudokod CKE? Tworzenie tabelek śledzenia zmiennych, rozrysowywanie drzew rekurencji oraz szacowanie złożoności obliczeniowej Big O.
Wstęp: Bądź jak kompilator
Część I matury z informatyki bezlitośnie weryfikuje, czy potrafisz "myśleć jak procesor". Zamiast pisać kod w wygodnym edytorze z kolorowaniem składni, dostajesz na kartce surowy pseudokod i pytanie: "Co wypisze ten algorytm dla n = 5?". Metoda "na oko" zazwyczaj kończy się błędem o jedną iterację (tzw. błąd off-by-one). W tym dziale nauczysz się niezawodnych technik śledzenia algorytmów: od tabelek zmiennych, przez drzewa wywołań, aż po błyskawiczne szacowanie złożoności.
📋 Spis treści
Iteracja (Pętle)
Rekurencja i Złożoność
1
Tabelka śledzenia zmiennych (Dry Run)
To najprostsza, a zarazem najbardziej skuteczna metoda ratująca punkty na maturze. Zamiast zgadywać wynik, rysujesz na brudnopisie tabelkę, gdzie każda kolumna to jedna zmienna z algorytmu, a każdy wiersz to jeden pełny obrót pętli.
a ← 2
b ← 5
dopóki b > 0 wykonuj:
a ← a + 2
b ← b - 2
wypisz a, b
| Iteracja | a | b | Warunek b > 0 |
|---|---|---|---|
| Start (0) | 2 | 5 | 5 > 0 (Prawda) |
| 1 | 4 | 3 | 3 > 0 (Prawda) |
| 2 | 6 | 1 | 1 > 0 (Prawda) |
| 3 | 8 | -1 | -1 > 0 (Fałsz) |
Wniosek: Pętla przerwie się, gdy . Algorytm wypisze liczby: 8, -1.
2
Pętle zagnieżdżone (Pętla w pętli)
To najczęstsze źródło błędów w zadaniach CKE. Gdy mamy zewnętrzną pętlę ze zmienną i wewnętrzną ze zmienną , musisz pamiętać, że wewnętrzna pętla musi wykonać się w całości, zanim zewnętrzna pętla przejdzie do kolejnego kroku!
Jeśli zewnętrzna pętla kręci się razy, a wewnętrzna razy, to instrukcje ukryte w samym środku wykonają się dokładnie razy.
s ← 0
dla i = 1 do 3 wykonuj:
dla j = 1 do 2 wykonuj:
s ← s + i + j
Zewnętrzna robi 3 kroki (i=1, 2, 3). Wewnętrzna robi 2 kroki (j=1, 2). Zatem zmienna zostanie zwiększona 6 razy. Nie zgaduj wyników – rozpisuj krok po kroku!
3
Magia Rekurencji: Drzewa wywołań
Rekurencja (funkcja wywołująca samą siebie) potrafi przepalić zwoje mózgowe, jeśli próbujesz ją śledzić w pamięci. Zamiast tabelki, do rekurencji zawsze rysuj drzewo wywołań (call tree).
funkcja F(n):
jeśli n == 0 to:
zwróć 1
w przeciwnym razie:
zwróć F(n - 1) + 2
Zawsze najpierw zejdź na samo dno (do warunku stopu), a dopiero potem dodawaj/mnoż wartości, wracając do góry.
4
Złożoność obliczeniowa (Notacja Big O)
Złożoność odpowiada na pytanie: "Jeśli ilość danych wzrośnie dwukrotnie, o ile dłużej będzie działał ten algorytm?". CKE nie wymaga od Ciebie precyzyjnych dowodów matematycznych, musisz jednak umieć poprawnie sklasyfikować algorytm do odpowiedniego rzędu.
Czas wykonania jest zawsze taki sam, niezależnie od wielkości danych . Np. odczyt pierwszego elementu z tablicy lub proste równanie matematyczne.
Z każdym krokiem pętli zbiór danych zmniejsza się o połowę (lub inną stałą część). Klasyczny przykład to Wyszukiwanie Binarne. Bardzo szybka!
Czas rośnie proporcjonalnie do danych. Występuje, gdy używasz jednej standardowej pętli (np. wyszukiwanie liniowe min/max w nieposortowanej tablicy).
Niebezpieczna przy dużych plikach. Oznacza zagnieżdżoną pętlę (pętla w pętli). Spotykana np. w standardowym Sortowaniu Bąbelkowym.
Trik CKE na szacowanie złożoności: Zignoruj operacje poza pętlami. Zlicz, ile razy wykona się "najgłębsza" pętla.
while, która w każdym kroku dzieli n przez 2 = Śledzenie kodu to czysta praktyka. Przejdź do naszej bazy quizów i spróbuj odgadnąć, jaki wynik zwrócą algorytmy przygotowane na wzór zeszłorocznych arkuszy maturalnych CKE.
Rozwiąż Quiz z Analizy Algorytmów 🚀