Matura informatyka

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

PythonC++23Java 25

Treść zadania (Biblioteczka): Półki są numerowane od 0 (najwyższa); półka i ma 2ⁱ przegródek numerowanych 1..2ⁱ, a B[i, j] to j-ta przegródka na i-tej półce (jedna książka na przegródkę). Adam wstawia książkę, zaczynając od B[0, 1]: jeśli przegródka jest pusta, kładzie ją tam; w przeciwnym razie, gdy numer wstawianej książki jest mniejszy od numeru stojącej, próbuje B[i+1, 2j−1], a gdy większy – B[i+1, 2j]. Np. po wstawieniu 10, 2, 15, 13, 1, 5, 25 półka 0 to [10], półka 1 to [2, 15], półka 2 to [1, 5, 13, 25].

  • 1.1 — Podaj zawartość biblioteczki po wstawieniu (do pustej) kolejno książek 14, 18, 12, 9, 20, 15, 17.
  • 1.2 — Uzupełnij tabelę: ile minimalnie, a ile maksymalnie półek musi mieć biblioteczka, by zmieścić n książek, tak aby na ostatniej półce była co najmniej jedna książka – dla n = 4, 7, 16, 32 oraz n = 2ᵏ − 1 (k > 0). Przykłady: n=1 → 1 i 1; n=2 → 2 i 2; n=3 → 2 i 3.
  • 1.3 — Algorytm A(i, j) (start: A(0, 1)) wypisuje numer książki z B[i, j], a następnie, jeśli niepuste, wywołuje A(i+1, 2j−1) i A(i+1, 2j) (dla przykładu wyżej wypisze 10, 2, 1, 5, 15, 13, 25). Podaj, co wypisze dla dwóch biblioteczek z arkusza: a) półki [9], [2, 12], [10, 14], [13, 15]; b) [10], [8, 15], [4, 12], [6, 13] (rozmieszczenie w przegródkach zgodne z regułą wstawiania).
Python
# biblioteczka jako słownik: (półka, przegródka) -> numer książki
def wstaw(B, ksiazka):
    i, j = 0, 1
    while (i, j) in B:
        if ksiazka < B[(i, j)]:
            i, j = i + 1, 2 * j - 1
        else:
            i, j = i + 1, 2 * j
    B[(i, j)] = ksiazka


def A(B, i, j, wynik):
    wynik.append(B[(i, j)])
    if (i + 1, 2 * j - 1) in B:
        A(B, i + 1, 2 * j - 1, wynik)
    if (i + 1, 2 * j) in B:
        A(B, i + 1, 2 * j, wynik)
    return wynik


# 1.1
B = {}
for k in [14, 18, 12, 9, 20, 15, 17]:
    wstaw(B, k)
for i in range(5):
    print(i, [(j, B[(i, j)]) for j in range(1, 2 ** i + 1) if (i, j) in B])

# 1.2 - minimum: półki zapełnione do końca (2^0 + 2^1 + ... >= n), maksimum: każda książka na innej półce
for n in [1, 3, 4, 7, 16, 31, 32]:
    polki = 0
    miejsca = 0
    while miejsca < n:
        miejsca += 2 ** polki
        polki += 1
    print(n, polki, n)

# 1.3
a = {(0, 1): 9, (1, 1): 2, (1, 2): 12, (2, 3): 10, (2, 4): 14, (3, 7): 13, (3, 8): 15}
b = {(0, 1): 10, (1, 1): 8, (1, 2): 15, (2, 1): 4, (2, 3): 12, (3, 2): 6, (3, 6): 13}
print(A(a, 0, 1, []))
print(A(b, 0, 1, []))

Odpowiedź: 1.1: półka 0: 14; półka 1: 12, 18; półka 2: B[2,1] = 9, B[2,3] = 15, B[2,4] = 20; półka 3: B[3,6] = 17. 1.2 (min, max): n = 7: 3, 7; n = 16: 5, 16; n = 31: 5, 31; n = 32: 6, 32; n = 2^k − 1: k, 2^k − 1. 1.3: a) 9, 2, 12, 10, 14, 13, 15; b) 10, 8, 4, 6, 15, 12, 13.

↑
PythonC++23Java 25

Treść zadania (Liczby binarne): Blok w zapisie binarnym to maksymalny (nierozszerzalny) niepusty ciąg kolejnych jednakowych cyfr, np. 111110000110111 ma 5 bloków.

  • 2.1 — Zapisz algorytm, który dla dodatniej liczby n obliczy liczbę bloków w jej zapisie binarnym (np. 67 = 1000011 → 3, 245 = 11110101 → 5). Wolno używać tylko podstawowych operacji arytmetycznych (w tym div, mod), porównań i instrukcji sterujących – bez funkcji wbudowanych i konwersji systemów.

Plik bin.txt zawiera 100 wierszy z zapisami binarnymi liczb dodatnich (do 20 cyfr). Odpowiedzi do 2.2 i 2.3 zapisz w wyniki2.txt z numerami zadań (do testów: bin_przyklad.txt).

  • 2.2 — Podaj, ile liczb w pliku składa się z co najwyżej dwóch bloków.
  • 2.3 — Wypisz największą liczbę z pliku (w zapisie binarnym; dla przykładu 10001111110111100000).
  • 2.4 — Operacja XOR działa bitowo (1 dla różnych bitów, krótszy zapis uzupełniamy zerami z lewej), np. 4 XOR 7 = 3. Oblicz (123₁₀ XOR 101101₂) XOR 2D₁₆ i podaj wynik dziesiętnie.
  • 2.5 — Dla każdej liczby p z bin.txt oblicz p XOR (p div 2) i zapisz wyniki binarnie do wyniki2_5.txt, każdy w osobnym wierszu, w kolejności z pliku (wynik dla przykładu: odp_bin_przyklad.txt).
Python · 2.1 - liczba bloków bez funkcji wbudowanych
def bloki(n):
    b = 1
    poprzednia = n % 2
    n = n // 2
    while n > 0:
        cyfra = n % 2
        if cyfra != poprzednia:
            b += 1
            poprzednia = cyfra
        n = n // 2
    return b


def na_dziesietny(napis):
    liczba = 0
    for c in napis:
        liczba = liczba * 2 + int(c)
    return liczba


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


print("2.1", bloki(67), bloki(245))

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

# 2.2
print("2.2", sum(1 for x in liczby if bloki(na_dziesietny(x)) <= 2))

# 2.3
print("2.3", na_binarny(max(na_dziesietny(x) for x in liczby)))

# 2.4
print("2.4", (123 ^ 0b101101) ^ 0x2D)

# 2.5
with open("wyniki2_5.txt", "w") as wyniki:
    for x in liczby:
        p = na_dziesietny(x)
        wyniki.write(na_binarny(p ^ (p // 2)) + "\n")

Odpowiedź: 2.1: funkcja bloki (dla 67 → 3, dla 245 → 5). 2.2: 10. 2.3: 1110100011100011100. 2.4: 123. 2.5: plik wyniki2_5.txt: 1001011000, 1111000001, 1110001000, 1101100001111010, … (100 wierszy).

↑
PythonC++23Java 25

Treść zadania (Liczba π): Plik pi.txt zawiera 10 000 wierszy – po jednej cyfrze rozwinięcia π po przecinku (1, 4, 1, 5, 9, …). Odpowiedzi zapisz w wyniki3.txt z numerami zadań (do testów: pi_przyklad.txt – pierwsze 100 wierszy).

  • 3.1 — Fragment 2-cyfrowy to dwie kolejne cyfry z pliku (jest ich 9999). Podaj, ile fragmentów jest zapisem liczby większej od 90 (dla przykładu: 13).
  • 3.2 — Spośród 100 możliwych fragmentów 00–99 znajdź ten, który występuje najrzadziej, i ten, który występuje najczęściej, podając je z liczbą wystąpień; przy remisie wybierz fragment o mniejszej wartości (dla przykładu: 00 0 i 62 4).

Ciąg co najmniej 4-elementowy jest rosnąco-malejący, jeśli dla pewnego k ∈ {2, …, n−2} zachodzi a₁ < … < aₖ oraz aₖ₊₁ > … > aₙ (np. (2,5,7,9,8,3,1) i (5,9,9,4,1) są takie, a (1,2,3,4) czy (5,5,3,2,1) – nie).

  • 3.3 — Podaj, ile jest rosnąco-malejących ciągów złożonych z dokładnie sześciu kolejnych cyfr pliku (dla przykładu: 3).
  • 3.4 — Znajdź najdłuższy rosnąco-malejący ciąg kolejnych cyfr (jest jedyny) i podaj w dwóch wierszach: pozycję (numer wiersza) jego początku oraz sam ciąg cyfr bez spacji (dla przykładu: 77 i 0899862).
Python
with open("pi.txt") as file:
    cyfry = [int(linia) for linia in file if linia.strip()]

# 3.1
fragmenty = [cyfry[i] * 10 + cyfry[i + 1] for i in range(len(cyfry) - 1)]
print("3.1", sum(1 for f in fragmenty if f > 90))

# 3.2
ile = [0] * 100
for f in fragmenty:
    ile[f] += 1
najrzadszy = ile.index(min(ile))  # index zwraca pierwszy, czyli najmniejszy fragment
najczestszy = ile.index(max(ile))
print("3.2", f"{najrzadszy:02d}", ile[najrzadszy])
print("3.2", f"{najczestszy:02d}", ile[najczestszy])


def rosnaco_malejacy(c):
    n = len(c)
    if n < 4:
        return False
    for k in range(2, n - 1):  # a1..ak rosnący, a(k+1)..an malejący
        rosnie = all(c[i] < c[i + 1] for i in range(k - 1))
        maleje = all(c[i] > c[i + 1] for i in range(k, n - 1))
        if rosnie and maleje:
            return True
    return False


# 3.3
print("3.3", sum(1 for i in range(len(cyfry) - 5) if rosnaco_malejacy(cyfry[i:i + 6])))

# 3.4 - ciąg rosnąco-malejący cyfr ma najwyżej 20 elementów (10 rosnących + 10 malejących)
najlepszy_start = 0
najlepsza_dlugosc = 0
for i in range(len(cyfry)):
    for dlugosc in range(4, 21):
        if i + dlugosc <= len(cyfry) and dlugosc > najlepsza_dlugosc:
            if rosnaco_malejacy(cyfry[i:i + dlugosc]):
                najlepszy_start = i
                najlepsza_dlugosc = dlugosc
print("3.4", najlepszy_start + 1)
print("".join(str(c) for c in cyfry[najlepszy_start:najlepszy_start + najlepsza_dlugosc]))

Odpowiedź: 3.1: 902. 3.2: 88 80 (najrzadszy), 65 124 (najczęstszy). 3.3: 214. 3.4: pozycja 2781, ciąg 014576540.

↑
PythonC++23Java 25
Treść zadania

Liczby zapisano w systemach o podstawach 3, 5 i 6. Wstaw w miejsce kropek znak <, > lub =: (2011)₃ … (134)₆ (w arkuszu uzupełnione jako przykład: =), (134)₅ … (134)₆, (2222)₃ … (1111)₆.

Python
def na_dziesietny(napis, podstawa):
    liczba = 0
    for c in napis:
        liczba = liczba * podstawa + int(c)
    return liczba


for (x, px), (y, py) in [(("2011", 3), ("134", 6)), (("134", 5), ("134", 6)), (("2222", 3), ("1111", 6))]:
    a, b = na_dziesietny(x, px), na_dziesietny(y, py)
    print(a, "<" if a < b else (">" if a > b else "="), b)

Odpowiedź: (2011)₃ = (134)₆ (58 = 58), (134)₅ < (134)₆ (44 < 58), (2222)₃ < (1111)₆ (80 < 259).

↑

Edytuj na GitHubie