Matura informatyka

Matura 2026 — maj, poziom rozszerzony (formuła 2023)

PythonC++23Java 25
Treść zadania

Dla dodatnich liczb całkowitych m, n funkcja A jest zdefiniowana rekurencyjnie:

  • A(m, n) = m, gdy n = 1;
  • A(m, n) = A(2·m, n/2), gdy n > 1 i n jest parzyste;
  • A(m, n) = 2·A(m, (n − 1)/2) + m, gdy n > 1 i n jest nieparzyste.

Przykład: obliczenie A(3, 9) wymaga trzech wywołań rekurencyjnych A(3, 4), A(6, 2), A(12, 1), bo A(3, 9) = 2·A(3, 4) + 3 = 2·A(6, 2) + 3 = 2·A(12, 1) + 3 = 27.

Uzupełnij tabelę: dla par (m, n) = (2⁵, 2⁵) oraz (10, 15) podaj liczbę wywołań rekurencyjnych funkcji A i wypisz te wywołania z argumentami, a dla (1, 2¹⁰⁰ + 1) podaj tylko liczbę wywołań rekurencyjnych.

Python
def A(m, n, wywolania):
    # wywolania - lista, do której dopisujemy argumenty kolejnych wywołań rekurencyjnych
    if n == 1:
        return m
    if n % 2 == 0:
        wywolania.append((2 * m, n // 2))
        return A(2 * m, n // 2, wywolania)
    wywolania.append((m, (n - 1) // 2))
    return 2 * A(m, (n - 1) // 2, wywolania) + m


for m, n in [(3, 9), (2 ** 5, 2 ** 5), (10, 15), (1, 2 ** 100 + 1)]:
    wywolania = []
    A(m, n, wywolania)
    print(m, n, len(wywolania), wywolania if len(wywolania) < 10 else "")

Odpowiedź: (2⁵, 2⁵): 5 wywołań — A(2⁶, 2⁴), A(2⁷, 2³), A(2⁸, 2²), A(2⁹, 2¹), A(2¹⁰, 2⁰); (10, 15): 3 wywołania — A(10, 7), A(10, 3), A(10, 1); (1, 2¹⁰⁰ + 1): 100 wywołań.

↑
PythonC++23Java 25
Treść zadania

Funkcja A(m, n) jest zdefiniowana w zadaniu 1.1.

Podaj wartości A(1, 777) oraz A(2·10⁶, 256·10⁶). Wynik można zapisać z użyciem mnożenia i potęgowania.

Python
def A(m, n):
    if n == 1:
        return m
    if n % 2 == 0:
        return A(2 * m, n // 2)
    return 2 * A(m, (n - 1) // 2) + m


# funkcja A liczy iloczyn m * n
print(A(1, 777))
print(A(2 * 10 ** 6, 256 * 10 ** 6))

Odpowiedź: A(1, 777) = 777, A(2·10⁶, 256·10⁶) = 512·10¹² = 512 000 000 000 000 (funkcja oblicza m·n).

↑
PythonC++23Java 25
Treść zadania

Funkcja A(m, n) jest zdefiniowana w zadaniu 1.1; pierwszy argument nie ma tu znaczenia.

Dla n = 8, n = 2ᵏ oraz n = 2ᵏ − 1 podaj liczbę wywołań rekurencyjnych funkcji A oraz wyrażenie opisujące drugi argument w i-tym wywołaniu rekurencyjnym (dla i od 1 do liczby wywołań). Przykład dla n = 8: drugi argument w i-tym wywołaniu to 8/2ⁱ, czyli 2³⁻ⁱ.

Python
def drugie_argumenty(n):
    # wartości drugiego argumentu w kolejnych wywołaniach rekurencyjnych
    wynik = []
    while n > 1:
        if n % 2 == 0:
            n = n // 2
        else:
            n = (n - 1) // 2
        wynik.append(n)
    return wynik


print(8, drugie_argumenty(8))
for k in range(3, 7):
    print("n = 2^%d:" % k, drugie_argumenty(2 ** k))
    print("n = 2^%d - 1:" % k, drugie_argumenty(2 ** k - 1))

Odpowiedź: n = 8: 3 wywołania, i-te ma drugi argument 8/2ⁱ = 2³⁻ⁱ; n = 2ᵏ: k wywołań, drugi argument 2ᵏ⁻ⁱ; n = 2ᵏ − 1: k − 1 wywołań, drugi argument 2ᵏ⁻ⁱ − 1.

↑
PythonC++23Java 25
Treść zadania

Rozważamy dodawanie pisemne dwóch liczb w systemie dziesiętnym i liczymy przeniesienia, np. przy dodawaniu 27732 + 72619 = 100351 występują 4 przeniesienia.

  • 2.1 — Podaj liczbę przeniesień przy dodawaniu par: 37932 + 12528 (przykład w tabeli: 3), 88765 + 11111 oraz 456789 + 222222.
  • 2.2 — Zapisz (w pseudokodzie lub wybranym języku) algorytm, który dla dwóch dodatnich liczb całkowitych a i b o tej samej liczbie cyfr oblicza liczbę p przeniesień w trakcie ich dodawania pisemnego (dla 27732 i 72619 wynik to 4).
Python
def przeniesienia(a, b):
    # a i b mają tyle samo cyfr; operujemy tylko na liczbach całkowitych
    w_pamieci = 0
    p = 0
    while a > 0:
        suma = a % 10 + b % 10 + w_pamieci
        if suma >= 10:
            w_pamieci = 1
            p += 1
        else:
            w_pamieci = 0
        a = a // 10
        b = b // 10
    return p


print(przeniesienia(27732, 72619))  # przykład z treści: 4
for a, b in [(37932, 12528), (88765, 11111), (456789, 222222)]:
    print(a, b, przeniesienia(a, b))

Odpowiedź: 2.1: 37932 + 12528 → 3, 88765 + 11111 → 0, 456789 + 222222 → 3. 2.2: funkcja przeniesienia powyżej.

↑
PythonC++23Java 25
Treść zadania

Plik pary.txt zawiera 500 wierszy; w każdym jest para słów z małych liter alfabetu angielskiego, oddzielonych pojedynczą spacją, każde o długości co najwyżej 50 (np. bcba babb, abaa ccc). Odpowiedzi zapisz w pliku wyniki3.txt, poprzedzając każdą numerem zadania. Plik pary_przyklad.txt (500 par) służy do testów.

Niech f(s) oznacza sumę kodów ASCII liter słowa s. Podaj parę słów s1, s2 z jednego wiersza, dla której |f(s1) − f(s2)| jest największe, oraz tę wartość (jest jedna taka para). Przykład: f(oko) = 329, f(pies) = 433, różnica 104; dla pliku przykładowego: eddcd eededcddceeecededcc 1403.

Python
def f(slowo):
    return sum(ord(znak) for znak in slowo)


najwieksza = -1
with open("pary.txt") as file:
    for linia in file:
        s1, s2 = linia.split()
        roznica = abs(f(s1) - f(s2))
        if roznica > najwieksza:
            najwieksza = roznica
            para = (s1, s2)

print(para[0], para[1], najwieksza)

Odpowiedź: gpeeazeugmvsbzwsrxfplqdbakoxxe lhpbmoirdm 2206

↑
PythonC++23Java 25
Treść zadania

Dane jak w zadaniu 3.1 (500 par słów w pliku pary.txt).

Wspólna liczba wystąpień litery x w słowach s1, s2 to W(x, s1, s2) = min(d(x, s1), d(x, s2)), gdzie d(x, s) to liczba wystąpień x w s. Podaj parę słów z jednego wiersza, dla której suma W po wszystkich literach jest największa, oraz tę sumę (jest jedna taka para). Przykład: dla adabbcdde i aadabbbccdc suma wynosi 2 + 2 + 1 + 2 = 7; dla pliku przykładowego: ccccdcedddddecde ccdcdddecc 10.

Python
najwieksza = -1
with open("pary.txt") as file:
    for linia in file:
        s1, s2 = linia.split()
        suma = 0
        for litera in "abcdefghijklmnopqrstuvwxyz":
            suma += min(s1.count(litera), s2.count(litera))
        if suma > najwieksza:
            najwieksza = suma
            para = (s1, s2)

print(para[0], para[1], najwieksza)

Odpowiedź: aacbcccaacacbcabac cccccaaaacaccbabcba 18

↑
PythonC++23Java 25Kod
Treść zadania

Dane jak w zadaniu 3.1.

Prefiksosufiks pary słów s1, s2 to słowo, które jest początkiem s1 i końcem s2 albo początkiem s2 i końcem s1. Wypisz wszystkie pary z pliku, których najdłuższy prefiksosufiks ma co najmniej 5 liter, a przy każdej podaj długość tego najdłuższego prefiksosufiksu. Przykład: dla aabbbca caacaab najdłuższy prefiksosufiks to aab (3 litery) — para nie spełnia warunku; dla abbaabaa baabaabba jest to baabaa (6) — spełnia; dla pliku przykładowego: ececdddeed dddeedd 6.

Python
def najdluzszy_prefiksosufiks(s1, s2):
    for dlugosc in range(min(len(s1), len(s2)), 0, -1):
        if s1[:dlugosc] == s2[-dlugosc:] or s2[:dlugosc] == s1[-dlugosc:]:
            return dlugosc
    return 0


with open("pary.txt") as file:
    for linia in file:
        s1, s2 = linia.split()
        dlugosc = najdluzszy_prefiksosufiks(s1, s2)
        if dlugosc >= 5:
            print(s1, s2, dlugosc)

Odpowiedź:

Kod
bbbbaabbababbaaaa baaaaabaaabbbabab 5
aababbbababbbbbbaab bbbbaabbababababa 7
aaaababaaaabbbb aabbbbbabbbaaaa 6
bbbbabaaabbbabb aaababaabbbbbbba 5
ccccabacbba acbbabcbcbcbaa 5
caabbccabccc cabccccabbaac 6
abaacabcccccabbbc abbbcbbbbbcabaca 5
↑
PythonC++23Java 25
Treść zadania

W korporacji pracuje n osób o numerach 1..n. Pracownik 1 jest prezesem i nie ma przełożonego; każdy inny ma dokładnie jednego bezpośredniego przełożonego o mniejszym numerze. Przełożonymi pracownika są jego bezpośredni przełożony i wszyscy przełożeni tamtego; podwładni są zdefiniowani odwrotnie. W przykładowej hierarchii (rysunek w arkuszu) bezpośrednimi przełożonymi pracowników 2–8 są kolejno 1, 2, 1, 2, 2, 3, 4.

Dla każdego pracownika z przykładowej hierarchii podaj liczbę jego bezpośrednich podwładnych oraz liczbę wszystkich podwładnych.

Python
# przykładowa hierarchia z Rysunku 1. (zapis jak w pliku: przełożony pracownika i)
szef = [0, 1, 2, 1, 2, 2, 3, 4]
n = len(szef)
bezposredni = [0] * (n + 1)
wszyscy = [0] * (n + 1)
for i in range(2, n + 1):
    bezposredni[szef[i - 1]] += 1
    p = szef[i - 1]
    while p != 0:  # każdy przełożony pracownika i ma go wśród podwładnych
        wszyscy[p] += 1
        p = szef[p - 1]

for i in range(1, n + 1):
    print(i, bezposredni[i], wszyscy[i])

Odpowiedź: 1: 2 i 7; 2: 3 i 4; 3: 1 i 1; 4: 1 i 1; 5, 6, 7, 8: 0 i 0.

↑
PythonC++23Java 25
Treść zadania

Plik korpo.txt zawiera n = 50 000 liczb, po jednej w wierszu, opisujących strukturę korporacji z zadania 4.1: w pierwszym wierszu jest 0 (prezes nie ma przełożonego), a w i-tym wierszu (2 ≤ i ≤ 50 000) — numer bezpośredniego przełożonego pracownika i (dla przykładowej hierarchii: 0 1 2 1 2 2 3 4). Odpowiedzi zapisz w pliku wyniki4.txt, poprzedzając każdą numerem zadania. W pliku testowym korpo_przyklad.txt przełożonym pracowników 2 i 3 jest 1, a wszystkich pozostałych — 3.

  • 4.2 — Podaj, ilu pracowników nie jest przełożonym nikogo (dla pliku przykładowego: 49 998).
  • 4.3 — Podaj numer pracownika mającego najwięcej bezpośrednich podwładnych oraz ich liczbę (dla pliku przykładowego: 3 49997).
  • 4.4 — Podaj największą liczbę przełożonych, jaką ma jeden pracownik, oraz liczbę pracowników mających tylu przełożonych (dla pliku przykładowego: 2 49997).
Python
szef = [0]  # szef[i] - bezpośredni przełożony pracownika i (indeks 0 nieużywany)
with open("korpo.txt") as file:
    for linia in file:
        szef.append(int(linia))
n = len(szef) - 1

# 4.2
podwladni = [0] * (n + 1)
for i in range(2, n + 1):
    podwladni[szef[i]] += 1
print("4.2", podwladni[1:].count(0))

# 4.3
numer = 1
for i in range(2, n + 1):
    if podwladni[i] > podwladni[numer]:
        numer = i
print("4.3", numer, podwladni[numer])

# 4.4 - liczba przełożonych = głębokość pracownika w drzewie
glebokosc = [-1] * (n + 1)
glebokosc[1] = 0
for i in range(2, n + 1):
    sciezka = []
    p = i
    while glebokosc[p] == -1:
        sciezka.append(p)
        p = szef[p]
    for q in reversed(sciezka):
        glebokosc[q] = glebokosc[szef[q]] + 1

najwiecej = max(glebokosc)
print("4.4", najwiecej, glebokosc.count(najwiecej))

Odpowiedź: 4.2: 25113; 4.3: 2 19 (pracownik 2 ma 19 bezpośrednich podwładnych); 4.4: 22 2 (najwięcej przełożonych: 22, mają ich 2 osoby).

↑
PythonC++23Java 25
Treść zadania

Uzupełnij brakujące liczby tak, aby obie równości były prawdziwe: 1440₅ + …₅ = 427₁₀ = …₃ − 110002₃ (pierwsza luka w systemie piątkowym, druga w trójkowym).

Python
def na_system(liczba, podstawa):
    cyfry = ""
    while liczba > 0:
        cyfry = str(liczba % podstawa) + cyfry
        liczba //= podstawa
    return cyfry


# 1440(5) + x(5) = 427(10) = y(3) - 110002(3)
x = 427 - int("1440", 5)
y = 427 + int("110002", 3)
print(na_system(x, 5), na_system(y, 3))

Odpowiedź: (1440)₅ + (1212)₅ = (427)₁₀ = (1000220)₃ − (110002)₃

↑

Edytuj na GitHubie