Matura informatyka

Matura 2015 — maj, poziom rozszerzony

PythonC++23Java 25
Treść zadania

Problem telewidza. Program telewizyjny to lista filmów emitowanych jednego dnia w różnych stacjach. Telewidz chce obejrzeć w całości jak najwięcej filmów, ale może oglądać tylko jeden film naraz (zmiana stacji nie zajmuje czasu, więc film kończący się o 12:00 nie koliduje z filmem zaczynającym się o 12:00). Przykładowy program:

  • TV1: film 1 od 9:00 do 12:00, film 2 od 15:00 do 17:00,
  • TV2: film 3 od 11:00 do 16:00,
  • TV3: film 4 od 12:00 do 14:00,
  • TV4: film 5 od 11:30 do 12:30.

Algorytm (dane: zbiór filmów T i strategia S; wynik: zbiór P filmów do obejrzenia): dopóki T nie jest pusty, wybierz z T film x według strategii S, przenieś go do P i usuń z T wszystkie filmy kolidujące z x.

  • Strategia A — najdłuższy film (remis: kończący się najwcześniej),
  • Strategia B — najkrótszy film (remis: kończący się najwcześniej),
  • Strategia C — film zaczynający się najwcześniej (remis: kończący się najwcześniej),
  • Strategia D — film kończący się najwcześniej (remis: zaczynający się najpóźniej).

Dla podanego programu strategia A daje P = {film 3}.

  • 1.1 — Podaj zawartość zbioru P po wykonaniu algorytmu dla powyższego programu przy strategiach B, C i D.
  • 1.2 — Strategia jest optymalna, jeśli dla każdego programu daje największą możliwą liczbę filmów. Dla każdej ze strategii A, B i C podaj kontrprzykład: program z czterema filmami w dwóch stacjach (godziny emisji i czasy trwania), wynik algorytmu dla tej strategii oraz liczniejszy zbiór filmów, które telewidz może obejrzeć.
Python
def minuty(godzina):
    h, m = godzina.split(":")
    return int(h) * 60 + int(m)


strategie = {
    "A": lambda f: (-(f[2] - f[1]), f[2]),  # najdłuższy, potem najwcześniej się kończy
    "B": lambda f: (f[2] - f[1], f[2]),     # najkrótszy, potem najwcześniej się kończy
    "C": lambda f: (f[1], f[2]),            # najwcześniej się zaczyna, potem najwcześniej się kończy
    "D": lambda f: (f[2], -f[1]),           # najwcześniej się kończy, potem najpóźniej się zaczyna
}


def telewidz(program, strategia):
    T = [(nazwa, minuty(od), minuty(do)) for nazwa, od, do in program]
    P = []
    while T:
        x = min(T, key=strategie[strategia])
        T.remove(x)
        P.append(x[0])
        # usuwamy filmy kolidujące z x (koniec jednego = początek drugiego to nie kolizja)
        T = [f for f in T if f[2] <= x[1] or f[1] >= x[2]]
    return P


# 1.1 - program z treści zadania
program = [
    ("film 1", "9:00", "12:00"),
    ("film 2", "15:00", "17:00"),
    ("film 3", "11:00", "16:00"),
    ("film 4", "12:00", "14:00"),
    ("film 5", "11:30", "12:30"),
]
for s in "ABCD":
    print(s, telewidz(program, s))

# 1.2 - kontrprzykłady (strategia D jest optymalna, więc służy jako wzorzec)
kontrprzyklady = {
    "A": [("film 1", "10:00", "12:00"), ("film 2", "12:00", "14:00"),
          ("film 3", "10:00", "11:00"), ("film 4", "11:00", "12:00")],
    "B": [("film 1", "11:30", "12:30"), ("film 2", "15:00", "16:00"),
          ("film 3", "10:00", "12:00"), ("film 4", "12:00", "14:00")],
    "C": [("film 1", "9:00", "14:00"), ("film 2", "15:00", "16:00"),
          ("film 3", "10:00", "12:00"), ("film 4", "12:00", "14:00")],
}
for s in kontrprzyklady:
    print(s, telewidz(kontrprzyklady[s], s), "optymalnie:", telewidz(kontrprzyklady[s], "D"))

Odpowiedź: 1.1: B: {film 5, film 2}, C: {film 1, film 4, film 2}, D: {film 1, film 4, film 2}. 1.2: np. A: {film 1, film 2} zamiast {film 3, film 4, film 2} (programy jak w kodzie).

↑
PythonC++23Java 25
Treść zadania

Rozszerzony algorytm Euklidesa. Dla liczb całkowitych a > 0 i b ≥ 0 należy wyznaczyć liczby całkowite x, y takie, że NWD(a, b) = a·x + b·y. Jeśli b ≠ 0 i dla pary (b, a mod b) znamy x', y' spełniające NWD(b, a mod b) = b·x' + (a mod b)·y', to x = y', y = x' − (a div b)·y'. Dla b = 0 wynikiem jest para (1, 0). Przykład: NWD(231, 30) = 3 = 3·231 + (−23)·30.

  • 3.1 — Uzupełnij tabelę kolejnych wywołań funkcji RozszerzonyEuklides(a, b) dla a = 188, b = 12: dla każdego wywołania podaj wartości a i b oraz zwrócone x i y.
  • 3.2 — Uzupełnij rekurencyjną funkcję:
Kod
RozszerzonyEuklides(a, b):
  Krok 1. Jeśli b = 0, zwróć (1, 0) i zakończ.
  Krok 2. r ← a mod b
  Krok 3. (x, y) ← RozszerzonyEuklides(____, ____)
  Krok 4. Zwróć parę (____, ____).
Python
def rozszerzony_euklides(a, b, poziom=1):
    if b == 0:
        print(poziom, a, b, 1, 0)
        return 1, 0
    r = a % b
    x, y = rozszerzony_euklides(b, r, poziom + 1)  # krok 3: (b, r)
    x, y = y, x - (a // b) * y                     # krok 4: (y', x' - (a div b) * y')
    print(poziom, a, b, x, y)
    return x, y


# 3.1 - tabela dla a = 188, b = 12 (wiersze wypisywane przy powrocie z rekurencji)
x, y = rozszerzony_euklides(188, 12)
print("NWD =", 188 * x + 12 * y)

Odpowiedź: 3.1: (188, 12, -1, 16), (12, 8, 1, -1), (8, 4, 0, 1), (4, 0, 1, 0). 3.2: krok 3: (b, r), krok 4: (y', x' - (a div b) · y').

↑
PythonC++23Java 25
Treść zadania

W pliku liczby.txt znajduje się 1000 liczb naturalnych zapisanych binarnie, każda w osobnym wierszu. Liczba ma co najwyżej 250 cyfr, więc może nie mieścić się w typie całkowitym (np. int). Odpowiedzi zapisz w pliku wynik4.txt, poprzedzając każdą numerem zadania.

Podaj, ile liczb z pliku ma w zapisie binarnym więcej zer niż jedynek.

Przykład: dla liczb 101011010011001100111, 10001001, 1000000, 101010011100, 100010 odpowiedzią jest 3.

Python
wynik = 0

with open("liczby.txt") as file:
    for line in file:
        liczba = line.strip()
        if liczba.count("0") > liczba.count("1"):
            wynik += 1

print(wynik)

Odpowiedź: 422

↑
PythonC++23Java 25
Treść zadania

Plik liczby.txt zawiera 1000 liczb binarnych (do 250 cyfr). Podaj, ile liczb z pliku jest podzielnych przez 2, a ile przez 8. Odpowiedź zapisz w wynik4.txt.

Przykład: dla liczb 101011010011001100000, 10001001, 100100, 101010010101011011000, 100011 trzy liczby są podzielne przez 2, a dwie przez 8.

Python
przez_dwa = przez_osiem = 0

with open("liczby.txt") as file:
    for line in file:
        liczba = line.strip()
        # liczba binarna jest podzielna przez 2, gdy kończy się na 0, a przez 8 - gdy kończy się na 000
        if liczba[-1] == "0":
            przez_dwa += 1
        if liczba[-3:] == "000":
            przez_osiem += 1

print(przez_dwa, przez_osiem)

Odpowiedź: 500 liczb podzielnych przez 2, 123 liczby podzielne przez 8

↑
PythonC++23Java 25
Treść zadania

Plik liczby.txt zawiera 1000 liczb binarnych (do 250 cyfr). Znajdź najmniejszą i największą liczbę w pliku i podaj numery wierszy, w których się znajdują (najpierw najmniejszej, potem największej). Odpowiedź zapisz w wynik4.txt.

Przykład: dla liczb 101011010011001100111, 10001001011101010, 1001000, 101010011100, 1000110 odpowiedzią jest 5, 1.

Python
lista = []

with open("liczby.txt") as file:
    for line in file:
        lista.append(int(line.strip(), 2))

# numer wiersza najmniejszej i największej liczby
print(lista.index(min(lista)) + 1, lista.index(max(lista)) + 1)

Odpowiedź: 859 (najmniejsza), 925 (największa)

↑
PythonC++23Java 25

Zadanie na arkusz kalkulacyjny — rozwiązanie w Pythonie.

Treść zadania

Plik kraina.txt zawiera dane demograficzne 50 województw Edulandii. Każde należy do jednego z regionów A, B, C, D. Wiersz zawiera dane rozdzielone średnikami: nazwa województwa, liczba kobiet w 2013, liczba mężczyzn w 2013, liczba kobiet w 2014, liczba mężczyzn w 2014 (np. w01D;1415007;1397195;1499070;1481105). Nazwa ma postać „w”, dwucyfrowy numer i litera regionu. Odpowiedzi zapisz w pliku wynik5.txt, poprzedzając je numerem zadania.

Wyznacz ludność (kobiety + mężczyźni) każdego z regionów A, B, C i D w roku 2013 i sporządź czytelny wykres kolumnowy porównujący te wartości.

Python
ludnosc = {"A": 0, "B": 0, "C": 0, "D": 0}

with open("kraina.txt") as file:
    for line in file:
        nazwa, k13, m13, k14, m14 = line.strip().split(";")
        region = nazwa[-1]
        ludnosc[region] += int(k13) + int(m13)

for region in ludnosc:
    print(region, ludnosc[region])

Odpowiedź: A: 33 929 579, B: 41 736 619, C: 57 649 017, D: 36 530 387 (+ wykres kolumnowy)

↑
PythonC++23Java 25

Zadanie na arkusz kalkulacyjny — rozwiązanie w Pythonie.

Treść zadania

Dane z pliku kraina.txt (województwo; kobiety 2013; mężczyźni 2013; kobiety 2014; mężczyźni 2014). Wybierz województwa, w których w 2014 roku zarówno liczba kobiet, jak i liczba mężczyzn była większa niż w 2013. Podaj liczbę takich województw w całym kraju oraz osobno w każdym regionie A, B, C i D.

Python
regiony = {"A": 0, "B": 0, "C": 0, "D": 0}

with open("kraina.txt") as file:
    for line in file:
        nazwa, k13, m13, k14, m14 = line.strip().split(";")
        if int(k14) > int(k13) and int(m14) > int(m13):
            regiony[nazwa[-1]] += 1

print(sum(regiony.values()))
for region in regiony:
    print(region, regiony[region])

Odpowiedź: 19 województw, w tym A: 3, B: 4, C: 8, D: 4

↑
PythonC++23Java 25

Zadanie na arkusz kalkulacyjny — rozwiązanie w Pythonie.

Treść zadania

Dane z pliku kraina.txt. Tempo wzrostu województwa to iloraz ludność(2014) / ludność(2013) zaokrąglony w dół do 4 miejsc po przecinku. Dla r > 2014: ludność(r) = ludność(r − 1) · tempo, zaokrąglone w dół do liczby całkowitej. Jeśli w danym roku ludność województwa jest ponad dwukrotnie większa niż w 2013, występuje przeludnienie i od następnego roku ludność tego województwa już się nie zmienia.

Przykład: dla w01D ludność 2013 = 2 812 202, 2014 = 2 980 175, tempo = 1,0597, ludność 2015 = 3 158 091; w 2025 roku wyniesie 5 639 669 (przeludnienie).

Podaj:

  • łączną liczbę mieszkańców Edulandii w 2025 roku oraz województwo, które będzie miało wtedy najwięcej mieszkańców,
  • liczbę województw, w których w latach 2014–2025 włącznie wystąpi efekt przeludnienia.
Python
suma_2025 = 0
najwiecej = 0
najwieksze = ""
przeludnione = 0

with open("kraina.txt") as file:
    for line in file:
        nazwa, k13, m13, k14, m14 = line.strip().split(";")
        l2013 = int(k13) + int(m13)
        l2014 = int(k14) + int(m14)
        # tempo zaokrąglone w dół do 4 miejsc - liczymy w dziesięciotysięcznych, żeby uniknąć błędów float
        tempo = l2014 * 10000 // l2013

        ludnosc = l2014
        przeludnienie = ludnosc > 2 * l2013
        for rok in range(2015, 2026):
            if not przeludnienie:
                ludnosc = ludnosc * tempo // 10000
                if ludnosc > 2 * l2013:
                    przeludnienie = True

        if przeludnienie:
            przeludnione += 1
        suma_2025 += ludnosc
        if ludnosc > najwiecej:
            najwiecej = ludnosc
            najwieksze = nazwa

print(suma_2025)
print(najwieksze)
print(przeludnione)

Odpowiedź: 125 930 205 mieszkańców w 2025 roku, najwięcej: w12C, przeludnienie w 18 województwach

↑

Edytuj na GitHubie