Matura informatyka

Matura 2024 — czerwiec (termin dodatkowy), poziom rozszerzony (formuła 2023)

PythonC++23Java 25
Treść zadania

Mamy tablicę o w wierszach i k kolumnach oraz dodatnią liczbę n. Cyfry zapisu binarnego n wpisujemy wierszami od lewego górnego rogu; po wpisaniu ostatniej cyfry zaczynamy znowu od pierwszej, aż do zapełnienia tablicy. Szukamy cyfry w prawym dolnym rogu. Np. dla w = 5, k = 3, n = 19 (10011) w prawym dolnym rogu jest 1.

  • 1.1 — Wpisz cyfry binarne liczby n = 179 do tablicy o wymiarach w = 4, k = 5.
  • 1.2 — Zapisz algorytm, który dla dodatnich w, k, n wyznaczy cyfrę binarną stojącą w prawym dolnym rogu tablicy w × k. Wolno używać tylko podstawowych operacji arytmetycznych, porównań, odwołań do elementów tablicy i instrukcji sterujących (bez funkcji wbudowanych).
Python · 1.1
def tablica(n, w, k):
    cyfry = bin(n)[2:]
    for i in range(w):
        wiersz = [cyfry[(i * k + j) % len(cyfry)] for j in range(k)]
        print(*wiersz)


tablica(179, 4, 5)


# 1.2 - tylko operacje arytmetyczne
def prawy_dolny(w, k, n):
    dl = 0             # liczba cyfr w zapisie binarnym n
    pom = n
    while pom > 0:
        pom = pom // 2
        dl = dl + 1
    poz = (w * k - 1) % dl   # pozycja cyfry w zapisie n, liczona od lewej od 0
    for i in range(dl - 1 - poz):
        n = n // 2
    return n % 2


print(prawy_dolny(5, 3, 19))
print(prawy_dolny(4, 5, 179))

# sprawdzenie z bezpośrednim wypełnianiem tablicy
for n in range(1, 300):
    for w in range(1, 8):
        for k in range(1, 8):
            cyfry = bin(n)[2:]
            assert prawy_dolny(w, k, n) == int(cyfry[(w * k - 1) % len(cyfry)])

Odpowiedź: 1.1: 1 0 1 1 0 / 0 1 1 1 0 / 1 1 0 0 1 / 1 1 0 1 1. 1.2: funkcja prawy_dolny — w prawym dolnym rogu stoi cyfra o numerze (w · k − 1) mod (liczba cyfr n) licząc od lewej od 0 (dla w = 5, k = 3, n = 19 wynik 1).

↑
PythonC++23Java 25
Treść zadania

Dana jest funkcja dla nieujemnej liczby całkowitej x:

Kod
F(x):
    jeżeli x = 0: wynikiem jest 0
    w przeciwnym przypadku: wynikiem jest 2 + F(x div 2)
  • 2.1 — Dla x = 16 i x = 35 podaj wartość F(x) oraz łączną liczbę wywołań funkcji F (wliczając pierwsze). Przykład: x = 3 → F = 4, 3 wywołania.
  • 2.2 — Podaj najmniejszą i największą wartość x, dla której F(x) = 18.
Python
wywolania = 0


def F(x):
    global wywolania
    wywolania += 1
    if x == 0:
        return 0
    return 2 + F(x // 2)


# 2.1
for x in [3, 16, 35]:
    wywolania = 0
    print(x, F(x), wywolania)

# 2.2
x_18 = [x for x in range(2000) if F(x) == 18]
print(min(x_18), max(x_18))

Odpowiedź: 2.1: 3 → 4, 3 wywołania; 16 → 10, 6 wywołań; 35 → 12, 7 wywołań. 2.2: najmniejsza 256, największa 511 (F(x) to podwojona liczba cyfr zapisu binarnego x, więc szukamy liczb 9-cyfrowych w systemie binarnym).

↑
PythonC++23Java 25
Treść zadania

Plik slowa.txt zawiera 1000 słów z małych liter alfabetu angielskiego, o długości od 1 do 200. Odpowiedzi zapisz w wyniki3.txt, poprzedzając je numerami zadań (przykład: slowa_przyklad.txt, 10 słów).

  • 3.1 — Podaj, w ilu słowach występuje fragment k?t, gdzie ? to dowolna jedna litera (np. „alamakota”, „brokat”, ale nie „krata”). Przykład: 2.
  • 3.2 — ROT13 zamienia każdą literę na literę o 13 pozycji dalej (cyklicznie, a↔n, b↔o, …). Podaj, ile słów po zakodowaniu ROT13 staje się swoim odwróceniem (np. aren → nera), oraz wypisz najdłuższe z nich. Przykład: 2 i aren.
  • 3.3 — Wypisz wszystkie słowa, w których ta sama litera zajmuje co najmniej połowę pozycji (np. „owocowo” tak, „ambaras” nie). Przykład: terefere, ananas, bo, alabama.
Python
with open("slowa.txt") as file:
    slowa = [wiersz.strip() for wiersz in file]

# 3.1
ile = 0
for slowo in slowa:
    for i in range(len(slowo) - 2):
        if slowo[i] == "k" and slowo[i + 2] == "t":
            ile += 1
            break
print("3.1", ile)


# 3.2
def rot13(slowo):
    wynik = ""
    for litera in slowo:
        wynik += chr((ord(litera) - ord("a") + 13) % 26 + ord("a"))
    return wynik


dobre = [slowo for slowo in slowa if rot13(slowo) == slowo[::-1]]
print("3.2", len(dobre))
print(max(dobre, key=len))

# 3.3
print("3.3")
for slowo in slowa:
    for litera in set(slowo):
        if 2 * slowo.count(litera) >= len(slowo):
            print(slowo)
            break

Odpowiedź: 3.1: 26. 3.2: 5 słów, najdłuższe: rhszzohhubwbojohuubmmfue. 3.3: vzwzwgszezvzzlzzzzzzouz, azaaasfakaaaxbaaaaau, ppppppnoppnoclpop, zggggggpegpnovzgg, nyrpvqycpaylffffffffffffff, kkkkkkkkkkwpijccdbl, tstevttebttktnetitbttti, gvsvjvvvvvqppvuvcvvvi.

↑
PythonC++23Java 25
Treść zadania

W sieci jest n > 1 komputerów; każdy ma ustalonego odbiorcę. W rundzie 0 każdy komputer ma jeden pakiet o swoim numerze. Na początku każdej rundy każdy komputer wysyła swojemu odbiorcy wszystkie pakiety, które miał po poprzedniej rundzie.

Dla n = 6 komputerów o odbiorcach (kolejno dla komputerów 1–6): 3, 1, 6, 5, 4, 5 (po 1. rundzie pakiety 1–6 są w komputerach 3, 1, 6, 5, 4, 5) uzupełnij tabelę: podaj, w których komputerach znajdą się pakiety 1–6 po rundach 2, 3 i 4.

Python
odbiorca = [0, 3, 1, 6, 5, 4, 5]   # odbiorca[i] - odbiorca komputera i (indeks 0 pomijamy)
n = 6
pozycja = list(range(n + 1))       # pozycja[p] - komputer z pakietem p
for runda in range(1, 5):
    pozycja = [odbiorca[pozycja[p]] if p > 0 else 0 for p in range(n + 1)]
    print(runda, *pozycja[1:])

Odpowiedź: po 2. rundzie: 6 3 5 4 5 4; po 3. rundzie: 5 6 4 5 4 5; po 4. rundzie: 4 5 5 4 5 4 (kolejno pakiety 1–6).

↑
PythonC++23Java 25
Treść zadania

Plik odbiorcy.txt zawiera numery odbiorców dla n = 1024 komputerów (wiersz i — odbiorca komputera i); zasady przesyłania pakietów jak w zadaniu 4.1. Odpowiedzi zapisz w wyniki4.txt z numerami zadań (przykład: odbiorcy_przyklad.txt, 16 wierszy).

  • 4.2 — Podaj liczbę komputerów, które nie są odbiorcami żadnych pakietów (przykład: 3).
  • 4.3 — Wyznacz najmniejszy numer rundy, w której jakikolwiek pakiet wraca do komputera, z którego wyruszył, i podaj najmniejszy numer takiego pakietu w tej rundzie (przykład: 3 7).
  • 4.4 — Podaj największą liczbę pakietów znajdujących się w jednym komputerze po rundach 1, 2, 4 i 8 — cztery liczby w jednym wierszu, oddzielone spacjami (przykład: 2 2 3 4).
Python
with open("odbiorcy.txt") as file:
    odbiorca = [0] + [int(wiersz) for wiersz in file]   # numeracja od 1
n = len(odbiorca) - 1

# 4.2
czy_odbiorca = [False] * (n + 1)
for i in range(1, n + 1):
    czy_odbiorca[odbiorca[i]] = True
print("4.2", czy_odbiorca[1:].count(False))

# 4.3
pozycja = list(range(n + 1))   # pozycja[p] - komputer, w którym jest pakiet p
runda = 0
znaleziony = 0
while znaleziony == 0:
    runda += 1
    for p in range(1, n + 1):
        pozycja[p] = odbiorca[pozycja[p]]
    for p in range(1, n + 1):
        if pozycja[p] == p:
            znaleziony = p
            break
print("4.3", runda, znaleziony)

# 4.4
pozycja = list(range(n + 1))
wyniki = []
for runda in range(1, 9):
    for p in range(1, n + 1):
        pozycja[p] = odbiorca[pozycja[p]]
    if runda in [1, 2, 4, 8]:
        ile = [0] * (n + 1)
        for p in range(1, n + 1):
            ile[pozycja[p]] += 1
        wyniki.append(max(ile))
print("4.4", *wyniki)

Odpowiedź: 4.2: 395. 4.3: runda 3, pakiet 436. 4.4: 6 8 15 20.

↑

Edytuj na GitHubie