Matura informatyka

Matura 2018 — maj, poziom rozszerzony

PythonC++23Java 25
Treść zadania

Zadanie 1 (analiza algorytmu). Dla liczby całkowitej dodatniej n algorytm wyznacza liczbę całkowitą dodatnią p (div oznacza dzielenie całkowite):

Kod
p ← 1
q ← n
dopóki p < q wykonuj
    s ← (p + q) div 2
    (*) jeżeli s*s*s < n
            p ← s + 1
        w przeciwnym wypadku
            q ← s
  • 1.1 — podaj wynik p dla n = 28, 64 i 80.
  • 1.2 — podaj najmniejszą i największą liczbę n, dla której wynikiem algorytmu jest p = 10.
Python
def algorytm(n):
    p = 1
    q = n
    while p < q:
        s = (p + q) // 2
        if s * s * s < n:
            p = s + 1
        else:
            q = s
    return p


# 1.1
for n in [28, 64, 80]:
    print(n, algorytm(n))

# 1.2 - najmniejsze i największe n, dla którego p = 10
liczby = [n for n in range(1, 2000) if algorytm(n) == 10]
print(min(liczby), max(liczby))

Odpowiedź: 1.1: 28 → 4, 64 → 4, 80 → 5; 1.2: najmniejsza 730, największa 1000

↑
PythonC++23Java 25
Treść zadania

Zadanie 2 (krajobraz). W paśmie górskim jest n szczytów — punktów o współrzędnych (X[i], Y[i]) z tablic X[1..n] (liczby całkowite) i Y[1..n] (liczby całkowite dodatnie). Obserwator stoi w punkcie (0,0). Szczyt A jest widoczny na lewo od B, gdy xA/yA < xB/yB; żadne dwa szczyty nie leżą w jednej linii z obserwatorem.

Napisz algorytm, który poda współrzędne x, y skrajnie lewego szczytu, czyli widocznego na lewo od wszystkich pozostałych.

Python
def skrajnie_lewy(n, X, Y):
    k = 0
    for i in range(1, n):
        if X[i] / Y[i] < X[k] / Y[k]:
            k = i
    return X[k], Y[k]


X = [3, -2, 5, -4]
Y = [4, 3, 2, 1]
print(skrajnie_lewy(len(X), X, Y))

Odpowiedź: przykładowy algorytm – szukamy szczytu o najmniejszym ilorazie X[i]/Y[i] (dla przykładu w kodzie: (-4, 1))

↑
PythonC++23Java 25
Treść zadania

Dane jak w zadaniu 2.1: tablice X[1..n], Y[1..n] ze współrzędnymi szczytów (Y[i] > 0), żadne dwa nie leżą w jednej linii z obserwatorem w (0,0).

Napisz algorytm, który przestawi elementy tablic X i Y tak, aby szczyty były uporządkowane w kolejności widzenia ich przez obserwatora od lewej do prawej (rosnąco względem X[i]/Y[i]). Złożoność co najwyżej kwadratowa; wolno używać tylko instrukcji sterujących, operatorów arytmetycznych i logicznych, porównań i przypisań — bez funkcji bibliotecznych (np. gotowego sortowania).

Python
def sortuj_szczyty(n, X, Y):
    # sortowanie przez wybór - złożoność kwadratowa
    for i in range(n - 1):
        m = i
        for j in range(i + 1, n):
            if X[j] / Y[j] < X[m] / Y[m]:
                m = j
        X[i], X[m] = X[m], X[i]
        Y[i], Y[m] = Y[m], Y[i]


X = [3, -2, 5, -4]
Y = [4, 3, 2, 1]
sortuj_szczyty(len(X), X, Y)
print(X)
print(Y)

Odpowiedź: przykładowy algorytm – sortowanie (np. przez wybór) względem X[i]/Y[i], zamieniając jednocześnie elementy X i Y

↑
PythonC++23Java 25
Treść zadania

Zadanie 4 (sygnały). Plik sygnaly.txt zawiera 1000 wierszy, w każdym jedno niepuste słowo z wielkich liter alfabetu angielskiego o długości co najwyżej 100. Odpowiedzi zapisz w pliku wyniki4.txt, poprzedzając każdą numerem zadania (dane przykładowe: przyklad.txt).

Złącz dziesiąte litery co czterdziestego słowa, zaczynając od słowa 40. (każde takie słowo ma co najmniej 10 znaków), i wypisz otrzymane przesłanie.

Dla pliku przykładowego wynikiem jest NIECHCIMATURAPROSTABEDZIE.

Python
przeslanie = ""

with open("sygnaly.txt") as file:
    slowa = file.read().split()

for i in range(39, len(slowa), 40):
    przeslanie += slowa[i][9]

print(przeslanie)

Odpowiedź: ZAPISZODPOWIEDZIWPLIKUTXT

↑
PythonC++23Java 25
Treść zadania

Dane z pliku sygnaly.txt (1000 słów z wielkich liter).

Znajdź słowo zawierające największą liczbę różnych liter i wypisz je wraz z tą liczbą. Jeśli takich słów jest kilka, wypisz pierwsze z nich w pliku.

Dla pliku przykładowego: AKLMNOPRSTWZA 12.

Python
with open("sygnaly.txt") as file:
    slowa = file.read().split()

maks = 0
najlepsze = ""

for slowo in slowa:
    rozne = len(set(slowo))
    if rozne > maks:
        maks = rozne
        najlepsze = slowo

print(najlepsze, maks)

Odpowiedź: SUOLDQWISCDRFLRWHZBNTMIAPHALMNCWHVGMXOZSQNXWXSFELZVTUTILXWKCTYBQYSUAKNYJKRXDJQYHXAQGWN 26

↑
PythonC++23Java 25
Treść zadania

Dane z pliku sygnaly.txt (1000 słów z wielkich liter).

Odległość liter to różnica ich pozycji w alfabecie (np. A–B: 1, A–E: 4, litera od siebie: 0). Wypisz, po jednym w wierszu i w kolejności z pliku, wszystkie słowa, w których każde dwie litery są od siebie oddalone co najwyżej o 10.

Przykład: CGECF spełnia warunek, a ABEZA nie (odległość A–Z wynosi 25).

Python
with open("sygnaly.txt") as file:
    slowa = file.read().split()

for slowo in slowa:
    # każde dwie litery są oddalone co najwyżej o 10 <=> największa i najmniejsza litera są oddalone co najwyżej o 10
    if ord(max(slowo)) - ord(min(slowo)) <= 10:
        print(slowo)

Odpowiedź: QQMLKKQNOHPKKPJOLHIPJKLKQIIHQHPNKNQPHNKLKQNIMLQPNLPMHNNIPNJJONQOHKKQOIHOHHJMOJPMNIPIKION, PTPNTOLNOPOSKLQOQKNTQTPLPNLNRRSTNNSMRNNMLPNLKORTSMNKRTLLLLNRKKOLKTRQOQOQONKTKRSPTTORMKQTRNOKKQ, … (lista słów w kluczu odpowiedzi)

↑
↑
PythonC++23Java 25

Zadanie na arkusz kalkulacyjny — rozwiązanie w Pythonie.

Treść zadania

Zadanie 5 (zbiornik). Plik woda.txt zawiera 3653 wiersze z danymi o dobowym dopływie wody z rzeki Wirki do zbiornika retencyjnego w latach 2008–2017. W wierszu: data (rrrr-mm-dd) i liczba m³ wody, która dopłynęła w ciągu doby, oddzielone tabulatorem (np. 2008-01-01 2275). Odpowiedzi zapisz w pliku wyniki5.txt, poprzedzając je numerem zadania.

Podaj rok, w którym do zbiornika dopłynęło łącznie najwięcej wody.

Python
suma_rok = {}

with open("woda.txt") as file:
    for line in file:
        data, doplyw = line.split()
        rok = data[:4]
        suma_rok[rok] = suma_rok.get(rok, 0) + int(doplyw)

najlepszy = max(suma_rok, key=suma_rok.get)
print(najlepszy, suma_rok[najlepszy])

Odpowiedź: 2015

↑
PythonC++23Java 25

Zadanie na arkusz kalkulacyjny — rozwiązanie w Pythonie.

Treść zadania

Dane z pliku woda.txt (data i dobowy dopływ wody w m³, lata 2008–2017).

Znajdź najdłuższy okres (w dniach), w którym każdego dnia dopływało co najmniej 10 000 m³ wody (jest dokładnie jeden taki okres). Podaj jego datę początkową i końcową.

Python
with open("woda.txt") as file:
    dane = [line.split() for line in file]

najdluzszy = 0
dlugosc = 0
poczatek = ""

for i in range(len(dane)):
    data, doplyw = dane[i][0], int(dane[i][1])
    if doplyw >= 10000:
        if dlugosc == 0:
            start = data
        dlugosc += 1
        if dlugosc > najdluzszy:
            najdluzszy = dlugosc
            poczatek = start
            koniec = data
    else:
        dlugosc = 0

print(najdluzszy, poczatek, koniec)

Odpowiedź: od 2015-03-17 do 2015-05-10

↑
PythonC++23Java 25

Zadanie na arkusz kalkulacyjny — rozwiązanie w Pythonie.

Treść zadania

Dane z pliku woda.txt (data i dobowy dopływ wody w m³, lata 2008–2017).

Zestaw łączne dopływy wody w poszczególnych miesiącach 2008 roku (od stycznia do grudnia) i na tej podstawie wykonaj wykres kolumnowy z tytułem i opisami osi.

Python
miesiace = {}

with open("woda.txt") as file:
    for line in file:
        data, doplyw = line.split()
        if data.startswith("2008"):
            miesiac = data[:7]
            miesiace[miesiac] = miesiace.get(miesiac, 0) + int(doplyw)

for miesiac in sorted(miesiace):
    print(miesiac, miesiace[miesiac])
# na podstawie zestawienia należy jeszcze wykonać wykres kolumnowy

Odpowiedź: 2008-01 95433, 2008-02 94730, 2008-03 109439, 2008-04 632931, 2008-05 329203, 2008-06 85628, 2008-07 166597, 2008-08 139747, 2008-09 282342, 2008-10 170729, 2008-11 222440, 2008-12 172072 (+ wykres kolumnowy)

↑
PythonC++23Java 25

Zadanie na arkusz kalkulacyjny — rozwiązanie w Pythonie.

Treść zadania

Dane z pliku woda.txt (data i dobowy dopływ wody w m³, lata 2008–2017). Cykl pracy zbiornika:

  1. Zaraz po północy mierzy się objętość wody w zbiorniku.
  2. Jeśli pomiar przekracza 1 000 000 m³ (przepełnienie), od razu wypuszcza się cały nadmiar ponad 1 000 000 m³.
  3. Codziennie o 8 rano wypuszcza się 2% objętości wykazanej przez nocny pomiar (zaokrąglone w górę do pełnych m³).
  4. W ciągu doby do zbiornika dopływa woda z rzeki zgodnie z danymi.

Pomiar 2008-01-01 wskazał 500 000 m³ (kontrolnie: pomiar 2008-02-01 wskazał 338 406 m³). Podaj:

  • a) dzień, w którym pierwszy raz wypuszczono nadmiar wody po przepełnieniu,
  • b) w ilu dniach okresu 2008-01-01 – 2017-12-31 pomiar wykazał co najmniej 800 000 m³,
  • c) największą objętość wody w momencie pomiaru w tym okresie, gdyby zrezygnować z wypuszczania nadmiaru (zbiornik o nieograniczonej pojemności; 2% nadal wypuszczane).
Python
import math

with open("woda.txt") as file:
    dane = [line.split() for line in file]


def symulacja(z_wypuszczaniem):
    woda = 500000
    pierwsze_przepelnienie = None
    dni_800 = 0
    maks = 0
    for data, doplyw in dane:
        pomiar = woda  # pomiar zaraz po północy
        maks = max(maks, pomiar)
        if pomiar >= 800000:
            dni_800 += 1
        if z_wypuszczaniem and woda > 1000000:
            if pierwsze_przepelnienie is None:
                pierwsze_przepelnienie = data
            woda = 1000000
        woda -= math.ceil(pomiar * 2 / 100)  # o 8 rano wypuszczamy 2% wody z pomiaru
        woda += int(doplyw)
    return pierwsze_przepelnienie, dni_800, maks


a, b, _ = symulacja(True)
_, _, c = symulacja(False)
print("a)", a)
print("b)", b)
print("c)", c)

Odpowiedź: a) 2015-04-19, b) 188 dni, c) 1 399 242 m3

↑

Edytuj na GitHubie