Matura informatyka

Matura 2017 — maj, poziom rozszerzony (stara formuła)

PythonC++23Java 25
Treść zadania

Zadanie 1. Sortowanie. Dane: liczby całkowite dodatnie n, k oraz ciąg T[1..n] liczb z zakresu [1..k]. Wynik: tablica W[1..n] — elementy T uporządkowane niemalejąco. Algorytm:

Kod
dla i=1..k: Liczba_wystapien[i] ← 0
dla i=1..n: Liczba_wystapien[T[i]] ← Liczba_wystapien[T[i]] + 1
p ← 1
dla j=1..k:
    dla i=1..Liczba_wystapien[j]:
        W[p] ← j; p ← p+1
  • 1.1 — Podaj końcową zawartość tablicy Liczba_wystapien[1..k] dla danych: n=10, k=5, T=[1,2,3,4,5,1,2,3,4,4]; n=5, k=10, T=[1,3,3,5,10]; n=5, k=5, T=[5,5,5,5,5]; n=10, k=4, T=[1,2,3,1,2,3,1,1,2,3].
  • 1.2 — Rangą elementu T[i] nazywamy liczbę elementów ciągu mniejszych od T[i] (np. dla T=[1,2,3,4,5,1,4,3,2,5] ranga T[8]=3 wynosi 4). Korzystając z gotowej tablicy Liczba_wystapien, uzupełnij algorytm r ← 0; dla j=1..___: r ← r + Liczba_wystapien[j] tak, by r było rangą T[i].
Python
def sortowanie(T, k):
    liczba_wystapien = [0] * (k + 1)       # indeksy 1..k
    for x in T:
        liczba_wystapien[x] += 1
    W = []
    for j in range(1, k + 1):
        for i in range(liczba_wystapien[j]):
            W.append(j)
    return liczba_wystapien[1:], W


def ranga(T, k, i):
    # i - numer elementu liczony od 1, jak w tresci zadania
    liczba_wystapien = [0] + sortowanie(T, k)[0]
    r = 0
    for j in range(1, T[i - 1]):           # j = 1 .. T[i]-1
        r += liczba_wystapien[j]
    return r


dane = [(5, [1, 2, 3, 4, 5, 1, 2, 3, 4, 4]), (10, [1, 3, 3, 5, 10]), (5, [5, 5, 5, 5, 5]), (4, [1, 2, 3, 1, 2, 3, 1, 1, 2, 3])]
for k, T in dane:
    print(sortowanie(T, k)[0])

T = [1, 2, 3, 4, 5, 1, 4, 3, 2, 5]
print(ranga(T, 5, 8), ranga(T, 5, 10), ranga(T, 5, 6))

Odpowiedź: 1.1: [2, 2, 2, 3, 1], [1, 0, 2, 0, 1, 0, 0, 0, 0, 1], [0, 0, 0, 0, 5], [4, 3, 3, 0]; 1.2: dla j = 1..T[i] - 1

↑
PythonC++23Java 25
Treść zadania

Teraz elementy tablicy T[1..n] mogą być dowolnymi dodatnimi liczbami całkowitymi. Algorytm LicznikiMod:

Kod
dla i=1..k: Liczba_wystapien[i] ← 0
dla i=1..n:
    m ← 1 + (T[i] mod k)
    Liczba_wystapien[m] ← Liczba_wystapien[m] + 1
w ← Liczba_wystapien[1]

Podaj końcową zawartość tablicy Liczba_wystapien[1..k] dla n=10, T=[1,2,3,4,5,1,2,3,4,4] i k = 2, 3, 4, 5. Uzupełnij też specyfikację: co oznacza wynik w?

Python
def liczniki_mod(T, k):
    liczba_wystapien = [0] * (k + 1)
    for x in T:
        m = 1 + x % k
        liczba_wystapien[m] += 1
    w = liczba_wystapien[1]                # liczba elementow podzielnych przez k
    return liczba_wystapien[1:], w


T = [1, 2, 3, 4, 5, 1, 2, 3, 4, 4]
for k in [2, 3, 4, 5]:
    print(k, *liczniki_mod(T, k))

Odpowiedź: k=3: [2, 5, 3], k=4: [3, 3, 2, 2], k=5: [1, 2, 2, 2, 3]; w — liczba elementów ciągu T[1..n] podzielnych przez k

↑
PythonC++23Java 25
Treść zadania

Zadanie 2. Ciąg Pentanacciego: p0=0, p1=1, p2=1, p3=2, p4=4, a dla n ≥ 5: pn = p(n-1) + p(n-2) + p(n-3) + p(n-4) + p(n-5).

  • 2.1 — Podaj pn dla n = 7 i 9 (dla n=5 jest to 8).
  • 2.2 — Uzupełnij luki w algorytmie obliczającym w = pn dla nieujemnego n, który przechowuje tylko 5 ostatnich wyrazów w tablicy tab[0..4]:
Kod
tab[0..4] ← 0, 1, 1, 2, 4
i ← 5
dopóki i ≤ ... wykonuj
    temp ← tab[0]+tab[1]+tab[2]+tab[3]+tab[4]
    tab[... mod 5] ← temp
    i ← i+1
Python
def pentanacci(n):
    tab = [0, 1, 1, 2, 4]
    i = 5
    while i <= n:
        temp = tab[0] + tab[1] + tab[2] + tab[3] + tab[4]
        tab[i % 5] = temp
        i += 1
    return tab[n % 5]


for n in [5, 7, 9]:
    print(n, pentanacci(n))

Odpowiedź: p7 = 31, p9 = 120; luki: i ≤ n, tab[i mod 5], w ← tab[n mod 5]

↑
PythonC++23Java 25
Treść zadania

Dla ciągu Pentanacciego (p0..p4 = 0, 1, 1, 2, 4, pn = suma pięciu poprzednich wyrazów) rozważamy ciąg rn = pn mod 2: r0..r4 = 0, 1, 1, 0, 0, rn = (r(n-1)+...+r(n-5)) mod 2. Liczba pn jest parzysta wtedy i tylko wtedy, gdy rn = 0, a ciąg rn jest okresowy z okresem 6 (zależy tylko od n mod 6). Zapisz algorytm o jak najmniejszej złożoności, który dla nieujemnego n zwraca w = 0, gdy pn jest parzysta, i w = 1, gdy nieparzysta.

Python
def parzystosc(n):
    k = n % 6
    if k == 1 or k == 2:
        return 1
    return 0


# sprawdzenie z algorytmem z 2.2 (funkcja pentanacci)
def pentanacci(n):
    tab = [0, 1, 1, 2, 4]
    for i in range(5, n + 1):
        tab[i % 5] = sum(tab)
    return tab[n % 5]


print(all(parzystosc(n) == pentanacci(n) % 2 for n in range(100)))

Odpowiedź: k ← n mod 6; jeżeli k = 1 lub k = 2, to w ← 1, w przeciwnym razie w ← 0

↑
PythonC++23Java 25
Treść zadania

Zadanie 4. Ciągi binarne. Plik binarne.txt zawiera 500 napisów złożonych z zer i jedynek (każdy w osobnym wierszu), a długość każdego napisu jest podzielna przez 4. Odpowiedzi zapisz w pliku zadanie4.txt, poprzedzając każdą numerem zadania.

Napis jest dwucykliczny, jeśli składa się z dwóch powtórzeń tego samego napisu (np. 10001000 = 1000+1000; 00011000 i 10001001 nie są dwucykliczne). Podaj liczbę napisów dwucyklicznych w pliku, najdłuższy z nich oraz jego długość.

Python
licznik = 0
najdluzszy = ""

with open("binarne.txt") as file:
    for line in file:
        napis = line.strip()
        polowa = len(napis) // 2
        if napis[:polowa] == napis[polowa:]:
            licznik += 1
            if len(napis) > len(najdluzszy):
                najdluzszy = napis

print(licznik, najdluzszy, len(najdluzszy))

Odpowiedź: 18; 00100101100011100010010110001110; 32

↑
PythonC++23Java 25
Treść zadania

Napisy z pliku binarne.txt (500 napisów 0/1 o długościach podzielnych przez 4) traktujemy jako zapis BCD: każdy 4-znakowy segment koduje binarnie jedną cyfrę dziesiętną. Napis jest niepoprawny, jeśli któryś segment ma wartość większą niż 9 (np. 10010111 = 97 jest poprawny, a 11010000 i 1110 nie). Podaj liczbę niepoprawnych napisów oraz najmniejszą długość niepoprawnego napisu. Wynik dopisz do zadanie4.txt.

Python
licznik = 0
najkrotszy = None

with open("binarne.txt") as file:
    for line in file:
        napis = line.strip()
        poprawny = True
        for i in range(0, len(napis), 4):
            if int(napis[i:i + 4], 2) > 9:
                poprawny = False
        if not poprawny:
            licznik += 1
            if najkrotszy is None or len(napis) < najkrotszy:
                najkrotszy = len(napis)

print(licznik, najkrotszy)

Odpowiedź: 359; 4

↑
PythonC++23Java 25
Treść zadania

Napisy z pliku binarne.txt traktujemy jako liczby naturalne w zwykłym zapisie binarnym, pomijając liczby większe niż 65 535. Znajdź największą z pozostałych liczb i podaj ją w zapisie binarnym oraz dziesiętnym. Wynik dopisz do zadanie4.txt.

Przykład: dla napisów 1111000011110000, 11110000111100001000, 10100110 drugi jest pomijany, a odpowiedzią jest 1111000011110000, 61680.

Python
maks = 0

with open("binarne.txt") as file:
    for line in file:
        liczba = int(line.strip(), 2)
        if liczba <= 65535 and liczba > maks:
            maks = liczba

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

Odpowiedź: 1101011001100101, 54885

↑
PythonC++23Java 25

Zadanie na arkusz kalkulacyjny — rozwiązanie w Pythonie.

Treść zadania

Zadanie 5. Ogrzewanie. Sezon grzewczy trwa od 15.09.2015 do 31.03.2016. Rano 15.09.2015 pan Binarny ma 550 kg drewna; jedno ogrzewanie drewnem zużywa 26 kg. Dom jest ogrzewany dwa razy dziennie:

  • w dni robocze (pn–pt) rano gazem;
  • w soboty i niedziele rano drewnem, jeśli jest co najmniej 26 kg drewna, w przeciwnym razie gazem;
  • codziennie wieczorem drewnem, jeśli jest co najmniej 26 kg drewna, w przeciwnym razie gazem.

W każdy piątek rano sprawdzany jest zapas: jeśli jest mniejszy niż 100 kg, tego dnia przed wieczornym ogrzewaniem dostarczane jest 300 kg drewna. Odpowiedzi zapisz w pliku zadanie5.txt, poprzedzając je numerami zadań.

  • 5.1 — Podaj datę i porę dnia (rano/wieczór), kiedy po raz pierwszy po ogrzewaniu zapas drewna był niższy niż 100 kg.
  • 5.2 — Podaj, ile razy w sezonie dostarczono drewno oraz ile razy wieczorem dom ogrzewano drewnem, a ile gazem.
  • 5.4 — Podaj minimalną masę drewna dostarczanego w piątki (przy zapasie < 100 kg; dostawa to zawsze co najmniej 300 kg), przy której przez cały sezon dom zawsze da się ogrzać drewnem, gdy przewiduje to harmonogram.
Python
from datetime import date, timedelta


def sezon(dostawa):
    dzien = date(2015, 9, 15)
    drewno = 550
    pierwszy_raz = None
    dostawy = 0
    wieczory_drewno = 0
    wieczory_gaz = 0
    ogrzewania_gazem_zamiast_drewnem = 0
    while dzien <= date(2016, 3, 31):
        dzien_tygodnia = dzien.weekday()    # 0 - poniedzialek, 4 - piatek, 5 i 6 - weekend
        if dzien_tygodnia == 4 and drewno < 100:
            drewno += dostawa
            dostawy += 1
        # rano - w weekend drewno (jesli jest), w dni robocze gaz
        if dzien_tygodnia >= 5:
            if drewno >= 26:
                drewno -= 26
            else:
                ogrzewania_gazem_zamiast_drewnem += 1
            if drewno < 100 and pierwszy_raz is None:
                pierwszy_raz = (dzien, "rano")
        # wieczor - zawsze drewno (jesli jest)
        if drewno >= 26:
            drewno -= 26
            wieczory_drewno += 1
        else:
            wieczory_gaz += 1
            ogrzewania_gazem_zamiast_drewnem += 1
        if drewno < 100 and pierwszy_raz is None:
            pierwszy_raz = (dzien, "wieczor")
        dzien += timedelta(days=1)
    return pierwszy_raz, dostawy, wieczory_drewno, wieczory_gaz, ogrzewania_gazem_zamiast_drewnem


pierwszy_raz, dostawy, wieczory_drewno, wieczory_gaz, _ = sezon(300)
print("5.1", pierwszy_raz[0], pierwszy_raz[1])
print("5.2", dostawy, wieczory_drewno, wieczory_gaz)

masa = 300
while sezon(masa)[4] > 0:
    masa += 1
print("5.4", masa)

Odpowiedź: 5.1: 2015-09-28, wieczorem; 5.2: 18 dostaw, 167 wieczorów drewnem, 32 wieczory gazem; 5.4: 468 kg

↑
PythonC++23Java 25

Zadanie na arkusz kalkulacyjny — rozwiązanie w Pythonie.

Treść zadania

W symulacji ogrzewania z zadania 5 (sezon 15.09.2015–31.03.2016, początkowo 550 kg drewna, 26 kg na ogrzewanie, dostawy 300 kg w piątki przy zapasie < 100 kg) przedstaw na wykresie liniowym masę drewna wieczorem (po wieczornym ogrzewaniu) we wszystkich dniach sezonu. Zadbaj o czytelność wykresu.

Python
from datetime import date, timedelta

# dane do wykresu liniowego: data, masa drewna po wieczornym ogrzewaniu
dzien = date(2015, 9, 15)
drewno = 550

with open("wykres_5_3.txt", "w") as wynik:
    while dzien <= date(2016, 3, 31):
        if dzien.weekday() == 4 and drewno < 100:
            drewno += 300
        if dzien.weekday() >= 5 and drewno >= 26:
            drewno -= 26
        if drewno >= 26:
            drewno -= 26
        wynik.write(f"{dzien};{drewno}\n")
        dzien += timedelta(days=1)

Odpowiedź: wykres liniowy (oś X — data, oś Y — masa drewna wieczorem) tworzymy z pliku wykres_5_3.txt

↑

Edytuj na GitHubie