Matura informatyka

Matura 2006 — maj, poziom rozszerzony

Przykładowe wyniki CKE do arkusza II znajdują się w folderze WYNIKI w paczce z danymi.

Arkusz I

1a

PythonC++23Java 25
Treść zadania

Zadanie 1 (suma silni). Silnia: 1! = 1, n! = (n−1)!·n dla n > 1. Funkcja ss(n) = 1! + 2! + ... + n! dla n ≥ 1.

Podaj, ile mnożeń trzeba wykonać, aby obliczyć ss(3), ss(4) oraz ss(n), jeśli każdą silnię we wzorze liczymy osobno, wprost z definicji.

Python
def ss_wprost(n):
    # każdą silnię liczymy osobno i liczymy mnożenia
    mnozenia = 0
    suma = 0
    for k in range(1, n + 1):
        silnia = 1
        for i in range(2, k + 1):
            silnia *= i
            mnozenia += 1
        suma += silnia
    return suma, mnozenia


for n in [3, 4, 10]:
    print(n, *ss_wprost(n), n * (n - 1) // 2)

Odpowiedź: ss(3): 0+1+2 = 3 mnożenia, ss(4): 0+1+2+3 = 6 mnożeń, ss(n): n(n-1)/2 mnożeń

↑

Arkusz I

1b

PythonC++23Java 25
Treść zadania

Czynnik 2 występuje w n−1 silniach sumy ss(n) = 1! + ... + n!, czynnik 3 w n−2 silniach itd. Wykorzystaj to i przekształć wzór (schemat zagnieżdżony, np. ss(3) = 1 + 2·(1 + 3), ss(4) = 1 + 2·(1 + 3·(1 + 4))), tak aby ss(n) dało się policzyć wykonując dokładnie n−2 mnożenia dla n ≥ 2. Uzupełnij tabelę dla ss(4), ss(5), ss(n), a następnie zapisz algorytm obliczania ss(n) według tego wzoru wraz ze specyfikacją.

Python
def ss(n):
    # Dane: n - liczba naturalna > 0
    # Wynik: ss = 1! + 2! + ... + n!
    # ss(n) = 1+2*(1+3*(1+...(n-2)*(1+(n-1)*(1+n))...))
    if n == 1:
        return 1
    wynik = 1 + n
    i = n - 1
    while i > 1:
        wynik = 1 + i * wynik
        i -= 1
    return wynik


for n in range(1, 8):
    print(n, ss(n))

Odpowiedź: ss(5) = 1+2*(1+3*(1+4*(1+5))) (3 mnożenia); algorytm: ss := 1 + n, i := n − 1; dopóki i > 1: ss := 1 + i·ss, i := i − 1

↑

Arkusz I

2a

PythonC++23Java 25
Treść zadania

Zadanie 2 (liczby pierwsze). Dany jest algorytm sita Eratostenesa: dla N ≥ 2 wypełnia tablicę T[2..N] tak, że T[i] = 0, gdy i jest pierwsza, i T[i] = 1, gdy złożona (dla kolejnych i z T[i] = 0 ustawia T[j] := 1 dla j = 2i, 3i, ... ≤ N).

Dane są liczba naturalna M ≥ 1 i tablica A[1..M] liczb z przedziału [2, N]. Korzystając z sita, zaprojektuj algorytm (ze specyfikacją) wyznaczający te liczby z [2, N], które nie są podzielne przez żadną z liczb A[1], ..., A[M].

Python
def niepodzielne(N, A):
    # Dane: N > 1, tablica A liczb z przedziału [2, N]
    # Wynik: T[i] = 0 wtedy i tylko wtedy, gdy i nie dzieli się przez żadną z liczb A
    T = [0] * (N + 1)
    for liczba in A:
        j = liczba
        while j <= N:
            T[j] = 1
            j += liczba
    return [i for i in range(2, N + 1) if T[i] == 0]


print(niepodzielne(30, [2, 3]))

Odpowiedź: dla każdej liczby A[k] wykreślamy (T[j] := 1) wszystkie jej wielokrotności j = A[k], 2A[k], … ≤ N; liczby z T[i] = 0 nie są podzielne przez żadną z A[1..M].

↑

Arkusz I

2b

PythonC++23Java 25
Treść zadania

Sito z zadania 2 zmodyfikowano: zamiast T[j] := 1 wykonuje się T[j] := T[j] + 1 (dla każdej liczby i z T[i] = 0 zwiększamy T[j] dla j = 2i, 3i, ... ≤ N).

Podaj wartości T[13], T[24], T[33] po wykonaniu algorytmu dla N = 100. Dla jakiej wartości T[i] liczba i jest pierwsza? Jaką własność liczby i opisuje wartość T[i]?

Python
N = 100
T = [0] * (N + 1)
i = 2
while i < N:
    if T[i] == 0:
        j = 2 * i
        while j <= N:
            T[j] = T[j] + 1
            j = j + i
    i = i + 1

print(T[13], T[24], T[33])

Odpowiedź: T[13] = 0, T[24] = 2, T[33] = 2; i jest pierwsza, gdy T[i] = 0; T[i] to liczba różnych dzielników pierwszych liczby i (mniejszych od i).

↑

Arkusz I

2c

PythonC++23Java 25
Treść zadania

Podaj (lista kroków, schemat blokowy lub program) inny niż sito algorytm sprawdzający, czy dana liczba naturalna L > 1 jest pierwsza — bez sprawdzania pierwszości liczb mniejszych od L. Wynik: „Tak”, gdy L jest pierwsza, „Nie” w przeciwnym razie. Oceniana jest także złożoność czasowa.

Python
def czy_pierwsza(L):
    j = 2
    pierwsza = True
    while j * j <= L and pierwsza:
        pierwsza = L % j != 0
        j += 1
    return "Tak" if pierwsza else "Nie"


for L in [2, 9, 13, 97, 100]:
    print(L, czy_pierwsza(L))

Odpowiedź: sprawdzamy dzielniki j = 2, 3, … dopóki j·j ≤ L; złożoność O(√L).

↑

Arkusz II

5a

PythonC++23Java 25
Treść zadania

Zadanie 5 (figura). Dla liczby naturalnej C > 0 figura F(C) jest ograniczona z lewej osią OY, z prawej prostą x = C, od dołu krzywą f(x) = −x²/50, a od góry krzywą g(x) = 1 + x²/100 − x/200.

Wyznacz przybliżone pole figury F(10) z dokładnością do 0,01. W pliku figura.txt opisz zastosowaną metodę i zapisz wynik (poprzedzony literą podpunktu).

Python
def f(x):
    return -x * x / 50


def g(x):
    return 1 + x * x / 100 - x / 200


# metoda trapezów
C = 10
n = 100000
krok = C / n
pole = 0
for i in range(n):
    x1 = i * krok
    x2 = x1 + krok
    pole += ((g(x1) - f(x1)) + (g(x2) - f(x2))) / 2 * krok

print(round(pole, 2))

Odpowiedź: 19,75

↑

Arkusz II

5b

PythonC++23Java 25
Treść zadania

Dla figury F(C) z zadania 5 wyznacz najmniejsze naturalne C, dla którego wewnątrz F(C) (brzeg należy do wnętrza) mieści się prostokąt 100 × 26 o wierzchołkach w punktach o współrzędnych całkowitych, o bokach równoległych do osi, z dłuższymi bokami równoległymi do OX. W pliku figura.txt podaj C i współrzędne wierzchołków prostokąta.

Python
import math


def f(x):
    return -x * x / 50


def g(x):
    return 1 + x * x / 100 - x / 200


# dla x >= 0 funkcja f maleje, a g rośnie dla x >= 0.25,
# więc na przedziale [x0, x0+100] największe f jest w x0, a najmniejsze g w max(x0, 0.25)
znalezione = False
C = 100
while not znalezione:
    for x0 in range(0, C - 100 + 1):
        dol = math.ceil(f(x0))
        gora = math.floor(g(max(x0, 0.25)))
        if gora - dol >= 26:
            znalezione = True
            print("C =", C)
            for y0 in range(dol, gora - 26 + 1):
                print((x0, y0), (x0 + 100, y0), (x0, y0 + 26), (x0 + 100, y0 + 26))
            break
    if not znalezione:
        C += 1

Odpowiedź: C = 130, np. prostokąt (30, −17), (130, −17), (30, 9), (130, 9)

↑

Arkusz II

6a

PythonC++23Java 25
Treść zadania

Zadanie 6 (słowa). W pliku dane.txt w osobnych wierszach znajdują się słowa długości od 2 do 20 znaków złożone z liter A–F. Odpowiedzi zapisz w pliku wyniki.txt, poprzedzając je literą podpunktu.

Podaj w osobnych wierszach: ile jest słów występujących w pliku więcej niż raz, słowo o największej liczbie wystąpień oraz liczbę jego wystąpień.

Python
ile = {}
with open("dane.txt") as file:
    for linia in file:
        slowo = linia.strip()
        ile[slowo] = ile.get(slowo, 0) + 1

powtorzone = 0
for slowo in ile:
    if ile[slowo] > 1:
        powtorzone += 1

najczestsze = max(ile, key=ile.get)
print(powtorzone)
print(najczestsze)
print(ile[najczestsze])

Odpowiedź: 21; EBFAABCCBD; 30

↑

Arkusz II

6b

PythonC++23Java 25
Treść zadania

Traktując słowa z pliku dane.txt (litery A–F) jako liczby zapisane w systemie szesnastkowym, podaj, ile z nich jest parzystych. Wynik zapisz w wyniki.txt.

Python
parzyste = 0
with open("dane.txt") as file:
    for linia in file:
        slowo = linia.strip()
        if int(slowo, 16) % 2 == 0:
            parzyste += 1

print(parzyste)

Odpowiedź: 483

↑

Arkusz II

6c

PythonC++23Java 25
Treść zadania

Palindrom to słowo czytane tak samo od lewej i od prawej (np. ABCDCBA, AEEFFEEA). Napisz program, który policzy palindromy w pliku dane.txt, i zapisz ich liczbę w wyniki.txt. Ocenie podlega też metoda sprawdzania, czy słowo jest palindromem.

Python
def czy_palindrom(slowo):
    i = 0
    j = len(slowo) - 1
    while i < j:
        if slowo[i] != slowo[j]:
            return False
        i += 1
        j -= 1
    return True


palindromy = 0
with open("dane.txt") as file:
    for linia in file:
        if czy_palindrom(linia.strip()):
            palindromy += 1

print(palindromy)

Odpowiedź: 20

↑

Arkusz II

7a

PythonC++23Java 25

Zadanie na arkusz kalkulacyjny — rozwiązanie w Pythonie.

Treść zadania

Zadanie 7 (finanse). Odpowiedzi zapisz w pliku odpfinanse.txt, poprzedzając je literą podpunktu. Plik lokaty.txt zawiera kwoty rocznych lokat klientów MatBanku (po jednej w wierszu). Oprocentowanie roczne zależy od kwoty:

  • poniżej 10 000 zł — 6%,
  • 10 000–19 999,99 zł — 7%,
  • 20 000–29 999,99 zł — 8%,
  • 30 000–39 999,99 zł — 9%,
  • 40 000–49 999,99 zł — 10%,
  • 50 000 zł i więcej — 11%.

Np. lokata 5 000,10 zł daje po roku 5 300,11 zł, a 45 000 zł — 49 500 zł.

Podaj sumaryczną wartość wszystkich lokat na początku i na końcu roku oraz wartość największej lokaty na końcu roku.

Python
def oprocentowanie(kwota):
    if kwota < 10000:
        return 6
    if kwota < 20000:
        return 7
    if kwota < 30000:
        return 8
    if kwota < 40000:
        return 9
    if kwota < 50000:
        return 10
    return 11


suma_poczatek = 0
suma_koniec = 0
najwieksza = 0
with open("lokaty.txt") as file:
    for linia in file:
        kwota = float(linia.strip().replace(",", "."))
        koniec = round(kwota * (100 + oprocentowanie(kwota)) / 100, 2)
        suma_poczatek += kwota
        suma_koniec += koniec
        najwieksza = max(najwieksza, koniec)

print("%.2f" % suma_poczatek)
print("%.2f" % suma_koniec)
print("%.2f" % najwieksza)

Odpowiedź: na początku roku 7 959 613,00 zł, na końcu roku 8 770 818,04 zł, największa lokata na końcu roku 88 728,96 zł

↑

Arkusz II

7b

PythonC++23Java 25

Zadanie na arkusz kalkulacyjny — rozwiązanie w Pythonie.

Treść zadania

1 stycznia 2005 r. mamy 20 000,00 zł. Każdego dnia możemy wymienić całe oszczędności z zł na euro lub odwrotnie po kursie średnim z danego dnia (plik kursy.txt: 365 kursów, po jednym w wierszu); po każdej wymianie kwotę zaokrąglamy do 0,01. Wyznacz wartość oszczędności na koniec roku dla dwóch strategii:

  • I) 1 stycznia wymieniamy wszystko na euro, a pierwszego dnia każdego kolejnego miesiąca zmieniamy walutę (1 lutego na złote, 1 marca na euro itd.);
  • II) 1 stycznia wymieniamy wszystko na euro; każdego kolejnego dnia: jeśli mamy euro, wymieniamy je na złote tylko wtedy, gdy kurs spadł względem dnia poprzedniego; jeśli mamy złote, bezwarunkowo wymieniamy je na euro.

Jeśli na koniec roku oszczędności są w euro, przelicz je na złote po kursie z 31 grudnia. Wyniki obu strategii zapisz w osobnych, opisanych wierszach odpfinanse.txt.

Python
import datetime

kursy = []
with open("kursy.txt") as file:
    for linia in file:
        kursy.append(float(linia.strip().replace(",", ".")))

# sposób I - zmiana waluty pierwszego dnia każdego miesiąca
pierwsze_dni = []
for miesiac in range(1, 13):
    dzien = datetime.date(2005, miesiac, 1) - datetime.date(2005, 1, 1)
    pierwsze_dni.append(dzien.days)

kwota = 20000.00
w_euro = False
for dzien in pierwsze_dni:
    if w_euro:
        kwota = round(kwota * kursy[dzien], 2)
    else:
        kwota = round(kwota / kursy[dzien], 2)
    w_euro = not w_euro
if w_euro:
    kwota = round(kwota * kursy[364], 2)
print("Sposób I:", "%.2f" % kwota)

# sposób II
kwota = round(20000.00 / kursy[0], 2)
w_euro = True
for dzien in range(1, 365):
    if w_euro:
        if kursy[dzien] < kursy[dzien - 1]:
            kwota = round(kwota * kursy[dzien], 2)
            w_euro = False
    else:
        kwota = round(kwota / kursy[dzien], 2)
        w_euro = True
if w_euro:
    kwota = round(kwota * kursy[364], 2)
print("Sposób II:", "%.2f" % kwota)

Odpowiedź: sposób I: 21 301,75 zł, sposób II: 21 335,51 zł

↑

Arkusz II

7c

PythonC++23Java 25

Zadanie na arkusz kalkulacyjny — rozwiązanie w Pythonie.

Treść zadania

Na podstawie kursów euro z pliku kursy.txt (po jednym na dzień) policz, w ilu dniach, począwszy od 2 stycznia, kurs euro wzrósł w porównaniu z dniem poprzednim. Wynik zapisz w odpfinanse.txt.

Python
kursy = []
with open("kursy.txt") as file:
    for linia in file:
        kursy.append(float(linia.strip().replace(",", ".")))

wzrosty = 0
for i in range(1, len(kursy)):
    if kursy[i] > kursy[i - 1]:
        wzrosty += 1

print(wzrosty)

Odpowiedź: 194

↑

Edytuj na GitHubie