Matura informatyka

Matura 2010 — maj, poziom rozszerzony

Arkusz I

1a

PythonC++23Java 25
Treść zadania

Szyfr przestawieniowy: tekst wpisujemy wierszami do kwadratowej tablicy n × n, a szyfrogram odczytujemy kolumnami od lewej do prawej. Wymiar n to najmniejsza liczba, przy której cały tekst mieści się w tablicy; wolne pola uzupełnia się znakami odstępu (oznaczanymi _).

Przykład: ALGORYTM_PRZESTAWIENIOWY (24 znaki) → tablica 5 × 5 → AYRAILTZWOGMEIWO_SEYRPTN_.

Podaj wzór (lub algorytm) wyznaczający liczbę wierszy i kolumn tablicy dla tekstu o długości d znaków.

Python
from math import ceil, sqrt


def wymiar(d):
    # najmniejsze n, dla którego n * n >= d, czyli n = sufit(pierwiastek(d))
    n = ceil(sqrt(d))
    while n * n < d:  # zabezpieczenie przed błędem zaokrąglenia
        n += 1
    return n


print(wymiar(24), wymiar(25), wymiar(26))

Odpowiedź: n = ⌈√d⌉ – najmniejsza liczba naturalna większa lub równa √d

↑

Arkusz I

1b i 1c

PythonC++23Java 25
Treść zadania

Szyfr przestawieniowy z zadania 1a (tekst wpisywany wierszami do tablicy n × n, odczytywany kolumnami).

  • 1b — Rozszyfruj cytat z Sokratesa zaszyfrowany tą metodą — szyfrogram (64 znaki, czyli tablica 8 × 8) jest podany w arkuszu.
  • 1c — Zapisz algorytm szyfrujący tą metodą. Dane: d — długość tekstu, tekst[1..d] — znaki tekstu. Wynik: s — długość szyfrogramu, szyfr[1..s] — znaki szyfrogramu.
Python
from math import ceil, sqrt


def szyfruj(tekst):
    d = len(tekst)
    n = ceil(sqrt(d))
    while n * n < d:
        n += 1
    s = n * n
    tekst = tekst + "_" * (s - d)  # puste pola uzupełniamy znakami odstępu
    szyfr = ""
    for kolumna in range(n):  # odczyt kolumnami
        for wiersz in range(n):
            szyfr += tekst[wiersz * n + kolumna]
    return szyfr


# c) przykład z treści
print(szyfruj("ALGORYTM_PRZESTAWIENIOWY"))

# b) szyfr ma 64 znaki (kwadrat 8 x 8), a zamiana wierszy z kolumnami
#    wykonana drugi raz przywraca tekst - wystarczy "zaszyfrować" szyfr
szyfr = "BTLLTU_ĘL_EOYPM_ĄPJZLCYNDREOKYLI_ZMFO_ĄGJY_Ó_N_DEWFWGISYSII_ŁEI_"
print(szyfruj(szyfr))

Odpowiedź: b) BŁĄD JEST PRZYWILEJEM FILOZOFÓW, TYLKO GŁUPCY NIE MYLĄ SIĘ NIGDY; c) przykład: AYRAILTZWOGMEIWO_SEYRPTN_

↑

Arkusz I

2a i 2b

PythonC++23Java 25
Treść zadania

W tablicy a[1..1023] zapisano ciąg zer i jedynek tak, że wszystkie zera poprzedzają jedynki (mogą wystąpić same zera albo same jedynki). Dany jest niepełny algorytm liczenia zer:

Kod
liczba_zer ← 0
l ← 1, p ← 1023
dopóki l ≤ p wykonuj
    s ← (l + p) div 2
    jeżeli a[s] = 1 to p ← s − 1
    w przeciwnym przypadku
        liczba_zer ← liczba_zer + .....
        l ← .....
  • 2a — Uzupełnij brakujące wyrażenia tak, aby algorytm zawsze poprawnie liczył zera.
  • 2b — Ile razy wykonywane jest przypisanie s ← (l + p) div 2 w każdym przebiegu algorytmu? Uzasadnij.
Python
def liczba_zer(a):
    # a[1..1023], a[0] nieużywane - indeksy jak w zadaniu
    przypisania_s = 0
    zera = 0
    l, p = 1, len(a) - 1
    while l <= p:
        s = (l + p) // 2
        przypisania_s += 1
        if a[s] == 1:
            p = s - 1
        else:
            zera = zera + (s - l + 1)  # zera na pozycjach l..s
            l = s + 1
    return zera, przypisania_s


# sprawdzenie dla wszystkich możliwych tablic (k zer, potem jedynki)
liczby_przypisan = set()
for k in range(1024):
    a = [None] + [0] * k + [1] * (1023 - k)
    zera, przypisania_s = liczba_zer(a)
    if zera != k:
        print("błąd dla", k)
    liczby_przypisan.add(przypisania_s)
print(liczby_przypisan)

Odpowiedź: a) liczba_zer + (s − l + 1), l ← s + 1; b) zawsze 10 = log₂1024 – w każdym przebiegu pętli przedział do sprawdzenia zmniejsza się o połowę

↑

Arkusz II

4a

PythonC++23Java 25
Treść zadania

W pliku anagram.txt jest 200 wierszy, w każdym 5 słów (ciągów liter alfabetu łacińskiego, długości od 1 do 20) oddzielonych spacjami. Anagram to słowo powstałe z innego przez przestawienie liter (np. barok – korba – robak).

Wypisz te wiersze, w których wszystkie słowa mają tę samą liczbę znaków. Zapisz je w pliku odp_4a.txt.

Python
with open("anagram.txt") as file, open("odp_4a.txt", "w") as wynik:
    for line in file:
        slowa = line.split()
        if all(len(slowo) == len(slowa[0]) for slowo in slowa):
            wynik.write(" ".join(slowa) + "\n")
            print(" ".join(slowa))

Odpowiedź: wrona rossa slowo gwert rezas, grant hello zakon lloeh hello, kabaret kabanos kabaret gertyfu kabaret, … , burza orkan lukde pudeh lerfy (25 wierszy z klucza; program wypisuje też pierwszy wiersz pliku – przykład z treści „abcd cdba dbac cbad dcba”, którego klucz nie wymienia)

↑

Arkusz II

4b

PythonC++23Java 25
Treść zadania

Dane jak w 4a (plik anagram.txt, 200 wierszy po 5 słów).

Wypisz wszystkie wiersze, w których każde słowo jest anagramem pierwszego słowa w danym wierszu. Zapisz je w pliku odp_4b.txt.

Python
def czy_anagram(a, b):
    return sorted(a) == sorted(b)


with open("anagram.txt") as file, open("odp_4b.txt", "w") as wynik:
    for line in file:
        slowa = line.split()
        if all(czy_anagram(slowa[0], slowo) for slowo in slowa[1:]):
            wynik.write(" ".join(slowa) + "\n")
            print(" ".join(slowa))

Odpowiedź: foto foto tofo tofo foto, glob lobg bogl glbo gblo, triada dariat aadrit iatdar adatri, kotek tekok teokk kokte otekk, rower werro werro owerr erwor, foto tofo foot ftoo ootf, spiker kerspi erspik erspki kiersp (oraz pierwszy wiersz pliku „abcd cdba dbac cbad dcba”, pominięty w kluczu)

↑

Arkusz II

5a

PythonC++23Java 25

Zadanie na arkusz kalkulacyjny — rozwiązanie w Pythonie.

Treść zadania

Plik pesel.txt zawiera 150 numerów PESEL pracowników biura (wszyscy urodzeni przed 2000 r.). Cyfry 1–6 to data urodzenia (RRMMDD), 7–9 — liczba porządkowa, 10. — płeć (parzysta: kobieta, nieparzysta: mężczyzna), 11. — cyfra kontrolna. Cyfrę kontrolną liczy się tak: dziesięć pierwszych cyfr mnoży się przez wagi 1, 3, 7, 9, 1, 3, 7, 9, 1, 3, sumuje iloczyny, bierze resztę z dzielenia sumy przez 10; jeśli reszta to 0, cyfra kontrolna wynosi 0, w przeciwnym razie 10 − reszta. Dane osobowe są poprawne nawet przy błędnej cyfrze kontrolnej. Odpowiedzi zapisz w pliku odp_5.txt, poprzedzając je literą podpunktu.

Podaj, ile osób urodziło się w grudniu.

Python
grudzien = 0

with open("pesel.txt") as file:
    for line in file:
        pesel = line.strip()
        if pesel[2:4] == "12":
            grudzien += 1

print(grudzien)

Odpowiedź: 20

↑

Arkusz II

5b

PythonC++23Java 25

Zadanie na arkusz kalkulacyjny — rozwiązanie w Pythonie.

Treść zadania

Dane z pliku pesel.txt (10. cyfra PESEL parzysta oznacza kobietę).

Podaj, ile kobiet pracuje w biurze.

Python
kobiety = 0

with open("pesel.txt") as file:
    for line in file:
        pesel = line.strip()
        if int(pesel[9]) % 2 == 0:
            kobiety += 1

print(kobiety)

Odpowiedź: 74

↑

Arkusz II

5c

PythonC++23Java 25

Zadanie na arkusz kalkulacyjny — rozwiązanie w Pythonie.

Treść zadania

Dane z pliku pesel.txt.

Podaj rok, w którym urodziło się najwięcej pracowników biura.

Python
lata = {}

with open("pesel.txt") as file:
    for line in file:
        rok = "19" + line.strip()[:2]
        lata[rok] = lata.get(rok, 0) + 1

print(max(lata, key=lata.get))

Odpowiedź: 1989

↑

Arkusz II

5d

PythonC++23Java 25

Zadanie na arkusz kalkulacyjny — rozwiązanie w Pythonie.

Treść zadania

Dane z pliku pesel.txt (algorytm cyfry kontrolnej opisany w 5a).

Wypisz numery PESEL z niepoprawną cyfrą kontrolną, posortowane rosnąco.

Python
wagi = [1, 3, 7, 9, 1, 3, 7, 9, 1, 3]
bledne = []

with open("pesel.txt") as file:
    for line in file:
        pesel = line.strip()
        suma = 0
        for i in range(10):
            suma += int(pesel[i]) * wagi[i]
        kontrolna = (10 - suma % 10) % 10
        if kontrolna != int(pesel[10]):
            bledne.append(pesel)

for pesel in sorted(bledne):
    print(pesel)

Odpowiedź: 54043010088, 60061144469, 77072919805, 77120835871, 83041812338, 89081421445, 91032272651, 92022716243

↑

Arkusz II

5e

PythonC++23Java 25

Zadanie na arkusz kalkulacyjny — rozwiązanie w Pythonie.

Treść zadania

Dane z pliku pesel.txt.

Zestaw liczby osób urodzonych w kolejnych dziesięcioleciach: latach 50., 60., 70., 80. i 90. (np. lata 50. to roczniki 1950–1959 włącznie). Wykonaj wykres przedstawiający procentowy rozkład liczby osób w tych przedziałach.

Python
dekady = {"50": 0, "60": 0, "70": 0, "80": 0, "90": 0}

with open("pesel.txt") as file:
    for line in file:
        dekady[line[0] + "0"] += 1

wszyscy = sum(dekady.values())
for dekada in dekady:
    procent = dekady[dekada] / wszyscy * 100
    print(f"{dekada}-te {dekady[dekada]} {procent:.1f}%")

Odpowiedź: 50-te 22, 60-te 28, 70-te 36, 80-te 58, 90-te 6 (wykres kołowy z procentami: ok. 15%, 19%, 24%, 39%, 4%)

↑

Edytuj na GitHubie