Matura informatyka

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

PythonC++23Java 25
Treść zadania

Dla ciągu A liczb całkowitych dodatnich tworzymy jego opis B: każdy maksymalny fragment A będący p-krotnym powtórzeniem liczby x zastępujemy parą liczb p, x. Np. opisem (1, 1, 3, 2, 2, 2, 1) jest (2, 1, 1, 3, 3, 2, 1, 1), a opisem (2, 2, 2, 2, 5, 3, 3) — (4, 2, 1, 5, 2, 3).

  • 1.1 — Uzupełnij tabelę: dla ciągów (3, 3, 3, 2, 2, 1, 1, 1, 6) i (2, 2, 2, 2, 2, 2) podaj opis i jego długość (liczbę elementów B); dla opisu (4, 1, 1, 4) odtwórz ciąg A.
  • 1.2 — Zapisz algorytm, który dla tablicy A[1..n] liczb całkowitych dodatnich obliczy długość jej opisu (liczbę elementów ciągu B). Wolno używać tylko podstawowych operacji arytmetycznych, porównań, odwołań do pojedynczych elementów tablicy i instrukcji sterujących — bez funkcji wbudowanych.
Python
def opis(A):
    B = []
    i = 0
    while i < len(A):
        p = 1
        while i + p < len(A) and A[i + p] == A[i]:
            p += 1
        B += [p, A[i]]
        i += p
    return B


# 1.2 - długość opisu: każda zmiana wartości rozpoczyna nowy fragment (2 liczby)
def dlugosc_opisu(A, n):
    w = 2
    for i in range(n - 1):
        if A[i] != A[i + 1]:
            w += 2
    return w


# 1.1
for A in [[3, 3, 3, 2, 2, 1, 1, 1, 6], [2, 2, 2, 2, 2, 2]]:
    print(A, opis(A), dlugosc_opisu(A, len(A)))

B = [4, 1, 1, 4]                  # odtworzenie ciągu A z opisu
A = []
for i in range(0, len(B), 2):
    A += [B[i + 1]] * B[i]
print(A, B, len(B))

Odpowiedź: 1.1: (3, 3, 3, 2, 2, 1, 1, 1, 6) → (3, 3, 2, 2, 3, 1, 1, 6), długość 8; (2, 2, 2, 2, 2, 2) → (6, 2), długość 2; ciąg A = (1, 1, 1, 1, 4), długość 4. 1.2: funkcja dlugosc_opisu.

↑
PythonC++23Java 25
Treść zadania

Dana jest tablica A[1..n] liczb całkowitych dodatnich i rekurencyjna funkcja f(p, q), gdzie 1 ≤ p ≤ q ≤ n:

Kod
f(p, q):
    jeżeli p < q
        k ← (q - p + 1) div 2
        dla i = 1, 2, ..., k
            zamień(A[p + i - 1], A[q - k + i])
        f(p, p + k - 1)
        f(q - k + 1, q)
  • 2.1 — Podaj zawartość tablicy A po wywołaniu f(1, n) dla: n = 3, A = [2, 3, 4]; n = 4, A = [1, 2, 3, 4]; n = 10, A = [1, 2, ..., 10].
  • 2.2 — Podaj, ile razy wykona się operacja zamień() po wywołaniu f(1, n) dla n = 8, 16 i 256 (dla n = 4 jest to 4). Liczba ta zależy tylko od n.
Python
zamiany = 0


def f(p, q):
    global zamiany
    if p < q:
        k = (q - p + 1) // 2
        for i in range(1, k + 1):
            A[p + i - 1], A[q - k + i] = A[q - k + i], A[p + i - 1]
            zamiany += 1
        f(p, p + k - 1)
        f(q - k + 1, q)


# 2.1 (tablica indeksowana od 1, A[0] nieużywane)
for A in [[0, 2, 3, 4], [0, 1, 2, 3, 4], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]]:
    f(1, len(A) - 1)
    print(A[1:])

# 2.2
for n in [4, 8, 16, 256]:
    A = [0] * (n + 1)
    zamiany = 0
    f(1, n)
    print(n, zamiany)

Odpowiedź: 2.1: [4, 3, 2]; [4, 3, 2, 1]; [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]. 2.2: n = 8 → 12, n = 16 → 32, liczba zamian 1024 dla n = 256.

↑
PythonC++23Java 25
Treść zadania

Plik slowa.txt zawiera 50 słów (długości do 1000) złożonych z małych liter alfabetu angielskiego (dane przykładowe: przyklad.txt).

WK-słowo to słowo, w którym litery w i k występują tyle samo razy (także po 0 razy, np. „matura”). Zapisz w pliku wyniki4_1.txt wszystkie WK-słowa z pliku, każde w osobnym wierszu, w kolejności z pliku.

Python
with open("slowa.txt") as file:
    slowa = [linia.strip() for linia in file if linia.strip()]

with open("wyniki4_1.txt", "w") as wynik:
    for slowo in slowa:
        if slowo.count("w") == slowo.count("k"):
            print(slowo, file=wynik)

Odpowiedź: dsasahdadelebsdsidihdiahsaihd, abba, echwakacjeachwakacje, weweakaddcjjreewakacjerk, … (19 słów, ostatnie: awszystkoprzepasanejakbywstega)

↑
PythonC++23Java 25
Treść zadania

Dane jak w zadaniu 4.1 (50 słów w slowa.txt).

Dla każdego słowa oblicz, ile słów wakacje można ułożyć z jego liter (każdej litery wolno użyć najwyżej raz). Np. dla wwwaaaaakkcccjjee wynik to 2, dla awkcjcje — 0. Zapisz w jednym wierszu pliku wyniki4_2.txt 50 liczb oddzielonych spacjami (i-ta liczba dotyczy i-tego słowa).

Python
with open("slowa.txt") as file:
    slowa = [linia.strip() for linia in file if linia.strip()]

wzor = "wakacje"
wyniki = []
for slowo in slowa:
    ile = len(slowo)
    for litera in set(wzor):
        ile = min(ile, slowo.count(litera) // wzor.count(litera))   # "a" potrzebne 2 razy
    wyniki.append(ile)

with open("wyniki4_2.txt", "w") as wynik:
    print(*wyniki, file=wynik)

Odpowiedź: 0 0 2 2 2 3 2 17 2 6 78 1 19 4 4 91 0 14 4 2 23 1 19 5 6 137 1 21 2 5 88 0 13 3 14 124 2 21 4 8 123 0 0 1 1 1 0 2 2 3

↑
PythonC++23Java 25
Treść zadania

Dane jak w zadaniu 4.1 (50 słów w slowa.txt).

Wakacyjne słowo to słowo wakacje sklejone ze sobą dowolnie wiele razy (także 0 razy — słowo puste). Dla każdego słowa oblicz najmniejszą liczbę liter, które trzeba z niego wykreślić (bez zmiany kolejności pozostałych), aby otrzymać wakacyjne słowo. Np. wakaaaacjee → 4, waktfaczdjeaewasakvgacrje → 11, awkcjcje → 8. Zapisz w jednym wierszu pliku wyniki4_3.txt 50 wyników oddzielonych spacjami.

Python
with open("slowa.txt") as file:
    slowa = [linia.strip() for linia in file if linia.strip()]

wzor = "wakacje"
wyniki = []
for slowo in slowa:
    j = 0           # która litera słowa "wakacje" jest teraz szukana
    pelne = 0       # liczba ułożonych pełnych słów "wakacje"
    for litera in slowo:
        if litera == wzor[j]:
            j += 1
            if j == len(wzor):
                pelne += 1
                j = 0
    wyniki.append(len(slowo) - len(wzor) * pelne)

with open("wyniki4_3.txt", "w") as wynik:
    print(*wyniki, file=wynik)

Odpowiedź: 29 4 6 6 10 17 100 965 33 65 545 100 965 12 79 419 100 972 12 93 951 100 965 5 65 48 100 958 33 65 426 100 965 19 2 146 100 951 12 44 160 9 4 55 0 76 30 24 44 15

↑

Edytuj na GitHubie