Algorytmika to serce matury z informatyki — od zapisu algorytmu po analizę jego złożoności i poprawności.
6zadań
1przykładów
01Co musisz umieć?
—Zapisywać algorytmy w postaci listy kroków, schematu blokowego i pseudokodu
—Analizować działanie algorytmu dla przykładowych danych
—Określać złożoność czasową i pamięciową algorytmu
—Stosować algorytmy na liczbach: NWD, sito Eratostenesa, rozkład na czynniki
—Stosować algorytmy sortowania i wyszukiwania
—Rozpoznawać typowe błędy w algorytmach i je poprawiać
02Najważniejsza teoria
Schemat blokowy: owal — początek i koniec; równoległobok — dane; romb — decyzja; prostokąt — operacja.
TEORIA — schemat blokowy i pseudokod
Bardzo popularnym sposobem zapisu algorytmu jest schemat blokowy. Przedstawia on w sposób graficzny kolejne czynności połączone strzałkami, co pozwala na tworzenie dowolnie skomplikowanych schematów i łatwą ich weryfikację oraz testowanie.
Pseudokod to jeszcze jeden sposób zapisu algorytmu. Używają go głównie programiści, ponieważ zachowuje on strukturę podobną do języka programowania, przy czym nie zachowuje reguł składniowych konkretnego języka. Dzięki temu na jego podstawie łatwiej tworzyć programy w różnych językach — są w nim zawarte konkretne sugestie rozwiązania problemu, a programista może skupić się jedynie na tworzeniu kodu w konkretnym języku programowania.
Cechy dobrego algorytmu
Dobry algorytm powinien mieć następujące cechy: precyzyjne zdefiniowanie — algorytm nie może pozostawiać dowolności w interpretacji zapisu; każdy, kto z niego skorzysta, musi go rozumieć w taki sam sposób. Skończoność — algorytm musi po pewnej liczbie kroków dać wynik, czyli wygenerować dane wyjściowe; liczba operacji musi być skończona. Wykonalność — wszystkie operacje opisane w algorytmie muszą być możliwe do wykonania. Efektywność — algorytm powinien być tak ułożony, by wynik jego działania był dostępny po jak najmniejszym zaangażowaniu zasobów komputera i w jak najkrótszym czasie; zależy to jednak nie tylko od algorytmu, lecz także od właściwości komputera, języka użytego do ułożenia programu, systemu operacyjnego i wielu innych parametrów.
Specyfikacja problemu
Bez względu na to, jakiego sposobu zapisu użyjesz przy tworzeniu algorytmu, musi on spełniać założenia projektu. Założenia zapisuje się w postaci tzw. specyfikacji, która powstaje podczas wstępnych prac nad algorytmem — mogą to być np. uzgodnienia z zamawiającym lub rozwinięcie własnego pomysłu na program. Specyfikacja zazwyczaj składa się z trzech części. Najważniejszą, uzgadnianą z autorem pomysłu lub zamawiającym program, jest szczegółowy opis problemu. W specyfikacji można podać także warunki, które powinny być spełnione przez dane i wyniki. Dobrze, jeśli w opisie znajdą się także zależności zachodzące między danymi wejściowymi a wynikami, np. wzory.
Specyfikację można zapisać w dowolny sposób — ważne, by uwzględniała wszystkie aspekty problemu. Tak przygotowana specyfikacja staje się podstawą do tworzenia algorytmu.
Dane wejściowe i wyjściowe
Dane wejściowe w wielu przypadkach to nie tylko liczby lub tekst wprowadzany za pośrednictwem klawiatury. Wiele z nich dostaje się do komputera za pośrednictwem urządzeń peryferyjnych, takich jak mikrofon, skaner, kamera czy mierniki temperatury, ciśnienia, zawartości pyłów zawieszonych i innych wielkości fizycznych. Wszystkie muszą być przetworzone przez algorytm na dane wyjściowe.
Dane wyjściowe powstają na skutek przetwarzania danych wejściowych zgodnie z algorytmem. Tu także mamy do czynienia z rozmaitymi typami danych. Dane wyjściowe mogą być jednocześnie wejściowymi dla innych algorytmów.
Złożoność obliczeniowa
Czasowa złożoność obliczeniowa to ilość czasu potrzebnego do rozwiązania problemu w zależności od tego, ile jest danych wejściowych. Wyraża się ją w jednostkach czasu albo w liczbie operacji dominujących, które należy wykonać dla n danych, aby otrzymać rozwiązanie. Złożoność pamięciowa ma za zadanie określić liczbę komórek pamięci, która będzie zajęta przez dane i wyniki pośrednie tworzone w trakcie pracy algorytmu.
Klasy złożoności obliczeniowej określają rząd funkcji T(n). Jednym ze sposobów określenia rzędu tej funkcji jest popularna notacja omikron, zwana także notacją dużegoO. Wyszukiwanie binarne ma złożoność O(logn), a sortowanie bąbelkoweO(n2) — przy dużych danych różnica jest ogromna.
Algorytm Euklidesa (NWD)
Największy wspólny dzielnik dwóch liczb wyznaczamy, powtarzając dzielenie z resztą:
NWD(a,b)=NWD(b,amodb)konˊczymy, gdy reszta wynosi 0
Przykład · Analiza algorytmu wyszukiwania binarnego
1Mamy posortowaną tablicę n=1000 elementów i szukamy wartości x.
2Porównujemy x ze środkowym elementem i odrzucamy połowę przedziału.
3Każdy krok zmniejsza przeszukiwany obszar dwukrotnie.
4Liczba kroków to około log21000≈10 — zamiast do 1000 porównań przy przeszukiwaniu liniowym.
04Zadania
Rok matury:
Znalezione zadania: 6
Zadanie 1
Matura: maj 2026
Oryginalne zadanie: zad. 1.1
Poziom: rozszerzony
Dział: Algorytmika
Temat: Rekurencja
Matura · 3 pkt
Dana jest zdefiniowana rekurencyjnie funkcja A(m,n), gdzie m i n są dodatnimi liczbami całkowitymi. A(m,n)=⎩⎨⎧mA(2⋅m,2n)2⋅A(m,2n−1)+mgdyn=1gdyn>1oraznjestpodzielneprzez2gdyn>1oraznniejestpodzielneprzez2 Obliczenie wartości funkcji A(3,9) wprost z definicji wymaga trzech wywołań rekurencyjnych: A(3,4), A(6,2), A(12,1), ponieważ: A(3,9)=2⋅A(3,4)+3=2⋅A(6,2)+3=2⋅A(12,1)+3=2⋅12+3=27 Uzupełnij poniższą tabelę. Podaj liczbę wywołań rekurencyjnych funkcji A oraz wypisz wywołania rekurencyjne wraz z ich argumentami (w ostatnim wierszu podaj tylko liczbę wywołań rekurencyjnych).
m
n
liczba wywołań rekurencyjnych funkcji A
wywołania rekurencyjne funkcji A
3
9
3
A(3,4), A(6,2), A(12,1)
25
25
10
15
1
2100+1
Odpowiedź do samodzielnego porównania z pełnym rozwiązaniem; bez automatycznej oceny.
Wskazówka
Śledź drugi argument: przy każdym wywołaniu dzielimy go całkowicie przez 2.
Rozwiązanie krok po kroku
1Nie wliczamy początkowego A(m,n); liczymy dopiero wywołania wykonane wewnątrz funkcji.
2Gdy n jest parzyste, podwajamy m i dzielimy n przez 2; gdy nieparzyste, m się nie zmienia, a n zastępujemy (n−1)/2.
3Powtarzamy aż drugi argument osiągnie 1.
4Dla m = 25, n = 25: 5 wywołań: A(26, 24), A(27, 23), A(28, 22), A(29, 21), A(210, 20). Dla m = 10, n = 15: 3 wywołania: A(10, 7), A(10, 3), A(10, 1). Dla m = 1, n = 2100 + 1: 100 wywołań.
Odpowiedź: Dla m = 25, n = 25: 5 wywołań: A(26, 24), A(27, 23), A(28, 22), A(29, 21), A(210, 20). Dla m = 10, n = 15: 3 wywołania: A(10, 7), A(10, 3), A(10, 1). Dla m = 1, n = 2100 + 1: 100 wywołań.
Zadanie 2
Matura: maj 2026
Oryginalne zadanie: zad. 1.2
Poziom: rozszerzony
Dział: Algorytmika
Temat: Rekurencja
Matura · 1 pkt
Dana jest zdefiniowana rekurencyjnie funkcja A(m,n), gdzie m i n są dodatnimi liczbami całkowitymi. A(m,n)=⎩⎨⎧mA(2⋅m,2n)2⋅A(m,2n−1)+mgdyn=1gdyn>1oraznjestpodzielneprzez2gdyn>1oraznniejestpodzielneprzez2 Obliczenie wartości funkcji A(3,9) wprost z definicji wymaga trzech wywołań rekurencyjnych: A(3,4), A(6,2), A(12,1), ponieważ: A(3,9)=2⋅A(3,4)+3=2⋅A(6,2)+3=2⋅A(12,1)+3=2⋅12+3=27 Uzupełnij poniższą tabelę. Podaj wartości funkcji A(m,n) dla zadanych argumentów m i n:
m
n
A(m, n)
1
777
2⋅106
256⋅106
Uwaga: W swoich odpowiedziach możesz zapisać wynik podobnie jak wartości w pierwszych dwóch kolumnach (z wykorzystaniem operatorów mnożenia i potęgowania).
Odpowiedź do samodzielnego porównania z pełnym rozwiązaniem; bez automatycznej oceny.
Wskazówka
Sprawdź zależność A(m,n) = m · n.
Rozwiązanie krok po kroku
1Dla n=1 definicja daje A(m,1)=m.
2Dla n parzystego otrzymujemy (2m)(n/2)=mn; dla nieparzystego: 2m((n−1)/2)+m=mn.
3Podstawiamy dane z dwóch wierszy tabeli.
4777; 512⋅1012=512000000000000.
Odpowiedź: 777; 512⋅1012=512000000000000.
Zadanie 3
Matura: maj 2026
Oryginalne zadanie: zad. 1.3
Poziom: rozszerzony
Dział: Algorytmika
Temat: Rekurencja
Matura · 3 pkt
Dana jest zdefiniowana rekurencyjnie funkcja A(m,n), gdzie m i n są dodatnimi liczbami całkowitymi. A(m,n)=⎩⎨⎧mA(2⋅m,2n)2⋅A(m,2n−1)+mgdyn=1gdyn>1oraznjestpodzielneprzez2gdyn>1oraznniejestpodzielneprzez2 Obliczenie wartości funkcji A(3,9) wprost z definicji wymaga trzech wywołań rekurencyjnych: A(3,4), A(6,2), A(12,1), ponieważ: A(3,9)=2⋅A(3,4)+3=2⋅A(6,2)+3=2⋅A(12,1)+3=2⋅12+3=27 Uzupełnij tabelę. W drugiej kolumnie podaj liczbę wywołań rekurencyjnych funkcji A dla każdej wartości n podanej w tabeli (drugiego argumentu wywołania funkcji, pierwszy jest nieistotny w tym zadaniu). W trzeciej kolumnie podaj wyrażenie, którego wartość jest równa drugiemu argumentowi funkcji w i-tym wywołaniu rekurencyjnym dla wszystkich wartości i większych bądź równych 1 i mniejszych bądź równych całkowitej liczbie wywołań.
n – drugi argument wywołania funkcji
liczba wywołań rekurencyjnych
wartość drugiego argumentu A w i-tym wywołaniu rekurencyjnym
8
3
2i8 (lub 23−i)
2k
2k−1
gdzie k jest pewną liczbą całkowitą dodatnią większą od 2.
Odpowiedź do samodzielnego porównania z pełnym rozwiązaniem; bez automatycznej oceny.
Wskazówka
Rozważ osobno potęgę dwójki i liczbę o jeden mniejszą.
Rozwiązanie krok po kroku
1Dla n=2k każde dzielenie przez 2 obniża wykładnik o 1.
2Dla n=2k−1 stosujemy (n−1)/2 i otrzymujemy 2k−1−1.
3Kończymy przy n=1, stąd odpowiednio k i k−1 wywołań.
4Dla n=2k: k wywołań, drugi argument 2k−i. Dla n=2k−1: k−1 wywołań, drugi argument 2k−i−1.
Odpowiedź: Dla n=2k: k wywołań, drugi argument 2k−i. Dla n=2k−1: k−1 wywołań, drugi argument 2k−i−1.
Zadanie 4
Matura: maj 2026
Oryginalne zadanie: zad. 2.1
Poziom: rozszerzony
Dział: Algorytmika
Temat: Dodawanie pisemne
Matura · 1 pkt
Rozważamy dodawanie pisemne dwóch liczb zapisanych w systemie dziesiętnym, zilustrowane na przykładzie.
Przeniesienie
1
1
1
1
Liczba a
2
7
7
3
2
Liczba b
+
7
2
6
1
9
Suma
1
0
0
3
5
1
W tym przykładzie mamy 4 przeniesienia. Dla danych dwóch liczb: *a* i *b*, podaj, ile razy pojawiają się przeniesienia podczas ich dodawania.
Liczba a
Liczba b
Liczba przeniesień
37932
12528
3
88765
11111
456789
222222
Odpowiedź do samodzielnego porównania z pełnym rozwiązaniem; bez automatycznej oceny.
Wskazówka
Dodawaj cyfry od prawej strony, uwzględniając przeniesienie.
Rozwiązanie krok po kroku
188765 + 11111: każda suma cyfr jest mniejsza od 10.
2456789 + 222222: przeniesienia występują przy trzech pierwszych pozycjach od prawej strony.
Zapisz w pseudokodzie lub w wybranym języku programowania algorytm, który dla danych dwóch liczb całkowitych dodatnich a i b, o tej samej liczbie cyfr w zapisie dziesiętnym, obliczy liczbę przeniesień otrzymanych w trakcie ich dodawania pisemnego. Przykład: dla liczb 27732 i 72619 wynik to 4. Uwaga: Twój algorytm może operować wyłącznie na liczbach całkowitych i używać tylko zmiennych przechowujących pojedyncze liczby całkowite. W zapisie algorytmu możesz korzystać tylko z operatorów arytmetycznych: dodawania, odejmowania, mnożenia, dzielenia, dzielenia całkowitego i reszty z dzielenia; z operatorów logicznych, porównań, instrukcji sterujących, instrukcji przypisania lub samodzielnie napisanych funkcji i procedur wykorzystujących powyższe operacje. Zabronione jest używanie funkcji wbudowanych oraz operatorów innych niż wymienione, dostępnych w językach programowania, nie wolno zwłaszcza korzystać z tablic/list oraz żadnych funkcji zamiany z typu znakowego lub napisowego na liczbowy – i odwrotnie. Specyfikacja: Dane: a,b – dodatnie liczby całkowite o tej samej liczbie cyfr Wynik: p – liczba przeniesień otrzymanych w trakcie dodawania pisemnego liczb a i b
Odpowiedź do samodzielnego porównania z pełnym rozwiązaniem; bez automatycznej oceny.
Wskazówka
Ostatnią cyfrę uzyskasz przez mod 10, a usuniesz przez div 10.
Rozwiązanie krok po kroku
1Ustawiamy p=0 i przeniesienie=0.
2Dopóki a>0, sumujemy ostatnie cyfry i przeniesienie.
3Suma co najmniej 10 oznacza kolejne przeniesienie; inaczej zerujemy przeniesienie.
4Usuwamy ostatnie cyfry obu liczb i wypisujemy p.
5Algorytm zlicza przeniesienia, pobierając cyfry przez mod 10 i usuwając je przez div 10; uwzględnia przeniesienie z poprzedniej pozycji.
Python
defprzeniesienia(a, b):
p = 0
pamiec = 0while a > 0:
suma = a % 10 + b % 10 + pamiec
if suma >= 10:
pamiec = 1
p += 1else:
pamiec = 0
a //= 10
b //= 10return p
Odpowiedź: Algorytm zlicza przeniesienia, pobierając cyfry przez mod 10 i usuwając je przez div 10; uwzględnia przeniesienie z poprzedniej pozycji.
Zadanie 6
Matura: maj 2026
Oryginalne zadanie: zad. 4.1
Poziom: rozszerzony
Dział: Algorytmika
Temat: Hierarchia w korporacji
Matura · 1 pkt
W korporacji pracuje *n* osób, które na potrzeby zadania ponumerujemy liczbami 1, 2, ..., *n*. Pracownik numer 1 jest prezesem korporacji, a każdy z pozostałych pracowników ma dokładnie jednego bezpośredniego przełożonego. Numer bezpośredniego przełożonego pracownika *x* jest zawsze mniejszy od numeru tego pracownika. Prezes korporacji nie ma żadnego przełożonego. Przełożonym pracownika jest jego bezpośredni przełożony i każdy przełożony tego bezpośredniego przełożonego. Jeśli *x* jest (bezpośrednim) przełożonym *y*, to powiemy, że *y* jest (bezpośrednim) podwładnym *x*. Prezes jest przełożonym każdego pracownika. Przykład 1. Przełożonymi pracownika 7 są pracownicy 3, 2 i 1. Bezpośrednim przełożonym pracownika 7 jest pracownik 3. Pracownik 3 (podobnie jak 5 oraz 6) jest bezpośrednim podwładnym pracownika 2, a podwładnymi pracownika 2 są pracownicy 3, 5, 6 i 7. Zadanie 4.1. (0–1) Dla każdego pracownika z przykładowej hierarchii w korporacji (Rysunek 1.) określ, ilu ma on bezpośrednich podwładnych oraz ilu ma wszystkich podwładnych.
Numer pracownika
Liczba bezpośrednich podwładnych
Liczba wszystkich podwładnych
1
2
3
4
3
4
5
6
7
8
0
0
Odpowiedź do samodzielnego porównania z pełnym rozwiązaniem; bez automatycznej oceny.
Wskazówka
Strzałka prowadzi od podwładnego do bezpośredniego przełożonego.
Rozwiązanie krok po kroku
1Bezpośrednich podwładnych odczytujemy z krawędzi dochodzących do pracownika.
2Wszystkich podwładnych zliczamy w całym jego poddrzewie.