Matura informatyka

Matura 2005 — maj, poziom rozszerzony

Arkusz I

1a

PythonC++23Java 25
Treść zadania

Zadanie 1 (szeregi nieskończone). Wartość ln 2 można przybliżać sumą nieskończoną: ln 2 = 2/3 · (1 + 1/3·1/9 + 1/5·1/9² + 1/7·1/9³ + 1/9·1/9⁴ + ...). Oznaczmy l₀ = 2/3 oraz dla n ≥ 1: lₙ = 2/3 · (1 + 1/3·1/9 + ... + 1/(2n+1)·1/9ⁿ).

Wypełnij tabelę wartości lₙ dla n = 0, 1, 2, 3. Podaj zależność między lₙ a lₙ₋₁ dla n ≥ 1 oraz wzór rekurencyjny na różnicę rₙ = lₙ − lₙ₋₁ (n > 0).

Python
from fractions import Fraction

# l0 = 2/3,  l(n) = l(n-1) + 2/3 * 1/((2n+1) * 9^n)
# r(1) = 2/81, r(n) = r(n-1) * (2n-1) / ((2n+1) * 9)
l = Fraction(2, 3)
print(0, l, float(l))

for n in range(1, 4):
    l = l + Fraction(2, 3) * Fraction(1, (2 * n + 1) * 9 ** n)
    print(n, l, round(float(l), 6))

Odpowiedź: l0 = 2/3, l1 = 56/81 ≈ 0,6913, l2 = 842/1215 ≈ 0,693004, l3 = 53056/76545 ≈ 0,693135; l(n) = l(n-1) + 2/3 · 1/((2n+1)·9^n); r1 = 2/81, r(n) = r(n-1) · (2n-1)/((2n+1)·9)

↑

Arkusz I

1b

PythonC++23Java 25
Treść zadania

Na podstawie wzoru z zadania 1 (lₙ = lₙ₋₁ + 2/3 · 1/((2n+1)·9ⁿ)) podaj algorytm ze specyfikacją (lista kroków, schemat blokowy lub program), który dla danej liczby ε > 0 oblicza przybliżoną wartość ln 2, sumując jak najmniej wyrazów — tak, aby różnica między dwoma ostatnimi przybliżeniami była mniejsza niż ε.

Python
import math


def ln2(eps):
    # Dane: eps > 0, Wynik: przybliżona wartość ln 2
    n = 1
    r = 2 / 81           # różnica l1 - l0
    l = 2 / 3 + r        # l1
    while r >= eps:
        n += 1
        r = r * (2 * n - 1) / ((2 * n + 1) * 9)
        l = l + r
    return l


for eps in [0.1, 0.001, 0.000001, 0.000000001]:
    print(eps, ln2(eps), math.log(2))

Odpowiedź: algorytm sumuje kolejne wyrazy r(n), dopóki różnica dwóch ostatnich przybliżeń (czyli r(n)) nie jest mniejsza niż ε; wynik to ostatnie przybliżenie l(n).

↑

Arkusz I

2a

PythonC++23Java 25
Treść zadania

Zadanie 2 (ewolucja). Na planecie MLAP organizm to napis z wielkich liter. Nowy organizm to A. Po każdym roku życia każda litera zostaje zastąpiona dwiema literami według reguł postaci L → F S. Rozważamy reguły: A → BC, A → CD, B → AD, C → BA, D → AA, D → BB. Organizmy roczne to BC lub CD, dwuletnie np. ADBA, BAAA, BABB. Dwa organizmy są odróżnialne, gdy odpowiadające im napisy są różne.

Wypisz wszystkie odróżnialne organizmy trzyletnie, które można otrzymać z organizmu dwuletniego ADBA.

Python
reguly = [("A", "BC"), ("A", "CD"), ("B", "AD"), ("C", "BA"), ("D", "AA"), ("D", "BB")]


def nastepne_pokolenie(organizm):
    wyniki = [""]
    for litera in organizm:
        nowe = []
        for poczatek in wyniki:
            for lewa, prawa in reguly:
                if lewa == litera:
                    nowe.append(poczatek + prawa)
        wyniki = nowe
    return sorted(set(wyniki))


for organizm in nastepne_pokolenie("ADBA"):
    print(organizm)

Odpowiedź: BCAAADBC, CDAAADBC, BCBBADBC, CDBBADBC, BCAAADCD, CDAAADCD, BCBBADCD, CDBBADCD

↑

Arkusz I

2b

PythonC++23Java 25
Treść zadania

Organizmy z zadania 2 podwajają długość co rok (start: jedna litera A). Podaj sposób sprawdzenia, czy dla danej liczby naturalnej n ≥ 1 mogą istnieć organizmy o długości n, a jeśli tak — ustal wiek takiego organizmu. Podaj też, ile poprawnych długości organizmów leży w przedziale (n, m] dla liczb naturalnych n < m. Odpowiedź uzasadnij.

Python
def wiek(n):
    # organizm o długości n istnieje tylko, gdy n jest potęgą dwójki; wiek = log2(n)
    lata = 0
    while n % 2 == 0:
        n //= 2
        lata += 1
    if n == 1:
        return lata
    return -1  # nie ma takiego organizmu


def ile_wielkosci(n, m):
    # liczba potęg dwójki w przedziale (n, m]
    ile = 0
    potega = 1
    while potega <= m:
        if potega > n:
            ile += 1
        potega *= 2
    return ile


print(wiek(1), wiek(8), wiek(12), wiek(1024))
print(ile_wielkosci(3, 100))

Odpowiedź: organizm o długości n istnieje wtedy i tylko wtedy, gdy n = 2^k, a jego wiek to k = log2 n; w przedziale (n, m] jest ⌊log2 m⌋ − ⌊log2 n⌋ poprawnych wielkości.

↑

Arkusz I

2d

PythonC++23Java 25
Treść zadania

Dla zbioru reguł L₁ → F₁S₁, ..., Lₚ → FₚSₚ z zadania 2 dana jest rekurencyjna funkcja sprawdź(napis, start):

Kod
jeśli długość napisu nie jest potęgą 2 → NIE
jeśli napis = start → TAK
jeśli długość napisu = 1 → NIE
podziel napis na równe połowy napis1, napis2
dla i = 1..p: jeśli Li = start oraz sprawdź(napis1, Fi) = TAK
              i sprawdź(napis2, Si) = TAK → TAK
NIE

Uzupełnij specyfikację funkcji (czym są dane napis i start). Dla reguł A → BC, A → CD, B → AD, C → BA, D → AA, D → BB oraz napis = BCAAADCD, start = A podaj parametry wszystkich wywołań rekurencyjnych i odpowiedź, jaką zwróci funkcja.

Python
reguly = [("A", "BC"), ("A", "CD"), ("B", "AD"), ("C", "BA"), ("D", "AA"), ("D", "BB")]


def potega_dwojki(n):
    while n % 2 == 0:
        n //= 2
    return n == 1


def sprawdz(napis, start):
    # Dane: napis - ciąg n liter, start - litera nowo powstałego organizmu
    # Wynik: czy napis to organizm, który można uzyskać z organizmu start
    print("sprawdz(", napis, ",", start, ")")
    if not potega_dwojki(len(napis)):
        return False
    if napis == start:
        return True
    if len(napis) == 1:
        return False
    polowa = len(napis) // 2
    napis1 = napis[:polowa]
    napis2 = napis[polowa:]
    for lewa, prawa in reguly:
        if lewa == start:
            wynik1 = sprawdz(napis1, prawa[0])
            wynik2 = sprawdz(napis2, prawa[1])
            if wynik1 and wynik2:
                return True
    return False


print(sprawdz("BCAAADCD", "A"))

Odpowiedź: wywołania: (BCAAADCD, A), (BCAA, B), (BC, A), (B, B), (C, C), (AA, D), (A, A), (A, A), (ADCD, C), (AD, B), (A, A), (D, D), (CD, A), (C, B), (D, C), (C, C), (D, D); wynik: TAK

↑

Arkusz II

4a

PythonC++23Java 25
Treść zadania

Zadanie 4 (projekt). Licencja na oprogramowanie do przetwarzania N gigabajtów danych kosztuje 0,01·N w firmie D1 oraz 0,5·√N w firmie D2. Czas obliczeń programu D1 wynosi f(N) = 10m³ + 7m² + 0,1m + 0,1 sekund, gdzie m = 0,0001·N; program D2 jest pięciokrotnie wolniejszy (5·f(N)). Koszt obliczeń jest równy ich czasowi, więc koszt wyboru D1 to 0,01N + f(N), a D2 to 0,5√N + 5f(N). Wybieramy zawsze tańsze rozwiązanie.

Wyznacz, dla jakich N ∈ [1, 7000] należy wybrać D1, a dla jakich D2 (każdy przedział w osobnym wierszu, końce z dokładnością do 0,01). Podaj też w tabeli koszt realizacji projektu przy wyborze D1 i D2 dla N = 100, 1000 i 5000 (zaokrąglony do 0,01). Wyniki umieść w dokumencie Raport4.

Python
import math


def f(N):
    m = 0.0001 * N
    return 10 * m ** 3 + 7 * m ** 2 + 0.1 * m + 0.1


def koszt_d1(N):
    return 0.01 * N + f(N)


def koszt_d2(N):
    return 0.5 * math.sqrt(N) + 5 * f(N)


# sprawdzamy wszystkie N z [1, 7000] z krokiem 0,01
poprzednia = None
for k in range(100, 700001):
    N = k / 100
    firma = "D1" if koszt_d1(N) <= koszt_d2(N) else "D2"
    if firma != poprzednia:
        print("od N =", N, "wybieramy", firma)
        poprzednia = firma

print()
print("N", "D1", "D2")
for N in [100, 1000, 5000]:
    print(N, round(koszt_d1(N), 2), round(koszt_d2(N), 2))

Odpowiedź: D1 dla N ∈ [1; 3617,62], D2 dla N ∈ [3617,63; 7000]

ND1D2
1001,105,51
100010,1916,76
500053,1551,11
↑

Arkusz II

4b

PythonC++23Java 25
Treść zadania

Dla danych z zadania 4 sporządź zestawienie porównujące koszt opłat licencyjnych firmy D2 (0,5√N) z kosztem obliczeń przy wyborze D2 (5f(N)) dla N od 6000 do 9000 z krokiem 100. Zestawienie ma mieć trzy kolumny: N, koszt licencji, koszt obliczeń; dołącz wykres liniowy ilustrujący wyniki (Raport4).

Python
import math


def f(N):
    m = 0.0001 * N
    return 10 * m ** 3 + 7 * m ** 2 + 0.1 * m + 0.1


print("N;licencja D2;obliczenia D2")
for N in range(6000, 9001, 100):
    licencja = 0.5 * math.sqrt(N)
    obliczenia = 5 * f(N)
    print(N, "%.2f" % licencja, "%.2f" % obliczenia, sep=";")

Odpowiedź: 6000: licencja 38,73, obliczenia 24,20; 6100: 39,05, 25,18; 6200: 39,37, 26,18; … 9000: 47,43, 65,75 (koszt obliczeń przewyższa licencję od N = 7700).

↑

Arkusz II

5a

PythonC++23Java 25
Treść zadania

Zadanie 5. Najlepszą sumą ciągu a₁, ..., aₙ nazywamy największą wartość spośród sum kolejnych (sąsiednich) elementów ciągu; pojedynczy element też jest sumą. Np. dla ciągu 1, 2, −5, 7 najlepsza suma wynosi 7.

Wyznacz najlepszą sumę dla ciągu 1, −2, 6, −5, 7, −3. Czy na podstawie tego wyniku można podać najlepszą sumę ciągu 1, −2, 2, 2, 2, −5, 3, 3, 1, −3? Odpowiedź uzasadnij.

Python
def najlepsza_suma(ciag):
    najlepsza = ciag[0]
    biezaca = 0
    for x in ciag:
        biezaca = max(biezaca + x, x)
        najlepsza = max(najlepsza, biezaca)
    return najlepsza


print(najlepsza_suma([1, -2, 6, -5, 7, -3]))
print(najlepsza_suma([1, -2, 2, 2, 2, -5, 3, 3, 1, -3]))

Odpowiedź: 8; drugi ciąg ma tę samą najlepszą sumę (8), bo powstał z pierwszego przez zastąpienie liczb dodatnich ciągami liczb dodatnich o tej samej sumie (6 = 2+2+2, 7 = 3+3+1).

↑

Arkusz II

5b

PythonC++23Java 25
Treść zadania

Zaproponuj algorytm wyznaczania najlepszej sumy (zadanie 5) dla dowolnego ciągu liczb całkowitych i napisz program, który obliczy najlepsze sumy ciągów zapisanych w plikach dane5-1.txt, dane5-2.txt, dane5-3.txt. Podaj wynik dla każdego pliku oraz opis algorytmu.

Python
def najlepsza_suma(ciag):
    # algorytm Kadane, czas O(n)
    najlepsza = ciag[0]
    biezaca = 0
    for x in ciag:
        biezaca = max(biezaca + x, x)
        najlepsza = max(najlepsza, biezaca)
    return najlepsza


for nazwa in ["dane5-1.txt", "dane5-2.txt", "dane5-3.txt"]:
    with open(nazwa) as file:
        ciag = [int(linia) for linia in file if linia.strip()]
    print(nazwa, najlepsza_suma(ciag))

Odpowiedź: dane5-1.txt: 106, dane5-2.txt: 139, dane5-3.txt: 1342

↑

Arkusz II

5c

PythonC++23Java 25
Treść zadania

Najpopularniejszy element ciągu to element występujący w nim najwięcej razy (przy remisie można podać dowolny z nich, np. dla 1, 3, 5, 1, 3 poprawne są 1 i 3). Zaprojektuj jak najszybszy algorytm jego wyznaczania, oszacuj liczbę wykonywanych operacji w zależności od długości ciągu, a następnie zastosuj go do ciągów z plików dane5-1.txt, dane5-2.txt, dane5-3.txt i podaj wyniki w czytelnej tabeli.

Python
def najpopularniejszy(ciag):
    # sortowanie O(n log n), potem jedno przejście po posortowanym ciągu O(n)
    ciag = sorted(ciag)
    najlepszy, najwiecej = ciag[0], 0
    licznik = 0
    for i in range(len(ciag)):
        if i > 0 and ciag[i] == ciag[i - 1]:
            licznik += 1
        else:
            licznik = 1
        if licznik > najwiecej:
            najwiecej = licznik
            najlepszy = ciag[i]
    return najlepszy, najwiecej


for nazwa in ["dane5-1.txt", "dane5-2.txt", "dane5-3.txt"]:
    with open(nazwa) as file:
        ciag = [int(linia) for linia in file if linia.strip()]
    print(nazwa, *najpopularniejszy(ciag))

Odpowiedź: dane5-1.txt: -22 (lub -15, 6, 19, 24), dane5-2.txt: -18 (lub 18), dane5-3.txt: 22; czas O(n log n)

↑

Edytuj na GitHubie