Trening CKE: programowanie i pliki

To zadanie egzaminacyjne celowo łączy kilka technik z całego roku, dokładnie tak jak zadania na maturze rozszerzonej — rzadko testują one jeden temat w izolacji.

2. Zadanie egzaminacyjne 1 — pełne zadanie łączone

Treść zadania

Plik wyniki.txt zawiera wyniki testu rekrutacyjnego — w każdej linii jedna liczba całkowita (0–100), po jednej osobie. Napisz program, który:
a) wczyta dane z pliku,
b) posortuje wyniki algorytmem MergeSort (Blok 08),
c) obliczy medianę wyników,
d) zapisze do nowego pliku raport.txt trzy najlepsze i trzy najgorsze wyniki oraz obliczoną medianę.

def merge_sort(tab):
    if len(tab) <= 1:
        return tab
    srodek = len(tab) // 2
    lewa = merge_sort(tab[:srodek])
    prawa = merge_sort(tab[srodek:])
    return scal(lewa, prawa)

def scal(lewa, prawa):
    wynik, i, j = [], 0, 0
    while i < len(lewa) and j < len(prawa):
        if lewa[i] <= prawa[j]:
            wynik.append(lewa[i]); i += 1
        else:
            wynik.append(prawa[j]); j += 1
    return wynik + lewa[i:] + prawa[j:]

with open("wyniki.txt") as plik:
    wyniki = [int(linia.strip()) for linia in plik]

posortowane = merge_sort(wyniki)
n = len(posortowane)
mediana = posortowane[n // 2] if n % 2 == 1 else (posortowane[n//2 - 1] + posortowane[n//2]) / 2

with open("raport.txt", "w") as plik:
    plik.write(f"Najlepsze: {posortowane[-3:]}\n")
    plik.write(f"Najgorsze: {posortowane[:3]}\n")
    plik.write(f"Mediana: {mediana}\n")

3. Zadanie egzaminacyjne 2 — rekurencja i struktury danych

Treść zadania

Napisz funkcję sprawdzającą, czy wyrażenie arytmetyczne zapisane w ONP (Blok 12) jest poprawne (tzn. czy po jego obliczeniu na stosie zostaje dokładnie jeden element, bez błędów niedomiaru stosu), a jeśli tak — oblicz jego wartość.

4. Zadanie egzaminacyjne 3 — grafy i programowanie dynamiczne

Treść zadania

Mając listę sąsiedztwa grafu reprezentującego sieć znajomości, napisz funkcję znajdującą najkrótszą (pod względem liczby kroków) ścieżkę między dwiema wskazanymi osobami, wykorzystując BFS (Blok 07). Jeśli ścieżka nie istnieje, funkcja powinna zwrócić informację o tym fakcie.

Zmodyfikuj klasyczny BFS z Bloku 07 tak, aby oprócz zbioru odwiedzonych wierzchołków przechowywał również "poprzednika" każdego wierzchołka (skąd do niego dotarliśmy). Po zakończeniu BFS, jeśli wierzchołek docelowy został odwiedzony, odtwórz ścieżkę, cofając się przez poprzedników od celu do startu.

5. Najczęstsze pułapki na egzaminie

6. Checklist gotowości egzaminacyjnej

Sprawdź, czy potrafisz bez pomocy notatek: wczytać dane z pliku, posortować je odpowiednim algorytmem, oraz uzasadnić dobór algorytmu pod kątem złożoności — to trzy filary, na których opiera się większość zadań programistycznych na maturze rozszerzonej.

Sprawdź wiedzę

1. W zadaniu 1, dlaczego zastosowano akurat MergeSort, a nie np. Counting Sort?

Bo wyniki testu (0-100) mają szeroki, nieznany zakres i mogą być duże zbiory danych Bo Counting Sort nie istnieje w Pythonie Nie ma znaczenia, który algorytm wybierzemy

2. Co powinna zrobić poprawna implementacja obliczania ONP, jeśli po przetworzeniu całego wyrażenia na stosie zostanie więcej niż jeden element?

Zignorować pozostałe elementy Zgłosić błąd — wyrażenie jest niepoprawne Zsumować wszystkie pozostałe elementy

3. Dlaczego do znajdowania najkrótszej ścieżki w nieważonym grafie znajomości używamy BFS, a nie DFS?

DFS jest wolniejszy w każdym przypadku BFS przeszukuje warstwami, więc pierwszy raz dotarcie do celu gwarantuje najkrótszą ścieżkę DFS nie działa na grafach

1. Mapa powtórkowa — Semestr I

2. Zadanie egzaminacyjne 1 — pełne zadanie łączone

Treść zadania

3. Zadanie egzaminacyjne 2 — rekurencja i struktury danych

Treść zadania

4. Zadanie egzaminacyjne 3 — grafy i programowanie dynamiczne

Treść zadania

5. Najczęstsze pułapki na egzaminie

6. Checklist gotowości egzaminacyjnej

Sprawdź wiedzę

Podsumowanie bloku