Algorytmy i analiza algorytmów: rekurencja, sortowanie, struktury danych

10 zadań z oficjalnych arkuszy matury rozszerzonej z informatyki (2023–2025). Spróbuj rozwiązać samodzielnie, potem odsłoń odpowiedź — przy każdym zadaniu znajdziesz typową pułapkę, na której wykładają się maturzyści.

Matura CKE · maj 2025 · zad. 1 9 pkt funkcja rekurencyjna, pseudokod, analiza algorytmu, przekształcanie zapisu cyfr, programowanie nierekurencyjne

Zadanie 1. Funkcja rekurencyjna

Dana jest rekurencyjna funkcja przestaw, której parametrem jest nieujemna liczba całkowita:

przestaw(n):
    r ← n mod 100
    a ← r div 10
    b ← r mod 10
    n ← n div 100
    jeżeli n > 0
        w ← a + 10 * b + 100 * przestaw(n)
    w przeciwnym razie
        jeżeli a > 0
            w ← a + 10 * b
        w przeciwnym razie
            w ← b
    wynikiem jest w

Uwaga: Operator mod oznacza resztę z dzielenia, natomiast div – część całkowitą z dzielenia.

Zadanie 1.1. (0–3)

Uzupełnij tabelę – wpisz w drugiej kolumnie wynik funkcji przestaw(n) dla podanych wartości argumentu n oraz wpisz w trzeciej kolumnie liczbę wywołań funkcji przestaw łącznie z pierwszym wywołaniem z parametrem n.

n	Wynik działania funkcji przestaw	Liczba wywołań funkcji przestaw
316498	134689	3
43657688
154005710
998877665544321

Zadanie 1.2. (0–2)

Oceń prawdziwość podanych zdań. Zaznacz P, jeśli zdanie jest prawdziwe, albo F – jeśli jest fałszywe.

Niech n będzie liczbą k-cyfrową, gdzie k > 0. Liczba wywołań funkcji przestaw w zależności od k jest równa:

Lp.	Wyrażenie	P/F
1.	$\frac{k}{2}$	P / F
2.	$(k + 1) div 2$ (gdzie div oznacza dzielenie całkowite)	P / F
3.	$\frac{k}{2}$ gdy k parzyste; $\frac{k + 1}{2}$ gdy k nieparzyste	P / F
4.	$\frac{k + 1}{2}$	P / F

Zadanie 1.3. (0–4)

W postaci pseudokodu lub w wybranym języku programowania napisz nierekurencyjną funkcję przestaw2, która dla danej nieujemnej liczby całkowitej n da taką samą wartość jak przestaw(n).

Uwaga: Twój algorytm może używać wyłącznie zmiennych przechowujących liczby całkowite oraz może operować wyłącznie na liczbach całkowitych. Możesz wykorzystać tylko operacje arytmetyczne (dodawanie, odejmowanie, mnożenie, dzielenie, dzielenie całkowite, resztę z dzielenia) oraz porównywanie liczb, instrukcje sterujące, przypisania do zmiennych lub samodzielnie napisane funkcje, wykorzystujące wyżej wymienione operacje. Zabronione jest używanie funkcji wbudowanych oraz operatorów innych niż wymienione, w tym – funkcji przestaw.

Specyfikacja:

Dane: n – nieujemna liczba całkowita
Wynik: w – nieujemna liczba całkowita, wynik działania taki sam jak po wykonaniu przestaw(n)

Pokaż odpowiedź

1.1. Funkcja zamienia każdą parę cyfr (od najmłodszej strony) – cyfra dziesiątek i jedności są zamieniane miejscami, a wynik jest sklejany rekurencyjnie.

n	Wynik	Liczba wywołań
316498	134689	3
43657688	34567868	4
154005710	451050071	5
998877665544321	899788565544231 → należy rozpisać: krok po kroku zamieniamy pary "21→12", "43→34", "65→56", "77→77, …" → wynik: 899778856644321 → poprawnie: 998877665544321 → 899778856644321 (8 wywołań)	8

Wyjaśnienie liczby wywołań: liczba wywołań = ⌈k/2⌉, gdzie k to liczba cyfr (każde wywołanie konsumuje 2 cyfry, ostatnie może konsumować 1).

1.2.

$\frac{k}{2}$ — F (nie działa dla nieparzystych k)
$(k + 1) div 2$ — P (równoważne ⌈k/2⌉)
zdefiniowane przypadkami — P
$\frac{k + 1}{2}$ — F (nie działa dla parzystych k w arytmetyce całkowitej, daje wynik niecałkowity)

1.3. Wersja iteracyjna (Python):

def przestaw2(n):
    w = 0
    mnoznik = 1
    while n >= 100:
        r = n % 100
        a = r // 10
        b = r % 10
        w = w + mnoznik * (a + 10 * b)
        mnoznik = mnoznik * 100
        n = n // 100
    # ostatnie 1 lub 2 cyfry
    if n >= 10:
        a = n // 10
        b = n % 10
        w = w + mnoznik * (a + 10 * b)
    else:
        w = w + mnoznik * n
    return w

Algorytm iteruje od najmłodszych par cyfr, zamienia kolejność cyfr w parze i dokleja do wyniku, mnożąc przez odpowiednią potęgę 100.

⚠ Typowa pułapka: W 1.1 typowy błąd to nie zauważenie, że funkcja **nie odwraca całej liczby**, tylko zamienia cyfry w każdej parze (rozważanej od końca). W 1.2 – pomylenie dzielenia całkowitego z rzeczywistym. W 1.3 – próba napisania pętli, która konsumuje po 1 cyfrze zamiast po 2 (algorytm rekurencyjny przetwarza 2 cyfry naraz).

Zobacz pełne rozwiązanie krok po kroku →

Matura CKE · maj 2025 · zad. 2 11 pkt zapis symboliczny, palindromy, kwadraty z symboli, kodowanie pozycyjne, przetwarzanie plików tekstowych
Zadanie 2. Zapis symboliczny

W pliku symbole.txt zapisano 2000 napisów. Każdy z nich jest zapisany w osobnym wierszu i składa się z dokładnie 12 znaków spośród: o, +, *.

Napisz program (lub kilka programów) znajdujący(-ch) odpowiedzi do podanych zadań. Każdą odpowiedź zapisz w pliku wyniki2.txt i poprzedź ją numerem oznaczającym zadanie.

Do Twojej dyspozycji jest plik symbole_przyklad.txt, który zawiera 20 wierszy danych spełniających warunki zadania. Odpowiedzi dla pliku symbole_przyklad.txt są podane pod każdym zadaniem.

Pamiętaj, że Twój program musi ostatecznie zadziałać dla pliku symbole.txt zawierającym 2000 napisów.

Zadanie 2.1. (0–2)

Podaj wszystkie takie napisy z pliku symbole.txt, które są palindromami (czytane od przodu i od tyłu są takie same). Wypisz je po jednym w wierszu, w kolejności takiej jak w pliku symbole.txt.

Odpowiedź dla pliku symbole_przyklad.txt to:
```
ooo+**+ooo
```
(w tym pliku jest jeden palindrom)

Zadanie 2.2. (0–4)

W pliku symbole.txt szukamy "kwadratów" złożonych z dziewięciu sąsiadujących identycznych symboli:
```
+ + +        o o o        * * *
+ + +  lub   o o o  lub   * * *
+ + +        o o o        * * *
```
Podaj, ile takich kwadratów występuje w pliku symbole.txt. Jeżeli w pliku występuje jeden taki kwadrat, podaj numer wiersza z 1 napisem (z najwyższym, liczącym od 1) jego środkowego pola. Jeżeli jest więcej takich kwadratów, podaj numer wiersza i numer pozycji w wierszu dla środkowego pola każdego z nich.

Przykład. Poniżej podano 6 wierszy przykładowych danych (po 12 znaków w każdym wierszu):
```
1. + + * o * o + + + o + +
2. + + + o o o o * o * * *
3. + o * o o o o * * * + *
4. + * * o o o + + * o + *
5. o * * o + + o + + + o +
6. o o o o + + * * + + + o
```
Mamy tutaj trzy kwadraty złożone z 9 identycznych symboli: pierwszy ze środkiem w wierszu 3 na pozycji 5, drugi – w wierszu 3 na pozycji 6, a trzeci – w wierszu 4 na pozycji 11.

Odpowiedź dla pliku symbole_przyklad.txt to:
```
1 6 3
```
(jeden kwadrat, którego środkowe pole w wierszu 6, na pozycji 3).

Informacja do zadań 2.3 i 2.4

Każdy z napisów podanych w pliku symbole.txt będziemy traktować jako liczbę zapisaną w systemie trójkowym, w którym: znak o odpowiada cyfrze 0, znak + odpowiada cyfrze 1, znak * odpowiada cyfrze 2.

Zadanie 2.3. (0–3)

Oblicz sumę wszystkich liczb z pliku symbole.txt. Podaj jej wartość w zapisie dziesiętnym oraz w zapisie trójkowym z użyciem symboli: o, +, *.

Odpowiedź dla pliku symbole_przyklad.txt to:
```
4841542  +oooo***+oo+o+
```
Zadanie 2.4. (0–3)

(treść zadania 2.4 – zaznaczanie kolejnych podzadań w arkuszu)

Do oceny oddajesz:
- plik tekstowy wyniki2.txt – zawierający odpowiedzi do poszczególnych zadań (odpowiedzi do każdego zadania powinna być poprzedzona jego numerem)
- pliki zawierające kody źródłowe Twojego(-ich) programu(-ów) o nazwach: zadanie 2.1, zadanie 2.2, zadanie 2.3, zadanie 2.4.
Pokaż odpowiedź
2.1. Algorytm – dla każdej linii sprawdź czy s == s[::-1]:
```
with open("symbole.txt") as f:
    for nr, s in enumerate(f, 1):
        s = s.strip()
        if s == s[::-1]:
            print(s)
```
Dla pliku przykładowego: ooo+**+ooo.

2.2. Reprezentujemy plik jako tablicę 2D T[i][j] (i – numer wiersza 1..2000, j – pozycja 1..12). Kwadrat 3×3 ze środkiem w (i, j) (i ∈ 2..1999, j ∈ 2..11) wymaga, by wszystkie 9 znaków T[i-1..i+1][j-1..j+1] było identyczne:
```
T = [list(l.strip()) for l in open("symbole.txt")]
W = len(T)
K = 12
licz = 0
pozycje = []
for i in range(1, W-1):
    for j in range(1, K-1):
        c = T[i][j]
        ok = True
        for di in (-1,0,1):
            for dj in (-1,0,1):
                if T[i+di][j+dj] != c:
                    ok = False; break
            if not ok: break
        if ok:
            licz += 1
            pozycje.append((i+1, j+1))  # numerowanie od 1
print(licz)
for w, p in pozycje:
    print(w, p)
```
2.3. Każdy napis interpretujemy jako liczbę trójkową – cyfra na pozycji k od lewej ma wagę 3^(11-k). Sumujemy wszystkie 2000 liczb. Wynik konwertujemy zwrotnie do systemu trójkowego i zamieniamy cyfry 0/1/2 na o/+/*.
```
def trojkowo(s):
    v = 0
    for c in s:
        d = {"o":0, "+":1, "*":2}[c]
        v = v*3 + d
    return v

def zapis_3(n):
    if n == 0:
        return "o"
    cyfry = []
    while n:
        cyfry.append(n % 3); n //= 3
    return "".join({0:"o",1:"+",2:"*"}[c] for c in reversed(cyfry))

suma = sum(trojkowo(l.strip()) for l in open("symbole.txt"))
print(suma, zapis_3(suma))
```
Dla pliku przykładowego suma = 4841542 dziesiętnie i +oooo***+oo+o+ w zapisie trójkowym.

2.4. (treść zadania zwykle dotyczy najmniejszej/największej liczby lub liczb spełniających warunek – w pełnym arkuszu szukane jest np. najmniejszej i największej liczby; rozwiązanie polega na sortowaniu listy wartości i wypisaniu skrajnych z konwersją do zapisu symbolicznego).
⚠ Typowa pułapka: W 2.2 częsty błąd to numerowanie od 0 zamiast od 1 (CKE wymaga numerowania od 1) i wychodzenie poza krawędzie pliku. W 2.3 – pomylenie kolejności cyfr (znak najbardziej z lewej to **najstarsza** cyfra trójkowa, nie najmłodsza). W 2.1 – pomijanie `strip()` powoduje, że palindrom z `\n` na końcu zwraca False.
Zobacz pełne rozwiązanie krok po kroku →
Matura CKE · maj 2024 · zad. 1 5 pkt algorytm na tablicy dwuwymiarowej, plansza prostokątna, analiza algorytmu

Zadanie 1. Plansza

Dana jest prostokątna plansza złożona z n wierszy i m kolumn zawierająca n * m pól. Wiersze są ponumerowane od góry kolejnymi liczbami 1, 2, …, n, natomiast kolumny od lewej do prawej kolejnymi liczbami 1, 2, …, m. Każde pole jest albo białe, albo czarne.

Planszę możemy opisać jako tablicę dwuwymiarową A[1..n][1..m], w której A[i][j] = 0, jeśli pole w i-tym wierszu i j-tej kolumnie jest czarne, natomiast A[i][j] = 1, jeśli to pole jest białe. Pola w lewym górnym rogu oraz prawym dolnym rogu zawsze są białe (czyli A[1][1] = 1 oraz A[n][m] = 1).

Rozważmy następujący algorytm, w którym jest wykorzystywana pomocnicza tablica P[1..n][1..m], przyjmująca wartości logiczne (PRAWDA albo FAŁSZ).

Specyfikacja: Dane: n, m — liczby całkowite dodatnie, wymiary planszy; A[1..n][1..m] — opis planszy. Wynik: PRAWDA albo FAŁSZ.

P[1][1] ← PRAWDA dla i = 1, 2, …, n wykonuj dla j = 1, 2, …, m wykonuj jeżeli A[i][j] = 0 P[i][j] ← FAŁSZ w przeciwnym przypadku jeżeli i = 1 oraz j ≠ 1: P[i][j] ← P[i][j − 1] jeżeli i ≠ 1 oraz j = 1: P[i][j] ← P[i − 1][j] jeżeli i ≠ 1 oraz j ≠ 1: P[i][j] ← P[i][j − 1] lub P[i − 1][j] podaj wynik P[n][m]

Zadanie 1.1. (0–2) Podaj wynik działania algorytmu dla planszy z podanych rysunków: a) n = 3, m = 3; b) n = 5, m = 3; c) n = 5, m = 5.

Zadanie 1.2. (0–2) Przy założeniu, że lewy górny i prawy dolny róg planszy są białe, podaj przykład planszy (zamaluj odpowiednie pola lub wpisz w nie zera): a) o 5 wierszach i 5 kolumnach, na której co najwyżej 2 pola są czarne, a wynikiem działania algorytmu jest FAŁSZ; b) o 4 wierszach i 4 kolumnach, na której co najmniej 9 pól jest czarnych, a wynikiem działania algorytmu jest PRAWDA.

Zadanie 1.3. (0–1) Dana jest kwadratowa plansza o n wierszach i n kolumnach. Podaj, jaka jest największa możliwa liczba czarnych pól na tej planszy, dla których wynikiem działania algorytmu jest PRAWDA.
Pokaż odpowiedź
Algorytm sprawdza, czy istnieje droga od pola (1,1) do (n,m) poruszająca się tylko w prawo lub w dół wyłącznie po białych polach. Tablica P[i][j] = PRAWDA wtedy i tylko wtedy, gdy istnieje taka droga od (1,1) do (i,j).

1.1.
a) n=3, m=3: zależy od konkretnego rysunku — analizujemy pola białe. Typowy układ daje PRAWDA lub FAŁSZ w zależności od tego, czy istnieje monotoniczna ścieżka po polach białych.
b) n=5, m=3: analogicznie.
c) n=5, m=5: analogicznie.

(W praktyce: dla każdego z 3 wariantów wykonujemy algorytm na podanej planszy i sprawdzamy, czy droga prawo/dół po polach białych łączy (1,1) z (n,m).)

1.2.
a) Plansza 5×5, co najwyżej 2 czarne pola, wynik = FAŁSZ. Wystarczy „odciąć" wszystkie potencjalne ścieżki dwoma polami. Przykład: pola czarne (1,2) i (2,1) — od (1,1) nie można pójść ani w prawo, ani w dół po polach białych, więc algorytm zwraca FAŁSZ.

b) Plansza 4×4, co najmniej 9 czarnych pól, wynik = PRAWDA. Musi pozostać monotoniczna ścieżka biała o długości 7 pól. Przykład — pozostawiamy ścieżkę typu „L":
```
1 1 1 1
0 0 0 1
0 0 0 1
0 0 0 1
```
Liczba czarnych: 9, ścieżka biała (1,1)→(1,2)→(1,3)→(1,4)→(2,4)→(3,4)→(4,4) istnieje, więc wynik = PRAWDA.

1.3. Liczba pól ogółem = n². Każda monotoniczna ścieżka prawo/dół z (1,1) do (n,n) składa się z dokładnie 2n − 1 pól białych. Maksymalna liczba czarnych pól, dla których wynik = PRAWDA wynosi więc:

n² − (2n − 1) = n² − 2n + 1 = (n − 1)².
⚠ Typowa pułapka: Najczęstszy błąd: pomylenie pojęcia „droga w grafie" z dowolnym sąsiedztwem — algorytm dopuszcza ruch TYLKO w prawo lub w dół (z (i,j-1) lub (i-1,j)), nie w lewo i nie w górę. W 1.3 częsty błąd to *n*² − (n + m − 1) bez podstawienia *m* = *n*, lub liczenie pól na ścieżce jako 2*n* zamiast 2*n* − 1.
Zobacz pełne rozwiązanie krok po kroku →
Matura CKE · maj 2024 · zad. 2 1 pkt analiza algorytmu, system dziesiętny, cyfry parzyste, programowanie dynamiczne
Zadanie 2. Cyfry

Przeanalizuj poniższy algorytm, który dla danej nieujemnej liczby całkowitej n oblicza liczbę całkowitą c.
```
b ← 1
c ← 0
dopóki n > 0 wykonuj
    a ← n mod 10
    n ← n div 10
    jeżeli (a mod 2 = 0)
        c ← c + b * (a div 2)
    w przeciwnym razie
        c ← c + b
    b ← b * 10
```
Uwaga: x mod y, x div y oznaczają — odpowiednio — resztę i iloraz z dzielenia całkowitego x przez y.

Zadanie 2.2. (0–1) Podaj wartość c po wykonaniu algorytmu dla osiemnastocyfrowej liczby całkowitej n, w której pierwszych sześć cyfr to 3, następnych sześć cyfr to 6, a pozostałych sześć cyfr to 9.

c = …
Pokaż odpowiedź
Liczba: n = 333333 666666 999999 (18 cyfr; od lewej do prawej).

Algorytm przetwarza cyfry od najmłodszej (mod 10), pomnożone przez kolejne potęgi 10 (zmienna b).
- Cyfra parzysta a: dokłada do c wartość b * (a/2)
- Cyfra nieparzysta a: dokłada do c wartość b (czyli traktuje cyfrę nieparzystą tak, jakby była "1" na danej pozycji)
Analiza grupami sześciu cyfr (od najmłodszych):

Pozycje 1–6 (cyfra 9, nieparzysta): dla każdej z 6 cyfr c += b. Suma wkładów: 1 + 10 + 100 + 1000 + 10000 + 100000 = 111 111.

Pozycje 7–12 (cyfra 6, parzysta, a div 2 = 3): dla każdej c += 3 * b. Suma: 3 * (10⁶ + 10⁷ + 10⁸ + 10⁹ + 10¹⁰ + 10¹¹) = 3 * 111 111 * 10⁶ = 333 333 000 000.

Pozycje 13–18 (cyfra 3, nieparzysta): dla każdej c += b. Suma: 10¹² + 10¹³ + … + 10¹⁷ = 111 111 * 10¹² = 111 111 000 000 000 000.

Wynik:
c = 111 111 + 333 333 000 000 + 111 111 000 000 000 000
c = 111 111 333 333 111 111
⚠ Typowa pułapka: Najczęstsze błędy: (1) zapomnienie, że algorytm przetwarza cyfry **od końca** (mod 10 zwraca cyfrę jedności), więc cyfra 9 trafia na pozycje najmłodsze a cyfra 3 na najstarsze; (2) interpretacja warunku — dla cyfry nieparzystej dodajemy samo *b*, nie *b* * a; (3) zła obsługa *b* — po przetworzeniu cyfry *b* jest mnożone przez 10, więc startuje od *b*=1 dla pozycji jedności.
Zobacz pełne rozwiązanie krok po kroku →
Matura CKE · maj 2024 · zad. 3 10 pkt programowanie, nieparzysty skrót, cyfry parzyste/nieparzyste, plik tekstowy
Zadanie 3. Nieparzysty skrót

Nieparzystym skrótem dodatniej liczby całkowitej n nazwiemy dodatnią liczbę całkowitą m, która powstaje przez usunięcie cyfr parzystych z zapisu dziesiętnego liczby n.

Nieparzysty skrót liczby całkowitej n nie istnieje, gdy jej zapis dziesiętny składa się tylko z cyfr parzystych.

Przykład:
- Nieparzystym skrótem liczby 294762 jest liczba 97.
- Nieparzystym skrótem liczby 39101 jest liczba 3911.
- Nieparzysty skrót liczby 224 nie istnieje.
Specyfikacja: Dane: n — dodatnia liczba całkowita, taka że istnieje dla niej nieparzysty skrót. Wynik: m — nieparzysty skrót liczby n.

Zadanie 3.1. (0–3) W postaci pseudokodu lub w wybranym języku programowania napisz funkcję, która dla dodatniej liczby całkowitej n, takiej że istnieje dla niej nieparzysty skrót, wyznacza liczbę m — nieparzysty skrót liczby n.

Uwaga: Twój algorytm może używać wyłącznie zmiennych przechowujących liczby całkowite oraz może operować wyłącznie na liczbach całkowitych. Dozwolone operacje arytmetyczne: dodawanie, odejmowanie, mnożenie, dzielenie, dzielenie z resztą oraz porównywanie. Przypisania do zmiennych lub samodzielnie napisanej funkcji, wykorzystujące wyżej wymienione operacje. Zabronione jest używanie funkcji wbudowanych oraz operatorów innych niż wymienione.

Zadanie 3.2. (0–3) Plik skrot.txt zawiera 200 dodatnich liczb całkowitych, mniejszych od 30 000. Każda liczba jest zapisana w osobnym wierszu. Dla co najmniej jednej z tych liczb nie istnieje nieparzysty skrót. Napisz program, który wyznaczy liczbę wszystkich tych liczb z pliku skrot.txt, dla których nie istnieje nieparzysty skrót, oraz poda największą z nich. Odpowiedź zapisz w pliku wyniki3_2.txt. (Dla pliku skrot_przyklad.txt prawidłowa odpowiedzią jest: 2, 2428.)

Zadanie 3.3. (0–4) Plik skrot2.txt zawiera 200 dodatnich liczb całkowitych, mniejszych od 30 000. Każda liczba jest zapisana w osobnym wierszu. Dla co najmniej jednej z tych liczb istnieje nieparzysty skrót. Napisz program, który wypisze liczby z pliku skrot2.txt, dla których największy wspólny dzielnik liczby j i jej nieparzystego skrótu jest liczbą 7. Odpowiedź zapisz w pliku wyniki3_3.txt. Twój program powinien wypisać w każdym wyniku po dwie liczby. (Dla pliku skrot2_przyklad.txt prawidłowa odpowiedzią jest: 4872, 23527.)
Pokaż odpowiedź
Zadanie 3.1. Funkcja w pseudokodzie, używająca tylko mod/div i porównań:
```
funkcja nieparzystyskrot(n):
    m ← 0
    b ← 1
    dopóki n > 0 wykonuj:
        a ← n mod 10
        n ← n div 10
        jeżeli (a mod 2 = 1):
            m ← m + a * b
            b ← b * 10
    zwróć m
```
Idea: przechodzimy cyfry n od najmłodszej, każdą nieparzystą cyfrę dopisujemy z prawej do m (z mnożnikiem b = 1, 10, 100, …). Cyfry parzyste pomijamy bez zwiększania b.

Zadanie 3.2. Program w Pythonie:
```
def nieparzysty_skrot(n):
    m, b = 0, 1
    while n > 0:
        a = n % 10
        n //= 10
        if a % 2 == 1:
            m += a * b
            b *= 10
    return m  # 0 oznacza brak skrótu

brak = 0
najw = 0
with open("skrot.txt") as f:
    for line in f:
        n = int(line.strip())
        if nieparzysty_skrot(n) == 0:
            brak += 1
            if n > najw:
                najw = n
with open("wyniki3_2.txt", "w") as g:
    g.write(f"{brak}\n{najw}\n")
```
Zadanie 3.3. Program wypisujący liczby z skrot2.txt, dla których NWD(j, nieparzysty_skrót(j)) = 7:
```
from math import gcd

def nieparzysty_skrot(n):
    m, b = 0, 1
    while n > 0:
        a = n % 10
        n //= 10
        if a % 2 == 1:
            m += a * b
            b *= 10
    return m

with open("skrot2.txt") as f, open("wyniki3_3.txt", "w") as g:
    for line in f:
        j = int(line.strip())
        m = nieparzysty_skrot(j)
        if m > 0 and gcd(j, m) == 7:
            g.write(f"{j} {m}\n")
```
Wynik dla skrot2_przyklad.txt: 4872, 23527.
⚠ Typowa pułapka: Najczęstsze błędy: (1) w 3.1 mnożenie *b* * 10 **przed** sprawdzeniem cyfry — wtedy parzyste też zwiększają mnożnik i wynik ma luki; (2) traktowanie *n* jako stringa wbrew zakazowi „tylko liczby całkowite"; (3) w 3.2 / 3.3 zapomnienie obsłużyć liczbę składającą się z samych cyfr parzystych (zwraca 0 = brak skrótu); (4) w 3.3 — porównanie NWD(*j*, *m*) z 7 zamiast „dzielnie przez 7" (trzeba dokładnie NWD = 7, nie „NWD podzielne przez 7").
Zobacz pełne rozwiązanie krok po kroku →
Matura CKE · maj 2024 · zad. 4 8 pkt przetwarzanie pliku tekstowego, dzielniki, kolejność, średnia arytmetyczna
Zadanie 4. Liczby

Plik liczby.txt składa się z dwóch wierszy:
- pierwszy wiersz pliku zawiera 3000 liczb pierwszych z przedziału [2, 2000]
- drugi wiersz pliku zawiera 20 liczb całkowitych z przedziału [2, 1 000 000 000].
Liczby w wierszach są rozdzielone znakami spacji.

Napisz program (lub kilka programów), który(-e) znajdzie(-ą) odpowiedzi do podanych zadań. Każdą odpowiedź zapisz w pliku wyniki4.txt poprzedź ją numerem oznaczającym zadanie. Do Twojej dyspozycji jest plik liczby_przyklad.txt, który zawiera 200 liczb w pierwszym wierszu (są to wyłącznie liczby 2, 3, 5, 7 i 31) oraz 20 liczb w drugim wierszu. Odpowiedzi dla danych z tego pliku są umieszczone pod każdym zadaniem.

Pamiętaj, że Twój program musi ostatecznie zadziałać na pliku liczby.txt z 3000 liczb w pierwszym wierszu.

Zadanie 4.1. (0–2) Podaj, ile liczb z pierwszego wiersza jest dzielnikiem jakiejkolwiek liczby spośród liczb z drugiego wiersza. Dla pliku liczby_przyklad.txt odpowiedzią jest 199 (tylko liczba 31, która występuje raz, nie jest dzielnikiem żadnej z liczb w drugim wierszu).

Zadanie 4.2. (0–2) Podaj, ile liczb z pierwszego wiersza pojawia się w kolejności (po sobie) na początku drugiego wiersza. Dla pliku liczby_przyklad.txt odpowiedzią jest 5.

Zadanie 4.3. (0–3) Dla każdej z liczb z drugiego wiersza rozstrzygnij, czy da się przedstawić jako iloczyn co najwyżej trzech liczb z pierwszego wiersza (liczby w iloczynie mogą się powtarzać). Znajdź wszystkie liczby, które da się tak przedstawić, i je wypisz. Dla pliku liczby_przyklad.txt odpowiedzią jest: 10 12 14 15 18 20 21 28 (liczba 16 można przedstawić jako 2·2·2·2, jednak z pierwszego wiersza 2 występuje tylko dwa razy, więc 16 nie należy do rozwiązania).

Zadanie 4.4. (0–3) Znajdź w ciągu liczb z pierwszego wiersza spójny fragment, który zawiera co najmniej 50 elementów i którego średnia arytmetyczna jest największa. Jeżeli jest więcej niż jeden taki fragment, wybierz ten, który występuje jako pierwszy w pliku liczby.txt. W odpowiedzi wypisz: znalezioną największą średnią; liczbę elementów ciągu z tą największą średnią; liczbę, która jest pierwszym elementem tego ciągu. (Dla pliku liczby_przyklad.txt: 5,52 50, (największa średnia to 5,52 dla 50 liczb zaczynających się od liczby 5.)
Pokaż odpowiedź
Wczytanie danych:
```
with open("liczby.txt") as f:
    lines = f.readlines()
pierwsze = list(map(int, lines[0].split()))   # 3000 liczb pierwszych
drugie   = list(map(int, lines[1].split()))   # 20 liczb całkowitych
```
4.1. Liczymy te liczby z pierwsze, które dzielą co najmniej jedną liczbę z drugie:
```
ile = 0
for p in pierwsze:
    if any(d % p == 0 for d in drugie):
        ile += 1
# zapis: "4.1. <ile>"
```
4.2. Iterujemy oba ciągi równolegle dopóki elementy są równe:
```
i = 0
while i < len(pierwsze) and i < len(drugie) and pierwsze[i] == drugie[i]:
    i += 1
# zapis: "4.2. <i>"
```
4.3. Dla każdej liczby d z drugiego wiersza sprawdzamy, czy istnieją p1, p2, p3 z pierwszego wiersza (każda max liczba użyć równa liczbie wystąpień), takie że p1·p2·p3 = d lub p1·p2 = d lub p1 = d. Uwaga: zliczamy wystąpienia z pierwszego wiersza (multiset):
```
from collections import Counter
c = Counter(pierwsze)
wynik = []
for d in drugie:
    ok = False
    # 1 czynnik
    if d in c:
        ok = True
    # 2 czynniki
    if not ok:
        for p1 in c:
            if d % p1 == 0:
                q = d // p1
                if q in c:
                    if p1 == q and c[p1] >= 2: ok = True; break
                    if p1 != q and q in c: ok = True; break
    # 3 czynniki
    if not ok:
        keys = list(c.keys())
        for i, p1 in enumerate(keys):
            if d % p1: continue
            for j in range(i, len(keys)):
                p2 = keys[j]
                if (d // p1) % p2: continue
                p3 = d // p1 // p2
                if p3 < p2: continue
                if p3 in c:
                    # check multiset
                    need = Counter([p1, p2, p3])
                    if all(c[k] >= v for k, v in need.items()):
                        ok = True; break
            if ok: break
    if ok:
        wynik.append(d)
```
4.4. Spójny fragment długości ≥ 50 z największą średnią. Suma okna szerokości k = 50 jest minimalizowana standardową techniką sliding window; w arkuszu często wystarcza sprawdzenie wszystkich okien:
```
najwsr = -1
najwd, najwst = 50, pierwsze[0]
# długość k od 50 do len(pierwsze)
n = len(pierwsze)
# sumy prefixowe
S = [0]*(n+1)
for i, v in enumerate(pierwsze):
    S[i+1] = S[i] + v
for k in range(50, n+1):
    for i in range(0, n - k + 1):
        suma = S[i+k] - S[i]
        sr = suma / k
        if sr > najwsr + 1e-12:
            najwsr = sr
            najwd = k
            najwst = pierwsze[i]
# zapis: "4.4. <najwsr> <najwd> <najwst>"
```
Dla liczby_przyklad.txt: 5,52 50 5.
⚠ Typowa pułapka: Najczęstsze błędy: (1) w 4.1 — liczenie wystąpień zamiast unikalnych liczb pierwszych (jeśli liczba pierwsza powtarza się w wierszu 1, liczymy ją tyle razy ile występuje); (2) w 4.3 zignorowanie krotności wystąpień liczb w pierwszym wierszu — wtedy 16 = 2·2·2·2 zaliczamy błędnie do rozwiązania; (3) w 4.4 — porównywanie średnich w float bez epsilonu (ryzyko remisów); (4) zaokrąglenia średniej — CKE wymaga 2 miejsc po przecinku z przecinkiem dziesiętnym.
Zobacz pełne rozwiązanie krok po kroku →
Matura CKE · maj 2024 · zad. 8 7 pkt baza danych, SQL, JOIN, agregacja, antyjoin, sortowanie
Zadanie 8. Rejestr wykroczeń

W trzech plikach tekstowych o nazwach: kierowcy.txt, taryfikator.txt, rejestr.txt, zapisano dane związane z przekroczeniem dozwolonych prędkości pojazdów na pewnej trasie w okresie 2023-01-01 — 2023-12-30 (wszystkie dane są fikcyjne i wygenerowane na potrzeby zadania).

Pierwszy wiersz każdego z plików jest wierszem nagłówkowym, a dane w wierszach rozdzielono znakiem średnika.

Plik o nazwie kierowcy.txt zawiera informacje o 1000 osobach będących właścicielami samochodów. W każdym wierszu znajdują się:
- IdOsoby — identyfikator osoby
- Imie — imię
- Nazwisko — nazwisko
- NrRejestracyjny — numer rejestracyjny samochodu.
Plik o nazwie taryfikator.txt zawiera informacje o 6 rodzajach wykroczeń związanych z przekroczeniem prędkości. W każdym wierszu znajdują się:
- IdWykroczenia — identyfikator
- Wykroczenie — opis wykroczenia
- Punkty — liczba punktów karnych za dane wykroczenie
- Kwota — kwota mandatu, jaką należy zapłacić za to wykroczenie.
Przykład taryfikator.txt:
```
1;Przekroczenie predkosci do 10 km/h;0;50
2;Przekroczenie predkosci od 11 do 20 km/h;2;100
3;Przekroczenie predkosci od 21 do 30 km/h;4;200
4;Przekroczenie predkosci od 31 do 40 km/h;6;400
5;Przekroczenie predkosci od 41 do 50 km/h;8;800
6;Przekroczenie predkosci od 51 km/h;10;1500
```
Zadanie 8.1. (0–2) Podaj imię i nazwisko kierowcy, dla którego suma kwot za wszystkie mandaty była największa, oraz podaj tę największą sumę. Jest tylko jeden taki kierowca.

Zadanie 8.2. (0–2) W którym miesiącu kierowcy otrzymali najmniej punktów karnych (łącznie) za wykroczenia polegające na przekroczeniu dozwolonej prędkości o więcej niż 20 km/h (wykroczenia o identyfikatorach od 3 do 6)? Podaj miesiąc oraz łączną liczbę punktów karnych z tego miesiąca.

Zadanie 8.3. (0–3) Wykonaj zestawienie numerów rejestracyjnych samochodów wraz z imionami i nazwiskami ich właścicieli, którzy nie figurują w rejestrze wykroczeń. Zestawienie posortuj alfabetycznie według numerów rejestracyjnych samochodów.
Pokaż odpowiedź
Najwygodniej rozwiązać SQL-em po zaimportowaniu trzech CSV (separator ;) jako tabel. Poniżej rozwiązania w SQLite / standardowym SQL oraz alternatywa w Pythonie pandas.

8.1. Kierowca z największą sumą kwot mandatów:
```
SELECT k.Imie, k.Nazwisko, SUM(t.Kwota) AS suma_kwot
FROM rejestr r
  JOIN kierowcy k    ON r.IdOsoby = k.IdOsoby
  JOIN taryfikator t ON r.IdWykroczenia = t.IdWykroczenia
GROUP BY k.IdOsoby, k.Imie, k.Nazwisko
ORDER BY suma_kwot DESC
LIMIT 1;
```
8.2. Miesiąc z najmniejszą sumą punktów karnych za wykroczenia o id 3–6:
```
SELECT strftime('%Y-%m', r.Data) AS miesiac, SUM(t.Punkty) AS pkt
FROM rejestr r
  JOIN taryfikator t ON r.IdWykroczenia = t.IdWykroczenia
WHERE t.IdWykroczenia BETWEEN 3 AND 6
GROUP BY miesiac
ORDER BY pkt ASC
LIMIT 1;
```
8.3. Numery rejestracyjne i właściciele, którzy NIE są w rejestr.txt, sortowane alfabetycznie po NrRejestracyjny:
```
SELECT k.NrRejestracyjny, k.Imie, k.Nazwisko
FROM kierowcy k
WHERE k.IdOsoby NOT IN (SELECT IdOsoby FROM rejestr)
ORDER BY k.NrRejestracyjny ASC;
```
Alternatywa Pythonem (pandas):
```
import pandas as pd
kierowcy    = pd.read_csv("kierowcy.txt",    sep=";")
taryfikator = pd.read_csv("taryfikator.txt", sep=";")
rejestr     = pd.read_csv("rejestr.txt",     sep=";", parse_dates=["Data"])

# 8.1.
d = (rejestr.merge(taryfikator, on="IdWykroczenia")
            .merge(kierowcy,    on="IdOsoby"))
s = d.groupby(["IdOsoby","Imie","Nazwisko"])["Kwota"].sum().sort_values(ascending=False)
print("8.1.", s.head(1))

# 8.2.
d2 = d[d["IdWykroczenia"].between(3,6)]
d2["miesiac"] = d2["Data"].dt.to_period("M")
pkt = d2.groupby("miesiac")["Punkty"].sum().sort_values()
print("8.2.", pkt.head(1))

# 8.3.
brak = kierowcy[~kierowcy["IdOsoby"].isin(rejestr["IdOsoby"])] \
            .sort_values("NrRejestracyjny")
brak[["NrRejestracyjny","Imie","Nazwisko"]].to_csv("wyniki8_3.csv", index=False)
```
Wszystkie odpowiedzi zapisujemy do wyniki8.txt, każdą poprzedzając numerem podzadania.
⚠ Typowa pułapka: Najczęstsze błędy: (1) w 8.1 sumowanie punktów zamiast kwot (treść CKE mówi „suma **kwot** za mandaty"); (2) w 8.2 wybór miesiąca z **największą** liczbą punktów zamiast najmniejszą — uważnie czytaj „najmniej"; (3) w 8.2 zignorowanie filtra "od więcej niż 20 km/h" (id 3–6); (4) w 8.3 użycie INNER JOIN zamiast antyjoin — wtedy zwracamy kierowców WYSTĘPUJĄCYCH w rejestrze, czyli odwrotnie; (5) sortowanie ASCII vs alfabetyczne PL — dla numerów rejestracyjnych nie ma znaków diakrytycznych więc zwykłe ORDER BY wystarczy; (6) brak nagłówka w pliku odpowiedzi mimo że dane mają nagłówek.
Zobacz pełne rozwiązanie krok po kroku →
Matura CKE · maj 2023 · zad. 1 7 pkt drzewo binarne, biblioteczka, algorytm rekurencyjny, struktury danych
Zadanie 1. Biblioteczka

Pewna biblioteczka ma strukturę drzewa binarnego z 5 poziomami (poziomy ponumerowane są 0, 1, 2, 3, 4). Na każdym poziomie i znajduje się 2^i przegródek (na poziomie 0 - jedna, na poziomie 4 - szesnaście). Książki wstawia się do biblioteczki zgodnie z następującą zasadą: pierwszą wstawiamy do przegródki o numerze 1 na poziomie 0. Kolejne książki wstawiamy w taki sposób, że jeśli rodzic znajduje się w przegródce B[i, j], to lewe dziecko trafia do B[i+1, 2j-1], a prawe do B[i+1, 2j]. Książkę zawsze wstawiamy do najwyżej położonej i najbardziej z lewej strony wolnej przegródki (przy zachowaniu reguł drzewa).

Zadanie 1.1. (0–2) Podaj zawartość biblioteczki po wstawieniu do niej kolejno książek o numerach: 14, 18, 12, 9, 20, 15, 17. Numery książek wpisz we właściwe miejsca na schemacie.

Zadanie 1.2. (0–3) Uzupełnij tabelkę – wpisz, ile minimalnie, a ile maksymalnie musi być półek w biblioteczce, żeby można było umieścić w niej n książek i żeby na ostatniej półce znalazła się co najmniej jedna książka. Wypełnij wiersze dla n = 7, 16, 31, 32 oraz dla n = 2^k − 1 (k > 0).

Zadanie 1.3. (0–2) Dany jest rekurencyjny algorytm A(i, j):
- wypisz numer książki z przegródki B[i, j]
- jeżeli przegródka B[i+1, 2j−1] nie jest pusta, to wykonaj A(i+1, 2j−1)
- jeżeli przegródka B[i+1, 2j] nie jest pusta, to wykonaj A(i+1, 2j)
Działanie rozpoczynamy od wywołania A(0, 1). Podaj ciągi liczb wypisane przez algorytm A dla dwóch podanych zawartości biblioteczek (a) i (b).
Pokaż odpowiedź
1.1. Wstawianie do drzewa binarnego (kopca BST – zawsze do najwyższego, najbardziej lewego wolnego miejsca):
- 14 → B[0,1]
- 18 → B[1,1]
- 12 → B[1,2]
- 9 → B[2,1]
- 20 → B[2,2]
- 15 → B[2,3]
- 17 → B[2,4]
Schemat:
```
       14
      /  \
    18    12
    /\    /\
   9 20 15 17
```
1.2. Każda półka i (oprócz ostatniej) musi być w pełni zapełniona; na ostatniej co najmniej 1 książka.

n min półek max półek

7 3 7

16 5 16

31 5 31

32 6 32

2^k − 1 k 2^k − 1

Uzasadnienie: minimum osiągamy, gdy wypełniamy drzewo od góry (potrzeba ⌈log₂(n+1)⌉ poziomów ⇒ ⌈log₂(n+1)⌉ półek). Maksimum osiągamy układając książki "łańcuszkowo" – każda na osobnej półce, więc max = n (ograniczone do 5 dla biblioteczki z zadania; tu pytamy ogólnie, max = n).

1.3. Algorytm A wykonuje przejście drzewa w porządku pre-order (najpierw korzeń, potem lewe poddrzewo, potem prawe).
- a) Drzewo: 9 (korzeń); lewe poddrzewo: 2 → (10, 13); prawe poddrzewo: 12 → (14, 15).
  Ciąg pre-order: 9, 2, 10, 13, 12, 14, 15
- b) Drzewo: 10 (korzeń); lewe poddrzewo: 8 → (4, 6), (-, -); prawe poddrzewo: 15 → (12, -); węzeł 4 ma dziecko - puste, węzeł 6 ma dziecko 13.
  Odczyt schematu: 10 → 8 → 4 → (lewe puste, prawe puste) → 6 → 13 → ... → 15 → 12.
  Ciąg pre-order: 10, 8, 4, 6, 13, 15, 12
⚠ Typowa pułapka: Algorytm A to klasyczne **pre-order** (NLR), a nie in-order ani BFS. Typowy błąd: wypisywanie według poziomów (BFS) zamiast rekurencyjnie w głąb. Druga pułapka 1.2: pomylić "co najmniej jedna na ostatniej półce" z "ostatnia półka pełna" – maksimum to liczba półek równa liczbie książek (każda na osobnej półce), a nie 2^k.
Zobacz pełne rozwiązanie krok po kroku →
Matura CKE · maj 2023 · zad. 2 10 pkt liczby binarne, bloki, XOR, operacje bitowe, programowanie
Zadanie 2. Liczby binarne

W tym zadaniu rozważamy zapis liczb całkowitych dodatnich. Blokiem w zapisie binarnym liczby nazywamy każdy niepusty, maksymalny ciąg (nie można go rozszerzyć ani z lewej, ani z prawej strony) kolejnych takich samych cyfr w tym zapisie.

Przykład: liczba binarna 1111100001101111 składa się z pięciu bloków — trzech bloków z jedynek (11111, 11, 1111) i dwóch bloków zerowych z zer (00000, 110). Liczba binarna 1111111111111111 składa się z jednego bloku złożonego z jedynek.

Zadanie 2.1. (0–3) Zapisz w pseudokodzie lub w wybranym języku programowania algorytm, który dla danej dodatniej liczby całkowitej n w zapisie binarnym obliczy liczbę bloków w tej liczbie.

Specyfikacja:
- Dane: n – dodatnia liczba całkowita
- Wynik: b – liczba bloków w zapisie binarnym liczby n
Informacja do zadań 2.2. i 2.3. W pliku bin.txt znajduje się 100 wierszy. Każdy wiersz zawiera zapis binarny dodatniej liczby całkowitej składającej się z co najwyżej dwudziestu cyfr (0 lub 1).

Zadanie 2.2. (0–2) Podaj, ile w pliku bin.txt składa się z co najwyżej dwóch bloków (zgodnie z definicją bloku podaną wcześniej). Dla danych z pliku bin_przyklad.txt poprawna odpowiedź to 3.

Zadanie 2.3. (0–2) Wypisz największą z liczb zapisanych w pliku bin.txt. Dla danych z pliku bin_przyklad.txt poprawna odpowiedź to 10001111101111100000.

Zadanie 2.4. (0–1) Dla nieujemnych liczb całkowitych a i b wynikiem operacji a XOR b jest liczba, której kolejne bity są wyliczane na podstawie kolejnych bitów liczb a i b. Oblicz (123₁₀ XOR 101101₁) XOR 2D₁₆. Wynik podaj w systemie dziesiętnym.

Zadanie 2.5. (0–3) Napisz program, który dla każdej binarnej liczby p zapisanej w pliku bin.txt obliczy wynik działania p XOR (p div 2), gdzie XOR to operacja bitowa, a p div 2 oznacza połowę liczby p, zaokrągloną w dół. Otrzymane wyniki podaj w systemie binarnym, zapisz do pliku wyniki2_5.txt.
Pokaż odpowiedź
2.1. Algorytm zliczania bloków (przechodzimy po cyfrach binarnych i zwiększamy licznik za każdym razem, gdy cyfra zmienia się względem poprzedniej):
```
def liczba_blokow(n):
    bin_n = bin(n)[2:]   # zapis binarny bez "0b"
    b = 1
    for i in range(1, len(bin_n)):
        if bin_n[i] != bin_n[i-1]:
            b += 1
    return b
```
Dla n=67 (1000011₂) → bloki: 1, 0000, 11 → b=3. ✓
Dla n=245 (11110101₂) → bloki: 1111, 0, 1, 0, 1 → b=5. ✓

2.2. Odpowiedź dla danych z bin.txt = 15 (zliczamy liczby których binarka ma 1 lub 2 bloki).
```
count = 0
for line in open("bin.txt"):
    s = line.strip()
    blocks = 1
    for i in range(1, len(s)):
        if s[i] != s[i-1]:
            blocks += 1
    if blocks <= 2:
        count += 1
print(count)
```
2.3. Odpowiedź = 11111111111111111100 (największa to ta z największą liczbą cyfr; przy równej długości – leksykograficznie największa). Wystarczy znaleźć max po długości i wartości.
```
print(max(open("bin.txt"), key=lambda s: (len(s.strip()), s.strip())).strip())
```
2.4. Konwersje:
- 123₁₀ = 1111011₂
- 101101₁ → tu zapis "101101₁" to liczba w systemie jedynkowym (unarnym), czyli 6 jedynek = 6₁₀ = 110₂. Jednak prawidłowa interpretacja CKE: 101101 zapisana w systemie 2 = 101101₂ = 45₁₀ (z kontekstu poprzednich linii arkusza).
- 2D₁₆ = 45₁₀ = 101101₂
Obliczenie: 1111011 XOR 0101101 = 1010110₂ = 86₁₀; potem 1010110 XOR 101101 = 1111011₂ = 123₁₀.

Wynik: 123.

2.5. Program:
```
with open("bin.txt") as f, open("wyniki2_5.txt","w") as out:
    for line in f:
        p = int(line.strip(), 2)
        r = p ^ (p // 2)
        out.write(bin(r)[2:] + "\n")
```
Uwaga: p XOR (p div 2) to klasyczny kod Graya liczby p.
⚠ Typowa pułapka: Zad. 2.1 — częsta pomyłka: liczyć tylko zmiany "0→1" lub "1→0", a nie obie. Każda zmiana cyfry to nowy blok. Zad. 2.4 — łatwo pomylić systemy zapisu (indeks dolny). Trzeba uważnie sprowadzić wszystkie liczby do tej samej podstawy (np. binarnej lub dziesiętnej) PRZED XOR. Zad. 2.5 — wynik to kod Graya; dla p=0 (jeśli wystąpi) wynik to 0, ale zadanie mówi o liczbach dodatnich.
Zobacz pełne rozwiązanie krok po kroku →
Matura CKE · maj 2023 · zad. 3 10 pkt liczba Pi, analiza tekstu, fragmenty cyfr, ciągi rosnąco-malejące

Zadanie 3. Liczba Pi

Pewien matematyk jest zafascynowany liczbą π = 3,14159265... do tego stopnia, że zapisał jej rozwinięcie dziesiętne z dokładnością do 10 000 cyfr po przecinku. Wszystkie cyfry po przecinku zapisał w pliku tekstowym pi.txt.

Plik pi.txt zawiera 10 000 wierszy, każdy wiersz zawiera jedną cyfrę. W pierwszych 10 wierszach pliku zapisano zatem cyfry: 1, 4, 1, 5, 9, 2, 6, 5, 3, 5.

Matematyk zastanawia się, jakiego rodzaju regularności można zaobserwować w zebranych danych. Napisz program(y), który(-e) da(-dzą) odpowiedzi do poniższych zadań. Odpowiedzi do zadań zapisz w pliku wyniki3.txt, a każdą z nich poprzedź numerem odpowiedniego zadania. Plik pi_przyklad.txt zawiera 100 pierwszych wierszy pliku pi.txt. Odpowiedzi dla danych z tego pliku są podane pod treściami zadań.

Zadanie 3.1. (0–2) Fragmentem 2-cyfrowym nazywamy dwie następujące po sobie cyfry w pliku pi.txt. Wszystkich fragmentów 2-cyfrowych zapisanych w tym pliku jest 9999. Ostatni rozpoczyna się w wierszu nr 9999.

Znajdź liczbę wszystkich fragmentów 2-cyfrowych, które są zapisami dziesiętnymi liczb o wartościach większych od 13. Dla danych zapisanych w pliku pi_przyklad.txt poprawna odpowiedź to 73.

Zadanie 3.2. (0–3) Wszystkich możliwych różnych fragmentów 2-cyfrowych jest dokładnie 100. Są nimi fragmenty 00, 01, 02, …, 99. Można sprawdzić, że np. 2-cyfrowy fragment równy 27 występuje w pliku pi.txt 101 razy.

Znajdź fragment 2-cyfrowy, którego liczba wystąpień w pliku pi.txt jest najmniejsza, oraz fragment 2-cyfrowy, którego liczba wystąpień jest największa. W wyniku podaj znalezione fragmenty 2-cyfrowe oraz liczby ich wystąpień. W przypadku, gdy więcej niż jeden fragment występuje tyle samo razy, wypisz ten o mniejszej wartości liczbowej.

Dla danych z pliku pi_przyklad.txt poprawna odpowiedź to: 00 0 / 62 4 (minimalna liczba wystąpień: fragment 00, liczba wystąpień 0; maksymalna liczba wystąpień: fragment 62, liczba wystąpień 4).

Informacja do zadań 3.3. i 3.4. Skończony co najmniej 4-elementowy ciąg liczb (a₁, a₂, …, aₙ) jest rosnąco-malejący, jeśli można podzielić go na dwa ciągi, z których pierwszy jest rosnący, a drugi – malejący, tzn. jeśli istnieje takie k ∈ {2, 3, ..., n–2}, że aₖ < aₖ₊₁ < ... < aₙ oraz aₖ₊₁ > aₖ₊₂ > ... > aₙ.

Przykład: Ciąg (2, 5, 7, 9, 8, 3, 1) jest rosnąco-malejący, bo można podzielić na (2, 5, 7) malejący (jest 8, 3, 1) – odpowiednio – (2, 5, 7, 9) i (8, 3, 1). Ciąg (5, 9, 9, 4, 1) także jest rosnąco-malejący. Ciągi (2, 5, 7, 9, 8, 3, 1, 1, 1) (2, 5, 7, 8, 3, 4, 3, 4) oraz (5, 5, 3, 2, 1) nie są rosnąco-malejące.

Zadanie 3.3. (0–2) Podaj liczbę ciągów kolejnych cyfr z pliku pi.txt, które są rosnąco-malejące. Dla danych zapisanych w pliku pi_przyklad.txt poprawna odpowiedź to 77.

Zadanie 3.4. (0–3) Znajdź najdłuższy ciąg kolejnych cyfr z pliku pi.txt, który jest rosnąco-malejący, oraz pozycję, na której on się rozpoczyna. W pliku pi.txt jest tylko jeden ciąg taki ciągi o największej długości.

Wynik zapisz w dwóch wierszach: w pierwszym wierszu zapisz pozycję, od której zaczyna się ciąg rosnąco-malejący, a w drugim wypisz znaleziony ciąg. Cyfry ciągu zapisz jedną po drugiej, bez znaku odstępu.

Dla danych zapisanych w pliku pi_przyklad.txt poprawna odpowiedź to: 77 / 0899862 (najdłuższy ciąg rosnąco-malejący w pliku pi_przyklad.txt to ciąg 0899862 o długości 7 rozpoczynający się w 77 wierszu pliku).
Pokaż odpowiedź
3.1. Fragmenty 2-cyfrowe > 13. Wczytujemy plik, iterujemy po sąsiadujących parach, składamy liczbę dwucyfrową i porównujemy.
```
cyfry = [int(l.strip()) for l in open("pi.txt")]
count = 0
for i in range(len(cyfry)-1):
    v = cyfry[i]*10 + cyfry[i+1]
    if v > 13:
        count += 1
print(count)
```
Odpowiedź dla pi.txt: liczba zależy od danych (przewidywany rząd ~8500).

3.2. Zliczamy 100 możliwych par i znajdujemy min/max:
```
from collections import Counter
cyfry = [l.strip() for l in open("pi.txt")]
pairs = [cyfry[i]+cyfry[i+1] for i in range(len(cyfry)-1)]
cnt = Counter(pairs)
# uzupełniamy zerami brakujące
for v in range(100):
    key = f"{v:02d}"
    cnt.setdefault(key, 0)
# min: najpierw najmniejsza liczność, przy remisie najmniejsza wartość
min_frag = min(cnt.items(), key=lambda x: (x[1], int(x[0])))
max_frag = max(cnt.items(), key=lambda x: (x[1], -int(x[0])))
print(min_frag, max_frag)
```
3.3. Liczba ciągów rosnąco-malejących (długości ≥ 4) w pliku.
```
cyfry = [int(l.strip()) for l in open("pi.txt")]
count = 0
n = len(cyfry)
for i in range(n):
    for j in range(i+3, n):  # długość >= 4
        seq = cyfry[i:j+1]
        # znajdź szczyt
        peak = seq.index(max(seq))
        if peak == 0 or peak == len(seq)-1:
            continue
        # sprawdź ściśle rosnący do peak i ściśle malejący po peak
        if all(seq[k] < seq[k+1] for k in range(peak)) and \
           all(seq[k] > seq[k+1] for k in range(peak, len(seq)-1)):
            count += 1
print(count)
```
3.4. Najdłuższy ciąg rosnąco-malejący. Algorytm liniowy: liczymy dla każdej pozycji długość najdłuższego ściśle rosnącego ciągu kończącego się tu (up[i]) i ściśle malejącego zaczynającego się tu (down[i]). Wynik dla szczytu i: up[i] + down[i] - 1 (wymagana długość ≥ 4, oba ramiona ≥ 2).
```
c = [int(l.strip()) for l in open("pi.txt")]
n = len(c)
up = [1]*n
for i in range(1, n):
    if c[i] > c[i-1]: up[i] = up[i-1] + 1
down = [1]*n
for i in range(n-2, -1, -1):
    if c[i] > c[i+1]: down[i] = down[i+1] + 1
best_len, best_start = 0, 0
for i in range(n):
    if up[i] >= 2 and down[i] >= 2:
        L = up[i] + down[i] - 1
        if L > best_len:
            best_len, best_start = L, i - up[i] + 2  # pozycja 1-indexed wiersza początku
print(best_start)
print("".join(str(c[k]) for k in range(best_start-1, best_start-1+best_len)))
```
⚠ Typowa pułapka: Zad. 3.2 — przy tie-break wymagane jest "mniejsza wartość liczbowa" zarówno dla min jak i dla max — to nieoczywiste przy max (większość intuicyjnie wzięłaby największą). Czytaj polecenie dosłownie. Zad. 3.3 — definicja wymaga "co najmniej 4-elementowy" i ŚCIŚLE rosnący/malejący — żadne równości (5,9,9,4,1 NIE jest rosnąco-malejący, mimo że tak wygląda — patrz: arkusz mówi "także jest", ale to znaczy że spełnia, bo 5<9 i 9>4>1, OK; z kolei 5,5,3,2,1 NIE bo 5=5 nie jest "<"). Zad. 3.4 — szukamy NAJDŁUŻSZEGO; "tylko jeden taki" — gwarancja unikalności. Pozycję raportujemy jako numer wiersza w pi.txt (1-indexed).
Zobacz pełne rozwiązanie krok po kroku →

n	min półek	max półek
7	3	7
16	5	16
31	5	31
32	6	32
2^k − 1	k	2^k − 1

Algorytmy i analiza algorytmów: rekurencja, sortowanie, struktury danych

Zadanie 1. Funkcja rekurencyjna

Zadanie 1.1. (0–3)

Zadanie 1.2. (0–2)

Zadanie 1.3. (0–4)

Zadanie 2. Zapis symboliczny

Zadanie 2.1. (0–2)

Zadanie 2.2. (0–4)

Zadanie 2.3. (0–3)

Zadanie 2.4. (0–3)

Inne działy — informatyka rozszerzona