Matura informatyka

Matura 2009 — maj, poziom rozszerzony

Arkusz I

2a i 2b

PythonC++23Java 25
Treść zadania

Zadanie 2 (punkty kratowe). Punkt kratowy ma obie współrzędne całkowite. K(R) to koło o środku (0, 0) i promieniu R (z brzegiem), a N(R) — liczba punktów kratowych w K(R). Np. N(0) = 1, N(1) = 5, N(1,5) = 9.

  • 2a — podaj N(R) dla R = 2,01 oraz R = 4,50;
  • 2b — zaproponuj algorytm, który dla danej nieujemnej liczby całkowitej R oblicza N(R).
Python
from math import floor


def punkty_kratowe(R):
    # liczba punktów (x, y) o współrzędnych całkowitych, dla których x^2 + y^2 <= R^2
    r = floor(R)
    N = 0
    for x in range(-r, r + 1):
        for y in range(-r, r + 1):
            if x * x + y * y <= R * R:
                N += 1
    return N


print(punkty_kratowe(0), punkty_kratowe(1), punkty_kratowe(1.5))  # przykłady z treści: 1 5 9
print(punkty_kratowe(2.01))
print(punkty_kratowe(4.50))

Odpowiedź: N(2,01) = 13, N(4,50) = 69

↑

Arkusz I

3a

PythonC++23Java 25
Treść zadania

Zadanie 3 (NWD). Algorytm Euklidesa rekurencyjnie: nwd(a, b) = a dla b = 0 oraz nwd(a, b) = nwd(b, a mod b) dla b ≥ 1. Np. nwd(16, 12) = nwd(12, 4) = nwd(4, 0) = 4 — funkcja jest wywoływana 3 razy.

Podaj liczbę wywołań funkcji dla a = 56, b = 72 oraz dla a = 72, b = 56.

Python
wywolania = 0


def nwd(a, b):
    global wywolania
    wywolania += 1
    if b == 0:
        return a
    return nwd(b, a % b)


for a, b in [(56, 72), (72, 56)]:
    wywolania = 0
    nwd(a, b)
    print(a, b, wywolania)

Odpowiedź: dla a = 56, b = 72 – 5 wywołań; dla a = 72, b = 56 – 4 wywołania

↑

Arkusz I

3b

PythonC++23Java 25
Treść zadania

Podaj nierekurencyjny algorytm obliczania nwd(a, b) (a, b — liczby naturalne, z których co najmniej jedna jest większa od 0) wraz ze specyfikacją.

Python
# Dane: liczby naturalne a i b, z których co najmniej jedna jest większa od 0
# Wynik: największy wspólny dzielnik liczb a i b
def nwd(a, b):
    while b > 0:
        reszta = a % b
        a = b
        b = reszta
    return a


print(nwd(16, 12), nwd(56, 72))

Odpowiedź: dopóki b > 0: reszta := a mod b, a := b, b := reszta; wynikiem jest a (np. nwd(16, 12) = 4)

↑

Arkusz II

4

PythonC++23Java 25

Zadanie na arkusz kalkulacyjny — rozwiązanie w Pythonie. Podpunkty korzystają z tych samych wylosowanych punktów, dlatego są w jednym programie. Wykres (b) zapisywany jest jako smok.svg bez dodatkowych bibliotek.

Treść zadania

Zadanie 4 (iteracje). Dwa przekształcenia punktu (x, y), stosowane wielokrotnie w losowej kolejności (każde z prawdopodobieństwem 1/2), dają obraz smoka Heighwaya:

  • x' = −0,4x − 1, y' = −0,4y + 0,1;
  • x' = 0,76x − 0,4y, y' = 0,4x + 0,76y.

Wyniki podpunktów a, c, d zapisz w pliku zad_4.txt, poprzedzając je literą podpunktu:

  • a) zaczynając od x = 1, y = 1, oblicz pierwsze 5000 wartości (x, y) kolejnych iteracji;
  • b) sporządź obraz smoka (pomiń 100 pierwszych iteracji) i zapisz go w pliku smok.*;
  • c) oblicz środek masy smoka — średnie wartości x i y (zaokrąglone do 0,1), pomijając 100 pierwszych iteracji;
  • d) podaj minimalne i maksymalne wartości x oraz y (zaokrąglone do 0,1), pomijając 100 pierwszych iteracji.
Python
from random import randint

x, y = 1, 1
punkty = []

# a) 5000 iteracji, za każdym razem losowy układ równań
for i in range(5000):
    if randint(0, 1) == 0:
        x, y = -0.4 * x - 1, -0.4 * y + 0.1
    else:
        x, y = 0.76 * x - 0.4 * y, 0.4 * x + 0.76 * y
    punkty.append((x, y))

smok = punkty[100:]  # pomijamy 100 pierwszych iteracji
xs = [p[0] for p in smok]
ys = [p[1] for p in smok]

with open("zad_4.txt", "w") as wynik:
    wynik.write("a)\n")
    for x, y in punkty:
        wynik.write(f"{x} {y}\n")
    # c) środek masy
    wynik.write(f"c) {round(sum(xs) / len(xs), 1)} {round(sum(ys) / len(ys), 1)}\n")
    # d) rozmiary smoka
    wynik.write(f"d) xmin={round(min(xs), 1)} xmax={round(max(xs), 1)} "
                f"ymin={round(min(ys), 1)} ymax={round(max(ys), 1)}\n")

print("c)", round(sum(xs) / len(xs), 1), round(sum(ys) / len(ys), 1))
print("d)", round(min(xs), 1), round(max(xs), 1), round(min(ys), 1), round(max(ys), 1))

# b) obraz smoka jako plik SVG
skala = 300
with open("smok.svg", "w") as obraz:
    obraz.write('<svg xmlns="http://www.w3.org/2000/svg" width="600" height="400" '
                'style="background:white">\n')
    for x, y in smok:
        px = (x + 1.2) * skala
        py = 400 - (y + 0.5) * skala
        obraz.write(f'<circle cx="{px:.1f}" cy="{py:.1f}" r="0.8" fill="green"/>\n')
    obraz.write("</svg>\n")

Odpowiedź: wyniki są losowe, klucz nie podaje wartości; przykładowo: c) środek masy ≈ (−0,6; −0,1), d) x od −1,2 do 0,4, y od −0,7 do 0,4

↑

Arkusz II

5a

PythonC++23Java 25
Treść zadania

Zadanie 5 (para słów). Plik dane.txt zawiera w każdym wierszu parę słów A i B z cyfr 0 i 1, oddzielonych spacją; |A| ≥ |B|. Dla pary szukamy najkrótszego słowa C zawierającego A i B (B może być zawarte w A albo słowa mogą się nakładać sufiksem i prefiksem, w przeciwnym razie C to sklejenie A i B). Odpowiedzi do a–c zapisz w zad_5.txt, poprzedzając je literą podpunktu.

Podaj, ile spośród wszystkich słów w pliku dane.txt to palindromy.

Python
palindromy = 0

with open("dane.txt") as file:
    for line in file:
        for slowo in line.split():
            if slowo == slowo[::-1]:
                palindromy += 1

print(palindromy)

Odpowiedź: 46

↑

Arkusz II

5b

PythonC++23Java 25
Treść zadania

Podaj, ile par (A, B) z pliku dane.txt ma tę własność, że słowo B jest zawarte wewnątrz słowa A. Odpowiedź zapisz w zad_5.txt.

Python
licznik = 0

with open("dane.txt") as file:
    for line in file:
        a, b = line.split()
        if b in a:
            licznik += 1

print(licznik)

Odpowiedź: 35

↑

Arkusz II

5c

PythonC++23Java 25
Treść zadania

Podaj, ile par (A, B) z pliku dane.txt ma tę własność, że jedynym sposobem utworzenia najkrótszego słowa C zawierającego oba słowa jest sklejenie A i B (B nie jest zawarte w A i żaden sufiks jednego słowa nie jest prefiksem drugiego). Odpowiedź zapisz w zad_5.txt.

Python
def nakladka(a, b):
    # długość najdłuższego sufiksu słowa a, który jest prefiksem słowa b
    for k in range(min(len(a), len(b)), 0, -1):
        if a[-k:] == b[:k]:
            return k
    return 0


licznik = 0

with open("dane.txt") as file:
    for line in file:
        a, b = line.split()
        if b not in a and nakladka(a, b) == 0 and nakladka(b, a) == 0:
            licznik += 1

print(licznik)

Odpowiedź: 13

↑

Arkusz II

5d

PythonC++23Java 25
Treść zadania

Dla każdej pary (A, B) z pliku dane.txt utwórz najkrótsze słowo C zawierające oba słowa (np. dla A = 10011101: z B = 111 → C = A; z B = 1100 nakładamy 3-znakowy sufiks B na prefiks A; z B = 1010 nakładamy 3-znakowy sufiks A na prefiks B). Słowa C zapisz w pliku slowa.txt, każde w osobnym wierszu, w kolejności par z pliku.

Python
def nakladka(a, b):
    # długość najdłuższego sufiksu słowa a, który jest prefiksem słowa b
    for k in range(min(len(a), len(b)), 0, -1):
        if a[-k:] == b[:k]:
            return k
    return 0


def slowo_c(a, b):
    if b in a:
        return a
    k1 = nakladka(a, b)  # najpierw A, potem B
    k2 = nakladka(b, a)  # najpierw B, potem A
    if k1 >= k2:
        return a + b[k1:]
    return b + a[k2:]


with open("dane.txt") as file, open("slowa.txt", "w") as wynik:
    for line in file:
        a, b = line.split()
        wynik.write(slowo_c(a, b) + "\n")

Odpowiedź: plik slowa.txt: 0001100111101010111, 1100001101, 11000100, …

↑

Edytuj na GitHubie