Matura informatyka

Matura 2012 — maj, poziom podstawowy

PythonC++23Java 25
Treść zadania

Funkcja rekurencyjna Fib oblicza k-ty wyraz ciągu Fibonacciego (k — liczba naturalna większa od zera):

Kod
Fib(k):
1. jeżeli k = 1 lub k = 2, to wynikiem jest 1
2. jeżeli k > 2, to wynikiem jest Fib(k − 1) + Fib(k − 2)

Np. Fib(4) = Fib(3) + Fib(2) = Fib(2) + Fib(1) + Fib(2) = 3.

  • 1a — Uzupełnij tabelę wartości Fib(k) (m.in. dla k = 8 i k = 11).
  • 1b — Wywołanie Fib(k) dla k > 2 powoduje dwa wywołania z mniejszymi argumentami, co można przedstawić jako drzewo wywołań (w arkuszu podano drzewo dla k = 5, w węzłach są argumenty). Narysuj drzewo wywołań dla Fib(6).
Python
poziomy = []


def fib(k, poziom=0):
    # zapamiętujemy argumenty wywołań na kolejnych poziomach drzewa
    if len(poziomy) <= poziom:
        poziomy.append([])
    poziomy[poziom].append(k)
    if k == 1 or k == 2:
        return 1
    return fib(k - 1, poziom + 1) + fib(k - 2, poziom + 1)


print("Fib(8) =", fib(8))
print("Fib(11) =", fib(11))

poziomy.clear()
fib(6)
for poziom in poziomy:  # drzewo wywołań dla Fib(6), poziom po poziomie
    print(*poziom)

Odpowiedź: a) Fib(8) = 21, Fib(11) = 89; b) drzewo: 6 / 5 4 / 4 3 3 2 / 3 2 2 1 2 1 / 2 1

↑
PythonC++23Java 25
Treść zadania

Ciąg Fibonacciego można liczyć iteracyjnie, pamiętając dwa ostatnie wyrazy. Zdefiniujmy nowy ciąg: pierwszy i drugi wyraz są równe 1; dla k > 2 parzystego k-ty wyraz jest sumą trzech wyrazów go poprzedzających; dla k > 2 nieparzystego k-ty wyraz jest równy wyrazowi o numerze k − 1. Początkowe wyrazy (k = 1..8): 1, 1, 1, 3, 3, 7, 7, 17.

Zapisz iteracyjny algorytm, który dla danego k > 0 wyznacza k-ty wyraz tego ciągu.

Python
def wyraz(k):
    a = [0, 1, 1]  # a[1] = a[2] = 1, a[0] nieużywane
    for i in range(3, k + 1):
        if i % 2 == 0:
            a.append(a[i - 1] + a[i - 2] + a[i - 3])
        else:
            a.append(a[i - 1])
    return a[k]


for k in range(1, 9):
    print(k, wyraz(k))

Odpowiedź: 1, 1, 1, 3, 3, 7, 7, 17 (zgodnie z tabelą w treści)

↑
PythonC++23Java 25
Treść zadania

W sejfie jest n diamentów o różnych cenach d₁, …, dₙ, znanych tylko jubilerowi. Jubiler wykonuje jedynie operację porównania: większe(i, j) jest prawdą, gdy dᵢ > dⱼ, a fałszem, gdy dᵢ < dⱼ. Dany jest algorytm:

Kod
1. j ← 0
2. i ← 1
3. dopóki i < n
       jeżeli większe(i, i + 1), to j ← j + 1
       i ← i + 1
4. wypisz j

Podaj wynik algorytmu dla n = 4 i ciągów cen: (5, 2, 1, 6), (2, 5, 1, 2), (1, 2, 3, 4), (4, 3, 2, 1) (pierwszy wynik, 2, podano w arkuszu).

Python
def algorytm(d):
    n = len(d)
    j = 0
    i = 1
    while i < n:
        if d[i - 1] > d[i]:  # większe(i, i+1), numeracja od 1
            j = j + 1
        i = i + 1
    return j


for d in [[5, 2, 1, 6], [2, 5, 1, 2], [1, 2, 3, 4], [4, 3, 2, 1]]:
    print(d, algorytm(d))

Odpowiedź: 2 (podane), 1, 0, 3

↑
PythonC++23Java 25
Treść zadania

Diamenty i operacja większe(i, j) jak w 2a.

Zapisz algorytm, który dla n > 0 diamentów o różnych cenach znajduje numer i diamentu o najwyższej cenie, korzystając wyłącznie z operacji większe. Podaj, ile porównań wykonuje Twój algorytm dla n = 1000.

Python
def najdrozszy(d):
    porownania = 0
    i = 1
    for k in range(2, len(d) + 1):
        porownania += 1
        if d[k - 1] > d[i - 1]:  # większe(k, i)
            i = k
    return i, porownania


print(najdrozszy([5, 2, 1, 6]))
print(najdrozszy(list(range(1000)))[1])

Odpowiedź: dla n = 1000 algorytm wykonuje 999 porównań

↑
PythonC++23Java 25
Treść zadania

W pliku cyfry.txt znajduje się 1000 liczb naturalnych mniejszych niż 10⁹, każda w osobnym wierszu. Odpowiedzi zapisz w pliku zadanie4.txt, poprzedzając je oznaczeniem podpunktu.

Ile liczb w pliku jest parzystych?

Python
parzyste = 0

with open("cyfry.txt") as file:
    for line in file:
        if int(line) % 2 == 0:
            parzyste += 1

print(parzyste)

Odpowiedź: 495

↑
PythonC++23Java 25
Treść zadania

Dane z pliku cyfry.txt (1000 liczb naturalnych < 10⁹).

Podaj liczbę o największej sumie cyfr oraz liczbę o najmniejszej sumie cyfr (każda jest jedyna). Przykład: dla 121324, 66562, 675100, 1187010 odpowiedzią jest 66562 (suma 25) oraz 121324 (suma 13).

Python
def suma_cyfr(liczba):
    suma = 0
    for cyfra in liczba:
        suma += int(cyfra)
    return suma


najwieksza = ""
najmniejsza = ""

with open("cyfry.txt") as file:
    for line in file:
        liczba = line.strip()
        if najwieksza == "" or suma_cyfr(liczba) > suma_cyfr(najwieksza):
            najwieksza = liczba
        if najmniejsza == "" or suma_cyfr(liczba) < suma_cyfr(najmniejsza):
            najmniejsza = liczba

print("największa suma cyfr:", najwieksza)
print("najmniejsza suma cyfr:", najmniejsza)

Odpowiedź: największa suma cyfr: 187869866, najmniejsza suma cyfr: 10010

↑
PythonC++23Java 25
Treść zadania

Dane z pliku cyfry.txt (1000 liczb naturalnych < 10⁹).

Wypisz wszystkie liczby, których cyfry tworzą ciąg ściśle rosnący (np. 123579 tak; 1232 i 34556 nie).

Python
with open("cyfry.txt") as file:
    for line in file:
        liczba = line.strip()
        rosnace = True
        for i in range(1, len(liczba)):
            if liczba[i] <= liczba[i - 1]:
                rosnace = False
        if rosnace:
            print(liczba)

Odpowiedź: 2389, 23567, 123456789, 3468

↑
PythonC++23Java 25
Treść zadania

Plik gielda.txt ma 400 wierszy; w każdym są trzy liczby całkowite — zmiany cen akcji firm A, B i C w kolejnych dniach. Przed pierwszym dniem każda akcja kosztowała 200 zł (np. wiersze 0 12 -7, 1 -3 4 dają ceny 200/212/193, potem 201/209/197). Odpowiedzi (poza wykresem z c) zapisz w pliku zadanie5.txt, poprzedzając je literą podpunktu.

  • 5a — Wyznacz końcową (po 400 dniach) cenę akcji każdej z firm.
  • 5b — Podaj najwyższą i najniższą cenę akcji każdej z firm w ciągu tych 400 dni.

Zadanie na Excel — rozwiązanie w Pythonie.

Python
cena = [200, 200, 200]
najwyzsza = [200, 200, 200]
najnizsza = [10 ** 9, 10 ** 9, 10 ** 9]

with open("gielda.txt") as file:
    for line in file:
        zmiany = list(map(int, line.split()))
        for i in range(3):
            cena[i] += zmiany[i]
            najwyzsza[i] = max(najwyzsza[i], cena[i])
            najnizsza[i] = min(najnizsza[i], cena[i])

print("a)", "A:", cena[0], "B:", cena[1], "C:", cena[2])
print("b) max:", najwyzsza, "min:", najnizsza)

Odpowiedź: a) A – 221, B – 117, C – 198; b) max: A 264, B 210, C 223; min: A 167, B 62, C 97

↑
PythonC++23Java 25
Treść zadania

Dane z pliku gielda.txt (dzienne zmiany cen akcji A, B, C; start 200 zł).

Krach giełdowy to dzień, w którym spadła cena akcji każdej z trzech firm, a suma spadków przekracza 20 zł (np. 233/166/164 → 230/150/160: spadki 3 + 16 + 4 > 20). Podaj liczbę krachów oraz ceny akcji wszystkich firm w dniu ostatniego krachu.

Zadanie na Excel — rozwiązanie w Pythonie.

Python
cena = [200, 200, 200]
krachy = 0
ostatni = []

with open("gielda.txt") as file:
    for line in file:
        zmiany = list(map(int, line.split()))
        for i in range(3):
            cena[i] += zmiany[i]
        if zmiany[0] < 0 and zmiany[1] < 0 and zmiany[2] < 0 and -sum(zmiany) > 20:
            krachy += 1
            ostatni = cena[:]

print(krachy, ostatni)

Odpowiedź: 6 krachów, ceny przy ostatnim krachu: A – 224, B – 163, C – 194

↑
PythonC++23Java 25
Treść zadania

Dane z pliku gielda.txt (dzienne zmiany cen akcji A, B, C; start 200 zł).

Rekord firmy to cena akcji w dniu, w którym jest ona wyższa od wszystkich wcześniejszych cen tej firmy (przed pierwszym dniem rekord wynosi 200 zł). Podaj, ile razy w ciągu 400 dni zmieniał się rekord firmy A.

Zadanie na Excel — rozwiązanie w Pythonie.

Python
cena = 200
rekord = 200
zmiany_rekordu = 0

with open("gielda.txt") as file:
    for line in file:
        cena += int(line.split()[0])
        if cena > rekord:
            rekord = cena
            zmiany_rekordu += 1

print(zmiany_rekordu)

Odpowiedź: 14 razy

↑

Edytuj na GitHubie