Matura 2027 PRO

Przykład 1. Najprostszy algorytm

Problem: wczytaj dwie liczby i wypisz większą.

Dane wejściowe: a, b.

Wynik: większa z liczb.

if a > b:
    print(a)
else:
    print(b)

Dlaczego działa? Są tylko dwa przypadki: a>b albo a≤b. W obu algorytm zwraca liczbę nie mniejszą od drugiej.

Wniosek / wynik: Dlaczego działa? Są tylko dwa przypadki: a>b albo a≤b. W obu algorytm zwraca liczbę nie mniejszą od drugiej.

Przykład 2. Pole prostokąta

Problem: dla boków a i b oblicz pole.

Wejście: a, b.

Przetwarzanie: P=a·b.

Wyjście: P.

a = float(input())
b = float(input())
P = a * b
print(P)

Wniosek / wynik: Wyjście: P.

Przykład 3. Śledzenie wartości zmiennej

Treść: Co wypisze kod?

x = 4
x = x + 3
x = 2 * x
print(x)

Po pierwszej linii x=4, po drugiej x=7, po trzeciej x=14.

Wynik: 14.

Przykład 4. Parzystość liczby

Problem: sprawdź, czy liczba n jest parzysta.

Klucz: liczba jest parzysta wtedy i tylko wtedy, gdy reszta z dzielenia przez 2 wynosi 0.

if n % 2 == 0:
    print("parzysta")
else:
    print("nieparzysta")

Wniosek / wynik: Klucz: liczba jest parzysta wtedy i tylko wtedy, gdy reszta z dzielenia przez 2 wynosi 0.

Przykład 5. Suma liczb od 1 do n

Problem: oblicz 1+2+...+n.

suma = 0
for i in range(1, n + 1):
    suma += i
print(suma)

Dlaczego startujemy od 0? Zero jest elementem neutralnym dodawania. Nie zmienia wyniku pierwszego dodania.

Wniosek / wynik: Dlaczego startujemy od 0? Zero jest elementem neutralnym dodawania. Nie zmienia wyniku pierwszego dodania.

Przykład 6. Pętla while

Problem: ile razy trzeba podzielić dodatnią liczbę n przez 2 całkowicie, aż stanie się mniejsza od 2?

k = 0
while n >= 2:
    n //= 2
    k += 1
print(k)

Wniosek / wynik: Problem: ile razy trzeba podzielić dodatnią liczbę n przez 2 całkowicie, aż stanie się mniejsza od 2?

Przykład 7. Maksimum w tablicy

Problem: znajdź największy element listy.

Błędny pomysł: maks = 0. Dla listy [-8,-3,-11] wynik byłby błędny.

Poprawnie:

maks = dane[0]
for x in dane[1:]:
    if x > maks:
        maks = x
print(maks)

Prześledzenie dla [5,2,9,4]: maks=5 → 5 → 9 → 9.

Złożoność: O(n).

Wniosek / wynik: Złożoność: O(n).

Przykład 8. Minimum i jego pozycja

min_w = dane[0]
min_i = 0
for i in range(1, len(dane)):
    if dane[i] < min_w:
        min_w = dane[i]
        min_i = i

Przechowujemy nie tylko wartość, ale również indeks.

Wniosek / wynik: Przechowujemy nie tylko wartość, ale również indeks.

Przykład 9. Ile liczb jest dodatnich?

ile = 0
for x in dane:
    if x > 0:
        ile += 1

Znaczenie zmiennej ile: po przetworzeniu kolejnych elementów przechowuje liczbę dodatnich elementów już obejrzanych.

Wniosek / wynik: Znaczenie zmiennej ile: po przetworzeniu kolejnych elementów przechowuje liczbę dodatnich elementów już obejrzanych.

Przykład 10. Suma tylko liczb parzystych

s = 0
for x in dane:
    if x % 2 == 0:
        s += x

Przykład 11. Czy x występuje w danych?

znaleziono = False
for a in dane:
    if a == x:
        znaleziono = True
        break

Najlepszy przypadek: O(1), gdy element jest pierwszy.

Najgorszy przypadek: O(n).

Wniosek / wynik: Najgorszy przypadek: O(n).

Przykład 12. Niezmiennik maksimum

Dla algorytmu maksimum niezmiennik brzmi:

Na początku k=1 i maks=dane[0], więc własność jest prawdziwa. Każdy kolejny element albo zastępuje maks, albo nie — więc własność pozostaje prawdziwa.

Wniosek / wynik: Na początku k=1 i maks=dane[0], więc własność jest prawdziwa. Każdy kolejny element albo zastępuje maks, albo nie — więc własność pozostaje prawdziwa.

Przykład 13. Analiza dwóch pętli

for i in range(n):
    for j in range(n):
        wykonaj_operacje()

Operacja wykona się n·n=n² razy.

Złożoność: O(n²).

Przykład 14. NWD(84,30)

a = 84
b = 30
while b != 0:
    a, b = b, a % b
print(a)

84 mod 30=24 → 30 mod 24=6 → 24 mod 6=0.

Odpowiedź: NWD=6.

Złożoność: O(log min(a,b)).

Przykład 15. Test pierwszości do √n

Jeśli n ma dzielnik większy od √n, to drugi odpowiadający dzielnik jest mniejszy od √n. Wystarczy więc sprawdzać do pierwiastka.

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

Złożoność: O(√n).

Wniosek / wynik: Złożoność: O(√n).

Przykład 16. Test maksimum

Dla algorytmu maksimum warto sprawdzić:

[5] → 5, [-4,-1,-9] → -1, [3,3,3] → 3, [100,-5,0] → 100.

Wniosek / wynik: [5] → 5, [-4,-1,-9] → -1, [3,3,3] → 3, [100,-5,0] → 100.

Przykład 17. Najdłuższa seria liczb dodatnich

Treść zadania: Dany jest ciąg liczb całkowitych. Wyznacz długość najdłuższego spójnego fragmentu składającego się wyłącznie z liczb dodatnich.

Pomysł: przechowujemy długość aktualnej serii oraz najlepszy wynik.

akt = 0
naj = 0
for x in dane:
    if x > 0:
        akt += 1
        if akt > naj:
            naj = akt
    else:
        akt = 0
print(naj)

Dlaczego reset do zera? Liczba niedodatnia przerywa bieżącą spójną serię.

Złożoność: O(n).

Test: [1,2,-1,3,4,5,0,7] → 3.

Wniosek / wynik: Test: [1,2,-1,3,4,5,0,7] → 3.

Przykład 18. Druga największa różna wartość

Treść zadania: Dla listy zawierającej co najmniej dwie różne liczby znajdź drugą największą różną wartość.

Idea: przechowujemy największą i drugą największą różną wartość.

naj1 = None
naj2 = None

for x in dane:
    if naj1 is None or x > naj1:
        if x != naj1:
            naj2 = naj1
        naj1 = x
    elif x != naj1 and (naj2 is None or x > naj2):
        naj2 = x

print(naj2)

Test: [7,3,7,5,2] → 5.

Pułapka: druga największa wartość różna nie oznacza drugiego elementu po sortowaniu z duplikatami.

Złożoność: O(n).

Wniosek / wynik: Złożoność: O(n).

Przykład rozszerzony. Druga największa różna wartość

Treść zadania: Dla tablicy [7,3,7,5,2] znajdź drugą największą różną wartość bez sortowania całej tablicy.

Pomysł: przechowujemy dwie wartości: największą oraz drugą największą różną od niej.

Przebieg: po 7 mamy naj1=7, naj2=None; 3 daje naj2=3; kolejne 7 pomijamy jako duplikat; 5 podnosi naj2 do 5; 2 nic nie zmienia.

Odpowiedź: 5.

Złożoność: O(n), pamięć O(1).

Przykład rozszerzony. Czy algorytm maksimum jest poprawny?

Treść zadania: Oceń kod maks=0; for x in dane: if x>maks: maks=x dla danych [-8,-3,-11].

Żaden element nie jest większy od 0, więc wynik pozostanie 0, choć 0 nie występuje w tablicy.

Odpowiedź: algorytm jest błędny; należy rozpocząć od maks=dane[0].

Przypadek brzegowy, który ujawnia błąd: wszystkie liczby ujemne.

Przykład 1. Typ wyniku

Treść: Jaki typ ma wynik działania 7 / 2 w Pythonie?

Operator / wykonuje dzielenie rzeczywiste.

Odpowiedź: float, wartość 3.5.

Przykład 2. Dzielenie całkowite i modulo

Treść: Oblicz wartości 17//5 oraz 17%5.

17=3·5+2.

Odpowiedź: 3 i 2.

Przykład 3. Wczytanie liczby

n = int(input())
print(n * 2)

Dla wejścia 7 program wypisze 14.

Wniosek / wynik: Dla wejścia 7 program wypisze 14.

Przykład 4. Indeksowanie

dane = [10, 20, 30, 40]
print(dane[2])

Wynik: 30.

Przykład 5. Przejście po liście

s = 0
for x in dane:
    s += x

Po pętli s jest sumą elementów listy.

Wniosek / wynik: Po pętli s jest sumą elementów listy.

Przykład 6. Indeks i wartość

for i, x in enumerate(dane):
    print(i, x)

enumerate jest wygodne, gdy potrzebujemy jednocześnie indeksu i wartości.

Wniosek / wynik: enumerate jest wygodne, gdy potrzebujemy jednocześnie indeksu i wartości.

Przykład 7. Liczenie cyfr w napisie

ile = 0
for znak in s:
    if znak.isdigit():
        ile += 1

Problem: policz znaki będące cyframi.

Wniosek / wynik: Problem: policz znaki będące cyframi.

Przykład 8. Palindrom

Treść: Sprawdź, czy napis jest palindromem.

if s == s[::-1]:
    print("TAK")
else:
    print("NIE")

Odwrócony napis porównujemy z oryginałem.

Wniosek / wynik: Odwrócony napis porównujemy z oryginałem.

Przykład 9. Funkcja maksimum dwóch liczb

def wieksza(a, b):
    if a > b:
        return a
    return b

return kończy funkcję i zwraca wynik.

Wniosek / wynik: return kończy funkcję i zwraca wynik.

Przykład 10. Funkcja z warunkiem

def parzysta(n):
    return n % 2 == 0

Dla 8 zwróci True, dla 7 — False.

Wniosek / wynik: Dla 8 zwróci True, dla 7 — False.

Przykład 11. Liczba par o sumie 10

ile = 0
for i in range(len(dane)):
    for j in range(i + 1, len(dane)):
        if dane[i] + dane[j] == 10:
            ile += 1

Dlaczego j zaczyna się od i+1? Nie liczymy pary elementu z samym sobą ani tej samej pary dwa razy.

Złożoność: O(n²).

Wniosek / wynik: Złożoność: O(n²).

Przykład 12. Licznik wystąpień

licznik = {}
for x in dane:
    if x not in licznik:
        licznik[x] = 0
    licznik[x] += 1

Po pętli licznik[x] mówi, ile razy wystąpiła wartość x.

Wniosek / wynik: Po pętli licznik[x] mówi, ile razy wystąpiła wartość x.

Przykład 13. Wczytanie liczb z pliku

with open("dane.txt", "r", encoding="utf-8") as f:
    dane = [int(wiersz.strip()) for wiersz in f]

strip() usuwa znak końca linii.

Wniosek / wynik: strip() usuwa znak końca linii.

Przykład 14. Dwie liczby w wierszu

with open("dane.txt", "r", encoding="utf-8") as f:
    for wiersz in f:
        a, b = map(int, wiersz.split())

split() dzieli wiersz po białych znakach.

Wniosek / wynik: split() dzieli wiersz po białych znakach.

Przykład 15. Sortowanie malejące

posortowane = sorted(dane, reverse=True)

Przykład 16. Sortowanie par według drugiej wartości

pary = [(2, 8), (1, 3), (5, 4)]
pary.sort(key=lambda p: p[1])

Po sortowaniu kolejność wynika z drugiej współrzędnej.

Wniosek / wynik: Po sortowaniu kolejność wynika z drugiej współrzędnej.

Przykład 17. Błąd o jeden

for i in range(1, len(dane)):
    if dane[i] > dane[i-1]:
        ...

Start od 1 jest konieczny, bo dla i=0 odwołanie do i−1 oznaczałoby ostatni element listy w Pythonie, co zwykle jest logicznie błędne.

Wniosek / wynik: Start od 1 jest konieczny, bo dla i=0 odwołanie do i−1 oznaczałoby ostatni element listy w Pythonie, co zwykle jest logicznie błędne.

Przykład 18. Co robi ten program?

wynik = 0
for x in dane:
    if x > wynik:
        wynik = x

Pytanie: Czy kod zawsze znajduje maksimum?

Nie. Dla wszystkich liczb ujemnych wynik pozostanie 0, choć 0 może wcale nie występować w danych.

Poprawa: zainicjalizować wynik = dane[0].

Wniosek / wynik: Poprawa: zainicjalizować wynik = dane[0] .

Zadanie A. Najczęściej występująca liczba

Treść: Dla listy liczb wyznacz wartość występującą najczęściej. Jeśli jest kilka takich wartości, podaj najmniejszą.

licznik = {}
for x in dane:
    licznik[x] = licznik.get(x, 0) + 1

maks_ile = max(licznik.values())
wynik = min(x for x in licznik if licznik[x] == maks_ile)
print(wynik)

Dlaczego działa? Najpierw liczymy częstości, potem wybieramy tylko klucze z maksymalną częstością i z nich najmniejszy.

Wniosek / wynik: Dlaczego działa? Najpierw liczymy częstości, potem wybieramy tylko klucze z maksymalną częstością i z nich najmniejszy.

Zadanie B. Liczba zmian kierunku

Treść: Dany jest ciąg różnych liczb. Policz, ile indeksów i ma własność, że a[i] jest większe od obu sąsiadów albo mniejsze od obu sąsiadów.

ile = 0
for i in range(1, len(dane)-1):
    if (dane[i] > dane[i-1] and dane[i] > dane[i+1]) or \
       (dane[i] < dane[i-1] and dane[i] < dane[i+1]):
        ile += 1

Przypadki brzegowe: pierwszy i ostatni element nie mają dwóch sąsiadów, więc ich nie badamy.

Złożoność: O(n).

Wniosek / wynik: Złożoność: O(n).

Przykład rozszerzony. Funkcja licząca lokalne maksima

Treść zadania: Dla listy różnych liczb policz elementy większe od obu swoich sąsiadów. Pierwszy i ostatni element pomijamy.

def lokalne_maksima(a):
    ile = 0
    for i in range(1, len(a)-1):
        if a[i] > a[i-1] and a[i] > a[i+1]:
            ile += 1
    return ile

Dla [1,5,2,7,3] lokalnymi maksimami są 5 i 7.

Odpowiedź: 2.

Dlaczego zakres zaczyna się od 1 i kończy przed len(a)-1? Skrajne elementy nie mają dwóch sąsiadów.

Przykład rozszerzony. Debugowanie błędu o jeden

Treść zadania: Program ma policzyć pary sąsiednich elementów, ale użyto pętli for i in range(len(a)) i odwołania do a[i+1]. Co jest nie tak?

Dla ostatniego i=len(a)-1 program spróbuje odczytać a[len(a)], czyli element poza tablicą.

Poprawa: użyj for i in range(len(a)-1).

Przykład 1. Rozbicie wiersza

wiersz = "2026-05-17 Lublin 24.5 81"
data, miasto, temp, wilg = wiersz.split()

Po split() wszystkie cztery wartości są napisami. Liczby trzeba przekonwertować.

Wniosek / wynik: Po split() wszystkie cztery wartości są napisami. Liczby trzeba przekonwertować.

Przykład 2. Odczyt wszystkich wierszy

with open("dane.txt", "r", encoding="utf-8") as f:
    for wiersz in f:
        wiersz = wiersz.strip()
        print(wiersz)

with automatycznie zamyka plik po zakończeniu pracy.

Wniosek / wynik: with automatycznie zamyka plik po zakończeniu pracy.

Przykład 3. Wczytanie liczb

with open("liczby.txt", "r", encoding="utf-8") as f:
    dane = [int(w.strip()) for w in f]

Przykład 4. Rekord liczbowy

Treść: W każdym wierszu są trzy liczby całkowite: identyfikator, liczba punktów, czas.

id_txt, pkt_txt, czas_txt = wiersz.split()
ident = int(id_txt)
pkt = int(pkt_txt)
czas = int(czas_txt)

Dlaczego jawnie? Dzięki temu łatwo kontrolować typ każdej kolumny.

Wniosek / wynik: Dlaczego jawnie? Dzięki temu łatwo kontrolować typ każdej kolumny.

Przykład 5. Liczba rekordów spełniających warunek

Problem: policz wiersze, w których temperatura przekracza 30°C.

ile = 0
for wiersz in f:
    data, miasto, temp_txt, wilg_txt = wiersz.split()
    temp = float(temp_txt)
    if temp > 30:
        ile += 1

Złożoność: O(n).

Wniosek / wynik: Złożoność: O(n).

Przykład 6. Średnia temperatur

suma = 0.0
ile = 0
for wiersz in f:
    _, _, temp_txt, _ = wiersz.split()
    suma += float(temp_txt)
    ile += 1

srednia = suma / ile

Przypadek brzegowy: jeśli plik może być pusty, trzeba sprawdzić ile > 0.

Wniosek / wynik: Przypadek brzegowy: jeśli plik może być pusty, trzeba sprawdzić ile > 0 .

Przykład 7. Średnia tylko dla wybranej grupy

Problem: oblicz średnią temperaturę tylko dla Lublina.

suma = 0.0
ile = 0
for wiersz in f:
    data, miasto, temp_txt, wilg_txt = wiersz.split()
    if miasto == "Lublin":
        suma += float(temp_txt)
        ile += 1

Wniosek / wynik: Problem: oblicz średnią temperaturę tylko dla Lublina.

Przykład 8. Rekord z najwyższym wynikiem

naj_pkt = None
naj_id = None

for wiersz in f:
    ident, pkt, czas = map(int, wiersz.split())
    if naj_pkt is None or pkt > naj_pkt:
        naj_pkt = pkt
        naj_id = ident

Dlaczego None? Nie zakładamy niczego o zakresie punktów.

Wniosek / wynik: Dlaczego None? Nie zakładamy niczego o zakresie punktów.

Przykład 9. Liczba rekordów na miasto

ile = {}
for wiersz in f:
    data, miasto, temp_txt, wilg_txt = wiersz.split()
    ile[miasto] = ile.get(miasto, 0) + 1

Przykład 10. Suma punktów na zawodnika

suma = {}
for wiersz in f:
    zawodnik, pkt_txt = wiersz.split()
    pkt = int(pkt_txt)
    suma[zawodnik] = suma.get(zawodnik, 0) + pkt

Przykład 11. Najwcześniejsza data

naj_data = None
for wiersz in f:
    data, wartosc = wiersz.split()
    if naj_data is None or data < naj_data:
        naj_data = data

Warunek: format musi być stały, np. 2026-09-05.

Wniosek / wynik: Warunek: format musi być stały, np. 2026-09-05.

Przykład 12. Maksimum strumieniowo

maks = None
for wiersz in f:
    x = int(wiersz)
    if maks is None or x > maks:
        maks = x

Pamięć: O(1).

Czas: O(n).

Wniosek / wynik: Czas: O(n).

Przykład 13. Plik wynikowy

with open("wyniki.txt", "w", encoding="utf-8") as out:
    out.write(f"Największa wartość: {maks}\n")
    out.write(f"Liczba rekordów: {ile}\n")

W zadaniu egzaminacyjnym trzeba pilnować dokładnie żądanego formatu wyniku.

Wniosek / wynik: W zadaniu egzaminacyjnym trzeba pilnować dokładnie żądanego formatu wyniku.

Przykład 14. Pomijanie pustych wierszy

for wiersz in f:
    wiersz = wiersz.strip()
    if not wiersz:
        continue
    # dalsze przetwarzanie

Przykład 15. Analiza pomiarów

Treść zadania: Plik zawiera wiersze: data, stacja, temperatura. Wyznacz: a) liczbę pomiarów powyżej 25°C, b) maksymalną temperaturę i stację, na której wystąpiła, c) średnią temperaturę dla każdej stacji.

Plan: jedno przejście po pliku i trzy struktury informacji.

ile25 = 0
maks_temp = None
maks_stacja = None
suma = {}
liczba = {}

for wiersz in f:
    data, stacja, temp_txt = wiersz.split()
    temp = float(temp_txt)

    if temp > 25:
        ile25 += 1

    if maks_temp is None or temp > maks_temp:
        maks_temp = temp
        maks_stacja = stacja

    suma[stacja] = suma.get(stacja, 0.0) + temp
    liczba[stacja] = liczba.get(stacja, 0) + 1

for stacja in suma:
    srednia = suma[stacja] / liczba[stacja]

Złożoność: O(n+k), gdzie k to liczba stacji.

Wniosek / wynik: Złożoność: O(n+k), gdzie k to liczba stacji.

Przykład 16. Najdłuższa seria rekordów spełniających warunek

Treść zadania: Plik zawiera po jednej liczbie dziennie. Wyznacz najdłuższą serię kolejnych dni, w których wartość była dodatnia.

akt = 0
naj = 0
for wiersz in f:
    x = int(wiersz)
    if x > 0:
        akt += 1
        naj = max(naj, akt)
    else:
        akt = 0

Nie trzeba przechowywać całego pliku.

Wniosek / wynik: Nie trzeba przechowywać całego pliku.

Przykład 17. Najpopularniejsza kategoria

Treść zadania: W każdym wierszu zapisano kategorię produktu. Wyznacz kategorię występującą najczęściej; przy remisie wybierz alfabetycznie pierwszą.

licznik = {}
for wiersz in f:
    kat = wiersz.strip()
    licznik[kat] = licznik.get(kat, 0) + 1

maks_ile = max(licznik.values())
wynik = min(k for k in licznik if licznik[k] == maks_ile)

Wniosek / wynik: Treść zadania: W każdym wierszu zapisano kategorię produktu. Wyznacz kategorię występującą najczęściej; przy remisie wybierz alfabetycznie pierwszą.

Przykład rozszerzony. Raport z pliku sprzedaży

Treść zadania: Plik zawiera w każdym wierszu: data, miasto, produkt, liczba_sztuk, cena_jednostkowa. Oblicz łączny przychód dla każdego miasta i wskaż miasto z największym przychodem.

Plan: dla każdego rekordu liczymy wartość sprzedaży = liczba_sztuk·cena_jednostkowa i dodajemy ją do sumy przypisanej do miasta.

przychod = {}
for wiersz in f:
    data, miasto, produkt, szt_txt, cena_txt = wiersz.split()
    wartosc = int(szt_txt) * float(cena_txt)
    przychod[miasto] = przychod.get(miasto, 0.0) + wartosc

naj_miasto = max(przychod, key=przychod.get)

Dlaczego słownik? liczba miast nie musi być znana wcześniej, a każdemu miastu przypisujemy jedną sumę.

Wynik: dla każdego miasta otrzymujemy sumę przychodu, a naj_miasto wskazuje największą.

Przykład 1. Odczyt znaków

s = "MATURA"
print(s[0])
print(s[-1])

Wynik: M oraz A.

Przykład 2. Fragment napisu

s = "INFORMATYKA"
print(s[2:6])

Indeksy 2,3,4,5 dają znaki F,O,R,M.

Wynik: FORM.

Przykład 3. Liczba liter A

ile = 0
for znak in s:
    if znak == "A":
        ile += 1

Złożoność: O(n).

Wniosek / wynik: Złożoność: O(n).

Przykład 4. Częstości wszystkich znaków

licznik = {}
for znak in s:
    licznik[znak] = licznik.get(znak, 0) + 1

Przykład 5. Test palindromu

def palindrom(s):
    return s == s[::-1]

Dla "KAJAK" funkcja zwróci True.

Wniosek / wynik: Dla "KAJAK" funkcja zwróci True.

Przykład 6. Test bez tworzenia kopii

def palindrom(s):
    i = 0
    j = len(s) - 1
    while i < j:
        if s[i] != s[j]:
            return False
        i += 1
        j -= 1
    return True

Pamięć dodatkowa: O(1).

Wniosek / wynik: Pamięć dodatkowa: O(1).

Przykład 7. Anagram przez sortowanie

def anagram(a, b):
    return sorted(a) == sorted(b)

Złożoność: O(n log n).

Wniosek / wynik: Złożoność: O(n log n).

Przykład 8. Anagram przez liczniki

Dla alfabetu o małej liczbie znaków można policzyć częstości i uzyskać O(n).

Wniosek / wynik: Dla alfabetu o małej liczbie znaków można policzyć częstości i uzyskać O(n).

Przykład 9. Najdłuższa seria tego samego znaku

Treść: Dla napisu wyznacz długość najdłuższego fragmentu złożonego z identycznych znaków.

if not s:
    wynik = 0
else:
    akt = 1
    wynik = 1
    for i in range(1, len(s)):
        if s[i] == s[i-1]:
            akt += 1
        else:
            akt = 1
        wynik = max(wynik, akt)

Test: "AAABBCCCCDA" → 4.

Wniosek / wynik: Test: "AAABBCCCCDA" → 4.

Przykład 10. Najdłuższa seria cyfr

Zamiast porównywać sąsiednie znaki, sprawdzamy isdigit() i resetujemy licznik po literze.

Wniosek / wynik: Zamiast porównywać sąsiednie znaki, sprawdzamy isdigit() i resetujemy licznik po literze.

Przykład 11. Ile elementów jest większych od średniej?

srednia = sum(dane) / len(dane)
ile = sum(1 for x in dane if x > srednia)

Przykład 12. Suma elementów macierzy

s = 0
for wiersz in A:
    for x in wiersz:
        s += x

Dla macierzy n×m złożoność wynosi O(nm).

Wniosek / wynik: Dla macierzy n×m złożoność wynosi O(nm).

Przykład 13. Suma głównej przekątnej

s = 0
for i in range(len(A)):
    s += A[i][i]

Dotyczy macierzy kwadratowej.

Wniosek / wynik: Dotyczy macierzy kwadratowej.

Przykład 14. Czterech sąsiadów pola

kierunki = [(-1,0),(1,0),(0,-1),(0,1)]

for di, dj in kierunki:
    ni = i + di
    nj = j + dj
    if 0 <= ni < n and 0 <= nj < m:
        # A[ni][nj] istnieje

Przykład 15. Suma fragmentu

pref = [0]
for x in dane:
    pref.append(pref[-1] + x)

# suma indeksów l..r
wynik = pref[r+1] - pref[l]

Budowa: O(n). Każde zapytanie o sumę fragmentu: O(1).

Wniosek / wynik: Budowa: O(n). Każde zapytanie o sumę fragmentu: O(1).

Przykład 16. Liczba zmian znaku

Treść: Dla tablicy niezerowych liczb policz, ile razy kolejne elementy mają przeciwne znaki.

ile = 0
for i in range(1, len(dane)):
    if dane[i] * dane[i-1] < 0:
        ile += 1

Dlaczego iloczyn? Iloczyn dwóch niezerowych liczb jest ujemny dokładnie wtedy, gdy mają przeciwne znaki.

Wniosek / wynik: Dlaczego iloczyn? Iloczyn dwóch niezerowych liczb jest ujemny dokładnie wtedy, gdy mają przeciwne znaki.

Przykład 17. Najczęstsza litera z remisem

Treść: Znajdź najczęściej występującą literę. Przy remisie wybierz alfabetycznie pierwszą.

licznik = {}
for znak in s:
    licznik[znak] = licznik.get(znak, 0) + 1

maks = max(licznik.values())
wynik = min(z for z in licznik if licznik[z] == maks)

Wniosek / wynik: Treść: Znajdź najczęściej występującą literę. Przy remisie wybierz alfabetycznie pierwszą.

Przykład 18. Największa suma spójnego fragmentu długości k

Treść: Dla tablicy i ustalonego k znajdź największą sumę k kolejnych elementów.

Lepszy pomysł niż liczenie każdej sumy od zera: przesuwane okno.

s = sum(dane[:k])
naj = s

for i in range(k, len(dane)):
    s += dane[i]
    s -= dane[i-k]
    naj = max(naj, s)

Złożoność: O(n), zamiast O(nk).

Wniosek / wynik: Złożoność: O(n), zamiast O(nk).

Przykład rozszerzony. Największa suma okna długości 3

Treść zadania: Dla [2,5,-1,4,6,0] znajdź największą sumę trzech kolejnych elementów w czasie O(n).

Pierwsze okno: 2+5−1=6. Następnie zamiast liczyć wszystko od nowa odejmujemy element wychodzący i dodajemy wchodzący.

Kolejne sumy: 8, 9, 10.

Odpowiedź: 10 dla fragmentu [4,6,0].

Dlaczego O(n)? każde przesunięcie okna wykonuje stałą liczbę operacji.

Przykład rozszerzony. Anagram z licznikami

Treść zadania: Sprawdź, czy "KOT" i "TOK" są anagramami bez sortowania.

Liczymy wystąpienia K,O,T w pierwszym napisie i odejmujemy wystąpienia z drugiego. Wszystkie liczniki kończą na 0.

Odpowiedź: tak, są anagramami.

Kontrola: napisy muszą mieć tę samą długość.

Przykład 1. Sens zapisu pozycyjnego

Treść: Zapisz wartość liczby 321₁₀ jako sumę wag pozycji.

3·10²+2·10¹+1·10⁰=300+20+1.

Wniosek / wynik: 3·10²+2·10¹+1·10⁰=300+20+1.

Przykład 2. Liczba 101101₂

1·32+0·16+1·8+1·4+0·2+1·1=45.

Odpowiedź: 45₁₀.

Przykład 3. Horner dla liczby binarnej

wartosc = 0
for cyfra in "101101":
    wartosc = wartosc * 2 + int(cyfra)

Po przetworzeniu wszystkich cyfr otrzymujemy 45.

Złożoność: O(k), gdzie k to liczba cyfr.

Wniosek / wynik: Złożoność: O(k), gdzie k to liczba cyfr.

Przykład 4. 45₁₀ na binarny

45÷2=22 r1, 22÷2=11 r0, 11÷2=5 r1, 5÷2=2 r1, 2÷2=1 r0, 1÷2=0 r1.

Odpowiedź: 101101₂.

Przykład 5. Algorytm

def na_bin(n):
    if n == 0:
        return "0"
    cyfry = ""
    while n > 0:
        cyfry = str(n % 2) + cyfry
        n //= 2
    return cyfry

Przykład 6. 157₈ na dziesiętny

1·8²+5·8+7=64+40+7=111.

Odpowiedź: 111₁₀.

Przykład 7. 2F₁₆ na dziesiętny

2·16+15=47.

Odpowiedź: 47₁₀.

Przykład 8. 255₁₀ na szesnastkowy

255=15·16+15, czyli FF₁₆.

Odpowiedź: FF₁₆.

Przykład 9. Binarny na hex

10111110₂ grupujemy: 1011 1110.

1011=B, 1110=E.

Odpowiedź: BE₁₆.

Przykład 10. AND

12=1100₂, 10=1010₂.

1100 AND 1010 = 1000₂ = 8.

Odpowiedź: 12 & 10 = 8.

Przykład 11. XOR

1100 XOR 1010 = 0110₂ = 6.

Odpowiedź: 6.

Przykład 12. Czy trzeci bit jest ustawiony?

if n & (1 << k):
    print("bit = 1")

Numerację bitów zwykle zaczynamy od 0 od prawej strony.

Wniosek / wynik: Numerację bitów zwykle zaczynamy od 0 od prawej strony.

Przykład 13. Prosty sposób

ile = bin(n).count("1")

Przykład 14. Sposób algorytmiczny

ile = 0
while n > 0:
    ile += n % 2
    n //= 2

Dla n=13, czyli 1101₂, wynik wynosi 3.

Wniosek / wynik: Dla n=13, czyli 1101₂, wynik wynosi 3.

Przykład 15. Liczby z dokładnie trzema jedynkami

Treść: Ile liczb z zakresu 0..31 ma w zapisie binarnym dokładnie trzy jedynki?

Zakres 0..31 używa maksymalnie 5 bitów. Wybieramy 3 pozycje spośród 5.

C(5,3)=10.

Odpowiedź: 10.

Przykład 16. Parzystość bez modulo

Treść: Jak za pomocą operacji bitowej sprawdzić, czy liczba jest parzysta?

Najmłodszy bit liczby parzystej jest równy 0.

if n & 1 == 0:
    print("parzysta")

Idea: sprawdzamy bit 0.

Przykład rozszerzony. Konwersja 173₁₀ na system dwójkowy i szesnastkowy

Treść zadania: Zapisz 173 w systemie binarnym, a następnie wykorzystaj ten zapis do otrzymania zapisu szesnastkowego.

173=128+32+8+4+1, więc bity dla wag 128,64,32,16,8,4,2,1 to 1,0,1,0,1,1,0,1.

Otrzymujemy 10101101₂.

Grupujemy po 4 bity: 1010 1101. 1010=A, 1101=D.

Odpowiedź: 173₁₀=10101101₂=AD₁₆.

Kontrola: A·16+D=10·16+13=173.

Przykład 1. Odliczanie

def odlicz(n):
    if n == 0:
        print("START")
        return
    print(n)
    odlicz(n - 1)

Dla n=3 wypisze: 3,2,1,START.

Wniosek / wynik: Dla n=3 wypisze: 3,2,1,START.

Przykład 2. Śledzenie wywołań

def f(n):
    if n == 0:
        return 0
    return 1 + f(n-1)

f(3)=1+f(2)=1+1+f(1)=1+1+1+f(0)=3.

Odpowiedź: f(3)=3.

Przykład 3. Silnia rekurencyjna

def silnia(n):
    if n == 0:
        return 1
    return n * silnia(n - 1)

Dla n=5 wynik to 120.

Złożoność czasowa: O(n).

Pamięć stosu: O(n).

Wniosek / wynik: Pamięć stosu: O(n).

Przykład 4. Naiwna rekurencja

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

Algorytm wielokrotnie liczy te same wartości.

Złożoność: wykładnicza, około O(2ⁿ).

Wniosek / wynik: Złożoność: wykładnicza, około O(2ⁿ).

Przykład 5. Fibonacci iteracyjnie

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

Złożoność: O(n), pamięć O(1).

Wniosek / wynik: Złożoność: O(n), pamięć O(1).

Przykład 6. NWD

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

Dla 84 i 30: nwd(84,30) → nwd(30,24) → nwd(24,6) → nwd(6,0)=6.

Odpowiedź: 6.

Przykład 7. Suma cyfr liczby

def suma_cyfr(n):
    if n < 10:
        return n
    return n % 10 + suma_cyfr(n // 10)

Dla 472: 2 + suma_cyfr(47) = 2+7+4=13.

Odpowiedź: 13.

Przykład 8. Palindrom

def palindrom(s):
    if len(s) <= 1:
        return True
    if s[0] != s[-1]:
        return False
    return palindrom(s[1:-1])

Każde wywołanie usuwa pierwszy i ostatni znak.

Wniosek / wynik: Każde wywołanie usuwa pierwszy i ostatni znak.

Przykład 9. Suma elementów

def suma(a, n):
    if n == 0:
        return 0
    return suma(a, n-1) + a[n-1]

Dla n elementów wykonujemy n wywołań.

Wniosek / wynik: Dla n elementów wykonujemy n wywołań.

Przykład 10. Maksimum rekurencyjnie

def maksimum(a, n):
    if n == 1:
        return a[0]
    return max(a[n-1], maksimum(a, n-1))

Przykład 11. Silnia iteracyjnie

wynik = 1
for i in range(2, n+1):
    wynik *= i

Czas O(n), pamięć dodatkowa O(1).

Wniosek / wynik: Czas O(n), pamięć dodatkowa O(1).

Przykład 12. Liczba wywołań

def f(n):
    if n == 0:
        return
    f(n-1)

Wywołań jest n+1, więc czas O(n).

Wniosek / wynik: Wywołań jest n+1, więc czas O(n).

Przykład 13. Potęga szybka

Treść: Oblicz aⁿ efektywniej niż przez n mnożeń.

def potega(a, n):
    if n == 0:
        return 1
    p = potega(a, n // 2)
    if n % 2 == 0:
        return p * p
    return p * p * a

Idea: aⁿ=(a^(⌊n/2⌋))², a dla nieparzystego n dodatkowo mnożymy przez a.

Złożoność: O(log n).

Wniosek / wynik: Złożoność: O(log n).

Przykład 14. Liczba jedynek binarnie

def jedynki(n):
    if n == 0:
        return 0
    return n % 2 + jedynki(n // 2)

Dla 13=1101₂ wynik to 3.

Wniosek / wynik: Dla 13=1101₂ wynik to 3.

Przykład 15. Odwracanie napisu

def odwroc(s):
    if len(s) <= 1:
        return s
    return odwroc(s[1:]) + s[0]

Dla "ABC" wynik to "CBA".

Wniosek / wynik: Dla "ABC" wynik to "CBA".

Przykład 16. Dobór metody

Treść: Czy do zsumowania miliona liczb lepsza jest prosta rekurencja czy pętla?

Pętla. Rekurencja wymagałaby bardzo głębokiego stosu i w Pythonie przekroczyłaby limit rekursji.

Wniosek: rekurencja nie zawsze jest najlepszym wyborem.

Przykład rozszerzony. Rekurencyjna suma 1+2+...+n

Treść zadania: Zdefiniuj rekurencyjnie funkcję S(n)=1+2+...+n i oblicz S(4).

Przypadek bazowy: S(0)=0.

Krok: S(n)=n+S(n−1).

def S(n):
    if n == 0:
        return 0
    return n + S(n-1)

Ślad: S(4)=4+S(3)=4+3+S(2)=4+3+2+S(1)=4+3+2+1+S(0)=10.

Odpowiedź: S(4)=10.

Dlaczego działa? Zakładamy, że S(n−1) poprawnie sumuje liczby od 1 do n−1; dodanie n daje sumę do n.

Przykład rozszerzony. Wykrycie błędnej rekurencji

Treść zadania: Czy funkcja f(n): return f(n) jest poprawną rekurencją?

Nie ma przypadku bazowego i argument nie zmniejsza się. Wywołania nigdy nie zbliżają się do zakończenia.

Odpowiedź: nie; prowadzi do nieskończonego ciągu wywołań aż do błędu limitu rekursji.

Przykład 1. Odczyt adresu

Treść: Komórka leży w kolumnie D i wierszu 7.

Adres: D7.

Przykład 2. Kopiowanie formuły

W C2 wpisano =A2+B2. Po skopiowaniu do C3 formuła stanie się:

=A3+B3

Przykład 3. Stała stawka VAT

Jeśli stawka VAT jest w F1 i formułę kopiujemy w dół, używamy:

=B2*$F$1

Przykład 4. Suma zakresu

Treść: Zsumuj komórki B2:B10.

=SUMA(B2:B10)

Przykład 5. Zaliczenie

Jeżeli wynik w B2 wynosi co najmniej 50, wpisz "TAK", w przeciwnym razie "NIE".

=JEŻELI(B2>=50;"TAK";"NIE")

Przykład 6. Liczenie wyników ≥ 80

=LICZ.JEŻELI(B2:B100;">=80")

Przykład 7. Suma sprzedaży dla miasta

Miasta są w A2:A100, sprzedaż w B2:B100.

=SUMA.JEŻELI(A2:A100;"Lublin";B2:B100)

Przykład 8. Dwa warunki

Policz rekordy, gdzie miasto=Lublin i wynik>=80.

=LICZ.WARUNKI(A2:A100;"Lublin";B2:B100;">=80")

Przykład 9. X.WYSZUKAJ

W A2:A100 są identyfikatory, w B2:B100 nazwiska. Znajdź nazwisko dla ID z E2.

=X.WYSZUKAJ(E2;A2:A100;B2:B100)

Przykład 10. WYSZUKAJ.PIONOWO

Dla klasycznej tabeli A2:C100:

=WYSZUKAJ.PIONOWO(E2;A2:C100;2;FAŁSZ)

FAŁSZ oznacza dokładne dopasowanie.

Przykład 11. Sortowanie wielopoziomowe

Treść: Posortuj najpierw po mieście rosnąco, potem po wyniku malejąco.

Używamy sortowania niestandardowego z dwoma poziomami.

Wniosek / wynik: Używamy sortowania niestandardowego z dwoma poziomami.

Przykład 12. Rok z daty

Jeżeli w A2 jest prawidłowa data:

=ROK(A2)

Przykład 13. Sprzedaż miesięczna

Dla sprzedaży w kolejnych miesiącach najlepszym wyborem jest zwykle wykres liniowy.

Wniosek / wynik: Dla sprzedaży w kolejnych miesiącach najlepszym wyborem jest zwykle wykres liniowy.

Przykład 14. Tabela wyników

Dane: A — uczeń, B — klasa, C — wynik, D — liczba nieobecności.

Zadania: policz średni wynik klasy 3A, liczbę uczniów z wynikiem ≥80 i nieobecnościami ≤5, oraz wskaż najwyższy wynik.

Formuły:

=ŚREDNIA.JEŻELI(B2:B200;"3A";C2:C200)
=LICZ.WARUNKI(C2:C200;">=80";D2:D200;"<=5")
=MAX(C2:C200)

Wniosek / wynik: Formuły:

Przykład 15. Próg podatkowy

Treść: Jeśli dochód w B2 przekracza 100000, zastosuj stawkę 20%, w przeciwnym razie 10%.

=JEŻELI(B2>100000;B2*20%;B2*10%)

Przykład 16. Ranking

Treść: Posortuj wyniki malejąco i przy równych wynikach nazwiska alfabetycznie.

To przykład sortowania wielopoziomowego: wynik malejąco, nazwisko rosnąco.

Wniosek / wynik: To przykład sortowania wielopoziomowego: wynik malejąco, nazwisko rosnąco.

Przykład rozszerzony. Formuła kopiowana w dół

Treść zadania: W B2:B100 jest cena netto, w F1 stawka VAT 23%. W C2 ma być kwota VAT, a formuła ma być kopiowana w dół. Podaj formułę.

Adres B2 powinien zmieniać się na B3, B4 itd., ale F1 ma pozostać stałe.

Odpowiedź: =B2*$F$1.

Dlaczego? B2 jest adresem względnym, a $F$1 jest całkowicie zablokowany.

Przykład rozszerzony. Dwa warunki

Treść zadania: W kolumnie A jest miasto, w B wynik. Policz rekordy z Lublina z wynikiem co najmniej 80.

Potrzebne są dwa jednoczesne warunki, więc używamy funkcji wielowarunkowej.

Odpowiedź: =LICZ.WARUNKI(A2:A100;"Lublin";B2:B100;">=80").

Przykład 1. Tabela UCZNIOWIE

Pola: id, imie, nazwisko, klasa.

Każdy wiersz opisuje jednego ucznia.

Wniosek / wynik: Każdy wiersz opisuje jednego ucznia.

Przykład 2. Relacja

Tabela UCZNIOWIE ma id, a tabela WYNIKI ma uczen_id. Pole uczen_id jest kluczem obcym wskazującym ucznia.

Wniosek / wynik: Tabela UCZNIOWIE ma id , a tabela WYNIKI ma uczen_id . Pole uczen_id jest kluczem obcym wskazującym ucznia.

Przykład 3. Wybór kolumn

SELECT imie, nazwisko
FROM uczniowie;

Zwracamy tylko dwie kolumny.

Wniosek / wynik: Zwracamy tylko dwie kolumny.

Przykład 4. Wszystkie kolumny

SELECT *
FROM uczniowie;

Przykład 5. Wynik co najmniej 80

SELECT *
FROM wyniki
WHERE punkty >= 80;

Przykład 6. Kilka warunków

SELECT *
FROM uczniowie
WHERE klasa = '3A'
  AND nazwisko LIKE 'K%';

LIKE 'K%' oznacza napis zaczynający się literą K.

Wniosek / wynik: LIKE 'K%' oznacza napis zaczynający się literą K.

Przykład 7. Ranking

SELECT imie, nazwisko, punkty
FROM wyniki
ORDER BY punkty DESC, nazwisko ASC;

Najpierw punkty malejąco, przy remisie nazwisko alfabetycznie.

Wniosek / wynik: Najpierw punkty malejąco, przy remisie nazwisko alfabetycznie.

Przykład 8. Różne klasy

SELECT DISTINCT klasa
FROM uczniowie;

Przykład 9. Średnia punktów

SELECT AVG(punkty)
FROM wyniki;

Przykład 10. Liczba uczniów

SELECT COUNT(*)
FROM uczniowie;

Przykład 11. Średnia dla każdej klasy

SELECT klasa, AVG(punkty)
FROM wyniki
GROUP BY klasa;

Przykład 12. Klasy ze średnią powyżej 75

SELECT klasa, AVG(punkty) AS sr
FROM wyniki
GROUP BY klasa
HAVING AVG(punkty) > 75;

Przykład 13. Uczeń i wynik

SELECT u.imie, u.nazwisko, w.punkty
FROM uczniowie u
JOIN wyniki w
  ON u.id = w.uczen_id;

Przykład 14. Wyniki tylko klasy 3A

SELECT u.nazwisko, w.punkty
FROM uczniowie u
JOIN wyniki w
  ON u.id = w.uczen_id
WHERE u.klasa = '3A';

Przykład 15. Wynik większy od średniej

SELECT *
FROM wyniki
WHERE punkty > (
    SELECT AVG(punkty)
    FROM wyniki
);

Najpierw obliczana jest średnia, potem wybierane są rekordy powyżej niej.

Wniosek / wynik: Najpierw obliczana jest średnia, potem wybierane są rekordy powyżej niej.

Przykład 16. Najlepszy uczeń każdej klasy

Treść: Dla każdej klasy wyznacz maksymalny wynik.

SELECT u.klasa, MAX(w.punkty) AS maks
FROM uczniowie u
JOIN wyniki w ON u.id = w.uczen_id
GROUP BY u.klasa;

Wniosek / wynik: Treść: Dla każdej klasy wyznacz maksymalny wynik.

Przykład 17. Liczba uczniów bez wyniku

Treść: Policz uczniów, którzy nie mają rekordu w tabeli WYNIKI.

SELECT COUNT(*)
FROM uczniowie u
LEFT JOIN wyniki w
  ON u.id = w.uczen_id
WHERE w.uczen_id IS NULL;

Dlaczego LEFT JOIN? Chcemy zachować także uczniów bez dopasowanego rekordu.

Wniosek / wynik: Dlaczego LEFT JOIN? Chcemy zachować także uczniów bez dopasowanego rekordu.

Przykład 18. Klasy z co najmniej 10 uczniami

SELECT klasa, COUNT(*) AS ile
FROM uczniowie
GROUP BY klasa
HAVING COUNT(*) >= 10;

Przykład rozszerzony. Średnia klasy i liczba uczniów powyżej średniej

Treść zadania: Tabele UCZNIOWIE(id, nazwisko, klasa) i WYNIKI(uczen_id, punkty). Dla każdej klasy podaj średni wynik oraz liczbę uczniów, którzy uzyskali wynik wyższy niż średnia swojej klasy.

Idea: najpierw trzeba znać średnią dla klasy, a następnie porównać z nią wynik ucznia. To zadanie wymaga połączenia tabel oraz operacji agregujących.

Wniosek: proste GROUP BY wystarcza do średniej, ale policzenie uczniów powyżej średniej klasy wymaga dodatkowej konstrukcji, np. podzapytania lub CTE zależnie od systemu SQL.

Najważniejsza umiejętność: rozpoznać, że porównujemy rekord indywidualny z agregatem jego grupy.

Przykład 1. Sortowanie przez wybór

for i in range(len(a)):
    p = i
    for j in range(i+1, len(a)):
        if a[j] < a[p]:
            p = j
    a[i], a[p] = a[p], a[i]

Przykład 2. Pierwiastek równania x²=10

l, r = 0.0, 10.0
for _ in range(100):
    m = (l+r)/2
    if m*m < 10:
        l = m
    else:
        r = m

Po odpowiedniej liczbie iteracji przedział jest bardzo mały.

Wniosek / wynik: Po odpowiedniej liczbie iteracji przedział jest bardzo mały.

Przykład 3. Wydawanie reszty

Dla nominałów 50,20,10,5,2,1 i kwoty 87 wybieramy kolejno największy możliwy nominał.

50+20+10+5+2=87.

Wniosek / wynik: 50+20+10+5+2=87.

Przykład 4. 2x³−3x²+4x−5 dla x=2

w = 2
w = w*2 - 3
w = w*2 + 4
w = w*2 - 5

Wynik = 7.

Wniosek / wynik: Wynik = 7.

Przykład 5. Wyszukiwanie binarne

Treść zadania: Dana jest uporządkowana rosnąco tablica [4,9,15,21,37,40,52]. Sprawdź metodą wyszukiwania binarnego, czy występuje w niej liczba 37. Pokaż kolejne przedziały wyszukiwania.

Krok 1: l=0, r=6, więc m=3. a[3]=21<37. Odrzucamy lewą połowę wraz ze środkiem.

Krok 2: l=4, r=6, m=5. a[5]=40>37. Odrzucamy prawą część.

Krok 3: l=4, r=4, m=4. a[4]=37.

Odpowiedź: liczba 37 występuje na indeksie 4.

Dlaczego ta metoda działa? Tablica jest uporządkowana, więc porównanie z elementem środkowym pozwala odrzucić połowę kandydatów.

Przykład 6. Najdłuższy spójny podciąg niemalejący

Treść zadania: Dla ciągu [1,2,2,5,3,4,4,7] wyznacz długość najdłuższego spójnego fragmentu niemalejącego.

Fragment [1,2,2,5] ma długość 4. Po przejściu z 5 do 3 seria się kończy. Drugi fragment [3,4,4,7] również ma długość 4.

Odpowiedź: 4.

Kontrola: żaden spójny fragment długości 5 nie jest niemalejący.

Przykład 7. Największa suma spójnego podciągu

Treść zadania: Dla tablicy [-2,3,-1,5,-6,4] znajdź największą sumę spójnego fragmentu.

Algorytm Kadane'a prowadzi wartości bieżącej najlepszej sumy kończącej się na danym elemencie: -2 → 3 → 2 → 7 → 1 → 5.

Największa napotkana wartość to 7, uzyskana dla fragmentu [3,-1,5].

Odpowiedź: 7.

Przykład 8. Dobór algorytmu sortowania

Treść zadania: Trzeba posortować około 1 000 000 liczb. Która klasa algorytmu będzie rozsądniejsza: O(n²) czy O(n log n)?

Dla miliona elementów n² to około 10¹² operacji porównań, podczas gdy n log₂n to około 20 milionów.

Odpowiedź: należy preferować algorytm klasy O(n log n), np. sortowanie przez scalanie.

Przykład 9. Sito Eratostenesa

Treść zadania: Wyznacz wszystkie liczby pierwsze nie większe niż 20 metodą sita Eratostenesa.

Zostawiamy 2 i wykreślamy jej wielokrotności, następnie zostawiamy 3 i wykreślamy jego wielokrotności. Dalej wystarczy dojść do √20.

Odpowiedź: 2,3,5,7,11,13,17,19.

Przykład 10. Schemat Hornera

Treść zadania: Oblicz wartość wielomianu W(x)=2x³−3x²+4x−5 dla x=2 schematem Hornera.

Startujemy od 2. Następnie: 2·2−3=1, 1·2+4=6, 6·2−5=7.

Odpowiedź: W(2)=7.

Dlaczego Horner jest dobry? Nie obliczamy osobno x² i x³; używamy tylko kolejnych mnożeń i dodawań.

Przykład 11. Kiedy nie wolno użyć wyszukiwania binarnego?

Treść zadania: Dana jest tablica [7,1,9,3,5]. Czy można bezpośrednio zastosować wyszukiwanie binarne, aby znaleźć 3?

Nie. Z porównania z elementem środkowym nie wynika, którą połowę można odrzucić, bo dane nie są uporządkowane.

Odpowiedź: nie; najpierw trzeba uporządkować dane albo użyć innej metody.

Przykład 12. Pułapka algorytmu zachłannego

Treść zadania: Mamy nominały 1,3,4 i chcemy wydać kwotę 6 minimalną liczbą monet. Czy wybieranie zawsze największego możliwego nominału daje optimum?

Zachłannie: 4+1+1, czyli 3 monety. Lepsze rozwiązanie: 3+3, czyli 2 monety.

Odpowiedź: nie. Dla tego systemu nominałów algorytm zachłanny nie daje optimum.

Przykład 13. Metoda połowienia

Treść zadania: Szukamy dodatniego rozwiązania równania x²=10 w przedziale [0,10]. Wyjaśnij jeden krok metody połowienia.

Środek to 5. Ponieważ 5²=25>10, rozwiązanie musi leżeć w [0,5]. Kolejny krok wykonujemy już tylko na tej połowie.

Wniosek: po jednym kroku przedział zawęża się z [0,10] do [0,5].

Przykład 14. Sortowanie przez wstawianie

Treść zadania: Dlaczego sortowanie przez wstawianie jest naturalne dla prawie uporządkowanych danych?

Każdy kolejny element jest przesuwany tylko o tyle pozycji, ile naprawdę trzeba. Jeśli niewiele elementów jest „nie na miejscu”, liczba przesunięć może być mała.

Odpowiedź: korzysta z istniejącego uporządkowania i może wykonać niewiele przesunięć.

Przykład 15. Dlaczego sito zaczyna od p²?

Treść zadania: W sicie Eratostenesa dla liczby pierwszej p wykreślamy wielokrotności od p². Uzasadnij.

Każda mniejsza wielokrotność p ma postać p·k z k<p, więc wcześniej została już wykreślona jako wielokrotność mniejszego dzielnika k.

Wniosek: rozpoczęcie od p² nie pomija żadnej liczby złożonej.

Przykład 16. Kadane dla samych liczb ujemnych

Treść zadania: Dla [-5,-2,-7] znajdź największą sumę niepustego spójnego fragmentu.

Najlepszym fragmentem jest pojedynczy element -2. Startowanie algorytmu od 0 dałoby błędny wynik, bo pusty fragment nie jest dozwolony.

Odpowiedź: -2.

Przykład 17. Liczba kroków wyszukiwania binarnego

Treść zadania: Ile razy trzeba mniej więcej dzielić zbiór 1024 elementów na pół, aby dojść do jednego elementu?

1024=2¹⁰.

Odpowiedź: około 10 podziałów.

Przykład 18. Rozpoznanie złożoności

Treść zadania: Klasyczne sortowanie bąbelkowe ma dwie zagnieżdżone pętle zależne od n. Jaka jest typowa złożoność w najgorszym przypadku?

Liczba porównań rośnie proporcjonalnie do n².

Odpowiedź: O(n²).

Przykład 1. Śledzenie stosu

Start: []. Po append(4): [4]. Po append(7): [4,7]. Po pop(): otrzymujemy 7, stos=[4].

Wniosek / wynik: Start: []. Po append(4): [4]. Po append(7): [4,7]. Po pop(): otrzymujemy 7, stos=[4].

Przykład 2. Typowe zastosowania

Cofanie ostatniej operacji, analiza nawiasów, ONP, przechodzenie grafu metodą DFS.

Wniosek / wynik: Cofanie ostatniej operacji, analiza nawiasów, ONP, przechodzenie grafu metodą DFS.

Przykład 3. Kolejka klientów

Przychodzą A, B, C. Obsługiwani są A, potem B, potem C.

Wniosek / wynik: Przychodzą A, B, C. Obsługiwani są A, potem B, potem C.

Przykład 4. Dlaczego nie list.pop(0)?

Usunięcie pierwszego elementu zwykłej listy wymaga przesunięcia pozostałych elementów. deque.popleft() jest do tego przeznaczone i działa efektywnie.

Wniosek / wynik: Usunięcie pierwszego elementu zwykłej listy wymaga przesunięcia pozostałych elementów. deque.popleft() jest do tego przeznaczone i działa efektywnie.

Przykład 5. Liczba różnych wartości

dane = [4,4,2,7,2,9]
ile = len(set(dane))

Różne wartości to 2,4,7,9.

Wynik: 4.

Przykład 6. Czy element już wystąpił?

widziane = set()
for x in dane:
    if x in widziane:
        print("powtórzenie")
    widziane.add(x)

Przykład 7. Częstości

licznik = {}
for x in dane:
    licznik[x] = licznik.get(x, 0) + 1

Przykład 8. Najczęstszy element

Po zbudowaniu licznika szukamy klucza o największej wartości. Przy remisie stosujemy regułę z zadania, np. wybieramy mniejszy klucz.

Wniosek / wynik: Po zbudowaniu licznika szukamy klucza o największej wartości. Przy remisie stosujemy regułę z zadania, np. wybieramy mniejszy klucz.

Przykład 9. Jeden rodzaj nawiasów

stos = []
poprawny = True

for z in s:
    if z == "(":
        stos.append(z)
    elif z == ")":
        if not stos:
            poprawny = False
            break
        stos.pop()

if stos:
    poprawny = False

Dlaczego stos? Zamykający nawias musi pasować do ostatniego jeszcze niezamkniętego otwierającego nawiasu.

Wniosek / wynik: Dlaczego stos? Zamykający nawias musi pasować do ostatniego jeszcze niezamkniętego otwierającego nawiasu.

Przykład 10. Wczesny błąd

Napis ())( jest błędny już przy trzecim znaku: pojawia się zamknięcie bez odpowiadającego mu otwarcia.

Wniosek / wynik: Napis ())( jest błędny już przy trzecim znaku: pojawia się zamknięcie bez odpowiadającego mu otwarcia.

Przykład 11. Proste wyrażenie

2 3 + oznacza 2+3=5.

Wniosek / wynik: 2 3 + oznacza 2+3=5.

Przykład 12. Złożone wyrażenie

2 3 + 5 * oznacza (2+3)·5=25.

Wniosek / wynik: 2 3 + 5 * oznacza (2+3)·5=25.

Przykład 13. Kolejność argumentów

Dla 8 3 - najpierw zdejmujemy 3 jako b, potem 8 jako a. Liczymy a−b=5, nie 3−8.

Wniosek / wynik: Dla 8 3 - najpierw zdejmujemy 3 jako b, potem 8 jako a. Liczymy a−b=5, nie 3−8.

Przykład 14. Pełny ślad

3 4 5 + 4 2 - * +

Stos: [3] → [3,4] → [3,4,5] → [3,9] → [3,9,4] → [3,9,4,2] → [3,9,2] → [3,18] → [21].

Wynik: 21.

Przykład 15. Inne wyrażenie

5 1 2 + 4 * + 3 - = 5 + (1+2)·4 − 3 = 14.

Wniosek / wynik: 5 1 2 + 4 * + 3 - = 5 + (1+2)·4 − 3 = 14.

Przykład 16. Dlaczego dobór struktury ma znaczenie?

Jeżeli wykonujemy milion operacji pobrania z początku kolejki, deque jest naturalnym wyborem zamiast wielokrotnego pop(0) na liście.

Wniosek / wynik: Jeżeli wykonujemy milion operacji pobrania z początku kolejki, deque jest naturalnym wyborem zamiast wielokrotnego pop(0) na liście.

Przykład 17. Pierwsze powtórzenie

Treść: Znajdź pierwszy element ciągu, który pojawił się już wcześniej.

widziane = set()
wynik = None
for x in dane:
    if x in widziane:
        wynik = x
        break
    widziane.add(x)

Jedno przejście, średnio O(n).

Wniosek / wynik: Jedno przejście, średnio O(n).

Przykład 18. Dobór struktury

Obsługa zadań w kolejności zgłoszeń → kolejka. Cofanie zmian → stos. Liczba różnych identyfikatorów → zbiór. Liczba wystąpień każdego identyfikatora → słownik.

Wniosek / wynik: Obsługa zadań w kolejności zgłoszeń → kolejka. Cofanie zmian → stos. Liczba różnych identyfikatorów → zbiór. Liczba wystąpień każdego identyfikatora → słownik.

Przykład 1. Kolejność leksykograficzna

Treść: Który napis jest wcześniej: "ALA" czy "ANNA"?

Porównujemy A=A, potem L z N. L jest wcześniej.

Odpowiedź: "ALA".

Przykład 2.

Tekst: ABABA, wzorzec: ABA. Wystąpienia zaczynają się na indeksach 0 i 2.

Wniosek / wynik: Tekst: ABABA , wzorzec: ABA . Wystąpienia zaczynają się na indeksach 0 i 2.

Przykład 3. Dlaczego n−m+1?

Ostatnie możliwe rozpoczęcie wzorca jest na indeksie n−m. Dlatego indeksy startowe to 0..n−m, czyli n−m+1 pozycji.

Wniosek / wynik: Ostatnie możliwe rozpoczęcie wzorca jest na indeksie n−m. Dlatego indeksy startowe to 0..n−m, czyli n−m+1 pozycji.

Przykład 4. Nakładające się wystąpienia

W "AAAA" wzorzec "AA" występuje na pozycjach 0,1,2. Naiwny algorytm ich nie pomija.

Wniosek / wynik: W "AAAA" wzorzec "AA" występuje na pozycjach 0,1,2. Naiwny algorytm ich nie pomija.

Przykład 5. Klucz 3

A→D, B→E, X→A, Y→B, Z→C.

Wniosek / wynik: A→D, B→E, X→A, Y→B, Z→C.

Przykład 6. Implementacja

def cezar(tekst, k):
    wynik = ""
    for z in tekst:
        if 'A' <= z <= 'Z':
            p = ord(z) - ord('A')
            wynik += chr(ord('A') + (p + k) % 26)
        else:
            wynik += z
    return wynik

Złożoność: O(n).

Wniosek / wynik: Złożoność: O(n).

Przykład 7.

D zaszyfrowane kluczem 3 → A.

Wniosek / wynik: D zaszyfrowane kluczem 3 → A.

Przykład 8. Brute force

Jeżeli klucza nie znamy, dla alfabetu 26-literowego można sprawdzić wszystkie 26 przesunięć i ocenić, który tekst ma sens.

Wniosek / wynik: Jeżeli klucza nie znamy, dla alfabetu 26-literowego można sprawdzić wszystkie 26 przesunięć i ocenić, który tekst ma sens.

Przykład 9. Co trzeci znak

Dla tekstu "INFORMATYKA" bierzemy najpierw pozycje 1,4,7,..., potem 2,5,8,..., na końcu 3,6,9,... (przy numeracji od 1).

def przestaw(tekst):
    wynik = ""
    for start in range(3):
        for i in range(start, len(tekst), 3):
            wynik += tekst[i]
    return wynik

Wniosek / wynik: Dla tekstu "INFORMATYKA" bierzemy najpierw pozycje 1,4,7,..., potem 2,5,8,..., na końcu 3,6,9,... (przy numeracji od 1).

Przykład 10.

Dla "EGZAMIN" wynik tego schematu to "EANGMZI".

Wniosek / wynik: Dla "EGZAMIN" wynik tego schematu to "EANGMZI".

Przykład 11. Częstości

licznik = {}
for z in tekst:
    if z.isalpha():
        licznik[z] = licznik.get(z, 0) + 1

Przykład 12. Liczba wystąpień wzorca

Treść: Ile razy "ABA" występuje w "ABABABA"?

Pozycje: 0,2,4.

Odpowiedź: 3.

Przykład 13. Pierwsze wystąpienie

pierwsza = -1
for i in range(len(t)-len(w)+1):
    if t[i:i+len(w)] == w:
        pierwsza = i
        break

Przykład 14. Cezar: MATURA, k=3

M→P, A→D, T→W, U→X, R→U, A→D.

Wynik: PDWXUD.

Przykład 15. Odszyfrowanie PDWXUD

Klucz 3 wstecz daje MATURA.

Wniosek / wynik: Klucz 3 wstecz daje MATURA.

Przykład 16. Wzorzec dłuższy od tekstu

Nie ma żadnej pozycji startowej. Wynik: 0 wystąpień.

Wniosek / wynik: Nie ma żadnej pozycji startowej. Wynik: 0 wystąpień.

Przykład 17. Pusty wzorzec

W zadaniu egzaminacyjnym trzeba stosować definicję podaną w treści. Nie wolno samodzielnie zakładać interpretacji, jeżeli przypadek nie jest określony.

Wniosek / wynik: W zadaniu egzaminacyjnym trzeba stosować definicję podaną w treści. Nie wolno samodzielnie zakładać interpretacji, jeżeli przypadek nie jest określony.

Przykład 18. Cezar a przestawieniowy

W Cezarze zmieniają się znaki, ale ich pozycje pozostają. W przestawieniowym zachowujemy znaki, lecz zmieniamy ich kolejność.

Wniosek / wynik: W Cezarze zmieniają się znaki, ale ich pozycje pozostają. W przestawieniowym zachowujemy znaki, lecz zmieniamy ich kolejność.

Przykład rozszerzony. Wszystkie wystąpienia wzorca

Treść zadania: Znajdź wszystkie pozycje wzorca "AA" w tekście "AAAA".

Sprawdzamy starty 0,1,2. Na każdym z nich dwa znaki są równe "AA".

Odpowiedź: pozycje 0,1,2.

Ważne: wystąpienia mogą się nakładać; nie wolno po znalezieniu automatycznie przeskakiwać o długość wzorca.

Przykład rozszerzony. Cezar z zawijaniem alfabetu

Treść zadania: Zaszyfruj "XYZ" szyfrem Cezara z kluczem 3.

X→A, Y→B, Z→C. Zawinięcie realizuje modulo 26.

Odpowiedź: ABC.

Kontrola: odszyfrowanie o 3 pozycje wstecz daje XYZ.

Przykład 1. Ile bitów?

1000 bajtów = 8000 bitów.

Wniosek / wynik: 1000 bajtów = 8000 bitów.

Przykład 2. ASCII — idea

Litera 'A' ma kod liczbowy. Program nie przechowuje „kształtu litery”, tylko wartość kodową interpretowaną według standardu.

Wniosek / wynik: Litera 'A' ma kod liczbowy. Program nie przechowuje „kształtu litery”, tylko wartość kodową interpretowaną według standardu.

Przykład 3. Obraz 100×200, 24 bity/piksel

100·200·24=480 000 bitów = 60 000 bajtów.

Odpowiedź: 60 000 B bez narzutów i kompresji.

Przykład 4. 256 kolorów

256=2⁸, więc do zapisania numeru jednego z 256 kolorów wystarczy 8 bitów.

Wniosek / wynik: 256=2⁸, więc do zapisania numeru jednego z 256 kolorów wystarczy 8 bitów.

Przykład 5.

Tekst źródłowy i kod programu wymagają zwykle kompresji bezstratnej, bo utrata pojedynczych znaków zmieniłaby dane.

Wniosek / wynik: Tekst źródłowy i kod programu wymagają zwykle kompresji bezstratnej, bo utrata pojedynczych znaków zmieniłaby dane.

Przykład 6. Router i switch

Switch łączy urządzenia w sieci lokalnej. Router przekazuje pakiety między różnymi sieciami.

Wniosek / wynik: Switch łączy urządzenia w sieci lokalnej. Router przekazuje pakiety między różnymi sieciami.

Przykład 7.

Użytkownik wpisuje nazwę domeny. DNS pomaga ustalić adres IP serwera, z którym ma zostać nawiązane połączenie.

Wniosek / wynik: Użytkownik wpisuje nazwę domeny. DNS pomaga ustalić adres IP serwera, z którym ma zostać nawiązane połączenie.

Przykład 8. TCP czy UDP?

Gdy kluczowa jest niezawodność i kolejność danych, naturalnym wyborem jest TCP. W zastosowaniach czasu rzeczywistego może być używany UDP, jeśli aplikacja toleruje utratę części pakietów.

Wniosek / wynik: Gdy kluczowa jest niezawodność i kolejność danych, naturalnym wyborem jest TCP. W zastosowaniach czasu rzeczywistego może być używany UDP, jeśli aplikacja toleruje utratę części pakietów.

Przykład 9. Bluetooth

Technologia krótkiego zasięgu używana np. do komunikacji słuchawek bezprzewodowych z telefonem.

Wniosek / wynik: Technologia krótkiego zasięgu używana np. do komunikacji słuchawek bezprzewodowych z telefonem.

Przykład 10. NFC

Technologia bardzo krótkiego zasięgu, stosowana m.in. w płatnościach zbliżeniowych i identyfikacji.

Wniosek / wynik: Technologia bardzo krótkiego zasięgu, stosowana m.in. w płatnościach zbliżeniowych i identyfikacji.

Przykład 11.

Pracownik poza biurem może wykorzystać VPN do dostępu do zasobów prywatnej sieci firmy.

Wniosek / wynik: Pracownik poza biurem może wykorzystać VPN do dostępu do zasobów prywatnej sieci firmy.

Przykład 12. Hasła

Silne i unikalne hasła ograniczają skutki wycieku jednego serwisu. Menedżer haseł pomaga używać różnych haseł bez ich zapamiętywania.

Wniosek / wynik: Silne i unikalne hasła ograniczają skutki wycieku jednego serwisu. Menedżer haseł pomaga używać różnych haseł bez ich zapamiętywania.

Przykład 13. MFA

Uwierzytelnianie wieloskładnikowe wymaga co najmniej dwóch różnych czynników, np. hasła i kodu z aplikacji.

Wniosek / wynik: Uwierzytelnianie wieloskładnikowe wymaga co najmniej dwóch różnych czynników, np. hasła i kodu z aplikacji.

Przykład 14. Phishing

Atakujący podszywa się pod zaufaną instytucję, aby skłonić użytkownika do ujawnienia danych lub wykonania niebezpiecznej czynności.

Wniosek / wynik: Atakujący podszywa się pod zaufaną instytucję, aby skłonić użytkownika do ujawnienia danych lub wykonania niebezpiecznej czynności.

Przykład 15. Rozmiar obrazu

Obraz 800×600 przy 24 bitach/piksel: 800·600·24=11 520 000 bitów = 1 440 000 bajtów bez kompresji i narzutów.

Wniosek / wynik: Obraz 800×600 przy 24 bitach/piksel: 800·600·24=11 520 000 bitów = 1 440 000 bajtów bez kompresji i narzutów.

Przykład 16. Rozpoznanie technologii

Tunel przez publiczny Internet do prywatnej sieci firmy → VPN. Krótkodystansowe słuchawki → Bluetooth. Bardzo bliska komunikacja zbliżeniowa → NFC.

Wniosek / wynik: Tunel przez publiczny Internet do prywatnej sieci firmy → VPN. Krótkodystansowe słuchawki → Bluetooth. Bardzo bliska komunikacja zbliżeniowa → NFC.

Przykład rozszerzony. Czas przesłania pliku

Treść zadania: Plik ma 120 MB. Łącze ma przepustowość 20 Mb/s. Oszacuj minimalny czas transmisji, pomijając narzuty protokołów.

120 MB = 120·8 = 960 Mb.

Czas = 960 Mb / 20 Mb/s = 48 s.

Odpowiedź: 48 sekund.

Pułapka: MB i Mb to nie to samo — bajty trzeba przeliczyć na bity.