Python na maturze: algorytmy, które musisz umieć

1. Wczytanie danych: punkt wyjścia każdego zadania CKE

Prawie każde zadanie praktyczne zaczyna się od pliku tekstowego (np. liczby.txt, dane.txt). Poniższe schematy wczytywania gwarantują poprawność typów i brak błędów pustych wierszy:

# Wariant A: Jedna liczba w wierszu
with open('liczby.txt', 'r', encoding='utf-8') as f:
    liczby = [int(line.strip()) for line in f if line.strip()]

# Wariant B: Kilka liczb rozdzielonych spacjami w jednym wierszu
with open('pary.txt', 'r', encoding='utf-8') as f:
    pary = [list(map(int, line.split())) for line in f if line.strip()]

# Wariant C: Wiersze z napisami (stringi)
with open('slowa.txt', 'r', encoding='utf-8') as f:
    slowa = [line.strip() for line in f if line.strip()]

2. Sprawdzanie liczb pierwszych i Sito Eratostenesa

Do pojedynczych liczb do $10^{12}$ stosujemy algorytm z ograniczeniem do pierwiastka $\sqrt{n}$. Dla wielu zapytań w zadanym przedziale (np. do $10^6$) bezkonkurencyjne jest Sito Eratostenesa o złożoności $O(n \log \log n)$.

# Test pierwszości dla pojedynczej liczby: O(sqrt(n))
def czy_pierwsza(n: int) -> bool:
    if n < 2:
        return False
    if n in (2, 3):
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    d = 5
    while d * d <= n:
        if n % d == 0 or n % (d + 2) == 0:
            return False
        d += 6
    return True

# Sito Eratostenesa dla przedziału [0, N]
def sito(limit: int) -> list[bool]:
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    for p in range(2, int(limit**0.5) + 1):
        if is_prime[p]:
            for multiple in range(p * p, limit + 1, p):
                is_prime[multiple] = False
    return is_prime

3. Rozkład liczby na czynniki pierwsze

Często wymagany w zadaniach sprawdzających właściwości liczb (np. liczby pierwsze bliźniacze, liczby pierwsze bezpieczne czy zliczanie różnych czynników):

def czynniki_pierwsze(n: int) -> list[int]:
    czynniki = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            czynniki.append(d)
            n //= d
        d += 1
    if n > 1:
        czynniki.append(n)
    return czynniki

# Liczba RÓŻNYCH czynników: len(set(czynniki_pierwsze(n)))

4. Algorytm Euklidesa: NWD i NWW

Wersja iteracyjna jest zwięzła i chroni przed limitem głębokości rekurencji (RecursionError w Pythonie):

def nwd(a: int, b: int) -> int:
    while b != 0:
        a, b = b, a % b
    return a

def nww(a: int, b: int) -> int:
    return (a * b) // nwd(a, b)

5. Algorytmy na napisach: palindromy, anagramy i zliczanie

Python posiada wbudowane mechanizmy, które w C++ zajmują kilkadziesiąt linii kodu:

from collections import Counter

# Sprawdzenie palindromu (wycinki / slicing)
def czy_palindrom(s: str) -> bool:
    return s == s[::-1]

# Sprawdzenie czy dwa słowa to anagramy
def czy_anagram(s1: str, s2: str) -> bool:
    return Counter(s1) == Counter(s2)

# Zliczanie częstotliwości liter i najczęstszy znak
def najczestszy_znak(s: str) -> tuple[str, int]:
    counts = Counter(s)
    return counts.most_common(1)[0]  # zwraca np. ('A', 14)

6. Wyszukiwanie binarne w czasie O(log n)

Gdy dane są posortowane, wyszukiwanie binarne pozwala przeszukać 1 000 000 elementów w zaledwie 20 krokach!

def wyszukiwanie_binarne(lista: list[int], cel: int) -> int:
    lewy, prawy = 0, len(lista) - 1
    while lewy <= prawy:
        srodek = (lewy + prawy) // 2
        if lista[srodek] == cel:
            return srodek  # Znaleziono pod indeksem
        elif lista[srodek] < cel:
            lewy = srodek + 1
        else:
            prawy = srodek - 1
    return -1  # Nie znaleziono

7. Konwersje systemów liczbowych

Na maturze musisz znać zarówno ręczną pętlę konwersji (pod zadania teoretyczne), jak i wbudowane funkcje Pythona:

# Konwersja na binarny (własna pętla)
def dec_to_bin(n: int) -> str:
    if n == 0:
        return '0'
    res = []
    while n > 0:
        res.append(str(n % 2))
        n //= 2
    return ''.join(reversed(res))

# Konwersje wbudowane w Pythonie:
liczba_z_bin = int('110101', 2)    # string binarny na dziesiętny int
liczba_z_hex = int('1A3F', 16)     # string szesnastkowy na dziesiętny int
bin_str = bin(53)[2:]              # dziesiętny int na string binarny (ucięcie prefiksu 0b)

8. Bezpieczny zapis wyników do pliku CKE

Kluczowe kryterium oceny CKE to poprawność formatu wyjściowego. Użyj formatowania f-stringów:

with open('wyniki4.txt', 'w', encoding='utf-8') as out:
    out.write("Zadanie 4.1:\n")
    out.write(f"Liczba odpowiedzi: {len(parzyste)}\n\n")
    
    out.write("Zadanie 4.2:\n")
    out.write(f"Najwieksza: {max(liczby)}, Najmniejsza: {min(liczby)}\n\n")
    
    out.write("Zadanie 4.3:\n")
    for wiersz in wyniki_3:
        out.write(f"{wiersz[0]} {wiersz[1]}\n")