Matura informatyka

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

PythonC++23Java 25
Treść zadania

Każdą liczbę całkowitą większą od 1 można rozłożyć na iloczyn czynników pierwszych (liczba pierwsza ma jeden czynnik — samą siebie), np. 120 = 2 · 2 · 2 · 3 · 5, więc największym czynnikiem pierwszym 120 jest 5.

  • 1.1 — Uzupełnij tabelę: dla liczb 32, 99 i 252 zapisz rozkład na czynniki pierwsze i największy czynnik pierwszy (przykłady: 120 → 5, 14 = 2 · 7 → 7).
  • 1.2 — Zapisz (w pseudokodzie, liście kroków lub wybranym języku) funkcję Największy_Czynnik(n), która dla liczby całkowitej n > 1 wyznacza największy czynnik d w jej rozkładzie na czynniki pierwsze. Wolno używać tylko zmiennych całkowitych, podstawowych operacji arytmetycznych (w tym dzielenia całkowitego i reszty), porównań, instrukcji sterujących i własnych funkcji — bez funkcji wbudowanych.
Python · 1.2
def najwiekszy_czynnik(n):
    d = 2
    while n > 1:
        if n % d == 0:
            n = n // d
        else:
            d = d + 1
    return d


def rozklad(n):
    czynniki = []
    d = 2
    while n > 1:
        if n % d == 0:
            czynniki.append(d)
            n //= d
        else:
            d += 1
    return czynniki


# 1.1
for n in [32, 99, 252]:
    print(n, " * ".join(map(str, rozklad(n))), najwiekszy_czynnik(n))

Odpowiedź: 1.1: 32 = 2 · 2 · 2 · 2 · 2, d = 2; 99 = 3 · 3 · 11, d = 11; 252 = 2 · 2 · 3 · 3 · 7, d = 7. 1.2: funkcja najwiekszy_czynnik.

↑
PythonC++23Java 25
Treść zadania

Dana jest funkcja rekurencyjna fun(a, b) dla liczb całkowitych a i b, b ≥ 2:

Kod
fun(a, b):
    jeżeli a ≤ 2
        jeżeli a = 2: wynikiem jest PRAWDA, zakończ
        w przeciwnym przypadku: wynikiem jest FAŁSZ, zakończ
    jeżeli a mod b = 0: wynikiem jest FAŁSZ, zakończ
    jeżeli b * b > a: wynikiem jest PRAWDA, zakończ
    wynikiem jest fun(a, b + 1)
  • 2.1 — Podaj wynik fun(a, 2) dla a = 1, 7, 16 i −4 (przykład: dla a = 0 wynikiem jest FAŁSZ).
  • 2.2 — Podaj, ile razy zostanie wykonane wywołanie fun(a, b + 1) po wywołaniu fun(a, 2) dla a = 17 i a = 77 (samego wywołania fun(a, 2) nie liczymy; przykłady: a = 2 → 0, a = 35 → 3).
Python
wywolania = 0


def fun(a, b):
    global wywolania
    if a <= 2:
        return a == 2
    if a % b == 0:
        return False
    if b * b > a:
        return True
    wywolania += 1
    return fun(a, b + 1)


# 2.1
for a in [1, 7, 16, -4]:
    print(a, fun(a, 2))

# 2.2
for a in [17, 77]:
    wywolania = 0
    fun(a, 2)
    print(a, wywolania)

Odpowiedź: 2.1: 1 – FAŁSZ, 7 – PRAWDA, 16 – FAŁSZ, −4 – FAŁSZ (funkcja sprawdza, czy a jest liczbą pierwszą). 2.2: a = 17 → 3, a = 77 → 5.

↑
PythonC++23Java 25
Treść zadania

Plik plansza.txt opisuje rozmieszczenie statków na planszy 100 × 100: 100 wierszy po 100 cyfr 0 lub 1 oddzielonych spacjami (1 — pole ze statkiem, 0 — pole puste). Jednomasztowiec to pojedyncza jedynka otoczona zewsząd zerami lub krawędzią planszy, a dwumasztowiec — dwie sąsiednie (w poziomie lub pionie) jedynki otoczone zerami lub krawędzią. Statki nie stykają się ani bokami, ani wierzchołkami. Odpowiedzi zapisz w pliku wyniki4.txt, poprzedzając każdą numerem zadania. Plik plansza_przyklad.txt (plansza 10 × 10) służy do testów.

  • 4.1 — Podaj liczbę pól, na których można jeszcze postawić jednomasztowiec, tj. pól z zerem, które nie stykają się bokiem ani wierzchołkiem z żadnym polem zajętym przez statek (dla pliku przykładowego: 11).
  • 4.2 — Podaj liczbę par jednomasztowców położonych symetrycznie względem przekątnej biegnącej od lewego górnego do prawego dolnego rogu; statków leżących na tej przekątnej nie liczymy (dla pliku przykładowego: 2).
  • 4.3 — Podaj liczbę dwumasztowców na planszy (dla pliku przykładowego: 7).
  • 4.4 — Podaj liczbę jednomasztowców i liczbę dwumasztowców, których co najmniej jedno pole leży na jednej z dwóch głównych przekątnych planszy (dla pliku przykładowego: 1 jednomasztowiec i 3 dwumasztowce).
Python
with open("plansza.txt") as file:
    plansza = [linia.split() for linia in file if linia.strip()]

n = len(plansza)
wynik = open("wyniki4.txt", "w")


def pole(w, k):
    # pole poza planszą traktujemy jak puste
    if 0 <= w < n and 0 <= k < n:
        return plansza[w][k]
    return "0"


def sasiedzi_puste(w, k, pomin=()):
    # czy wszystkie pola dookoła (w, k) - poza polami z listy pomin - są puste
    for dw in (-1, 0, 1):
        for dk in (-1, 0, 1):
            if (dw, dk) != (0, 0) and (w + dw, k + dk) not in pomin and pole(w + dw, k + dk) == "1":
                return False
    return True


# 4.1
wolne = 0
for w in range(n):
    for k in range(n):
        if plansza[w][k] == "0" and sasiedzi_puste(w, k):
            wolne += 1
print("4.1", wolne, file=wynik)

# wyszukanie jednomasztowców i dwumasztowców
jednomasztowce = []
dwumasztowce = []
for w in range(n):
    for k in range(n):
        if plansza[w][k] == "1":
            if sasiedzi_puste(w, k):
                jednomasztowce.append((w, k))
            for dw, dk in ((0, 1), (1, 0)):          # drugi maszt na prawo albo poniżej
                w2, k2 = w + dw, k + dk
                if pole(w2, k2) == "1" and sasiedzi_puste(w, k, [(w2, k2)]) \
                        and sasiedzi_puste(w2, k2, [(w, k)]):
                    dwumasztowce.append(((w, k), (w2, k2)))

# 4.2
pary = 0
for w, k in jednomasztowce:
    if w < k and (k, w) in jednomasztowce:
        pary += 1
print("4.2", pary, file=wynik)

# 4.3
print("4.3", len(dwumasztowce), file=wynik)


# 4.4
def na_przekatnej(w, k):
    return w == k or w + k == n - 1


jedno = 0
for w, k in jednomasztowce:
    if na_przekatnej(w, k):
        jedno += 1
dwu = 0
for (w1, k1), (w2, k2) in dwumasztowce:
    if na_przekatnej(w1, k1) or na_przekatnej(w2, k2):
        dwu += 1
print("4.4", jedno, dwu, file=wynik)

wynik.close()

Odpowiedź: 4.1: 9321. 4.2: 5. 4.3: 35. 4.4: 1 jednomasztowiec, 10 dwumasztowców.

↑

Edytuj na GitHubie