Matura informatyka

Matura 2012 — maj, poziom rozszerzony

Arkusz I

1a, 1c i 1d

PythonC++23Java 25
Treść zadania

Dana jest liczba naturalna n > 0 i tablica a[1..n] różnych liczb całkowitych. Rozważamy rekurencyjną funkcję F z argumentem i (1 ≤ i ≤ n):

Kod
F(i):
    jeżeli i = n, to wynikiem jest n
    w przeciwnym razie
        j := F(i + 1)
        jeżeli a[i] < a[j], to wynikiem jest i
        w przeciwnym razie wynikiem jest j
  • 1a — Dla tablicy a = [5, 1, 8, 9, 7, 2, 3, 11, 20, 15] podaj F(9), F(7) i F(5).
  • 1b — (w odpowiedzi poniżej) Wskaż, czym zawsze jest a[w], gdzie w = F(i): najmniejszą liczbą w całej tablicy, najmniejszą spośród elementów o indeksach od i do n, czy najmniejszą spośród elementów o indeksach od 1 do i.
  • 1c — Ile porównań między elementami tablicy zostanie wykonanych przy wywołaniu F(512) dla n = 2012?
  • 1d — Zapisz funkcję F w wersji iteracyjnej.
Python
import sys

sys.setrecursionlimit(5000)

porownania = 0


def F(i):
    # a[1..n], a[0] nieużywane - indeksy jak w zadaniu
    global porownania
    if i == n:
        return n
    j = F(i + 1)
    porownania += 1
    if a[i] < a[j]:
        return i
    return j


# d) wersja iteracyjna
def F_iteracyjnie(i):
    ind_min = n
    for k in range(n - 1, i - 1, -1):
        if a[k] < a[ind_min]:
            ind_min = k
    return ind_min


# a)
a = [None, 5, 1, 8, 9, 7, 2, 3, 11, 20, 15]
n = 10
for i in [9, 7, 5]:
    print(i, F(i), F_iteracyjnie(i))

# c)
n = 2012
a = [None] + list(range(1, n + 1))  # dowolne różne liczby
porownania = 0
F(512)
print(porownania)

Odpowiedź: a) F(9) = 10, F(7) = 7, F(5) = 6; b) a[w] to najmniejsza liczba spośród elementów o indeksach od i do n; c) 1500

↑

Arkusz I

2a i 2c

PythonC++23Java 25
Treść zadania

Liczbę naturalną n nazywamy osiągalną, jeśli istnieje liczba naturalna k taka, że n = k + s(k), gdzie s(k) to suma cyfr k w zapisie dziesiętnym (np. 505 = 491 + 14 jest osiągalna, 20 nie jest).

  • 2a — Uzupełnij tabelę (k, s(k), czy osiągalna) dla n = 28 i n = 31.
  • 2b — (w odpowiedzi poniżej) Uzasadnij, że jeśli n jest czterocyfrowa i n = k + s(k), to s(k) ≤ 36.
  • 2c — Zapisz algorytm, który dla n z przedziału [1000, 9999] sprawdza, czy n jest osiągalna, korzystając z faktu z 2b. Wynik: liczba k taka, że n = k + s(k), albo komunikat NIE.
Python
def suma_cyfr(k):
    s = 0
    while k > 0:
        s += k % 10
        k //= 10
    return s


def osiagalna(n):
    # z podpunktu b): dla n czterocyfrowego s(k) <= 36, więc sprawdzamy k = n-1, ..., n-36
    for i in range(1, 37):
        k = n - i
        if k > 0 and k + suma_cyfr(k) == n:
            return k
    return "NIE"


# a)
for n in [505, 20, 28, 31]:
    k = osiagalna(n)
    if k == "NIE":
        print(n, "-", "-", "NIE")
    else:
        print(n, k, suma_cyfr(k), "TAK")

# c)
print(osiagalna(2012), osiagalna(1000))

Odpowiedź: a) n = 28: k = 23, s(k) = 5, TAK; n = 31: NIE; b) suma cyfr liczby co najwyżej czterocyfrowej nie przekracza 4·9 = 36

↑

Arkusz II

4a

PythonC++23Java 25
Treść zadania

Szyfr podstawieniowy na wielkich literach alfabetu angielskiego: litery mają numery A = 1, …, Z = 26 i kody ASCII 65–90. Kolejne litery tekstu jawnego szyfruje się kolejnymi literami klucza (w razie potrzeby powtarzanego): do kodu ASCII litery tekstu dodaje się numer litery klucza, a gdy wynik przekroczy 90, odejmuje się 26; szyfrem jest litera o otrzymanym kodzie. Przykład: LATO z kluczem WODA → IPXP (L + W = 76 + 23 = 99 → 73 = I); MARTA z kluczem TOR → GPJNP. Deszyfrowanie polega na odjęciu numeru litery klucza (z korektą o 26, gdy wynik spadnie poniżej 65).

W pliku tj.txt znajdują się słowa do zaszyfrowania, a w pliku klucze1.txt — klucze (po jednym słowie w wierszu). Zaszyfruj słowo z N-tego wiersza pliku tj.txt kluczem z N-tego wiersza pliku klucze1.txt i zapisz szyfrogramy (w tej samej kolejności) w pliku wynik4a.txt.

Python
def szyfruj(tekst, klucz):
    wynik = ""
    for i in range(len(tekst)):
        numer = ord(klucz[i % len(klucz)]) - 64  # numer litery klucza (A = 1)
        kod = ord(tekst[i]) + numer
        if kod > 90:
            kod -= 26
        wynik += chr(kod)
    return wynik


print(szyfruj("LATO", "WODA"), szyfruj("MARTA", "TOR"))  # IPXP GPJNP

with open("tj.txt") as file:
    teksty = file.read().split()
with open("klucze1.txt") as file:
    klucze = file.read().split()

with open("wynik4a.txt", "w") as wynik:
    for i in range(len(teksty)):
        wynik.write(szyfruj(teksty[i], klucze[i]) + "\n")

Odpowiedź: CNA, UUU, WNS, TRX, WCCG, YOYG, XEUUAU, … , MDO (120 słów)

↑

Arkusz II

4b

PythonC++23Java 25
Treść zadania

Szyfr opisany w 4a; deszyfrowanie: od kodu litery szyfrogramu odejmujemy numer odpowiadającej litery klucza (gdy wynik jest mniejszy niż 65, dodajemy 26).

W pliku sz.txt znajdują się zaszyfrowane słowa, a w pliku klucze2.txt — klucze. Odszyfruj słowo z N-tego wiersza pliku sz.txt kluczem z N-tego wiersza pliku klucze2.txt i zapisz teksty jawne (w tej samej kolejności) w pliku wynik4b.txt.

Python
def deszyfruj(szyfr, klucz):
    wynik = ""
    for i in range(len(szyfr)):
        numer = ord(klucz[i % len(klucz)]) - 64
        kod = ord(szyfr[i]) - numer
        if kod < 65:
            kod += 26
        wynik += chr(kod)
    return wynik


with open("sz.txt") as file:
    szyfry = file.read().split()
with open("klucze2.txt") as file:
    klucze = file.read().split()

with open("wynik4b.txt", "w") as wynik:
    for i in range(len(szyfry)):
        wynik.write(deszyfruj(szyfry[i], klucze[i]) + "\n")

Odpowiedź: KOT, PIES, COS, NIC, NUTA, BUT, LUPA, ZUPA, KWIAT, CEL, … , KROWA, OWCA (120 słów)

↑

Arkusz II

5a

PythonC++23Java 25

Zadanie na arkusz kalkulacyjny — rozwiązanie w Pythonie.

Treść zadania

Trójkąt Pascala: na brzegach są jedynki, a każda liczba wewnątrz to suma dwóch najbliższych liczb z wiersza powyżej. W wersji prostokątnej jedynki wypełniają pionową przyprostokątną i przeciwprostokątną, a liczba wewnątrz jest sumą liczby stojącej bezpośrednio nad nią i liczby na lewo od tamtej. Rozważamy trójkąt złożony z 30 wierszy numerowanych od 1. Odpowiedzi do a)–c) zapisz w pliku wynik5.txt, poprzedzając je literą podpunktu.

Podaj największą liczbę w 10., 20. i 30. wierszu trójkąta.

Python
trojkat = [[1]]
for w in range(1, 30):
    poprzedni = trojkat[-1]
    wiersz = [1]
    for j in range(1, w):
        wiersz.append(poprzedni[j - 1] + poprzedni[j])
    wiersz.append(1)
    trojkat.append(wiersz)

print(max(trojkat[9]), max(trojkat[19]), max(trojkat[29]))  # wiersze 10, 20, 30

Odpowiedź: wiersz 10: 126, wiersz 20: 92378, wiersz 30: 77558760

↑

Arkusz II

5b

PythonC++23Java 25

Zadanie na arkusz kalkulacyjny — rozwiązanie w Pythonie.

Treść zadania

Trójkąt Pascala z 30 wierszy (numeracja od 1), jak w 5a.

Utwórz zestawienie zawierające dla każdego wiersza jego numer oraz łączną liczbę cyfr (nie liczb) w tym wierszu.

Python
trojkat = [[1]]
for w in range(1, 30):
    poprzedni = trojkat[-1]
    wiersz = [1]
    for j in range(1, w):
        wiersz.append(poprzedni[j - 1] + poprzedni[j])
    wiersz.append(1)
    trojkat.append(wiersz)

for numer in range(1, 31):
    cyfry = 0
    for liczba in trojkat[numer - 1]:
        cyfry += len(str(liczba))
    print(numer, cyfry)

Odpowiedź: 1 1, 2 2, 3 3, 4 4, 5 5, 6 8, 7 10, 8 12, 9 14, 10 18, … , 29 166, 30 178

↑

Arkusz II

5c

PythonC++23Java 25

Zadanie na arkusz kalkulacyjny — rozwiązanie w Pythonie.

Treść zadania

Trójkąt Pascala z 30 wierszy (numeracja od 1), jak w 5a.

Podaj numery wierszy, które nie zawierają żadnej liczby podzielnej przez 5.

Python
trojkat = [[1]]
for w in range(1, 30):
    poprzedni = trojkat[-1]
    wiersz = [1]
    for j in range(1, w):
        wiersz.append(poprzedni[j - 1] + poprzedni[j])
    wiersz.append(1)
    trojkat.append(wiersz)

for numer in range(1, 31):
    if all(liczba % 5 != 0 for liczba in trojkat[numer - 1]):
        print(numer, end=" ")

Odpowiedź: 1, 2, 3, 4, 5, 10, 15, 20, 25

↑

Arkusz II

5d

PythonC++23Java 25

Zadanie na arkusz kalkulacyjny — rozwiązanie w Pythonie.

Treść zadania

Trójkąt Pascala z 30 wierszy, jak w 5a. Rozmieszczenie liczb parzystych i nieparzystych tworzy wzór przypominający trójkąt Sierpińskiego.

Na podstawie trójkąta (prostokątnego lub równoramiennego) przedstaw graficznie rozmieszczenie liczb podzielnych przez 3: komórki z takimi liczbami oznacz np. znakiem X (lub czarnym tłem), a pozostałe — spacją (białym tłem). Wynik zapisz w osobnym pliku.

Python
trojkat = [[1]]
for w in range(1, 30):
    poprzedni = trojkat[-1]
    wiersz = [1]
    for j in range(1, w):
        wiersz.append(poprzedni[j - 1] + poprzedni[j])
    wiersz.append(1)
    trojkat.append(wiersz)

# X - liczba podzielna przez 3, spacja - pozostałe (trójkąt prostokątny)
with open("wynik5d.txt", "w") as wynik:
    for wiersz in trojkat:
        linia = ""
        for liczba in wiersz:
            if liczba % 3 == 0:
                linia += "X"
            else:
                linia += " "
        wynik.write(linia + "\n")
        print(linia)

Odpowiedź: obraz w pliku wynik5d.txt – pierwsze X w wierszu 4 („ XX ”), wzór podobny do trójkąta Sierpińskiego

↑

Edytuj na GitHubie