Matura informatyka

Przykładowy arkusz CKE — formuła 2015

PythonC++23Java 25
Treść zadania

Całkowity pierwiastek kwadratowy. Dla dodatniej liczby całkowitej n całkowitym pierwiastkiem kwadratowym nazywamy dodatnią liczbę całkowitą k taką, że k·k ≤ n i (k+1)·(k+1) > n (np. 3 jest całkowitym pierwiastkiem z liczb 9–15). Specyfikacja: dane — dodatnia liczba całkowita n; wynik — k, całkowity pierwiastek kwadratowy z n. Przykład: dla n = 39 wynikiem jest k = 6.

  • a) Uzupełnij wiersz (3) algorytmu tak, aby był poprawny, i podaj, ile razy sprawdzany jest warunek w wierszu (2) dla n = 32 i dla n = 1024:
Kod
(1) k ← 1
(2) dopóki (k+1)*(k+1) ≤ n wykonuj
(3)     k ← ......
  • b) Uzupełnij wiersz (5) algorytmu (div — dzielenie całkowite):
Kod
(1) k ← 1; m ← n
(2) dopóki (k+1)*(k+1) ≤ n wykonuj
(3)     s ← (k+m) div 2
(4)     jeśli s*s ≤ n to
(5)         k ← ......
(6)     w przeciwnym przypadku
(7)         m ← s
  • c) Podaj, ile razy sprawdzany jest warunek w wierszu (2) algorytmu z punktu b) dla n = 32 i dla n = 1024.
Python
def pierwiastek_liniowo(n):
    # 2a - brakująca instrukcja: k <- k + 1
    k = 1
    sprawdzenia = 0
    while True:
        sprawdzenia += 1  # sprawdzenie warunku z wiersza (2)
        if not (k + 1) * (k + 1) <= n:
            break
        k = k + 1
    return k, sprawdzenia


def pierwiastek_binarnie(n):
    # 2b - brakująca instrukcja: k <- s (wyszukiwanie binarne w przedziale [k, m])
    k = 1
    m = n
    sprawdzenia = 0
    while True:
        sprawdzenia += 1
        if not (k + 1) * (k + 1) <= n:
            break
        s = (k + m) // 2
        if s * s <= n:
            k = s
        else:
            m = s
    return k, sprawdzenia


for n in [32, 1024]:
    print(n, pierwiastek_liniowo(n)[1], pierwiastek_binarnie(n)[1])

Odpowiedź: 2a: k ← k + 1; liczba sprawdzeń: 5 (n = 32) i 32 (n = 1024). 2b: k ← s. 2c: 6 (n = 32) i 6 (n = 1024).

↑
PythonC++23Java 25
Treść zadania

Progi i schody. W ciągu liczb naturalnych parę sąsiednich liczb nazywamy progiem, jeśli następna liczba jest mniejsza od poprzedniej. Schody do dołu to podciąg kolejnych elementów złożony z co najmniej dwóch liczb, w którym każda liczba (poza pierwszą) nie jest większa od poprzedniej i którego nie da się rozszerzyć w żadną stronę. Długość schodów to liczba ich elementów.

Przykład: ciąg 3, 7, 7, 6, 5, 4, 4, 4, 5 zawiera schody 7, 7, 6, 5, 4, 4, 4 o długości 7, z 3 progami (7 i 6, 6 i 5, 5 i 4).

Dla ciągu 2, 2, 2, 3, 1, 1, 3, 3, 1, 10, 11, 7, 7, 6, 7, 7, 8, 9, 9, 7 wypisz kolejno wszystkie schody do dołu, podając przy każdych ich długość i liczbę progów.

Python
def schody(a):
    # zwraca listę (schody, długość, liczba progów)
    wynik = []
    n = len(a)
    i = 0
    while i < n - 1:
        if a[i + 1] <= a[i]:
            j = i
            progi = 0
            while j < n - 1 and a[j + 1] <= a[j]:
                if a[j + 1] < a[j]:
                    progi += 1
                j += 1
            wynik.append((a[i:j + 1], j - i + 1, progi))
            i = j
        else:
            i += 1
    return wynik


ciag = [2, 2, 2, 3, 1, 1, 3, 3, 1, 10, 11, 7, 7, 6, 7, 7, 8, 9, 9, 7]
for schodki, dlugosc, progi in schody(ciag):
    print(schodki, dlugosc, progi)

Odpowiedź: (2, 2, 2) 3 0; (3, 1, 1) 3 1; (3, 3, 1) 3 1; (11, 7, 7, 6) 4 2; (7, 7) 2 0; (9, 9, 7) 3 1

↑
PythonC++23Java 25
Treść zadania

Próg to para sąsiednich liczb ciągu, w której następna liczba jest mniejsza od poprzedniej. Opracuj algorytm (schemat blokowy, lista kroków lub język programowania) zgodny ze specyfikacją:

  • Dane: dodatnia liczba całkowita n oraz tablica a[1..n] liczb całkowitych.
  • Wynik: liczba_progów — liczba wszystkich progów w ciągu zapisanym w tablicy a.
Python
def liczba_progow(a):
    licznik = 0
    for i in range(len(a) - 1):
        if a[i] > a[i + 1]:
            licznik += 1
    return licznik


print(liczba_progow([2, 2, 2, 3, 1, 1, 3, 3, 1, 10, 11, 7, 7, 6, 7, 7, 8, 9, 9, 7]))

Odpowiedź: algorytm powyżej (dla ciągu z 3a: 5 progów)

↑
PythonC++23Java 25
Treść zadania

Próg to para sąsiednich liczb, w której następna jest mniejsza od poprzedniej; schody do dołu to nierozszerzalny podciąg co najmniej dwóch kolejnych elementów, w którym każdy element (poza pierwszym) nie jest większy od poprzedniego.

  • c) Opracuj algorytm zgodny ze specyfikacją — dane: dodatnia liczba całkowita n i tablica a[1..n] liczb całkowitych; wynik: najw_liczba_progów — największa liczba progów w jednych schodach do dołu w ciągu a.
  • d) Podaj, ile dokładnie porównań między elementami ciągu wykona Twój algorytm z punktu c) w przypadku pesymistycznym, i uzasadnij odpowiedź.
Python
def najw_liczba_progow(a):
    najw = 0
    w_schodach = 0
    for i in range(len(a) - 1):
        if a[i] < a[i + 1]:
            # a[i + 1] może być początkiem nowych schodów
            if w_schodach > najw:
                najw = w_schodach
            w_schodach = 0
        elif a[i] > a[i + 1]:
            w_schodach += 1
    # schody mogą kończyć się ostatnim elementem ciągu
    if w_schodach > najw:
        najw = w_schodach
    return najw


print(najw_liczba_progow([3, 7, 7, 6, 5, 4, 4, 4, 5]))
print(najw_liczba_progow([2, 2, 2, 3, 1, 1, 3, 3, 1, 10, 11, 7, 7, 6, 7, 7, 8, 9, 9, 7]))

Odpowiedź: 3c: algorytm powyżej (dla przykładu z treści: 3). 3d: 2(n − 1) porównań — w każdym z n − 1 obrotów pętli w najgorszym razie wykonywane są dwa porównania (wykrycie nowych schodów i wykrycie progu).

↑
PythonC++23Java 25
Treść zadania

Anagramy cyfrowe. Dwie liczby naturalne są anagramami cyfrowymi, jeśli zapis dziesiętny jednej da się utworzyć z cyfr drugiej, używając każdej cyfry dokładnie tyle razy, ile razy w niej występuje (liczby nie mają zer wiodących). W pliku dane_anagramy.txt jest 1000 par dodatnich liczb całkowitych nie większych niż 2 000 000, po jednej parze w wierszu, oddzielonych spacją. Odpowiedzi zapisz w pliku wyniki_anagramy.txt, każdą w osobnym wierszu poprzedzoną oznaczeniem pytania.

  • a) W ilu wierszach obie liczby są anagramami cyfrowymi?
  • b) Ile maksymalnie liczb z pliku można wybrać tak, aby każde dwie były anagramami cyfrowymi?

Przykład: dla wierszy 232 322, 112 111, 223 121, 223 322 odpowiedź na a) to 2 (pierwszy i ostatni wiersz), a na b) to 5 (232, 322, 223, 223, 322).

Python
wiersze_z_anagramami = 0
ile = {}  # posortowane cyfry liczby -> ile liczb ma taki zestaw cyfr

with open("dane_anagramy.txt") as file:
    for line in file:
        a, b = line.split()
        # anagramy cyfrowe mają ten sam posortowany zapis cyfr
        klucz_a = "".join(sorted(a))
        klucz_b = "".join(sorted(b))
        if klucz_a == klucz_b:
            wiersze_z_anagramami += 1
        ile[klucz_a] = ile.get(klucz_a, 0) + 1
        ile[klucz_b] = ile.get(klucz_b, 0) + 1

with open("wyniki_anagramy.txt", "w") as wynik:
    print("a)", wiersze_z_anagramami, file=wynik)
    print("b)", max(ile.values()), file=wynik)

Odpowiedź: a) 258; b) 11

↑

Edytuj na GitHubie