Matura informatyka

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

PythonC++23Java 25
Treść zadania

Niech n będzie nieujemną liczbą całkowitą, której najbardziej znacząca cyfra jest większa od 0 i mniejsza od 9. Cyfrowe dopełnienie d liczby n powstaje przez zastąpienie każdej cyfry n jej uzupełnieniem do 9 (np. dla 2021 jest to 7978).

  • 1.1 — Podaj czterocyfrową liczbę n, dla której |n − d| jest a) najmniejsza, b) największa.
  • 1.2 — Napisz algorytm, który dla dodatniej liczby n (spełniającej warunek jak wyżej) oblicza jej cyfrowe dopełnienie d. Algorytm może używać wyłącznie zmiennych całkowitych i podstawowych operacji arytmetycznych (w tym div i mod); nie wolno korzystać z funkcji wbudowanych ani konwersji liczba ↔ napis.
Python
def dopelnienie(n):
    # 1.2 - tylko operacje na liczbach całkowitych
    d = 0
    potega = 1
    while n > 0:
        cyfra = n % 10
        n = n // 10
        d = d + (9 - cyfra) * potega
        potega = potega * 10
    return d


print(dopelnienie(2021))

# 1.1 - sprawdzamy wszystkie czterocyfrowe n z pierwszą cyfrą od 1 do 8
najmniejsza = najwieksza = 1000
for n in range(1000, 9000):
    roznica = abs(n - dopelnienie(n))
    if roznica < abs(najmniejsza - dopelnienie(najmniejsza)):
        najmniejsza = n
    if roznica > abs(najwieksza - dopelnienie(najwieksza)):
        najwieksza = n
print(najmniejsza, najwieksza)

Odpowiedź: 1.1: a) 4999 (lub 5000) — różnica 1; b) 1000 (lub 8999) — różnica 7999. 1.2: algorytm powyżej (dopelnienie(2021) = 7978)

↑
PythonC++23Java 25
Treść zadania

T[1..n] to tablica n liczb całkowitych (dla n = 0 pusta). Funkcja d(x) dopisuje x na końcu tablicy i przesuwa go w górę (div — dzielenie całkowite; „oraz” liczone leniwie):

Kod
d(x):
    n ← n + 1
    T[n] ← x
    s ← n
    dopóki ((s div 2) ≥ 1) oraz (T[s] > T[s div 2]) wykonuj
        zamień T[s] z T[s div 2]
        s ← s div 2
  • 2.1 — Podaj zawartość T po wykonaniu d(x) dla: T=[36,15,17,3], x=−5 oraz T=[27,6,13,4,−3,−2,−3], x=30. (Przykład: [26,3,5,−4], x=5 → [26,5,5,−4,3].)
  • 2.2 — Podaj zawartość T po kolejnych wywołaniach d z argumentami 6, −4, 12, 27, 26, 8, zaczynając od pustej tablicy.
  • 2.3 — Do pustej tablicy wstawiono kolejno liczby 1, 2, …, k−1, a potem wywołano d(k). Podaj, ile razy sprawdzany jest warunek pętli „dopóki” podczas d(k) dla wartości k podanych w tabeli arkusza (np. dla k = 4 — 3 razy).
Python
def d(T, x):
    # T[0] nieużywane - tablica indeksowana od 1, jak w treści
    # zwraca liczbę sprawdzeń warunku pętli dopóki
    T.append(x)
    s = len(T) - 1
    sprawdzenia = 0
    while True:
        sprawdzenia += 1
        if not (s // 2 >= 1 and T[s] > T[s // 2]):
            break
        T[s], T[s // 2] = T[s // 2], T[s]
        s = s // 2
    return sprawdzenia


# 2.1
for T, x in [([26, 3, 5, -4], 5), ([36, 15, 17, 3], -5), ([27, 6, 13, 4, -3, -2, -3], 30)]:
    T = [None] + T
    d(T, x)
    print(T[1:])

# 2.2
T = [None]
for x in [6, -4, 12, 27, 26, 8]:
    d(T, x)
print(T[1:])

# 2.3
for k in [4, 16, 1025]:
    T = [None]
    for x in range(1, k):
        d(T, x)
    print(k, d(T, k))

Odpowiedź: 2.1: 36, 15, 17, 3, −5 oraz 30, 27, 13, 6, −3, −2, −3, 4. 2.2: 27, 26, 8, −4, 12, 6. 2.3: k = 16 — 5 razy, k = 1025 — 11 razy

↑
PythonC++23Java 25
Treść zadania

Plik instrukcje.txt zawiera 2000 instrukcji automatu tworzącego napis z wielkich liter (początkowo pusty). Każda instrukcja to polecenie, spacja i jeden znak:

  • DOPISZ litera — dopisz literę na końcu napisu;
  • ZMIEN litera — zamień ostatnią literę napisu na podaną;
  • USUN 1 — usuń ostatnią literę;
  • PRZESUN litera — pierwsze od lewej wystąpienie litery zamień na następną w alfabecie (Z → A); gdy litery brak, nic nie rób.

Odpowiedzi zapisz w wyniki4.txt, poprzedzając je numerem zadania. Plik przyklad.txt (20 instrukcji) służy do testów.

  • 4.1 — Podaj długość napisu po wykonaniu wszystkich instrukcji. (Przykład: 10.)
  • 4.2 — Znajdź najdłuższy ciąg kolejnych instrukcji tego samego rodzaju; podaj rodzaj i długość (jest jeden taki ciąg). (Przykład: DOPISZ 5.)
  • 4.3 — Podaj literę najczęściej dopisywaną instrukcją DOPISZ i liczbę jej dopisań (jest jedna taka). (Przykład: U 3.)
  • 4.4 — Podaj napis powstały po wykonaniu wszystkich instrukcji. (Przykład: ALANTURING.)
Python
instrukcje = []
with open("instrukcje.txt") as file:
    for line in file:
        polecenie, znak = line.split()
        instrukcje.append((polecenie, znak))

# 4.1 i 4.4 - wykonujemy wszystkie instrukcje
napis = []
for polecenie, znak in instrukcje:
    if polecenie == "DOPISZ":
        napis.append(znak)
    elif polecenie == "ZMIEN":
        napis[-1] = znak
    elif polecenie == "USUN":
        napis.pop()
    elif polecenie == "PRZESUN":
        if znak in napis:
            i = napis.index(znak)  # pierwsze wystąpienie od lewej
            napis[i] = chr((ord(znak) - ord("A") + 1) % 26 + ord("A"))

# 4.2 - najdłuższy ciąg kolejnych instrukcji tego samego rodzaju
najdluzszy = 0
rodzaj = ""
dlugosc = 0
for i in range(len(instrukcje)):
    if i > 0 and instrukcje[i][0] == instrukcje[i - 1][0]:
        dlugosc += 1
    else:
        dlugosc = 1
    if dlugosc > najdluzszy:
        najdluzszy = dlugosc
        rodzaj = instrukcje[i][0]

# 4.3 - najczęściej dopisywana litera
ile = {}
for polecenie, znak in instrukcje:
    if polecenie == "DOPISZ":
        ile[znak] = ile.get(znak, 0) + 1
litera = max(ile, key=ile.get)

with open("wyniki4.txt", "w") as wynik:
    print("4.1.", len(napis), file=wynik)
    print("4.2.", rodzaj, najdluzszy, file=wynik)
    print("4.3.", litera, ile[litera], file=wynik)
    print("4.4.", "".join(napis), file=wynik)

Odpowiedź: 4.1: 517; 4.2: ZMIEN 7; 4.3: Z 37; 4.4: POZNIEJMOWIONOZECZLOWIEKTENNADSZEDLODPOLNOCYODBRAMYPOWROZNIC… (początek opowiadania „Wiedźmin” A. Sapkowskiego)

↑

Edytuj na GitHubie