Algorytmy na maturę rozszerzoną z informatyki — kod i złożoność

Lista algorytmów maturalnych jest krótka i od lat ta sama. Problem polega na tym, że sama lista nic nie daje: uczeń wie, że „trzeba znać sito", ale nie wie, czym się różni od testu pierwszości, dlaczego wewnętrzna pętla zaczyna się akurat od kwadratu i co odpowiedzieć, gdy arkusz pyta o złożoność.

Ten wpis idzie po każdym algorytmie osobno i przy każdym odpowiada na cztery pytania: kiedy pojawia się na maturze, jak wygląda kod, jaka jest jego złożoność i skąd się bierze, oraz na czym uczniowie się na nim wykładają. Na końcu jest sekcja o rozpoznawaniu, którego algorytmu oczekuje treść zadania — bo to zwykle trudniejsze niż samo napisanie kodu.

Złożoność obliczeniowa: jak ją czytać i jak ją oszacować#

Złożoność to odpowiedź na pytanie „ile razy więcej pracy wykona program, gdy danych będzie dziesięć razy więcej". Nie mierzy się jej w sekundach, tylko w liczbie operacji zależnej od rozmiaru danych, oznaczanego zwykle jako n.

Jak oszacować złożoność, patrząc na pętle

Nie trzeba niczego liczyć na kartce. Wystarczy przejrzeć kod i zadać sobie trzy pytania.

Pytanie 1: ile pętli jest zagnieżdżonych jedna w drugiej? Każdy poziom zagnieżdżenia, w którym pętla przechodzi przez wszystkie dane, mnoży koszt przez n. Jedna pętla to n, pętla w pętli to n², trzy poziomy to n³.

# O(n) - jedna petla po danych
for x in dane:
  suma += x

# O(n) - dwie petle OBOK siebie, koszt sie dodaje: n + n = 2n
for x in dane:
  suma += x
for x in dane:
  if x > maks:
      maks = x

# O(n^2) - petla W petli, koszt sie mnozy
for i in range(len(dane)):
  for j in range(len(dane)):
      if dane[i] == dane[j]:
          pary += 1

Pytanie 2: czy licznik pętli rośnie o jeden, czy zmienia się razy dwa? Jeżeli zakres w każdym kroku dzieli się na pół albo zmienna mnoży się przez dwa — złożoność jest logarytmiczna. Milion podzielony na pół dwadzieścia razy daje jedynkę, i stąd bierze się „dwadzieścia kroków dla miliona elementów".

ile = 0
n = 1000000
while n > 1:
  n = n // 2
  ile += 1
print(ile)   # 19

Pytanie 3: czy pętla wewnętrzna zależy od zewnętrznej? Jeśli druga pętla startuje od i + 1 albo kończy się na i, liczba obiegów to nie n², tylko mniej więcej połowa tego — ale nadal jest to złożoność kwadratowa. Stałych i podziału przez dwa się nie zapisuje: interesuje nas tempo wzrostu, a nie dokładna liczba.

Wniosek: zanim uruchomisz program na właściwym pliku, pomnóż w głowie liczbę wierszy przez liczbę zagnieżdżonych przejść. Wynik rzędu milionów jest w porządku, rzędu miliardów — nie. Systematycznie temat rozwija dział algorytmiki i logiki.

Sprawdzanie pierwszości: dlaczego pierwiastek naprawdę wystarczy#

Test pierwszości pojawia się albo jako samodzielny podpunkt („ile liczb pierwszych jest w pliku"), albo jako cegiełka w większym zadaniu — przy liczbach będących sumą cyfr, przy palindromach pierwszych, przy bliźniakach. Wraca niemal w każdej sesji.

def pierwsza_naiwnie(n):
  if n < 2:
      return False
  for d in range(2, n):
      if n % d == 0:
          return False
  return True

Dowód intuicyjny: dzielniki chodzą w parach

Weź liczbę 36. Jej dzielniki to 1, 2, 3, 4, 6, 9, 12, 18, 36. Zapisz je w pary, których iloczyn daje 36:

Rozumowanie w jednym zdaniu: jeżeli n rozkłada się na iloczyn a razy b, to niemożliwe jest, żeby oba czynniki były większe od pierwiastka z n — ich iloczyn byłby wtedy większy niż n. Zatem co najmniej jeden z nich jest mniejszy lub równy pierwiastkowi. Jeśli więc nie znalazłeś żadnego dzielnika do pierwiastka włącznie, żadnego nie ma w ogóle.

def pierwsza(n):
  if n < 2:
      return False
  d = 2
  while d * d <= n:
      if n % d == 0:
          return False
      d += 1
  return True

Sito Eratostenesa i pytanie o kwadrat#

Sito odpowiada na inne pytanie niż test pierwszości: nie „czy ta liczba jest pierwsza", tylko „które liczby w całym zakresie są pierwsze". Typowa treść maturalna brzmi „wypisz wszystkie liczby pierwsze mniejsze od miliona" albo „sprawdź, ile liczb z pliku jest pierwszych", gdzie plik ma dziesiątki tysięcy wierszy.

Idea: robisz listę wszystkich liczb, a potem wykreślasz wielokrotności. To, co zostanie niewykreślone, jest pierwsze.

def sito(n):
  czy_pierwsza = [True] * (n + 1)
  czy_pierwsza[0] = czy_pierwsza[1] = False

  i = 2
  while i * i <= n:
      if czy_pierwsza[i]:
          for j in range(i * i, n + 1, i):
              czy_pierwsza[j] = False
      i += 1

  return [x for x in range(n + 1) if czy_pierwsza[x]]

print(sito(30))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Dlaczego wewnętrzna pętla startuje od i razy i

To jedno z ulubionych pytań w części teoretycznej, bo sprawdza zrozumienie, a nie pamięć. Odpowiedź jest prosta: wszystko poniżej kwadratu zostało już wykreślone wcześniej.

Weź i równe 5. Wielokrotności piątki to 5, 10, 15, 20, 25, 30, ... Ale:

• 10 to 5 razy 2 — wykreśliła je już pętla dla dwójki,
• 15 to 5 razy 3 — wykreśliła je pętla dla trójki,
• 20 to 5 razy 4, a czwórka jest wielokrotnością dwójki — też już wykreślone,
• 25 to 5 razy 5 — pierwsza wielokrotność piątki, której mniejszy czynnik nie jest mniejszy od piątki.

Ogólnie: każda wielokrotność i postaci i razy k, gdzie k jest mniejsze od i, ma mniejszy czynnik k i została skreślona, gdy pętla zewnętrzna była przy k (albo przy dzielniku pierwszym liczby k). Pierwsza wielokrotność wymagająca uwagi to i razy i.

Rozkład na czynniki pierwsze#

Zadanie brzmi zwykle: „dla każdej liczby z pliku podaj jej największy czynnik pierwszy", „znajdź liczby mające dokładnie trzy różne dzielniki pierwsze" albo „wypisz liczby będące iloczynem dwóch liczb pierwszych". Wszystkie sprowadzają się do jednej procedury.

def czynniki(n):
  wynik = []
  d = 2
  while d * d <= n:
      while n % d == 0:
          wynik.append(d)
          n = n // d
      d += 1
  if n > 1:
      wynik.append(n)
  return wynik

print(czynniki(60))    # [2, 2, 3, 5]
print(czynniki(97))    # [97]
print(czynniki(1024))  # osiem dwojek

Dwa miejsca w tym kodzie wyglądają na drobiazgi, a decydują o poprawności.

Warunek if n > 1 na końcu. Pętla chodzi tylko do pierwiastka z bieżącej wartości. Jeśli po wszystkich podziałach zostaje coś większego od jedynki, jest to liczba pierwsza większa od pierwiastka — i to ostatni czynnik. Bez tej linijki rozkład liczby 14 dałby samą dwójkę, a siódemka przepadłaby. Dla liczby pierwszej funkcja zwróciłaby pustą listę.

Dzielenie podwójnym ukośnikiem. Zapis n = n / d zamienia liczbę na typ zmiennoprzecinkowy. Po kilku obiegach reszta z dzielenia przestaje wychodzić dokładnie zerowa i rozkład się rozjeżdża — po cichu, bez komunikatu o błędzie.

Złożoność: O(√n) w najgorszym przypadku, czyli gdy n jest pierwsze i pętla przechodzi cały zakres. W typowym przypadku znacznie szybciej, bo każdy znaleziony czynnik zmniejsza liczbę, a razem z nią pierwiastek będący granicą pętli. Dlatego warunek d * d <= n musi porównywać się z bieżącą wartością, a nie z zapamiętaną kopią pierwotnej liczby.

Algorytm Euklidesa: odejmowanie, modulo i NWW#

NWD pojawia się przy skracaniu ułamków, przy zadaniach o wspólnej mierze, o synchronizacji cykli, a także jako narzędzie w podpunktach, które wprost o niego nie proszą. Sam algorytm ma dwie wersje i różnica między nimi jest częstym pytaniem egzaminacyjnym.

Podstawa obu: NWD dwóch liczb nie zmienia się, gdy większą zastąpimy różnicą lub resztą z dzielenia. Skoro wspólny dzielnik dzieli a i b, to dzieli również a minus b.

def nwd_odejmowanie(a, b):
  while a != b:
      if a > b:
          a = a - b
      else:
          b = b - a
  return a

print(nwd_odejmowanie(48, 18))   # 6

def nwd(a, b):
  while b != 0:
      a, b = b, a % b
  return a

print(nwd(48, 18))    # 6
print(nwd(1000000, 3))  # 1 - dwa obiegi petli

NWW przez NWD

Najmniejszej wspólnej wielokrotności nie liczy się osobnym algorytmem. Wynika z zależności: iloczyn dwóch liczb równa się iloczynowi ich NWD i NWW.

def nww(a, b):
  return a // nwd(a, b) * b

print(nww(4, 6))    # 12

# dla calej listy - skladanie parami
def nwd_listy(liczby):
  wynik = liczby[0]
  for x in liczby[1:]:
      wynik = nwd(wynik, x)
  return wynik

print(nwd_listy([24, 36, 60]))   # 12

Pułapka: dla pary zawierającej zero wzór na NWW dzieli przez zero. Jeśli w danych mogą być zera, warunek trzeba dopisać jawnie.

Schemat Hornera: konwersja systemów i wartość wielomianu#

Horner to jeden pomysł w dwóch zastosowaniach, które na pierwszy rzut oka nie mają ze sobą nic wspólnego. Warto je zobaczyć razem, bo wtedy schemat zostaje w głowie na dobre.

Pomysł: zamiast liczyć potęgi, wyciągasz podstawę przed nawias tyle razy, ile się da. Liczba 1101 w systemie dwójkowym to zwykle zapisywane jako suma potęg:

Po wyciągnięciu dwójki przed nawias:

Potęgowanie zniknęło. Zostały same mnożenia i dodawania, po jednym na cyfrę.

def horner(zapis, podstawa):
  wynik = 0
  for cyfra in zapis:
      wynik = wynik * podstawa + int(cyfra)
  return wynik

print(horner("1101", 2))    # 13
print(horner("777", 8))     # 511
print(horner("2024", 10))   # 2024

# system szesnastkowy
CYFRY = "0123456789ABCDEF"

def horner16(zapis):
  wynik = 0
  for znak in zapis.upper():
      wynik = wynik * 16 + CYFRY.index(znak)
  return wynik

print(horner16("FF"))       # 255

def wartosc(wspolczynniki, x):
  wynik = 0
  for w in wspolczynniki:
      wynik = wynik * x + w
  return wynik

# 2x^3 - 6x^2 + 2x - 1 dla x = 3
print(wartosc([2, -6, 2, -1], 3))   # 5

Wyszukiwanie binarne: dwa błędy, które je psują#

Wyszukiwanie binarne działa wyłącznie na danych posortowanych. Za to wtedy jest nie do pobicia: dla miliona elementów odpowiada po około dwudziestu porównaniach, bo każdy krok odrzuca połowę pozostałego zakresu.

Na maturze pojawia się w dwóch rolach: jako samodzielne zadanie z pseudokodem w części teoretycznej i jako narzędzie w części praktycznej, gdy trzeba wielokrotnie sprawdzać obecność wartości w dużym zbiorze danych.

def szukaj(t, x):
  lewy = 0
  prawy = len(t) - 1
  while lewy <= prawy:
      srodek = (lewy + prawy) // 2
      if t[srodek] == x:
          return srodek
      elif t[srodek] < x:
          lewy = srodek + 1
      else:
          prawy = srodek - 1
  return -1

dane = [1, 4, 7, 9, 12, 15, 20]
print(szukaj(dane, 12))   # 4
print(szukaj(dane, 13))   # -1

Błąd pierwszy: warunek pętli bez równości

Zapis while lewy < prawy wygląda niewinnie, a gubi przypadek, w którym zakres zwęził się do jednego elementu — czyli dokładnie ten, w którym często siedzi szukana wartość. Program zwraca „nie znaleziono" dla elementów, które w tablicy są. Najłatwiej to wyłapać na danych brzegowych: tablica jednoelementowa oraz szukanie pierwszego i ostatniego elementu.

Błąd drugi: liczenie środka pojedynczym ukośnikiem

(lewy + prawy) / 2 daje liczbę zmiennoprzecinkową, a listy nie da się indeksować liczbą z kropką — program kończy się wyjątkiem. To akurat błąd głośny, więc łatwy. Gorsza jest jego wersja z round(): zaokrąglenie w górę przy pewnych układach granic sprawia, że zakres przestaje się kurczyć i pętla nigdy się nie kończy. Środek liczy się podwójnym ukośnikiem — zawsze.

Wniosek: jeśli szukasz w danych wielokrotnie, masz dwie drogi — posortować raz i szukać binarnie, albo wrzucić dane do zbioru set i sprawdzać operatorem in. Druga jest krótsza i na maturze zwykle wystarcza; pierwszą musisz umieć napisać, bo teoria o nią pyta. Wersje do przećwiczenia znajdziesz w quizach programistycznych.

Sortowanie: bąbelkowe, przez wstawianie, szybkie — i kiedy wystarczy sorted()#

Zacznijmy od wniosku, bo jest zaskakująco jednoznaczny: w części praktycznej sortujesz wbudowaną funkcją, chyba że treść zadania wyraźnie każe zapisać własny algorytm. sorted() używa algorytmu o złożoności O(n log n), jest przetestowany lepiej niż cokolwiek, co napiszesz pod presją czasu, i obsługuje sortowanie po kluczu jedną linijką.

liczby = [5, 2, 9, 1]
print(sorted(liczby))                 # [1, 2, 5, 9]
print(sorted(liczby, reverse=True))   # [9, 5, 2, 1]

osoby = [("Kowalski", 3, 45), ("Nowak", 1, 45), ("Abacki", 2, 12)]

# po liczbie punktow malejaco
print(sorted(osoby, key=lambda o: o[2], reverse=True))

# po punktach malejaco, a przy remisie po nazwisku rosnaco
print(sorted(osoby, key=lambda o: (-o[2], o[0])))

Po co więc uczyć się sortowań ręcznie? Bo część teoretyczna pyta o ich własności: ile porównań wykona algorytm, jak zachowa się na danych już posortowanych, który jest stabilny. Na te pytania nie odpowie się, znając tylko nazwę funkcji.

def babelkowe(t):
  n = len(t)
  for i in range(n - 1):
      zamiana = False
      for j in range(n - 1 - i):
          if t[j] > t[j + 1]:
              t[j], t[j + 1] = t[j + 1], t[j]
              zamiana = True
      if not zamiana:
          break
  return t

Zakres wewnętrznej pętli, range(n - 1 - i), bierze się stąd, że po i przebiegach i największych elementów siedzi już na swoich miejscach na końcu i nie ma sensu ich ruszać. Pominięcie odjęcia jedynki daje wyjście poza listę.

def przez_wstawianie(t):
  for i in range(1, len(t)):
      klucz = t[i]
      j = i - 1
      while j >= 0 and t[j] > klucz:
          t[j + 1] = t[j]
          j -= 1
      t[j + 1] = klucz
  return t

def szybkie(t):
  if len(t) <= 1:
      return t
  os = t[len(t) // 2]
  mniejsze = [x for x in t if x < os]
  rowne    = [x for x in t if x == os]
  wieksze  = [x for x in t if x > os]
  return szybkie(mniejsze) + rowne + szybkie(wieksze)

print(szybkie([5, 2, 9, 1, 5, 6]))   # [1, 2, 5, 5, 6, 9]

Wniosek: naucz się rozpoznawać trzy sortowania z kodu lub pseudokodu i umieć powiedzieć, jaka jest ich złożoność oraz jak zachowają się na danych już uporządkowanych. Do samego sortowania w zadaniu praktycznym używaj sorted().

Fibonacci: rekurencja wykładnicza kontra iteracja liniowa#

Ciąg Fibonacciego sam w sobie jest prosty — każdy wyraz to suma dwóch poprzednich. Na maturze służy do czegoś innego: jest standardowym przykładem pokazującym, że poprawny algorytm może być bezużyteczny.

def fib_rek(n):
  if n <= 1:
      return n
  return fib_rek(n - 1) + fib_rek(n - 2)

Policzmy, ile wywołań funkcji potrzeba, żeby dostać jedną liczbę. Wywołanie dla 5 wymaga wywołań dla 4 i 3; wywołanie dla 4 znowu wymaga dla 3 i 2 — a wynik dla trójki nie jest nigdzie zapamiętany, więc liczy się drugi raz od zera.

def fib(n):
  a, b = 0, 1
  for _ in range(n):
      a, b = b, a + b
  return a

print(fib(50))   # 12586269025 - natychmiast

pamiec = {}

def fib_pam(n):
  if n <= 1:
      return n
  if n in pamiec:
      return pamiec[n]
  pamiec[n] = fib_pam(n - 1) + fib_pam(n - 2)
  return pamiec[n]

Wniosek dla całej rekurencji, nie tylko dla Fibonacciego: rekurencja jest bezpieczna, gdy każde wywołanie generuje jedno wywołanie zależne (jak w silni czy w algorytmie Euklidesa). Gdy generuje dwa lub więcej, a wyniki nie są zapamiętywane, koszt rośnie wykładniczo. Rozpoznasz to po tym, że po prawej stronie znaku równości nazwa funkcji pojawia się więcej niż raz.

Algorytmy na napisach: palindrom, anagram, zliczanie wystąpień#

Zadania tekstowe wracają w każdej sesji, zwykle jako podpunkt większego zadania z plikiem: „ile słów w pliku to palindromy", „które pary wyrazów są anagramami", „jaka litera występuje najczęściej".

Palindrom

# 1. najkrocej - porownanie z odwroconym napisem
def palindrom(s):
  return s == s[::-1]

# 2. dwa wskazniki od konca i od poczatku
def palindrom2(s):
  i = 0
  j = len(s) - 1
  while i < j:
      if s[i] != s[j]:
          return False
      i += 1
      j -= 1
  return True

# 3. wersja odporna na wielkosc liter i spacje
def palindrom3(s):
  czysty = "".join(z.lower() for z in s if z.isalnum())
  return czysty == czysty[::-1]

print(palindrom("kajak"))              # True
print(palindrom3("Kobyla ma maly bok"))  # True

Zapis s[::-1] to wycinek z krokiem minus jeden, czyli napis od końca. Warto go umieć, bo skraca też odwracanie liczby czy listy. Pułapka: liczby nie da się odwrócić wycinkiem — najpierw str(n), a przy porównaniu z powrotem int().

Anagram

# 1. przez sortowanie liter - O(n log n)
def anagram(a, b):
  return sorted(a.lower()) == sorted(b.lower())

# 2. przez zliczanie liter - O(n)
def anagram2(a, b):
  if len(a) != len(b):
      return False
  licznik = {}
  for z in a.lower():
      licznik[z] = licznik.get(z, 0) + 1
  for z in b.lower():
      if z not in licznik:
          return False
      licznik[z] -= 1
      if licznik[z] == 0:
          del licznik[z]
  return len(licznik) == 0

print(anagram("Barok", "Kobra"))   # True

Pułapka: porównywanie bez ujednolicenia wielkości liter. „Barok" i „kobra" to anagramy, ale wielka litera na początku sprawia, że kod bez lower() odpowie przecząco. To samo dotyczy polskich znaków — jeśli treść je dopuszcza, sprawdź, czy plik czytasz z właściwym kodowaniem.

Zliczanie wystąpień

tekst = "matura z informatyki"

licznik = {}
for znak in tekst:
  if znak != " ":
      licznik[znak] = licznik.get(znak, 0) + 1

# najczestszy znak
najczestszy = max(licznik, key=licznik.get)
print(najczestszy, licznik[najczestszy])

# posortowane malejaco po liczbie wystapien,
# a przy remisie alfabetycznie
for znak, ile in sorted(licznik.items(), key=lambda p: (-p[1], p[0])):
  print(znak, ile)

Zliczanie w słowniku ma złożoność liniową i jest właściwą odpowiedzią wszędzie tam, gdzie odruch podpowiada pętlę w pętli z licznikiem. Ten drugi zapis daje złożoność kwadratową i na dużym pliku przestaje się liczyć w rozsądnym czasie. Więcej o strukturach danych w Pythonie znajdziesz w dziale teorii programowania.

Jak rozpoznać, którego algorytmu chce od Ciebie zadanie#

To umiejętność, którą trenuje się osobno — i której brak jest częstszą przyczyną straty punktów niż nieznajomość kodu. Treści maturalne rzadko mówią wprost „użyj algorytmu Euklidesa". Mówią za to rzeczy, które jednoznacznie na niego wskazują.

Trzy dodatkowe wskazówki, które pomagają wybrać dobrze:

• Sprawdź rozmiar danych, zanim wybierzesz metodę. Plik z dwudziestoma liczbami wybaczy wszystko. Plik z setkami tysięcy wierszy wyklucza rozwiązania kwadratowe, a to często jedyna podpowiedź, że zadanie oczekuje sita, słownika albo wyszukiwania binarnego.
• Zwróć uwagę, czy pytanie dotyczy jednej wartości, czy zakresu. To rozstrzyga między testem pierwszości a sitem, między pojedynczym przejściem a przygotowaniem struktury pomocniczej.
• Sprawdź, czy podpunkty się na sobie opierają. Zadania maturalne mają zwykle cztery lub pięć podpunktów liczonych na tych samych danych. Jeśli pierwszy każe wczytać dane, a trzeci pyta o liczby pierwsze — sito policzone raz na początku obsłuży wszystkie kolejne podpunkty.

Plan powtórki: dwa tygodnie po pół godziny dziennie#

Algorytmów maturalnych jest tyle, że da się je przerobić w dwa tygodnie, jeśli robi się to systematycznie i pisząc kod z pamięci, a nie czytając gotowy. Sprawdzianem nie jest „rozumiem", tylko „potrafię odtworzyć na pustej kartce".

Tydzień pierwszy — schematy z pamięci. Każdego dnia jeden algorytm: piszesz go bez zaglądania, uruchamiasz na trzech zestawach danych (typowym, brzegowym i pustym), a potem porównujesz ze wzorcem.

1. Test pierwszości do pierwiastka wraz z obsługą liczb mniejszych od dwóch.
2. Sito Eratostenesa — ze świadomym uzasadnieniem startu od kwadratu.
3. Rozkład na czynniki pierwsze wraz z warunkiem końcowym.
4. Algorytm Euklidesa w obu wersjach oraz NWW.
5. Schemat Hornera w dwóch zastosowaniach: konwersja i wielomian.
6. Wyszukiwanie binarne — z testem na tablicy jedno- i dwuelementowej.
7. Fibonacci iteracyjnie oraz trzy funkcje na napisach.

Tydzień drugi — zadania, nie algorytmy. Bierzesz arkusze z poprzednich sesji i przed napisaniem choćby jednej linijki zapisujesz na brudno: który algorytm, jaka złożoność, ile jest danych. Dopiero potem kodujesz. To ćwiczenie na rozpoznawanie, a nie na pisanie — i to ono najbardziej się opłaca.

Uczysz się w technikum informatycznym? Prowadzimy też przygotowanie do kwalifikacji INF.02, INF.03 i INF.04. Zobacz egzaminy zawodowe →