Matura informatyka

Matura 2016 — maj, poziom rozszerzony

PythonC++23Java 25
Treść zadania

Liczby skojarzone. Dwie różne liczby całkowite a, b > 1 są skojarzone, jeśli suma wszystkich dodatnich dzielników a mniejszych od a wynosi b + 1, a suma wszystkich dodatnich dzielników b mniejszych od b wynosi a + 1. Np. 140 i 195 są skojarzone: dzielniki 140 sumują się do 196 = 195 + 1, a dzielniki 195 — do 141 = 140 + 1.

  • 1.1 — Dla par (78, 64), (20, 21), (75, 48) podaj dzielniki a i b (mniejsze od tych liczb), ich sumy oraz rozstrzygnij, czy liczby są skojarzone (dla pary 78, 64: sumy 90 i 63, odpowiedź NIE).
  • 1.2 — Zapisz algorytm, który dla danej liczby całkowitej a > 1 znajdzie i wypisze liczbę b skojarzoną z a albo komunikat „NIE”, jeśli taka liczba nie istnieje. Wolno używać tylko dodawania, odejmowania, mnożenia, dzielenia całkowitego i reszty z dzielenia; oceniana jest też liczba wykonywanych operacji arytmetycznych.
Python
def suma_dzielnikow(n):
    # suma dzielników n mniejszych od n - sprawdzamy tylko i <= pierwiastek(n)
    suma = 1
    i = 2
    while i * i <= n:
        if n % i == 0:
            suma += i
            if n // i != i:
                suma += n // i
        i += 1
    return suma


def czy_skojarzone(a, b):
    return a != b and suma_dzielnikow(a) == b + 1 and suma_dzielnikow(b) == a + 1


def skojarzona(a):
    b = suma_dzielnikow(a) - 1
    if b > 1 and b != a and suma_dzielnikow(b) == a + 1:
        return b
    return "NIE"


# 1.1
for a, b in [(78, 64), (20, 21), (75, 48)]:
    print(a, b, suma_dzielnikow(a), suma_dzielnikow(b), "TAK" if czy_skojarzone(a, b) else "NIE")

# 1.2
print(skojarzona(140), skojarzona(75), skojarzona(20))

Odpowiedź: 1.1: (78, 64) NIE, (20, 21) sumy 22 i 11 - NIE, (75, 48) sumy 49 i 76 - TAK. 1.2: b = suma_dzielnikow(a) - 1, sprawdzamy, czy suma_dzielnikow(b) = a + 1.

↑
PythonC++23Java 25
Treść zadania

Przestawienia w tablicy. Dana jest dodatnia liczba całkowita n i tablica A[1..n] liczb całkowitych. Funkcja przestawia elementy tak, by na lewo znalazły się elementy mniejsze od klucza (pierwszego elementu tablicy), a na prawo — większe lub równe:

Kod
funkcja przestaw(A)
  klucz ← A[1]
  w ← 1
  dla k = 2, 3, ..., n wykonaj
      jeśli A[k] < klucz
          zamień(A[w], A[k])
          w ← w + 1
  • 2.1 — Podaj kolejność elementów tablicy A = [4, 6, 3, 5, 2, 1] (n = 6) po wykonaniu przestaw(A).
  • 2.2 — Podaj przykład siedmioelementowej tablicy A, dla której funkcja wykona zamień dokładnie 5 razy.
  • 2.3 — Tablica A[1..100] zawiera liczby 1–100 w kolejności: najpierw rosnąco liczby kończące się na 0 (10, 20, …, 100), potem rosnąco kończące się na 9 (9, 19, …, 99), potem na 8 itd., aż do 1, 11, …, 91. Podaj wartość zmiennej w oraz A[1], A[2], A[3] po wykonaniu przestaw(A).
Python
def przestaw(A):
    # A indeksowana od 0 (w treści od 1); zwraca w (indeksowane od 1) i liczbę zamian
    klucz = A[0]
    w = 0
    zamiany = 0
    for k in range(1, len(A)):
        if A[k] < klucz:
            A[w], A[k] = A[k], A[w]
            w += 1
            zamiany += 1
    return w + 1, zamiany


# 2.1
A = [4, 6, 3, 5, 2, 1]
przestaw(A)
print(A)

# 2.2 - zamiana wykona się tyle razy, ile elementów A[2..n] jest mniejszych od A[1]
A = [8, 1, 2, 3, 4, 5, 9]
print(przestaw(A)[1])

# 2.3
A = []
for koncowka in [0, 9, 8, 7, 6, 5, 4, 3, 2, 1]:
    for liczba in range(1, 101):
        if liczba % 10 == koncowka:
            A.append(liczba)
w, zamiany = przestaw(A)
print(w, A[0], A[1], A[2])

Odpowiedź: 2.1: A = [3, 2, 1, 5, 6, 4]; 2.2: np. [8, 1, 2, 3, 4, 5, 9]; 2.3: w = 10, A[1] = 9, A[2] = 8, A[3] = 7

↑
PythonC++23Java 25
Treść zadania

Na płaszczyźnie narysowano kwadrat o boku 400 i środku w punkcie (200, 200), o bokach równoległych do osi, i wpisano w niego koło. W pliku punkty.txt jest 10 000 wylosowanych punktów kwadratu — w każdym wierszu dwie liczby całkowite x, y z zakresu ⟨0, 400⟩ oddzielone spacją. Wyniki zapisz w pliku wyniki_4.txt, poprzedzając je numerem zadania.

Wypisz współrzędne punktów leżących na brzegu koła (okręgu (x − a)² + (y − b)² = r²) oraz podaj liczbę punktów leżących we wnętrzu koła (brzeg nie należy do wnętrza). Informacja: spośród pierwszych 100 punktów 80 leży we wnętrzu koła.

Python
wewnatrz = 0

with open("punkty.txt") as file:
    for line in file:
        x, y = map(int, line.split())
        # porównujemy kwadraty odległości od środka (200, 200) - bez pierwiastków i błędów float
        odleglosc = (x - 200) ** 2 + (y - 200) ** 2
        if odleglosc == 200 ** 2:
            print(x, y)
        elif odleglosc < 200 ** 2:
            wewnatrz += 1

print(wewnatrz)

Odpowiedź: punkty okręgu: (256, 8), (200, 400); wewnątrz koła: 7852

↑
PythonC++23Java 25
Treść zadania

Punkty z pliku punkty.txt (kwadrat o boku 400, środek (200, 200), koło wpisane). Przy równomiernym rozkładzie punktów stosunek liczby punktów w kole n_k do liczby wszystkich punktów n jest w przybliżeniu równy stosunkowi pola koła (πr²) do pola kwadratu. Wyznacz przybliżoną wartość π na podstawie: pierwszych 1000 punktów, pierwszych 5000 punktów oraz wszystkich punktów. Wyniki zaokrąglij do 4 miejsc po przecinku (dla pierwszych 100 punktów wychodzi 3,2000).

Python
punkty = []
with open("punkty.txt") as file:
    for line in file:
        x, y = map(int, line.split())
        punkty.append((x, y))


def przyblizenie_pi(n):
    # punkty należące do koła (razem z brzegiem) spośród n pierwszych
    w_kole = 0
    for x, y in punkty[:n]:
        if (x - 200) ** 2 + (y - 200) ** 2 <= 200 ** 2:
            w_kole += 1
    # nk / n = Pk / P = pi * 200^2 / 400^2 = pi / 4
    return 4 * w_kole / n


for n in [1000, 5000, len(punkty)]:
    print(f"{przyblizenie_pi(n):.4f}")

Odpowiedź: 3,2280; 3,1656; 3,1416

↑
PythonC++23Java 25
Treść zadania

Punkty z pliku punkty.txt; π_n to przybliżenie liczby π wyznaczone (jak w 4.2) z n pierwszych punktów pliku. Błąd bezwzględny definiujemy jako ε_n = |π − π_n|, gdzie π to wartość ze standardowej funkcji używanego narzędzia. Oblicz ε_n dla n = 1, 2, …, 1700 i utwórz czytelny wykres liniowy zmian tego błędu. Wartości ε_1000 i ε_1700, zaokrąglone do 4 miejsc po przecinku, zapisz w wyniki_4.txt.

Python
import math

w_kole = 0
bledy = []  # bledy[n - 1] = |pi - pi_n|

with open("punkty.txt") as file:
    for n in range(1, 1701):
        x, y = map(int, file.readline().split())
        if (x - 200) ** 2 + (y - 200) ** 2 <= 200 ** 2:
            w_kole += 1
        bledy.append(abs(math.pi - 4 * w_kole / n))

# dane do wykresu liniowego: n -> bledy[n - 1]
print(f"{bledy[1000 - 1]:.4f}")
print(f"{bledy[1700 - 1]:.4f}")

Odpowiedź: ε1000 = 0,0864; ε1700 = 0,0184 (+ wykres liniowy)

↑
PythonC++23Java 25
Treść zadania

Szyfr Cezara z kluczem k zastępuje każdą literę literą położoną o k pozycji dalej w alfabecie, cyklicznie (po Z następuje A), np. dla k = 3: B → E, X → A, Z → C. Rozważamy słowa z wielkich liter alfabetu angielskiego (A–Z) o długości do 30 znaków.

W pliku dane_6_1.txt jest 100 słów, każde w osobnym wierszu. Zaszyfruj je kluczem k = 107 i zapisz wynik do wyniki_6_1.txt, każde słowo w osobnym wierszu, w kolejności z pliku. Dla pierwszego słowa INTERPRETOWANIE wynikiem jest LQWHUSUHWRZDQLH.

Python
def szyfruj(slowo, klucz):
    wynik = ""
    for znak in slowo:
        wynik += chr((ord(znak) - 65 + klucz) % 26 + 65)
    return wynik


with open("dane_6_1.txt") as file, open("wyniki_6_1.txt", "w") as wynik:
    for line in file:
        wynik.write(szyfruj(line.strip(), 107) + "\n")

Odpowiedź: plik wyniki_6_1.txt (pierwsze słowo: LQWHUSUHWRZDQLH, ostatnie: DUBVWRWHOHV)

↑
PythonC++23Java 25
Treść zadania

Szyfr Cezara (litery A–Z, przesunięcie cykliczne o k). W pliku dane_6_2.txt jest 3000 wierszy, każdy zawiera szyfrogram i po spacji klucz, którym go zaszyfrowano (co najwyżej czterocyfrowa liczba), np. BCYKUNCM 1718. Odszyfruj słowa i zapisz je do wyniki_6_2.txt, każde w osobnym wierszu, w kolejności z pliku. Dla pierwszego szyfrogramu BCYKUNCM wynikiem jest ZAWISLAK.

Python
def odszyfruj(slowo, klucz):
    wynik = ""
    for znak in slowo:
        wynik += chr((ord(znak) - 65 - klucz) % 26 + 65)
    return wynik


with open("dane_6_2.txt") as file, open("wyniki_6_2.txt", "w") as wynik:
    for line in file:
        dane = line.split()
        slowo = dane[0]
        if len(dane) > 1:
            klucz = int(dane[1])
        else:
            klucz = 0  # w kilku wierszach brakuje klucza - słowo zostaje bez zmian
        wynik.write(odszyfruj(slowo, klucz) + "\n")

Odpowiedź: plik wyniki_6_2.txt (pierwsze słowo: ZAWISLAK, wiersz 10: KREZEL, wiersz 100: KWIATKOWSKI)

↑
PythonC++23Java 25
Treść zadania

Szyfr Cezara (litery A–Z, przesunięcie cykliczne o k). W pliku dane_6_3.txt jest 3000 par słów oddzielonych spacją; drugie słowo jest szyfrogramem pierwszego z nieznanym kluczem (oba mają tę samą długość), np. ZAWISLAK EFBNXQFP. Niektóre szyfrogramy są błędne — litery zakodowano w nich z różnymi przesunięciami. Wypisz do wyniki_6_3.txt te słowa (pierwsze z pary), które zaszyfrowano błędnie, każde w osobnym wierszu, w kolejności z pliku. Pierwszym takim słowem jest SMIGIELSKI.

Python
with open("dane_6_3.txt") as file, open("wyniki_6_3.txt", "w") as wynik:
    for line in file:
        jawne, szyfr = line.split()
        klucz = (ord(szyfr[0]) - ord(jawne[0])) % 26
        poprawne = True
        for i in range(len(jawne)):
            if (ord(szyfr[i]) - ord(jawne[i])) % 26 != klucz:
                poprawne = False
                break
        if not poprawne:
            wynik.write(jawne + "\n")

Odpowiedź: SMIGIELSKI, JANEK, JANUSZEWSKI, WOLAK, GAJEK, MROCZKOWSKI, SZCZESNIAK, CIESLINSKI

↑

Edytuj na GitHubie