Matura informatyka

Matura 2008 — maj, poziom rozszerzony

Przykładowe wyniki CKE do części II znajdują się w folderze wyniki w paczce z danymi.

Część I

1a

PythonC++23Java 25
Treść zadania

Zadanie 1 (potęgi). Ciąg a = (a₀, a₁, a₂, ...) zdefiniowano wzorem: aₖ = reszta z dzielenia 2ᵏ przez 10 (k = 0, 1, 2, ...).

Korzystając z definicji, podaj 16 pierwszych wyrazów ciągu (a₀, ..., a₁₅).

Python
for k in range(16):
    print(k, 2 ** k % 10)

Odpowiedź: 1 2 4 8 6 2 4 8 6 2 4 8 6 2 4 8

↑

Część I

1b

PythonC++23Java 25
Treść zadania

Podaj algorytm, który dla danej liczby całkowitej k ≥ 0 wyznacza resztę z dzielenia 2ᵏ przez 10 (np. dla k = 15 wynikiem jest 8). Oceniana jest poprawność i złożoność czasowa (liczba operacji arytmetycznych; operacje na liczbach całkowitych wykonują się w czasie stałym).

Python
def ostatnia_cyfra(k):
    # Dane: k >= 0, Wynik: reszta z dzielenia 2^k przez 10 (stała liczba operacji)
    if k == 0:
        return 1
    reszta = k % 4
    if reszta == 0:
        return 6
    if reszta == 1:
        return 2
    if reszta == 2:
        return 4
    return 8


print(ostatnia_cyfra(15))
print(all(ostatnia_cyfra(k) == 2 ** k % 10 for k in range(1000)))

Odpowiedź: k = 0 → 1; w przeciwnym razie zależnie od k mod 4: 0 → 6, 1 → 2, 2 → 4, 3 → 8 (dla k = 15 wynik 8)

↑

Część I

1c

PythonC++23Java 25
Treść zadania

Podaj algorytm obliczania aⁿ, gdzie a jest liczbą całkowitą, a n jest potęgą dwójki (n = 2ᵏ, k ≥ 0). Oceniana jest złożoność czasowa w zależności od n. Wskazówka: aⁿ = a^(n/2) · a^(n/2) dla n > 1.

Python
def potega(a, n):
    # Dane: a - liczba całkowita, n = 2^k, Wynik: a^n (log2(n) mnożeń)
    p = a
    while n > 1:
        p = p * p
        n = n // 2
    return p


print(potega(3, 8), 3 ** 8)
print(potega(2, 1024) == 2 ** 1024)

Odpowiedź: p := a; dopóki n > 1: p := p·p, n := n div 2; wynikiem jest p

↑

Część I

2a

PythonC++23Java 25
Treść zadania

Zadanie 2 (słowa). Napis to niepusty ciąg liter z alfabetu {a, b}. Napis 2-regularny: każdy napis jednoliterowy jest 2-regularny, a jeśli w jest 2-regularny, to ww też; innych nie ma. Procedura 2REG(w):

Kod
1. jeśli |w| = 1 → TAK
2. jeśli |w| > 1 i |w| nieparzyste → NIE
3. jeśli |w| > 1 i |w| parzyste:
   3.1 podziel w na połowy w1, w2 (w = w1w2)
   3.2 jeśli w1 ≠ w2 → NIE
   3.3 wynik = 2REG(w1)

Wypisz parametry wszystkich wywołań rekurencyjnych 2REG i wynik dla napisów: aabbaabb, aaaaaaaa, bbbbbbbbbbbbbbbbbbbb (np. dla abab: abab → NIE).

Python
def reg2(w):
    print(w)
    if len(w) == 1:
        return "TAK"
    if len(w) % 2 == 1:
        return "NIE"
    polowa = len(w) // 2
    w1 = w[:polowa]
    w2 = w[polowa:]
    if w1 != w2:
        return "NIE"
    return reg2(w1)


for napis in ["aabbaabb", "aaaaaaaa", "bbbbbbbbbbbbbbbbbbbb"]:
    print(reg2(napis))
    print()

Odpowiedź: i. aabbaabb → aabb → NIE; ii. aaaaaaaa → aaaa → aa → a → TAK; iii. bbbbbbbbbbbbbbbbbbbb → bbbbbbbbbb → bbbbb → NIE

↑

Część I

2d

PythonC++23Java 25
Treść zadania

Napisy 3-regularne: każdy napis jednoliterowy jest 3-regularny; jeśli w jest 3-regularny, to napisy wxw oraz wwx (x — dowolny napis nad {a, b} o tej samej długości co w) też są 3-regularne; innych nie ma. Np. a, aba, abaabaaaa są 3-regularne, a aaaabaaba nie jest.

Napisz algorytm, który dla danego napisu w (|w| ≥ 1) odpowiada TAK, jeśli w jest 3-regularny, i NIE w przeciwnym razie.

Python
def reg3(w):
    # Dane: napis w nad alfabetem {a, b}, Wynik: TAK, jeśli w jest 3-regularny
    n = len(w)
    if n == 1:
        return "TAK"
    if n % 3 != 0:
        return "NIE"
    d = n // 3
    w1 = w[:d]
    w2 = w[d:2 * d]
    w3 = w[2 * d:]
    if w1 == w2 or w1 == w3:
        return reg3(w1)
    return "NIE"


for napis in ["a", "aba", "abaabaaaa", "aaaabaaba"]:
    print(napis, reg3(napis))

Odpowiedź: dzielimy w na trzy równe części w1 w2 w3; jeśli w1 = w2 lub w1 = w3, to wynikiem jest 3REG(w1), w przeciwnym razie NIE (a, aba, abaabaaaa — TAK; aaaabaaba — NIE)

↑

Część II

4a

PythonC++23Java 25
Treść zadania

Zadanie 4 (wybory). Mandaty przydziela się uproszczoną metodą d'Hondta: dopóki są wolne mandaty, dla każdego komitetu liczymy X = v/(s+1) (v — liczba głosów komitetu, s — liczba mandatów już mu przydzielonych) i kolejny mandat dostaje komitet o największym X. Np. dla głosów A = 950, B = 350, C = 500 i 5 mandatów kolejno mandaty dostają A, C, A, B, A.

Plik dane.txt zawiera dane z 20 okręgów (wiersz = okręg, po kolei od nr 1): 6 liczb głosów na komitety A–F oraz liczba mandatów w okręgu (razem 350). Odpowiedzi zapisz w wybory.txt, poprzedzając je numerem podpunktu:

  1. ile głosów łącznie otrzymał każdy komitet;
  2. numery okręgów, w których łącznie oddano najwięcej i najmniej głosów;
  3. liczby mandatów komitetów A–F w okręgu 6;
  4. liczby mandatów komitetów A–F w całym parlamencie.
Python
okregi = []
with open("dane.txt") as file:
    for linia in file:
        if linia.strip():
            okregi.append([int(x) for x in linia.split()])

komitety = "ABCDEF"


def podziel_mandaty(glosy, mandaty):
    # uproszczona metoda d'Hondta: X = v / (s + 1)
    s = [0] * len(glosy)
    for _ in range(mandaty):
        najlepszy = 0
        for i in range(len(glosy)):
            if glosy[i] / (s[i] + 1) > glosy[najlepszy] / (s[najlepszy] + 1):
                najlepszy = i
        s[najlepszy] += 1
    return s


print("1")
for i in range(6):
    print(komitety[i], sum(okreg[i] for okreg in okregi))

print("2")
sumy = [sum(okreg[:6]) for okreg in okregi]
print("najwięcej: okręg nr", sumy.index(max(sumy)) + 1)
print("najmniej: okręg nr", sumy.index(min(sumy)) + 1)

print("3")
mandaty6 = podziel_mandaty(okregi[5][:6], okregi[5][6])
for i in range(6):
    print(komitety[i], mandaty6[i])

print("4")
razem = [0] * 6
for okreg in okregi:
    mandaty = podziel_mandaty(okreg[:6], okreg[6])
    for i in range(6):
        razem[i] += mandaty[i]
for i in range(6):
    print(komitety[i], razem[i])

Odpowiedź: 1. A 6331, B 3801, C 3866, D 4941, E 4351, F 2281; 2. najwięcej okręg nr 2, najmniej okręg nr 4; 3. A 9, B 1, C 4, D 4, E 4, F 2; 4. A 93, B 50, C 50, D 69, E 62, F 26

↑

Część II

4b

PythonC++23Java 25

Zadanie na arkusz kalkulacyjny — rozwiązanie w Pythonie.

Treść zadania

Dla danych z pliku dane.txt (zadanie 4) wykonaj wykres przedstawiający procentowy rozkład głosów oddanych w całej Infolandii na poszczególne komitety A–F. Zadbaj o czytelny opis wykresu.

Python
glosy = [0] * 6
with open("dane.txt") as file:
    for linia in file:
        if linia.strip():
            liczby = [int(x) for x in linia.split()]
            for i in range(6):
                glosy[i] += liczby[i]

# dane do wykresu kołowego/kolumnowego: procentowy rozkład głosów
for i in range(6):
    print("ABCDEF"[i], round(100 * glosy[i] / sum(glosy), 2), "%")

Odpowiedź: wykres procentowego rozkładu głosów: A 24,76%, B 14,86%, C 15,12%, D 19,32%, E 17,02%, F 8,92%

↑

Część II

5a

PythonC++23Java 25
Treść zadania

Zadanie 5 (hasła jednorazowe). Plik slowa.txt zawiera 1000 słów (każde w osobnym wierszu, wielkie litery alfabetu angielskiego, długość do 30 znaków).

Hasłem jest słowo zapisane od końca (np. EGZAMIN → NIMAZGE). Utwórz listę haseł i zapisz ją w pliku hasla_a.txt (każde w osobnym wierszu). W pliku slowa_a.txt podaj najdłuższe i najkrótsze hasło oraz ich długości (każde z nich jest jedyne).

Python
hasla = []
with open("slowa.txt") as file:
    for linia in file:
        hasla.append(linia.strip()[::-1])

with open("hasla_a.txt", "w") as wyjscie:
    for haslo in hasla:
        wyjscie.write(haslo + "\n")

najkrotsze = min(hasla, key=len)
najdluzsze = max(hasla, key=len)
print(najkrotsze, len(najkrotsze))
print(najdluzsze, len(najdluzsze))

Odpowiedź: najkrótsze EHJA (4), najdłuższe DCBAJAHHJIGABCDCCDCBAGIJHHAJ (28)

↑

Część II

5b

PythonC++23Java 25
Treść zadania

Nowy algorytm tworzenia hasła ze słowa w (plik slowa.txt): wyznacz najdłuższy palindrom w1 będący początkiem w, zapisz w = w1w2, a hasło utwórz, sklejając odwrócone w2 i całe w (np. KAJAKARSTWO → OWTSRAKAJAKARSTWO, MAMA → AMAMA, EGZAMIN → NIMAZGEGZAMIN; jeśli w jest palindromem, hasło = w).

Hasła zapisz w pliku hasla_b.txt (każde w osobnym wierszu), a w pliku slowa_b.txt (poprzedzając numerem podpunktu) podaj:

  1. wszystkie hasła o długości 12;
  2. najdłuższe i najkrótsze hasło;
  3. sumę długości wszystkich haseł.
Python
def utworz_haslo(w):
    # najdłuższy palindrom będący początkiem słowa w
    dlugosc = len(w)
    while w[:dlugosc] != w[:dlugosc][::-1]:
        dlugosc -= 1
    w2 = w[dlugosc:]
    return w2[::-1] + w


hasla = []
with open("slowa.txt") as file:
    for linia in file:
        hasla.append(utworz_haslo(linia.strip()))

with open("hasla_b.txt", "w") as wyjscie:
    for haslo in hasla:
        wyjscie.write(haslo + "\n")

print("1")
for haslo in hasla:
    if len(haslo) == 12:
        print(haslo)

print("2")
print(min(hasla, key=len))
print(max(hasla, key=len))

print("3")
print(sum(len(haslo) for haslo in hasla))

Odpowiedź: 1. BDJBFBBFBJDB, DFDAHEEHADFD, IHBIBCCBIBHI, FABBEAAEBBAF; 2. najkrótsze OKOOKO, najdłuższe AJBEIKKFIIGIIJBAHADIBCIDHDICBIDAHABJIIGIIFKKIEBJA; 3. 27731

↑

Edytuj na GitHubie