SStrefa Nauki w Elektryku
Informatyka

Algorytmika

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: początek, wczytanie danych, decyzja, dwie ścieżki i koniec.
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 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 . Jednym ze sposobów określenia rzędu tej funkcji jest popularna notacja omikron, zwana także notacją dużego . Wyszukiwanie binarne ma złożoność , a sortowanie bąbelkowe — 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ą:
Przykład: .

03Przykłady

Przykład · Analiza algorytmu wyszukiwania binarnego

  1. 1Mamy posortowaną tablicę elementów i szukamy wartości .
  2. 2Porównujemy ze środkowym elementem i odrzucamy połowę przedziału.
  3. 3Każdy krok zmniejsza przeszukiwany obszar dwukrotnie.
  4. 4Liczba kroków to około — zamiast do 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 , gdzie i są dodatnimi liczbami całkowitymi.



Obliczenie wartości funkcji wprost z definicji wymaga trzech wywołań rekurencyjnych: , , , ponieważ:



Uzupełnij poniższą tabelę. Podaj liczbę wywołań rekurencyjnych funkcji oraz wypisz wywołania rekurencyjne wraz z ich argumentami (w ostatnim wierszu podaj tylko liczbę wywołań rekurencyjnych).
mnliczba wywołań rekurencyjnych funkcji Awywołania rekurencyjne funkcji A
393, ,
  
1015  
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

  1. 1Nie wliczamy początkowego A(m,n); liczymy dopiero wywołania wykonane wewnątrz funkcji.
  2. 2Gdy n jest parzyste, podwajamy m i dzielimy n przez 2; gdy nieparzyste, m się nie zmienia, a n zastępujemy (n−1)/2.
  3. 3Powtarzamy aż drugi argument osiągnie 1.
  4. 4Dla m = , n = : 5 wywołań: A(, ), A(, ), A(, ), A(, ), A(, ). Dla m = 10, n = 15: 3 wywołania: A(10, 7), A(10, 3), A(10, 1). Dla m = 1, n = + 1: 100 wywołań.
Odpowiedź: Dla m = , n = : 5 wywołań: A(, ), A(, ), A(, ), A(, ), A(, ). Dla m = 10, n = 15: 3 wywołania: A(10, 7), A(10, 3), A(10, 1). Dla m = 1, n = + 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 , gdzie i są dodatnimi liczbami całkowitymi.



Obliczenie wartości funkcji wprost z definicji wymaga trzech wywołań rekurencyjnych: , , , ponieważ:



Uzupełnij poniższą tabelę. Podaj wartości funkcji dla zadanych argumentów i :
mnA(m, n)
1777 
 
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

  1. 1Dla n=1 definicja daje A(m,1)=m.
  2. 2Dla n parzystego otrzymujemy (2m)(n/2)=mn; dla nieparzystego: 2m((n−1)/2)+m=mn.
  3. 3Podstawiamy dane z dwóch wierszy tabeli.
  4. 4777; .
Odpowiedź: 777; .

Zadanie 3

Matura: maj 2026
Oryginalne zadanie: zad. 1.3
Poziom: rozszerzony
Dział: Algorytmika
Temat: Rekurencja
Matura · 3 pkt
Dana jest zdefiniowana rekurencyjnie funkcja , gdzie i są dodatnimi liczbami całkowitymi.



Obliczenie wartości funkcji wprost z definicji wymaga trzech wywołań rekurencyjnych: , , , ponieważ:



Uzupełnij tabelę. W drugiej kolumnie podaj liczbę wywołań rekurencyjnych funkcji A dla każdej wartości 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 -tym wywołaniu rekurencyjnym dla wszystkich wartości większych bądź równych 1 i mniejszych bądź równych całkowitej liczbie wywołań.
– drugi argument wywołania funkcjiliczba wywołań rekurencyjnychwartość drugiego argumentu A w -tym wywołaniu rekurencyjnym
83 (lub )
  
  
gdzie 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

  1. 1Dla każde dzielenie przez 2 obniża wykładnik o 1.
  2. 2Dla stosujemy i otrzymujemy .
  3. 3Kończymy przy n=1, stąd odpowiednio k i k−1 wywołań.
  4. 4Dla : wywołań, drugi argument . Dla : wywołań, drugi argument .
Odpowiedź: Dla : wywołań, drugi argument . Dla : wywołań, drugi argument .

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.
Przeniesienie111 1 
Liczba a 27732
Liczba b+72619
Suma100351
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 aLiczba bLiczba przeniesień
37932125283
8876511111 
456789222222 

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

  1. 188765 + 11111: każda suma cyfr jest mniejsza od 10.
  2. 2456789 + 222222: przeniesienia występują przy trzech pierwszych pozycjach od prawej strony.
  3. 388765 + 11111: 0 przeniesień. 456789 + 222222: 3 przeniesienia.
Odpowiedź: 88765 + 11111: 0 przeniesień. 456789 + 222222: 3 przeniesienia.

Zadanie 5

Matura: maj 2026
Oryginalne zadanie: zad. 2.2
Poziom: rozszerzony
Dział: Algorytmika
Temat: Dodawanie pisemne
Matura · 4 pkt
Zapisz w pseudokodzie lub w wybranym języku programowania algorytm, który dla danych dwóch liczb całkowitych dodatnich i , 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:
– dodatnie liczby całkowite o tej samej liczbie cyfr

Wynik:
– liczba przeniesień otrzymanych w trakcie dodawania pisemnego liczb i

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

  1. 1Ustawiamy p=0 i przeniesienie=0.
  2. 2Dopóki a>0, sumujemy ostatnie cyfry i przeniesienie.
  3. 3Suma co najmniej 10 oznacza kolejne przeniesienie; inaczej zerujemy przeniesienie.
  4. 4Usuwamy ostatnie cyfry obu liczb i wypisujemy p.
  5. 5Algorytm zlicza przeniesienia, pobierając cyfry przez mod 10 i usuwając je przez div 10; uwzględnia przeniesienie z poprzedniej pozycji.
Python
def przeniesienia(a, b):
    p = 0
    pamiec = 0
    while a > 0:
        suma = a % 10 + b % 10 + pamiec
        if suma >= 10:
            pamiec = 1
            p += 1
        else:
            pamiec = 0
        a //= 10
        b //= 10
    return 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 pracownikaLiczba bezpośrednich podwładnychLiczba wszystkich podwładnych
1  
234
3  
4  
5  
6  
7  
800
Hierarchia pracowników korporacji – strzałki wskazują przełożonych

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

  1. 1Bezpośrednich podwładnych odczytujemy z krawędzi dochodzących do pracownika.
  2. 2Wszystkich podwładnych zliczamy w całym jego poddrzewie.
  3. 3Prezes ma 7 podwładnych, w tym 2 bezpośrednich.
  4. 4
    Pracownikbezpośredni podwładniwszyscy podwładni
    127
    234
    311
    411
    500
    600
    700
    800
Odpowiedź:
Pracownikbezpośredni podwładniwszyscy podwładni
127
234
311
411
500
600
700
800