Matura informatyka

Matura 2019 — maj, poziom rozszerzony

PythonC++23Java 25
Treść zadania

Zadanie 1 (ulubione liczby). Małgosia lubi liczby nieparzyste, a Jaś parzyste. Na wspólnej kartce najpierw Małgosia zapisała kilka swoich liczb, a potem Jaś dopisał swoje (każde co najmniej jedną). Dane: n > 1 i tablica A[1..n] — najpierw same liczby nieparzyste, potem same parzyste. Wynik: w — pierwsza od lewej liczba parzysta w A.

Przykład: dla A = 5, 99, 3, 7, 111, 13, 4, 24, 4, 8 (n = 10) wynikiem jest w = 4.

  • 1.1 — napisz algorytm znajdujący pierwszą liczbę zapisaną przez Jasia. Maksymalną liczbę punktów daje algorytm o złożoności lepszej niż liniowa. Wolno używać tylko operacji arytmetycznych (w tym div i mod), porównań, instrukcji sterujących, przypisań i własnych funkcji.
  • 1.2 — podaj złożoność czasową swojego algorytmu (kwadratowa, liniowa, logarytmiczna lub inna).
Python
def pierwsza_parzysta(A):
    # wyszukiwanie binarne - złożoność logarytmiczna
    p = 0
    k = len(A) - 1
    while p < k:
        s = (p + k) // 2
        if A[s] % 2 == 1:
            p = s + 1
        else:
            k = s
    return A[p]


A = [5, 99, 3, 7, 111, 13, 4, 24, 4, 8]
print(pierwsza_parzysta(A))

Odpowiedź: dla przykładu w = 4; złożoność logarytmiczna (wyszukiwanie binarne)

↑
PythonC++23Java 25
Treść zadania

Zadanie 2 (analiza algorytmu). Dane: napis s, liczba całkowita n nie mniejsza niż długość s oraz k z zakresu [2..10]. dł(x) to długość napisu, + łączy napisy, napis(p) to zapis dziesiętny liczby p.

Kod
funkcja pisz(s, n, k)
    jeżeli dł(s) = n
        wypisz s
    w przeciwnym razie
        dla i = 0, 1, …, k-1 wykonuj
            pisz(s + napis(i), n, k)
  • 2.1 — uzupełnij drzewo wywołań funkcji dla pisz("", 2, 2) (korzeń ma dzieci pisz("0",2,2) i pisz("1",2,2)) i ponumeruj węzły w kolejności wywołań (pierwsze wywołanie ma numer 1).
  • 2.2 — dla wywołań pisz("", 3, 2) i pisz("", 2, 3) podaj wypisane napisy oraz łączną liczbę wywołań funkcji.
  • 2.3 — podaj wzór na łączną liczbę wywołań funkcji pisz po wywołaniu pisz("", n, k).
Python
wywolania = 0


def pisz(s, n, k):
    global wywolania
    wywolania += 1
    if len(s) == n:
        print(s)
    else:
        for i in range(k):
            pisz(s + str(i), n, k)


for n, k in [(2, 2), (3, 2), (2, 3)]:
    wywolania = 0
    print(f'pisz("", {n}, {k}):')
    pisz("", n, k)
    # 2.3 - wzór: 1 + k + k^2 + ... + k^n = (k^(n+1) - 1) / (k - 1)
    print("liczba wywołań:", wywolania, "wzór:", (k ** (n + 1) - 1) // (k - 1))

Odpowiedź: 2.1: pisz("10",2,2), pisz("11",2,2) (kolejność wywołań 1, 2, 3, 4, 5, 6, 7 – w głąb); 2.2: pisz("",3,2) wypisuje 000 001 010 011 100 101 110 111, 15 wywołań; pisz("",2,3) wypisuje 00 01 02 10 11 12 20 21 22, 13 wywołań; 2.3: (k^(n+1) − 1)/(k − 1)

↑
PythonC++23Java 25
Treść zadania

Zadanie 4 (liczby). Plik liczby.txt zawiera 500 liczb całkowitych z zakresu [1, 100 000], po jednej w wierszu. Odpowiedzi zapisz w pliku wyniki4.txt, poprzedzając je numerem zadania (dane przykładowe: przyklad.txt).

Podaj, ile liczb z pliku jest potęgami liczby 3 (1, 3, 9, 27, …).

Dla pliku przykładowego odpowiedź wynosi 2.

Python
potegi_trojki = []
potega = 1
while potega <= 100000:
    potegi_trojki.append(potega)
    potega *= 3

ile = 0

with open("liczby.txt") as file:
    for line in file:
        if int(line) in potegi_trojki:
            ile += 1

print(ile)

Odpowiedź: 18

↑
PythonC++23Java 25
Treść zadania

Dane z pliku liczby.txt (500 liczb z zakresu [1, 100 000]).

Silnia: k! = 1·2·…·k, przy czym 0! = 1. Dla liczby można obliczyć sumę silni jej cyfr, np. dla 343: 3! + 4! + 3! = 36. Wypisz, w kolejności z pliku, wszystkie liczby równe sumie silni swoich cyfr.

W pliku przykładowym jest jedna taka liczba: 145 (1! + 4! + 5! = 145).

Python
from math import factorial

with open("liczby.txt") as file:
    for line in file:
        liczba = line.strip()
        suma = 0
        for cyfra in liczba:
            suma += factorial(int(cyfra))
        if suma == int(liczba):
            print(liczba)

Odpowiedź: 145, 1, 40585, 2

↑
PythonC++23Java 25
Treść zadania

Dane z pliku liczby.txt (500 liczb z zakresu [1, 100 000]).

Znajdź najdłuższy spójny fragment ciągu liczb, których największy wspólny dzielnik jest większy od 1 (jest dokładnie jeden taki fragment). Podaj pierwszą liczbę fragmentu, jego długość i NWD wszystkich jego liczb. Można korzystać z NWD(a, b, c) = NWD(NWD(a, b), c).

Przykłady: dla 3, 7, 4, 6, 10, 2, 5 odpowiedź to 4, 4, 2; dla 5, 70, 28, 42, 98, 1 — 70, 4, 14. Dla pliku przykładowego: 90, 5, 10.

Python
from math import gcd

with open("liczby.txt") as file:
    liczby = [int(line) for line in file]

najdluzszy = 0

for i in range(len(liczby)):
    nwd = liczby[i]
    j = i
    # rozszerzamy ciąg zaczynający się od i, dopóki NWD wszystkich liczb jest większy od 1
    while j + 1 < len(liczby) and gcd(nwd, liczby[j + 1]) > 1:
        j += 1
        nwd = gcd(nwd, liczby[j])
    if j - i + 1 > najdluzszy:
        najdluzszy = j - i + 1
        pierwsza = liczby[i]
        dzielnik = nwd

print(pierwsza, najdluzszy, dzielnik)

Odpowiedź: pierwsza liczba 31968, długość ciągu 150, dzielnik 74

↑
↑
PythonC++23Java 25

Zadanie na arkusz kalkulacyjny — rozwiązanie w Pythonie.

Treść zadania

Zadanie 5 (chmury). Plik pogoda.txt zawiera dane z 500 kolejnych dni pomiarów na odległej planecie, rozdzielone średnikami, z wierszem nagłówkowym: numer dnia (1–500), temperatura (z jednym miejscem po przecinku, nieujemna), opad w mm (całkowity), kategoria chmur (C — cirrusy, S — stratusy, 0 — brak chmur) i wielkość chmur (1–5, 0 gdy bezchmurnie). Każdego dnia występuje tylko jeden rodzaj chmur. Od dnia 301 kamera była zepsuta i wszystkie dni raportowano jako bezchmurne (temperatura i opad są nadal poprawne). Odpowiedzi zapisz w pliku wyniki5.txt, poprzedzając je numerem zadania.

Podaj liczbę dni z temperaturą co najmniej 20 stopni i jednocześnie opadem nie większym niż 5 mm.

Python
ile = 0

with open("pogoda.txt") as file:
    file.readline()  # nagłówek
    for line in file:
        dzien, temperatura, opad, kategoria, wielkosc = line.strip().split(";")
        temperatura = float(temperatura.replace(",", "."))
        if temperatura >= 20 and int(opad) <= 5:
            ile += 1

print(ile)

Odpowiedź: 63

↑
PythonC++23Java 25

Zadanie na arkusz kalkulacyjny — rozwiązanie w Pythonie.

Treść zadania

Dane z pliku pogoda.txt (500 dni: temperatura, opad, kategoria i wielkość chmur).

Znajdź najdłuższy ciąg kolejnych dni, w którym temperatura każdego dnia jest wyższa niż dnia poprzedniego (jest jeden taki ciąg). Podaj numer pierwszego i ostatniego dnia ciągu.

Przykład: dla temperatur dni 34–39: 3,7; 3,4; 3,5; 3,6; 3,7; 3,5 ciąg zaczyna się w dniu 36 i kończy w dniu 38.

Python
with open("pogoda.txt") as file:
    file.readline()
    temperatury = []
    for line in file:
        temperatury.append(float(line.split(";")[1].replace(",", ".")))

najdluzszy = 0
dlugosc = 0  # liczba kolejnych dni cieplejszych od dnia poprzedniego

for i in range(1, len(temperatury)):
    if temperatury[i] > temperatury[i - 1]:
        dlugosc += 1
    else:
        dlugosc = 0
    if dlugosc > najdluzszy:
        najdluzszy = dlugosc
        koniec = i + 1  # dni numerujemy od 1

print(koniec - najdluzszy + 1, koniec)

Odpowiedź: od dnia 448 do dnia 455

↑
PythonC++23Java 25

Zadanie na arkusz kalkulacyjny — rozwiązanie w Pythonie.

Treść zadania

Dane z pliku pogoda.txt (500 dni: temperatura, opad, kategoria i wielkość chmur).

Dla pierwszych 300 dni oblicz z dokładnością do dwóch miejsc po przecinku średni opad dla każdego rodzaju chmur (C1–C5, S1–S5) i przedstaw wyniki na czytelnie opisanym wykresie kolumnowym.

Python
suma = {}
ile = {}

with open("pogoda.txt") as file:
    file.readline()
    for line in file:
        dzien, temperatura, opad, kategoria, wielkosc = line.strip().split(";")
        if int(dzien) <= 300 and kategoria != "0":
            rodzaj = kategoria + wielkosc
            suma[rodzaj] = suma.get(rodzaj, 0) + int(opad)
            ile[rodzaj] = ile.get(rodzaj, 0) + 1

for rodzaj in sorted(suma):
    print(rodzaj, round(suma[rodzaj] / ile[rodzaj], 2))
# na podstawie zestawienia należy jeszcze wykonać wykres kolumnowy

Odpowiedź: C1 3,45; C2 7,28; C3 9,05; C4 11,58; C5 19,40; S1 3,73; S2 6,52; S3 10,29; S4 15,00; S5 19,64 (+ wykres kolumnowy)

↑
PythonC++23Java 25

Zadanie na arkusz kalkulacyjny — rozwiązanie w Pythonie.

Treść zadania

Dane z pliku pogoda.txt (500 dni). Teoria prof. Nubisa:

  • po dniu bezchmurnym następnego dnia pojawiają się chmury wielkości 1;
  • chmury po trzech dniach przechodzą w wielkość o 1 większą (najwyżej do 5);
  • chmury wielkości 5 znikają, gdy danego dnia spadnie co najmniej 20 mm deszczu — następny dzień jest wtedy bezchmurny;
  • kategoria powstających chmur zależy od temperatury w dniu ich pojawienia się: co najmniej 10 stopni — C, w przeciwnym razie — S.

Przyjmij, że chmury przez wszystkie 500 dni rozwijają się według teorii, a dzień 1 jest bezchmurny (przez pierwsze 20 dni teoria zgadza się z obserwacjami). Podaj:

  • a) liczbę dni z chmurami wielkości 0, 1, 2, 3, 4 i 5 (osobno dla każdej wielkości; opady jak w pliku),
  • b) w ilu z pierwszych 300 dni wielkość chmur według teorii zgadza się z odczytem kamery,
  • c) w ilu z pierwszych 300 dni kategoria chmur według teorii zgadza się z odczytem kamery.
Python
with open("pogoda.txt") as file:
    file.readline()
    dane = [line.strip().split(";") for line in file]

wielkosc = 0      # dzień pierwszy jest bezchmurny
kategoria = "0"
dni_tej_wielkosci = 1

ile_wielkosci = [0] * 6
zgodne_wielkosci = 0
zgodne_kategorie = 0

for i in range(len(dane)):
    dzien, temperatura, opad, kat_kamera, wlk_kamera = dane[i]
    temperatura = float(temperatura.replace(",", "."))

    if i > 0:
        poprzedni_opad = int(dane[i - 1][2])
        if wielkosc == 0:
            # pojawiają się chmury wielkości 1, kategoria zależy od temperatury w dniu ich powstania
            wielkosc = 1
            kategoria = "C" if temperatura >= 10 else "S"
            dni_tej_wielkosci = 1
        elif wielkosc == 5:
            if poprzedni_opad >= 20:
                wielkosc = 0
                kategoria = "0"
        elif dni_tej_wielkosci == 3:
            wielkosc += 1
            dni_tej_wielkosci = 1
        else:
            dni_tej_wielkosci += 1

    ile_wielkosci[wielkosc] += 1
    if int(dzien) <= 300:
        if int(wlk_kamera) == wielkosc:
            zgodne_wielkosci += 1
        if kat_kamera == kategoria:
            zgodne_kategorie += 1

print("a)")
for w in range(6):
    print(w, ile_wielkosci[w])
print("b)", zgodne_wielkosci)
print("c)", zgodne_kategorie)

Odpowiedź: a) 0: 34, 1: 102, 2: 102, 3: 102, 4: 100, 5: 60; b) 296; c) 286

↑

Edytuj na GitHubie