Matura informatyka

Matura 2022 — maj, poziom rozszerzony (formuła 2015)

PythonC++23Java 25

Treść zadania (n-permutacja): n-permutacją nazywamy n-elementowy ciąg liczb całkowitych zawierający każdą z liczb 1, 2, …, n dokładnie raz, np. (4,2,1,3) jest 4-permutacją, a (1,3,1,2) czy (2,3,4,5) nie są. W ciągu, który nie jest n-permutacją, można podmienić niektóre elementy, aby nią był – np. w (1,3,1) wystarczy zmienić jedną jedynkę na 2.

  • 1.1 — Dla podanych ciągów wpisz najmniejszą liczbę elementów do podmiany (0, jeśli ciąg już jest n-permutacją): n=4 (1,4,2,5); n=5 (2,2,2,2,2); n=4 (4,2,3,1); n=6 (5,4,1,5,6,8); n=6 (8,4,9,6,5,7). Przykład: n=3 (1,3,1) → 1.
  • 1.2 — Zapisz algorytm, który dla tablicy A[1..n] dodatnich liczb całkowitych obliczy minimalną liczbę k elementów do podmiany, aby powstała n-permutacja. Wolno używać tylko instrukcji sterujących, podstawowych operatorów arytmetycznych (w tym div, mod), logicznych, porównań, odwołań do elementów tablicy i przypisań – bez funkcji wbudowanych.
Python
def do_podmiany(A):
    n = len(A)
    wystapienia = [0] * (n + 1)   # wystapienia[x] - ile razy liczba x (1..n) jest w A
    k = 0
    for x in A:
        if 1 <= x <= n:
            wystapienia[x] += 1
        else:
            k += 1                # liczba spoza [1, n] na pewno do podmiany
    for x in range(1, n + 1):
        if wystapienia[x] > 1:
            k += wystapienia[x] - 1   # wszystkie powtórzenia poza jednym
    return k


for A in [[1, 3, 1], [1, 4, 2, 5], [2, 2, 2, 2, 2], [4, 2, 3, 1], [5, 4, 1, 5, 6, 8], [8, 4, 9, 6, 5, 7]]:
    print(A, do_podmiany(A))

Odpowiedź: 1.1: (1,3,1) → 1, (1,4,2,5) → 1, (2,2,2,2,2) → 4, (4,2,3,1) → 0, (5,4,1,5,6,8) → 2, (8,4,9,6,5,7) → 3. 1.2: do podmiany są liczby spoza [1, n] oraz wszystkie powtórzenia (poza jednym wystąpieniem) liczb z [1, n] — funkcja do_podmiany.

↑
PythonC++23Java 25
Treść zadania

Dla słowa s długości n złożonego z liter a i b wykonujemy algorytm, którego wynikiem jest k:

Kod
A[0] ← 0
dla i = 1..n:   jeżeli s[i] = 'a' to A[i] ← A[i-1] + 1, w p.p. A[i] ← A[i-1]
B[n+1] ← 0
dla j = n..1:   jeżeli s[j] = 'b' to B[j] ← B[j+1] + 1, w p.p. B[j] ← B[j+1]
k ← 1
dla i = 0..n:   jeżeli A[i] + B[i+1] > k to k ← A[i] + B[i+1]
  • 2.1 — Podaj wynik k dla słów aababb (n=6) i baabbaaab (n=9). Przykłady: aabab → 4, ab → 2, aaa → 3.
  • 2.2 — Podaj przykłady dziesięcioliterowych słów, dla których k = 10 oraz k = 5.
  • 2.3 — Zapis aᵐ (bᵐ) oznacza literę a (b) powtórzoną m razy. Podaj wynik k dla słowa a³⁰⁰b⁵⁵⁰a³⁰⁰b⁷a²⁸⁰b¹¹⁰.
Python
def algorytm(s):
    n = len(s)
    s = " " + s                   # indeksowanie od 1 jak w treści
    A = [0] * (n + 2)
    for i in range(1, n + 1):
        if s[i] == "a":
            A[i] = A[i - 1] + 1
        else:
            A[i] = A[i - 1]
    B = [0] * (n + 2)
    for j in range(n, 0, -1):
        if s[j] == "b":
            B[j] = B[j + 1] + 1
        else:
            B[j] = B[j + 1]
    k = 1
    for i in range(0, n + 1):
        if A[i] + B[i + 1] > k:
            k = A[i] + B[i + 1]
    return k


# 2.1
for s in ["aabab", "ab", "aaa", "aababb", "baabbaaab"]:
    print(s, algorytm(s))

# 2.2 - k = najdłuższy podciąg postaci a...ab...b; szukamy przykładów
print("aaaaabbbbb", algorytm("aaaaabbbbb"))
print("bbbbbaaaaa", algorytm("bbbbbaaaaa"))

# 2.3
print(algorytm("a" * 300 + "b" * 550 + "a" * 300 + "b" * 7 + "a" * 280 + "b" * 110))

Odpowiedź: 2.1: aababb → 5, baabbaaab → 6. 2.2: k = 10 np. aaaaabbbbb (wszystkie a przed wszystkimi b), k = 5 np. bbbbbaaaaa. 2.3: k = 990

↑
PythonC++23Java 25

Treść zadania (Liczby): Plik liczby.txt zawiera 200 różnych liczb całkowitych z zakresu [10, 100000], każda w osobnym wierszu. Odpowiedzi zapisz w wyniki4.txt, poprzedzając je numerem zadania (do testów: przyklad.txt).

  • 4.1 — Podaj, ile liczb ma taką samą pierwszą i ostatnią cyfrę, oraz pierwszą taką liczbę w pliku. Dla pliku przykładowego: 26 626.
  • 4.2 — Znajdź liczbę o największej liczbie czynników pierwszych (licząc z powtórzeniami) i podaj ją wraz z tą liczbą czynników, a także liczbę o największej liczbie różnych czynników pierwszych wraz z ich liczbą. Np. 420 = 2·2·3·5·7 ma 5 czynników, w tym 4 różne. Dla pliku przykładowego: 144 6 210 4.
  • 4.3 — Trójka (x, y, z) jest dobra, gdy x dzieli y, y dzieli z i liczby są różne; analogicznie dobra piątka (u, w, x, y, z) – każda kolejna liczba jest podzielna przez poprzednią, wszystkie różne. Liczby mogą stać w pliku w dowolnych miejscach. a) Podaj liczbę dobrych trójek i zapisz je wszystkie do pliku trojki.txt (każdą w osobnym wierszu); b) podaj liczbę dobrych piątek. Dla pliku przykładowego: a) 10, b) 1 (np. trójka 13 26 52).
Python
liczby = []
with open("liczby.txt") as file:
    for line in file:
        liczby.append(int(line))

# 4.1
ile = 0
pierwsza = 0
for x in liczby:
    napis = str(x)
    if napis[0] == napis[-1]:
        if ile == 0:
            pierwsza = x
        ile += 1
print("4.1", ile, pierwsza)


# 4.2
def czynniki(x):
    wszystkie = 0
    rozne = 0
    d = 2
    while d * d <= x:
        if x % d == 0:
            rozne += 1
            while x % d == 0:
                x //= d
                wszystkie += 1
        d += 1
    if x > 1:
        wszystkie += 1
        rozne += 1
    return wszystkie, rozne


max_wsz, liczba_wsz = 0, 0
max_roz, liczba_roz = 0, 0
for x in liczby:
    wszystkie, rozne = czynniki(x)
    if wszystkie > max_wsz:
        max_wsz, liczba_wsz = wszystkie, x
    if rozne > max_roz:
        max_roz, liczba_roz = rozne, x
print("4.2", liczba_wsz, max_wsz, liczba_roz, max_roz)

# 4.3 - liczby w pliku są różne, więc wystarczy x | y, y | z i x != y != z
trojki = 0
with open("trojki.txt", "w") as wyjscie:
    for x in liczby:
        for y in liczby:
            if y != x and y % x == 0:
                for z in liczby:
                    if z != y and z % y == 0:
                        trojki += 1
                        print(x, y, z, file=wyjscie)

# dobre piątki - liczymy rekurencyjnie łańcuchy podzielności długości 5
def lancuchy(ostatnia, dlugosc):
    if dlugosc == 5:
        return 1
    wynik = 0
    for nastepna in liczby:
        if nastepna != ostatnia and nastepna % ostatnia == 0:
            wynik += lancuchy(nastepna, dlugosc + 1)
    return wynik


piatki = 0
for u in liczby:
    piatki += lancuchy(u, 1)
print("4.3", trojki, piatki)

Odpowiedź: 4.1: 18 93639; 4.2: 99792 10 (także 20992 i 56064 mają 10 czynników), 62790 6; 4.3: a) 27 dobrych trójek (np. 955 8595 42975, 232 13688 27376, 13594 27188 81564, …), b) 2 dobre piątki

↑

Edytuj na GitHubie