Matura informatyka

Matura 2020 — czerwiec (termin główny), poziom rozszerzony (stara formuła)

PythonC++23Java 25
Treść zadania

Zadanie 1 (algorytm). Dane: dodatnia parzysta liczba całkowita n i tablica A[0..n-1].

Kod
i ← 0
dopóki i < n-1 wykonuj
    (*) jeżeli A[i] > A[i+1]
            zamień A[i] z A[i+1]
    i ← i + 2
i ← 0
x ← A[i]
y ← A[i+1]
dopóki i < n-3 wykonuj
    (*) jeżeli A[i+2] < x wykonuj x ← A[i+2]
    (*) jeżeli A[i+3] > y wykonuj y ← A[i+3]
    i ← i + 2
  • 1.1 — podaj wartości x i y po wykonaniu algorytmu dla A = [5, 8, 10, 14, 20, 12, 19, 23, 38, 30].
  • 1.2 — rozstrzygnij, czy po wykonaniu algorytmu x (podpunkt a) oraz y (podpunkt b) jest najmniejszą czy największą liczbą w tablicy A.
  • 1.3 — wskaż łączną liczbę porównań w wierszach oznaczonych (*): A. n, B. 2n, C. 3n/2, D. 3n/2 − 2.
Python
def algorytm(A):
    # zwraca x, y oraz liczbę porównań w wierszach (*)
    A = A[:]
    n = len(A)
    porownania = 0
    # w każdej parze (A[i], A[i+1]) mniejszy element trafia na lewo
    i = 0
    while i < n - 1:
        porownania += 1
        if A[i] > A[i + 1]:
            A[i], A[i + 1] = A[i + 1], A[i]
        i = i + 2
    # x - minimum z lewych elementów par, y - maksimum z prawych
    i = 0
    x = A[i]
    y = A[i + 1]
    while i < n - 3:
        porownania += 2
        if A[i + 2] < x:
            x = A[i + 2]
        if A[i + 3] > y:
            y = A[i + 3]
        i = i + 2
    return x, y, porownania


A = [5, 8, 10, 14, 20, 12, 19, 23, 38, 30]
x, y, porownania = algorytm(A)
print(x, y)
print(porownania, 3 * len(A) // 2 - 2)  # n/2 + 2*(n/2 - 1) = 3n/2 - 2

Odpowiedź: 1.1: x = 5, y = 38. 1.2: a) A (najmniejsza liczba), b) B (największa liczba). 1.3: D (3n/2 − 2)

↑
PythonC++23Java 25
Treść zadania

Zadanie 2 (BCD). Kod BCD nieujemnej liczby całkowitej L powstaje przez zamianę każdej cyfry dziesiętnej L na jej czterobitowy kod binarny, np. 3768 → 0011 0111 0110 1000.

  • 2.1 — uzupełnij tabelę: podaj kod BCD i liczbę jedynek dla 259 oraz 15893, a także liczby dziesiętne odpowiadające kodom 0010000000010111 (5 jedynek) i 00100011010101110100 (9 jedynek).
  • 2.2 — napisz algorytm, który dla dodatniej liczby całkowitej L poda w — liczbę jedynek w kodzie BCD liczby L. Wolno używać tylko operacji arytmetycznych (w tym div i mod), odwołań do elementów tablicy, porównań, instrukcji sterujących, przypisań i własnych funkcji.
Python
def kod_bcd(L):
    # każda cyfra dziesiętna -> 4 bity
    kod = ""
    for cyfra in str(L):
        kod += format(int(cyfra), "04b")
    return kod


def z_bcd(kod):
    liczba = ""
    for i in range(0, len(kod), 4):
        liczba += str(int(kod[i:i + 4], 2))
    return int(liczba)


def jedynki_bcd(L):
    # 2.2 - tylko operacje arytmetyczne
    w = 0
    while L > 0:
        cyfra = L % 10
        while cyfra > 0:
            if cyfra % 2 == 1:
                w += 1
            cyfra = cyfra // 2
        L = L // 10
    return w


# 2.1
for L in [259, 15893]:
    print(L, kod_bcd(L), jedynki_bcd(L))
for kod in ["0010000000010111", "00100011010101110100"]:
    print(z_bcd(kod), kod, kod.count("1"))

Odpowiedź: 2.1: 259 — 001001011001, 5 jedynek; 2017 — 0010000000010111; 23574 — 00100011010101110100; 15893 — 00010101100010010011, 8 jedynek. 2.2: algorytm jedynki_bcd powyżej

↑
PythonC++23Java 25
Treść zadania

Zadanie 4 (własności liczb). Plik dane.txt zawiera 5000 różnych liczb całkowitych z zakresu [100, 100 000], po jednej w wierszu (dane przykładowe: dane_przyklad.txt, 500 liczb).

Podaj, ile liczb z pliku jest pierwszych, oraz największą i najmniejszą z nich. Wynik zapisz w pliku wyniki4_1.txt.

Dla danych przykładowych: 47 liczb pierwszych, największa 97501, najmniejsza 1669.

Python
def czy_pierwsza(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True


pierwsze = []
with open("dane.txt") as file:
    for line in file:
        liczba = int(line)
        if czy_pierwsza(liczba):
            pierwsze.append(liczba)

with open("wyniki4_1.txt", "w") as wynik:
    print("Liczba liczb pierwszych:", len(pierwsze), file=wynik)
    print("Największa liczba:", max(pierwsze), file=wynik)
    print("Najmniejsza liczba:", min(pierwsze), file=wynik)

Odpowiedź: liczb pierwszych: 501; największa: 99767; najmniejsza: 311

↑
PythonC++23Java 25
Treść zadania

Dane z pliku dane.txt (5000 różnych liczb z zakresu [100, 100 000]).

Liczba jest palindromiczna, jeśli jej zapis binarny (zaczynający się od 1) jest palindromem, np. 107 = 1101011₂. Liczba jest prawie palindromiczna, jeśli jej zapis binarny poprzedzony jednym lub kilkoma zerami jest palindromem, np. 238 = 11101110₂ (011101110 jest palindromem) albo 476 = 111011100₂ (00111011100).

Podaj łączną liczbę liczb palindromicznych i prawie palindromicznych w pliku. Wynik zapisz w pliku wyniki4_2.txt (dla danych przykładowych: 10).

Python
licznik = 0
with open("dane.txt") as file:
    for line in file:
        zapis = bin(int(line))[2:]
        # dopisanie zer z przodu = usunięcie zer z końca zapisu
        zapis = zapis.rstrip("0")
        if zapis == zapis[::-1]:
            licznik += 1

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

Odpowiedź: 107

↑
PythonC++23Java 25
Treść zadania

Dane z pliku dane.txt (5000 różnych liczb z zakresu [100, 100 000]).

Podaj, ile różnych par liczb z pliku ma w zapisie dziesiętnym ten sam zbiór cyfr (liczby mogą mieć różną długość), np. 178 i 817, 1037 i 30071, 10122 i 120. Pary (a, b) i (b, a) liczymy jako jedną. Wynik zapisz w pliku wyniki4_3.txt (dla danych przykładowych: 240).

Python
ile = {}  # zbiór cyfr liczby (jako napis) -> ile liczb ma dokładnie te cyfry
with open("dane.txt") as file:
    for line in file:
        cyfry = "".join(sorted(set(line.strip())))
        ile[cyfry] = ile.get(cyfry, 0) + 1

# z k liczb o tym samym zbiorze cyfr można utworzyć k*(k-1)/2 par
pary = 0
for k in ile.values():
    pary += k * (k - 1) // 2

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

Odpowiedź: 23515

↑

Edytuj na GitHubie