Matura informatyka

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

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.

  • 1.1 — Dla par (m, n) = (32, 17), (2⁵, 2⁵) i (10, 15) podaj liczbę wywołań rekurencyjnych funkcji A i wypisz te wywołania z argumentami; dla (1, 2¹⁰⁰ + 1) podaj tylko liczbę wywołań rekurencyjnych.
  • 1.2 — Podaj wartości A(1, 777) oraz A(2·10⁹, 256·10⁹) (wynik można zapisać z użyciem mnożenia, potęgowania i dodawania).
  • 1.3 — Dla n = 2ᵏ oraz n = 2ᵏ − 1 (k — liczba całkowita większa od 2) podaj liczbę wywołań rekurencyjnych funkcji A oraz wyrażenie opisujące drugi argument w i-tym wywołaniu rekurencyjnym (pierwszy argument nie ma znaczenia). Przykład dla n = 8: 3 wywołania, drugi argument w i-tym to 8/2ⁱ, czyli 2³⁻ⁱ.
Python
wywolania = []                      # argumenty kolejnych wywołań rekurencyjnych


def A(m, n, pierwsze=True):
    if not pierwsze:
        wywolania.append((m, n))
    if n == 1:
        return m
    if n % 2 == 0:
        return A(2 * m, n // 2, False)
    return 2 * A(m, (n - 1) // 2, False) + m


# 1.1
for m, n in [(32, 17), (2 ** 5, 2 ** 5), (10, 15), (1, 2 ** 100 + 1)]:
    wywolania = []
    A(m, n)
    print(m, n, len(wywolania), wywolania if n < 1000 else "")

# 1.2 - funkcja oblicza iloczyn m * n
print(A(1, 777), A(2 * 10 ** 9, 256 * 10 ** 9))

# 1.3 - drugie argumenty kolejnych wywołań dla n = 2^k oraz n = 2^k - 1
for k in range(3, 7):
    for n in [2 ** k, 2 ** k - 1]:
        wywolania = []
        A(1, n)
        print(k, n, len(wywolania), [drugi for pierwszy, drugi in wywolania])

Odpowiedź: 1.1: (32, 17): 4 wywołania – A(32, 8), A(64, 4), A(128, 2), A(256, 1); (2⁵, 2⁵): 5 – A(2⁶, 2⁴), A(2⁷, 2³), A(2⁸, 2²), A(2⁹, 2¹), A(2¹⁰, 2⁰); (10, 15): 3 – A(10, 7), A(10, 3), A(10, 1); (1, 2¹⁰⁰ + 1): 100. 1.2: 777; 512 · 10¹⁸. 1.3: n = 2ᵏ: k wywołań, i-te ma drugi argument 2ᵏ⁻ⁱ; n = 2ᵏ − 1: k − 1 wywołań, i-te ma 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 88765 + 11111 oraz 456789 + 222222 (przykład w tabeli: 37932 + 12528 → 3).
  • 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). Wolno używać tylko zmiennych przechowujących pojedyncze liczby całkowite, operatorów arytmetycznych (w tym dzielenia całkowitego i reszty), logicznych, porównań, przypisań i własnych funkcji — bez funkcji wbudowanych, tablic/list i konwersji liczba ↔ napis.
Python · 2.2
def przeniesienia(a, b):
    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 //= 10
        b //= 10
    return p


# 2.1
for a, b in [(88765, 11111), (456789, 222222)]:
    print(a, b, przeniesienia(a, b))

Odpowiedź: 2.1: 88765 i 11111 – 0; 456789 i 222222 – 3. 2.2: funkcja przeniesienia.

↑
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. Odpowiedzi zapisz w pliku wyniki4.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 (np. f(oko) = 329, f(pies) = 433).

  • a) Podaj parę słów s1, s2 z jednego wiersza, dla której f(s1) + f(s2) jest najmniejsza, oraz tę sumę (dla pliku przykładowego: aba aab 584).
  • b) Podaj parę słów z jednego wiersza, dla której |f(s1) − f(s2)| jest największe, oraz tę wartość (jest jedna taka para; dla pliku przykładowego: eddcd eededcddceeecededcc 1403).
Python
pary = []
with open("pary.txt") as file:
    for linia in file:
        if linia.strip():
            pary.append(linia.split())


def f(s):
    return sum(ord(c) for c in s)


a = min(pary, key=lambda para: f(para[0]) + f(para[1]))
b = max(pary, key=lambda para: abs(f(para[0]) - f(para[1])))

with open("wyniki4.txt", "w") as wynik:
    print("4.1", file=wynik)
    print("a)", a[0], a[1], f(a[0]) + f(a[1]), file=wynik)
    print("b)", b[0], b[1], abs(f(b[0]) - f(b[1])), file=wynik)

Odpowiedź: a) bca cdd 593; b) gpeeazeugmvsbzwsrxfplqdbakoxxe lhpbmoirdm 2206.

↑
PythonC++23Java 25
Treść zadania

Dane jak w zadaniu 4.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 (np. dla adabbcdd i aadabbbccdc: a: 2, b: 2, c: 1, d: 2, suma 7).

  • a) Podaj parę (lub wszystkie pary, jeśli jest ich więcej) z jednego wiersza, w której litera b ma największą wspólną liczbę wystąpień (dla pliku przykładowego: bbabac bbac).
  • b) Podaj parę z jednego wiersza, dla której suma wspólnych wystąpień wszystkich liter jest największa (jest jedna taka; dla pliku przykładowego: ccccdcedddddecde ccdcdddecc).
Python
pary = []
with open("pary.txt") as file:
    for linia in file:
        if linia.strip():
            pary.append(linia.split())


def W(x, s1, s2):
    return min(s1.count(x), s2.count(x))


def suma_wspolnych(para):
    s1, s2 = para
    return sum(W(x, s1, s2) for x in "abcdefghijklmnopqrstuvwxyz")


najwiecej_b = max(W("b", s1, s2) for s1, s2 in pary)
b = max(pary, key=suma_wspolnych)

with open("wyniki4.txt", "a") as wynik:
    print("4.2", file=wynik)
    print("a)", file=wynik)
    for s1, s2 in pary:
        if W("b", s1, s2) == najwiecej_b:
            print(s1, s2, file=wynik)
    print("b)", b[0], b[1], file=wynik)

Odpowiedź: a) abbbbaabbbabbba abbbbbbbbbabbabbaba oraz aababbbababbbbbbaab bbbbaabbababababa; b) aacbcccaacacbcabac cccccaaaacaccbabcba.

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

Dane jak w zadaniu 4.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
pary = []
with open("pary.txt") as file:
    for linia in file:
        if linia.strip():
            pary.append(linia.split())


def prefiksosufiks(s1, s2):
    najdluzszy = 0
    for d in range(1, min(len(s1), len(s2)) + 1):
        if s1[:d] == s2[-d:] or s2[:d] == s1[-d:]:
            najdluzszy = d
    return najdluzszy


with open("wyniki4.txt", "a") as wynik:
    print("4.3", file=wynik)
    for s1, s2 in pary:
        d = prefiksosufiks(s1, s2)
        if d >= 5:
            print(s1, s2, d, file=wynik)

Odpowiedź:

Kod
bbbbaabbababbaaaa baaaaabaaabbbabab 5
aababbbababbbbbbaab bbbbaabbababababa 7
aaaababaaaabbbb aabbbbbabbbaaaa 6
bbbbabaaabbbabb aaababaabbbbbbba 5
ccccabacbba acbbabcbcbcbaa 5
caabbccabccc cabccccabbaac 6
abaacabcccccabbbc abbbcbbbbbcabaca 5
↑

Edytuj na GitHubie