Matura informatyka

Matura 2011 — maj, poziom rozszerzony

Arkusz I

1a

PythonC++23Java 25
Treść zadania

Funkcja rekurencyjna sklej(n) wyznacza, dla liczby naturalnej n > 0, długość napisu powstałego ze sklejenia zapisów binarnych liczb naturalnych od 1 do n − 1:

Kod
krok 1. jeśli n = 1, to wynikiem jest 0 (koniec)
krok 2. jeśli n parzyste, to wynikiem jest n − 1 + 2 · sklej(n / 2)
krok 3. jeśli n nieparzyste, to wynikiem jest n − 1 + sklej((n − 1) / 2) + sklej((n + 1) / 2)

Wykonanie funkcji można przedstawić jako drzewo wszystkich wywołań rekurencyjnych (w arkuszu podano drzewo dla sklej(5): korzeń ma dzieci sklej(2) i sklej(3) itd.). Narysuj analogiczne drzewo wywołań dla sklej(7).

Python
# drzewo wywołań - każde wywołanie wypisane z wcięciem równym głębokości rekurencji
def drzewo(n, glebokosc=0):
    print("    " * glebokosc + f"sklej({n})")
    if n == 1:
        return
    if n % 2 == 0:
        drzewo(n // 2, glebokosc + 1)
    else:
        drzewo((n - 1) // 2, glebokosc + 1)
        drzewo((n + 1) // 2, glebokosc + 1)


drzewo(7)

Odpowiedź: sklej(7) → sklej(3), sklej(4); sklej(3) → sklej(1), sklej(2); sklej(4) → sklej(2); każde sklej(2) → sklej(1)

↑

Arkusz I

1b

PythonC++23Java 25
Treść zadania

Funkcja sklej(n) jak w 1a (sklej(1) = 0, sklej(2) = 1).

Uzupełnij tabelę wartości funkcji dla n = 3, 4, 5, 6.

Python
def sklej(n):
    if n == 1:
        return 0
    if n % 2 == 0:
        return n - 1 + 2 * sklej(n // 2)
    return n - 1 + sklej((n - 1) // 2) + sklej((n + 1) // 2)


for n in range(1, 7):
    print(n, sklej(n))

Odpowiedź: sklej(3) = 3, sklej(4) = 5, sklej(5) = 8, sklej(6) = 11

↑

Arkusz I

1c

PythonC++23Java 25
Treść zadania

Funkcja sklej(n) jak w 1a.

Podaj algorytm bez rekurencji (bez wywoływania sklej), który wypełnia tablicę s[1..n] tak, że s[i] = sklej(i) dla 1 ≤ i ≤ n. Wskazówka: przy liczeniu s[i] można korzystać z obliczonych już wartości s[1], …, s[i − 1]. Dane: liczba naturalna n > 0. Wynik: tablica s[1..n].

Python
def wypelnij(n):
    # s[1..n], s[i] = sklej(i), bez rekurencji
    s = [0] * (n + 1)
    s[1] = 0
    for i in range(2, n + 1):
        if i % 2 == 0:
            s[i] = i - 1 + 2 * s[i // 2]
        else:
            s[i] = i - 1 + s[(i - 1) // 2] + s[(i + 1) // 2]
    return s


s = wypelnij(10)
print(s[1:])

# sprawdzenie: s[n] to długość sklejonych zapisów binarnych liczb od 1 do n-1
for n in range(1, 11):
    napis = ""
    for i in range(1, n):
        napis += bin(i)[2:]
    print(n, s[n], len(napis))

Odpowiedź: s[1] := 0; dla i = 2..n: jeśli i parzyste, to s[i] := i − 1 + 2·s[i div 2], w przeciwnym razie s[i] := i − 1 + s[(i − 1) div 2] + s[(i + 1) div 2]

↑

Arkusz I

2a

PythonC++23Java 25
Treść zadania

Algorytm szybkiego potęgowania: dla liczby rzeczywistej a i naturalnej n ≥ 0 oblicza p = aⁿ.

Kod
krok 1. p := 1, b := a
krok 2. dopóki n > 0 wykonuj:
    a) jeśli n mod 2 = 1, to p := p * b
    b) b := b * b
    c) n := n div 2

Uzupełnij tabelę wartości zmiennych p, b, n po kolejnych wykonaniach kroku 2 dla dowolnego a i początkowego n = 12 (pierwszy wiersz: 1, a, 12).

Python · zamiast wartości pamiętamy wykładniki: p = a^wp, b = a^wb
wp, wb, n = 0, 1, 12
print(f"p = a^{wp}, b = a^{wb}, n = {n}")
while n > 0:
    if n % 2 != 0:
        wp = wp + wb  # p := p * b
    wb = wb + wb      # b := b * b
    n = n // 2
    print(f"p = a^{wp}, b = a^{wb}, n = {n}")

Odpowiedź: (1, a, 12), (1, a², 6), (1, a⁴, 3), (a⁴, a⁸, 1), (a¹², a¹⁶, 0)

↑

Arkusz I

2b i 2c

PythonC++23Java 25
Treść zadania

Algorytm potęgowania z zadania 2a; liczymy mnożenia, czyli wykonania instrukcji p := p * b oraz b := b * b.

  • 2b — Podaj liczbę wszystkich mnożeń wykonywanych przez algorytm dla n = 2, 3, 4, 5, 6, 7.
  • 2c — Wskaż funkcję równą liczbie mnożeń dla n będącego potęgą dwójki; do wyboru: f(n) = 2 + log₂n, f(n) = 1 + n, f(n) = 2n² − 1, f(n) = 2ⁿ.
Python
def liczba_mnozen(n):
    mnozenia = 0
    while n > 0:
        if n % 2 != 0:
            mnozenia += 1  # p := p * b
        mnozenia += 1      # b := b * b
        n = n // 2
    return mnozenia


# b)
for n in range(2, 8):
    print(n, liczba_mnozen(n))

# c) dla n będącego potęgą dwójki
for k in range(6):
    print(2 ** k, liczba_mnozen(2 ** k), 2 + k)

Odpowiedź: b) 2 → 3, 3 → 4, 4 → 4, 5 → 5, 6 → 5, 7 → 6; c) f(n) = 2 + log₂n

↑

Arkusz II

4a

PythonC++23Java 25

Zadanie na arkusz kalkulacyjny — rozwiązanie w Pythonie.

Treść zadania

Firma utrzymuje trawniki od 1 kwietnia do 30 października 2011 r. Rano 1 kwietnia zgromadzonych jest 10 000 m³ skoszonej trawy. Codziennie: przed południem każdy z 30 samochodów wywozi 15 m³ trawy, w ciągu dnia kosi się 600 m³, a w nocy objętość trawy maleje o 3% (ubytek zaokrąglamy w dół do całkowitej liczby m³, np. z 60 m³ ubywa 1 m³). Odpowiedzi zapisz w pliku zadanie4.txt, poprzedzając je literą podpunktu.

Podaj, o ile m³ zmniejszy się objętość trawy w nocy z 9 na 10 kwietnia 2011 r.

Python
trawa = 10000  # 1 kwietnia rano

for dzien in range(1, 10):  # 1..9 kwietnia
    trawa = max(0, trawa - 30 * 15)  # przed południem 30 samochodów wywozi po 15 m3
    trawa += 600                     # w ciągu dnia kosi się 600 m3
    ubytek = trawa * 3 // 100        # w nocy ubywa 3% (w dół)
    trawa -= ubytek

print(ubytek)  # noc z 9 na 10 kwietnia

Odpowiedź: 271

↑

Arkusz II

4b

PythonC++23Java 25

Zadanie na arkusz kalkulacyjny — rozwiązanie w Pythonie.

Treść zadania

Model zmian objętości trawy jak w 4a (start: 10 000 m³, 30 samochodów po 15 m³, +600 m³ dziennie, −3% w nocy z zaokrągleniem w dół).

Oceń, które zdania są prawdziwe, i uzupełnij je liczbami:

  • 1. Po ilu dniach objętość trawy rano po raz pierwszy była większa niż rano dnia poprzedniego (i jaka to data)?
  • 2. Po ilu dniach objętość trawy rano po raz pierwszy będzie taka sama jak dnia poprzedniego (i jaka to data)?
  • 3. Jaka jest najmniejsza liczba samochodów, przy której 12 kwietnia 2011 r. po raz pierwszy zostanie wywieziona cała trawa zgromadzona rano?
Python
from datetime import date, timedelta


def poranki(trawa, samochody, dni):
    # objętość trawy rano w kolejnych dniach, indeks 0 to 1 kwietnia
    rano = [trawa]
    for i in range(dni):
        trawa = max(0, trawa - samochody * 15)
        trawa += 600
        trawa -= trawa * 3 // 100
        rano.append(trawa)
    return rano


start = date(2011, 4, 1)
rano = poranki(10000, 30, 213)  # do 31 października

# 1.
zdanie1 = False
for i in range(1, len(rano)):
    if rano[i] > rano[i - 1]:
        zdanie1 = True
        print("1.", i, start + timedelta(days=i))
        break
if not zdanie1:
    print("1. fałsz")

# 2.
for i in range(1, len(rano)):
    if rano[i] == rano[i - 1]:
        print("2.", i, start + timedelta(days=i))
        break

# 3. 12 kwietnia ma indeks 11
samochody = 1
while True:
    rano = poranki(10000, samochody, 11)
    pierwszy = None
    for i in range(len(rano)):
        if rano[i] <= samochody * 15:
            pierwszy = i
            break
    if pierwszy == 11:
        print("3.", samochody)
        break
    samochody += 1

Odpowiedź: 1. fałsz; 2. prawda – po 185 dniach, 2011-10-03; 3. prawda – 83 samochody

↑

Arkusz II

4c

PythonC++23Java 25

Zadanie na arkusz kalkulacyjny — rozwiązanie w Pythonie.

Treść zadania

Model zmian objętości trawy jak w 4a.

Wyznacz objętość trawy po 100 dniach pracy (rano 101. dnia, przed wywozem), gdy 1 kwietnia rano zgromadzone było odpowiednio 10 000 m³, 7 000 m³ i 4 000 m³. Sporządź czytelny wykres kolumnowy (z tytułem i opisem danych) porównujący te trzy wartości. Wyniki zapisz w pliku zadanie4.txt.

Python
for trawa in [10000, 7000, 4000]:
    poczatek = trawa
    for dzien in range(100):
        trawa = max(0, trawa - 30 * 15)
        trawa += 600
        trawa -= trawa * 3 // 100
    print(poczatek, trawa)

Odpowiedź: 5109, 4968, 4824 (wykres kolumnowy dla 10 000, 7 000 i 4 000 m³)

↑

Arkusz II

6a

PythonC++23Java 25
Treść zadania

W pliku liczby.txt znajduje się 1000 liczb zapisanych w systemie dwójkowym (każda w osobnym wierszu), o długości od 2 do 16 cyfr. Odpowiedzi zapisz w pliku zadanie6.txt, poprzedzając je literą podpunktu.

Ile liczb w pliku jest parzystych?

Python
parzyste = 0

with open("liczby.txt") as file:
    for line in file:
        liczba = line.strip()
        if liczba[-1] == "0":
            parzyste += 1

print(parzyste)

Odpowiedź: 497

↑

Arkusz II

6b

PythonC++23Java 25
Treść zadania

Dane z pliku liczby.txt (1000 liczb dwójkowych).

Podaj największą liczbę z pliku w systemie dwójkowym i dziesiętnym.

Python
najwieksza = 0

with open("liczby.txt") as file:
    for line in file:
        liczba = int(line.strip(), 2)
        if liczba > najwieksza:
            najwieksza = liczba

print(bin(najwieksza)[2:], najwieksza)

Odpowiedź: 1111101111110110 (dwójkowo), 64502 (dziesiętnie)

↑

Arkusz II

6c

PythonC++23Java 25
Treść zadania

Dane z pliku liczby.txt (1000 liczb dwójkowych).

Ile liczb w pliku ma dokładnie 9 cyfr? Podaj sumę tych liczb w systemie dwójkowym.

Python
ile = 0
suma = 0

with open("liczby.txt") as file:
    for line in file:
        liczba = line.strip()
        if len(liczba) == 9:  # liczymy cyfry zapisu z pliku
            ile += 1
            suma += int(liczba, 2)

print(ile, bin(suma)[2:])

Odpowiedź: 101 liczb, suma 1001100111110111 (dziesiętnie 39415)

↑

Edytuj na GitHubie