Matura informatyka

Algorytmy z wymagań CKE

Wszystkie algorytmy z wymagań egzaminacyjnych CKE z informatyki w Pythonie, z pseudokodem: systemy liczbowe, liczby pierwsze, NWD, sortowania, wyszukiwanie binarne, Horner, szyfry i geometria.

Algorytmy na liczbach całkowitych

8 algorytmów

  1. 1.1Systemy liczboweReprezentacja liczb w dowolnym systemie pozycyjnym, w tym w dwójkowym i szesnastkowym
  2. 1.2Liczba pierwszaSprawdzanie, czy liczba jest liczbą pierwszą
  3. 1.3Sito Eratostenesa
  4. 1.4Liczba doskonałaSprawdzanie, czy liczba jest liczbą doskonałą
  5. 1.5Rozkład na czynniki pierwszeRozkładanie liczby na czynniki pierwsze
  6. 1.6NWD i NWW (algorytm Euklidesa)Iteracyjna i rekurencyjna realizacja algorytmu Euklidesa + NWW
  7. 1.7Liczby FibonacciegoIteracyjne i rekurencyjne obliczanie wartości liczb Fibonacciego
  8. 1.8Wydawanie reszty (algorytm zachłanny)Wydawanie reszty metodą zachłanną

Algorytmy wyszukiwania i porządkowania (sortowania)

9 algorytmów

  1. 2.1Wyszukiwanie liniowe
  2. 2.2Wyszukiwanie binarneWyszukiwanie binarne (iteracyjne i rekurencyjne)
  3. 2.3Minimum i maksimum jednocześnieJednoczesne wyszukiwanie minimum i maksimum
  4. 2.4Sortowanie bąbelkoweBąbelkowy
  5. 2.5Sortowanie przez wybórPrzez wybór
  6. 2.6Sortowanie przez wstawianiePrzez wstawianie liniowe lub binarne
  7. 2.7Sortowanie przez scalaniePrzez scalanie
  8. 2.8Sortowanie szybkieSzybki
  9. 2.9Sortowanie kubełkoweKubełkowy

Algorytmy numeryczne

5 algorytmów

  1. 3.1Szybkie potęgowanieSzybkie podnoszenie do potęgi
  2. 3.2Bisekcja (miejsce zerowe funkcji)Wyznaczanie miejsc zerowych funkcji metodą połowienia
  3. 3.3Pierwiastek metodą HeronaObliczanie pierwiastka kwadratowego metodą Herona (Newtona)
  4. 3.4Schemat HorneraObliczanie wartości wielomianu za pomocą schematu Hornera
  5. 3.5Pole pod wykresem funkcjiObliczanie pola obszarów zamkniętych (metoda prostokątów i trapezów)

Algorytmy na tekstach

5 algorytmów

  1. 4.1PalindromSprawdzanie, czy dany ciąg znaków tworzy palindrom
  2. 4.2AnagramSprawdzanie, czy dany ciąg znaków tworzy anagram
  3. 4.3Porządek alfabetycznyPorządkowanie alfabetyczne, (leksykograficzne)
  4. 4.4Wyszukiwanie wzorca w tekście
  5. 4.5Odwrotna notacja polska (ONP)Obliczanie wartości wyrażenia w odwrotnej notacji polskiej (ONP)

Algorytmy kompresji i szyfrowania

8 algorytmów

  1. 5.1Kod prefiksowy (kompresja)Kompresja danych (kod prefiksowy)
  2. 5.2Kod Huffmana
  3. 5.3Alfabet Morse’a
  4. 5.4Szyfr przestawieniowyTranspozycyjny
  5. 5.5Szyfr AtBash
  6. 5.6Szyfr Cezara
  7. 5.7Szyfr Vigenère’a
  8. 5.8RSA i rozszerzony EuklidesRSA + rozszerzony algorytm Euklidesa

Algorytmy geometryczne

7 algorytmów

  1. 6.1Warunek trójkątaSprawdzanie warunku trójkąta
  2. 6.2Punkt względem prostejBadanie położenia punktów względem prostej
  3. 6.3Punkt na odcinkuBadanie przynależności punktu do odcinka
  4. 6.4Przecinanie się odcinków
  5. 6.5Punkt w wielokąciePrzynależność punktu do obszaru (wielokąta)
  6. 6.6Krzywa Kocha
  7. 6.7Drzewo Pitagorasa
1.1

Algorytmy na liczbach całkowitych

Systemy liczbowe

Reprezentacja liczb w dowolnym systemie pozycyjnym, w tym w dwójkowym i szesnastkowym

PythonPseudokodC++23Java 25
Wersja 1 · int("number_string",base) ANY --> DEC
dec_numbers = [15, 12, 2, 4, 7, 8]

dec_TO_bin = [bin(i)[2:] for i in dec_numbers]
dec_TO_oct = [oct(i)[2:] for i in dec_numbers]
dec_TO_hex = [hex(i)[2:] for i in dec_numbers]

bin_TO_dec = [int(i, 2) for i in dec_TO_bin]
oct_TO_dec = [int(i, 8) for i in dec_TO_oct]
hex_TO_dec = [int(i, 16) for i in dec_TO_hex]
Wersja 2 · recursive one-liner version DEC --> ANY
BS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"


def to_base(n, b):  # to_base(number,base), n >= 0, 2 <= b <= 36
    return BS[n] if n < b else to_base(n // b, b) + BS[n % b]
Wersja 3 · recursive version DEC --> ANY
BS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"

def to_base(n, b):  # to_base(number,base), n >= 0, 2 <= b <= 36
    if n < b:
        return BS[n]
    return to_base(n // b, b) + BS[n % b]
Wersja 4 · iterated version with slices DEC --> ANY
BS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"


def to_base(n, b):  # to_base(number,base), n >= 0, 2 <= b <= 36
    if n == 0:
        return "0"
    res = ""
    while n > 0:
        res += BS[n % b]
        n //= b
    return res[::-1]  # cyfry powstają od końca, więc odwracamy napis
Wersja 5 · manual version ANY --> DEC (schemat Hornera)
BS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"


def to_dec(liczba, b):  # to_dec("number_string", base), np. to_dec("1F", 16) == 31
    wynik = 0
    for znak in liczba.upper():
        wynik = wynik * b + BS.index(znak)  # BS.index(znak) - wartość cyfry
    return wynik
↑
1.2

Algorytmy na liczbach całkowitych

Liczba pierwsza

Sprawdzanie, czy liczba jest liczbą pierwszą

PythonPseudokodC++23Java 25
Python
def is_prime(x):
    if x <= 1:
        return False
    for i in range(2, int(x**0.5) + 1):
        if x % i == 0:
            return False
    return True
↑
1.3

Algorytmy na liczbach całkowitych

Sito Eratostenesa

PythonPseudokodC++23Java 25

Wyznacza wszystkie liczby pierwsze z przedziału [2, n]. Zaczynamy od tablicy, w której każda liczba jest "kandydatem" na liczbę pierwszą, a następnie dla kolejnych liczb pierwszych i wykreślamy ich wielokrotności (zaczynając od i * i, bo mniejsze wielokrotności zostały już wykreślone).

Python
def sito(n):  # zwraca listę liczb pierwszych <= n
    if n < 2:
        return []
    pierwsza = [True] * (n + 1)
    pierwsza[0] = pierwsza[1] = False
    i = 2
    while i * i <= n:
        if pierwsza[i]:
            for j in range(i * i, n + 1, i):
                pierwsza[j] = False
        i += 1

    wynik = []
    for i in range(2, n + 1):
        if pierwsza[i]:
            wynik.append(i)
    return wynik


print(sito(30))  # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
↑
1.4

Algorytmy na liczbach całkowitych

Liczba doskonała

Sprawdzanie, czy liczba jest liczbą doskonałą

PythonPseudokodC++23Java 25

Liczba doskonała to liczba naturalna równa sumie swoich dzielników mniejszych od niej samej, np. 6 = 1 + 2 + 3, 28 = 1 + 2 + 4 + 7 + 14.

Wersja 1 · O(n) version
def is_perfect(n):
    s = 1
    for i in range(2, n):
        if n % i == 0:
            s += i
    if n == s and n != 1:
        return True
    return False
Wersja 2
#O(sqrt(n)) version - dzielniki występują w parach (i, n // i)

def is_perfect(n):
    if n < 2:
        return False
    s = 1
    i = 2
    while i * i <= n:
        if n % i == 0:
            s += i
            if i != n // i:  # drugi dzielnik z pary (nie dodajemy dwa razy pierwiastka)
                s += n // i
        i += 1
    return s == n
↑
1.5

Algorytmy na liczbach całkowitych

Rozkład na czynniki pierwsze

Rozkładanie liczby na czynniki pierwsze

PythonPseudokodC++23Java 25
Python
def prime_factors(n):  # dla n <= 1 zwraca pustą listę
    czynniki = []
    k = 2
    while n > 1:
        while n % k == 0:
            n //= k
            czynniki.append(k)  # albo print(k)
        k += 1
    return czynniki


print(prime_factors(360))  # [2, 2, 2, 3, 3, 5]
↑
1.6

Algorytmy na liczbach całkowitych

NWD i NWW (algorytm Euklidesa)

Iteracyjna i rekurencyjna realizacja algorytmu Euklidesa + NWW

PythonPseudokodC++23Java 25
Wersja 1 · rekurencyjnie, 1 linia
def nwd(a, b): return nwd(b, a % b) if b else a
Wersja 2 · rekurencyjnie
def nwd(a, b):
    if b > 0:
        return nwd(b, a % b)
    return a
Wersja 3 · iteracyjnie
def nwd(a, b):
    while b:
        a, b = b, a % b
    return a
Wersja 4
#Najmniejsza wspólna wielokrotność (korzysta z funkcji nwd powyżej)

def nww(a, b): return a * b // nwd(a, b)
↑
1.7

Algorytmy na liczbach całkowitych

Liczby Fibonacciego

Iteracyjne i rekurencyjne obliczanie wartości liczb Fibonacciego

PythonPseudokodC++23Java 25
Wersja 1 · iteracyjnie
def f(n):
    a, b = 0, 1
    for i in range(0, n):
        a, b = b, a + b
    return a
Wersja 2 · rekurencyjnie
def f(n):
    if n <= 1:
        return n
    return f(n - 1) + f(n - 2)
↑
1.8

Algorytmy na liczbach całkowitych

Wydawanie reszty (algorytm zachłanny)

Wydawanie reszty metodą zachłanną

PythonPseudokodC++23Java 25

W każdym kroku wybieramy największą monetę, która nie jest większa od kwoty pozostałej do wydania. Dla nominałów takich jak w Polsce (1, 2, 5, 10, ...) daje to najmniejszą liczbę monet, ale dla dowolnych nominałów nie zawsze (np. kwota 6 i monety [1, 3, 4] -> 4 + 1 + 1 zamiast 3 + 3).

Python
do_wydania = 6
monety = [1, 2, 5]

def wydawanie(do_wydania, monety):
    count = 0
    historia = []

    while do_wydania > 0:
        nominal = 0
        for i in range(len(monety)):
            if do_wydania >= monety[i] > nominal:
                nominal = monety[i]
        if nominal == 0:  # żadna moneta nie mieści się w kwocie - reszty nie da się wydać
            return None
        do_wydania -= nominal

        historia.append(nominal)
        count += 1

    return count, historia


wynik = wydawanie(do_wydania, monety)
if wynik is None:
    print("Nie da się wydać reszty tymi monetami")
else:
    print(f'Resztę wydasz w {wynik[0]} monetach, te monety to {wynik[1]}')
↑
2.1

Algorytmy wyszukiwania i porządkowania (sortowania)

Wyszukiwanie liniowe

PythonPseudokodC++23Java 25

Sprawdzamy po kolei wszystkie elementy tablicy (tablica nie musi być posortowana). Złożoność O(n).

Python
def linear_search(tab, x):  # indeks pierwszego wystąpienia x albo -1
    for i in range(len(tab)):
        if tab[i] == x:
            return i
    return -1
↑
2.2

Algorytmy wyszukiwania i porządkowania (sortowania)

Wyszukiwanie binarne

Wyszukiwanie binarne (iteracyjne i rekurencyjne)

PythonPseudokodC++23Java 25

Działa tylko dla tablicy posortowanej rosnąco. W każdym kroku porównujemy szukaną wartość ze środkowym elementem i odrzucamy połowę przedziału. Złożoność O(log n).

Wersja 1 · iteracyjnie
def binary_search(tab, x):  # indeks elementu równego x albo -1
    lewy, prawy = 0, len(tab) - 1
    while lewy <= prawy:
        srodek = (lewy + prawy) // 2
        if tab[srodek] == x:
            return srodek
        elif tab[srodek] < x:
            lewy = srodek + 1
        else:
            prawy = srodek - 1
    return -1
Wersja 2
#Recursive version - wywołanie: binary_search_rek(tab, x, 0, len(tab) - 1)

def binary_search_rek(tab, x, lewy, prawy):
    if lewy > prawy:
        return -1
    srodek = (lewy + prawy) // 2
    if tab[srodek] == x:
        return srodek
    if tab[srodek] < x:
        return binary_search_rek(tab, x, srodek + 1, prawy)
    return binary_search_rek(tab, x, lewy, srodek - 1)
↑
2.3

Algorytmy wyszukiwania i porządkowania (sortowania)

Minimum i maksimum jednocześnie

Jednoczesne wyszukiwanie minimum i maksimum

PythonPseudokodC++23Java 25

Wersja naiwna porównuje każdy element osobno z minimum i z maksimum, czyli wykonuje ok. 2n porównań. Metoda "parami" bierze po dwa elementy, najpierw porównuje je ze sobą, a potem mniejszy z minimum, a większy z maksimum - 3 porównania na 2 elementy, czyli ok. 3n/2 porównań.

Wersja 1 · Wersja naiwna (ok. 2n porównań)
def min_max_naiwnie(tab):
    if len(tab) == 0:
        return None
    mini = maks = tab[0]
    for i in range(1, len(tab)):
        if tab[i] < mini:
            mini = tab[i]
        if tab[i] > maks:
            maks = tab[i]
    return mini, maks
Wersja 2 · Metoda "parami" (ok. 3n/2 porównań)
def min_max(tab):  # zwraca (minimum, maksimum) albo None dla pustej tablicy
    n = len(tab)
    if n == 0:
        return None
    if n % 2 == 1:  # nieparzysta liczba elementów - pierwszy element jest i min, i max
        mini = maks = tab[0]
        start = 1
    else:  # parzysta - pierwszą parę porównujemy ze sobą
        if tab[0] < tab[1]:
            mini, maks = tab[0], tab[1]
        else:
            mini, maks = tab[1], tab[0]
        start = 2

    for i in range(start, n - 1, 2):
        if tab[i] < tab[i + 1]:
            mniejszy, wiekszy = tab[i], tab[i + 1]
        else:
            mniejszy, wiekszy = tab[i + 1], tab[i]
        if mniejszy < mini:
            mini = mniejszy
        if wiekszy > maks:
            maks = wiekszy
    return mini, maks
↑
2.4

Algorytmy wyszukiwania i porządkowania (sortowania)

Sortowanie bąbelkowe

Bąbelkowy

PythonPseudokodC++23Java 25

Sortuje rosnąco (zamiana, gdy tab[j] > tab[j + 1]).

Wersja 1 · w miejscu
def bubble_sort(tab):
    for i in range(len(tab)):
        for j in range(len(tab) - i - 1):
            if tab[j] > tab[j + 1]:
                tab[j + 1], tab[j] = tab[j], tab[j + 1]
Wersja 2
# Wersja zoptymalizowana - kończy pracę, gdy w całym przebiegu nie było żadnej zamiany
arr = [1,1,1,1,1,1,2]


def swap(arr,x,y): #to albo swap jak wyżej
    temp = arr[x]
    arr[x] = arr[y]
    arr[y] = temp

def bubblesort(arr):

    for i in range(len(arr)):
        issorted = True
        for j in range(1,len(arr)-i):
            if arr[j] < arr[j-1]:
                swap(arr,j ,j-1)
                issorted = False
        if issorted:
            break

bubblesort(arr)
print(arr)
↑
2.5

Algorytmy wyszukiwania i porządkowania (sortowania)

Sortowanie przez wybór

Przez wybór

PythonPseudokodC++23Java 25
Python · w miejscu
def selection_sort(tab):
    for i in range(len(tab)):
        mini = i
        for j in range(i+1, len(tab)):
            if tab[mini] > tab[j]:
                mini = j
        tab[i], tab[mini] = tab[mini], tab[i]
↑
2.6

Algorytmy wyszukiwania i porządkowania (sortowania)

Sortowanie przez wstawianie

Przez wstawianie liniowe lub binarne

PythonPseudokodC++23Java 25

Wstawianie liniowe

Kolejny element wstawiamy do posortowanej już części tablicy, przesuwając większe elementy o jedno miejsce w prawo.

Python · w miejscu
def insertion_sort(A):
    for i in range(1, len(A)):
        liczba = A[i]
        j = i
        while j > 0 and A[j - 1] > liczba:
            A[j] = A[j - 1]
            j -= 1
        A[j] = liczba

Wstawianie binarne

Miejsce dla kolejnego elementu w posortowanej części tablicy szukamy wyszukiwaniem binarnym (mniej porównań), a potem przesuwamy elementy w prawo i wstawiamy go.

Python · w miejscu
def binary_insertion_sort(A):
    for i in range(1, len(A)):
        liczba = A[i]
        # szukamy binarnie pierwszej pozycji w A[0..i-1], na której stoi element > liczba
        lewy, prawy = 0, i
        while lewy < prawy:
            srodek = (lewy + prawy) // 2
            if A[srodek] <= liczba:
                lewy = srodek + 1
            else:
                prawy = srodek
        # przesuwamy A[lewy..i-1] o jedno miejsce w prawo
        for j in range(i, lewy, -1):
            A[j] = A[j - 1]
        A[lewy] = liczba
↑
2.7

Algorytmy wyszukiwania i porządkowania (sortowania)

Sortowanie przez scalanie

Przez scalanie

PythonPseudokodC++23Java 25
Python · In place (sortuje przekazaną tablicę, dodatkowo ją zwraca)
def merge_sort(tab):
    if len(tab) < 2:
        return tab

    i = j = k = 0
    mid = len(tab) // 2
    L, R = tab[:mid], tab[mid:]
    merge_sort(L)
    merge_sort(R)

    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            tab[k] = L[i]
            i += 1
        else:
            tab[k] = R[j]
            j += 1
        k += 1

    while i < len(L):
        tab[k] = L[i]
        i += 1
        k += 1

    while j < len(R):
        tab[k] = R[j]
        j += 1
        k += 1

    return tab
↑
2.8

Algorytmy wyszukiwania i porządkowania (sortowania)

Sortowanie szybkie

Szybki

PythonPseudokodC++23Java 25
Python
def quicksort(t):
    # jeżeli tablica jest pusta lub ma jeden element, to nie trzeba nic robić, można ją zwrócić.
    if len(t) <= 1:
        return t

    # wybierasz pivot (tutaj na końcu)
    pivot = t[-1]
    smaller = []
    greater = []

    # wszystkie mniejsze lub równe wartości od pivota idą do listy smaller a większe do greater.
    # len(t) - 1, bo pracujemy na elementach bez ostatniego, którym jest pivot.
    for i in range(0, len(t) - 1):
        if t[i] <= pivot:
            smaller.append(t[i])
        else:
            greater.append(t[i])

    # zwracasz tablicę, gdzie wszystkie mniejsze wartości są po lewej, a większe po prawej od pivota,
    # a pivot trafia na miejsce końcowe w tablicy wyjściowej.
    return quicksort(smaller) + [pivot] + quicksort(greater)


if __name__ == '__main__':
    arr = [60, 20, 11, 122, 214, 345, 1324, 1, 2, 3, 6, 74, 3, 9]
    print(quicksort(arr))
↑
2.9

Algorytmy wyszukiwania i porządkowania (sortowania)

Sortowanie kubełkowe

Kubełkowy

PythonPseudokodC++23Java 25

Założenia: sortujemy liczby (całkowite lub rzeczywiste), najlepiej nieujemne i w miarę równomiernie rozłożone w przedziale [min, max]. Przedział [min, max] dzielimy na n równych części (kubełków), każdą liczbę wrzucamy do odpowiedniego kubełka, sortujemy kubełki (np. przez wstawianie) i sklejamy je po kolei. Dzięki odejmowaniu minimum kod działa także dla liczb ujemnych.

Python · Not in place - zwraca nową, posortowaną listę
def insertion_sort(A):
    for i in range(1, len(A)):
        liczba = A[i]
        j = i
        while j > 0 and A[j - 1] > liczba:
            A[j] = A[j - 1]
            j -= 1
        A[j] = liczba


def bucket_sort(arr):
    n = len(arr)
    if n <= 1:
        return arr[:]
    mini, maks = min(arr), max(arr)  # liczone raz, przed pętlą
    if mini == maks:  # wszystkie elementy są równe
        return arr[:]

    buckets = [[] for _ in range(n)]
    szerokosc = (maks - mini) / n  # zakres wartości jednego kubełka

    for i in range(n):
        j = int((arr[i] - mini) / szerokosc)
        if j >= n:  # maksimum trafia do ostatniego kubełka
            j = n - 1
        buckets[j].append(arr[i])

    output = []
    for z in range(n):
        insertion_sort(buckets[z])
        output += buckets[z]
    return output
↑
3.1

Algorytmy numeryczne

Szybkie potęgowanie

Szybkie podnoszenie do potęgi

PythonPseudokodC++23Java 25

Zamiast mnożyć a przez siebie n razy (n mnożeń), korzystamy z tego, że a^n = (a^(n div 2))^2 dla parzystego n oraz a^n = a * a^(n - 1) dla nieparzystego n. Wystarczy wtedy ok. 2 * log2(n) mnożeń.

Szybkie potęgowanie a^n (iteracyjnie, na bitach wykładnika)

Python · iteracyjnie
def fast_power(a, n):  # a^n, n >= 0
    wynik = 1
    while n > 0:
        if n % 2 == 1:  # ostatni bit wykładnika to 1
            wynik *= a
        a *= a  # a, a^2, a^4, a^8, ...
        n //= 2
    return wynik

Szybkie potęgowanie modularne (szybko znajduje wartość base ^ power mod m, domyślnie m = 1000000007)

Python · iteracyjnie
def fast_power_mod(base, power, m=1000000007):
    result = 1 % m
    base %= m
    while power > 0:
        if power % 2 == 1:
            result = (result * base) % m
        power //= 2
        base = (base * base) % m
    return result

Szybkie potęgowanie a^n - wersja rekurencyjna (bez modulo, działa dla dowolnie dużych wyników).

Python · rekurencyjnie
def fast_pow(a, n):  # a^n, n >= 0 (przyjmujemy 0^0 = 1, tak jak pow w Pythonie)
    if n == 0:
        return 1
    # jeżeli wykładnik jest nieparzysty, to zmniejsz o jeden, by stał się parzysty,
    # a następnie oblicz potęgę a do parzystego wykładnika i pomnóż to przez a,
    # aby dostać a * a^parzysty_wykładnik.
    # na przykład: a^5 = a^4 * a
    if n % 2 == 1:
        return fast_pow(a, n - 1) * a
    # dla parzystego wykładnika szukamy potęgę z wykładnikiem o połowę mniejszym.
    # robiąc to, można dojść do a^2, co potem się składa na a^4 itd...
    # np. a^4 = a^2 * a^2.
    # kiedy n == 2, to funkcja szuka a^1, bo 2 div 2 == 1.
    # kiedy n == 1, to funkcja szuka a^0 * a, bo 1 jest liczbą nieparzystą, więc trafia do drugiego warunku.
    p = fast_pow(a, n // 2)
    return p * p
↑
3.2

Algorytmy numeryczne

Bisekcja (miejsce zerowe funkcji)

Wyznaczanie miejsc zerowych funkcji metodą połowienia

PythonPseudokodC++23Java 25

Funkcja f musi być ciągła w przedziale [a, b] i przyjmować na jego końcach wartości o przeciwnych znakach (f(a) * f(b) < 0). Wtedy w przedziale jest miejsce zerowe, a my w każdym kroku zostawiamy tę połowę przedziału, na której końcach znaki wciąż są przeciwne.

Python
def f(x):
    return -4 * x + 2


# bisection(od,do)
def bisection(a, b, precyzja=0.0001):
    if f(a) * f(b) >= 0:  # brak gwarancji miejsca zerowego w [a, b]
        return None
    c = a
    while b - a >= precyzja:
        c = (a + b) / 2
        if f(c) == 0.0:
            return c
        if f(c) * f(a) < 0:
            b = c
        else:
            a = c
    return c
↑
3.3

Algorytmy numeryczne

Pierwiastek metodą Herona

Obliczanie pierwiastka kwadratowego metodą Herona (Newtona)

PythonPseudokodC++23Java 25

Szukamy kwadratu o polu x. Zaczynamy od prostokąta o bokach a = x i b = 1 (pole x). W każdym kroku nowy bok a to średnia arytmetyczna boków, a drugi bok b = x / a (pole się nie zmienia). Prostokąt coraz bardziej przypomina kwadrat, a jego bok zbliża się do pierwiastka z x.

Python
def heron(x, precyzja=0.000001):  # pierwiastek kwadratowy z x >= 0
    if x == 0:
        return 0
    a = x
    b = 1
    while abs(a - b) > precyzja:
        a = (a + b) / 2
        b = x / a
    return a


print(heron(2))  # 1.41421356...
↑
3.4

Algorytmy numeryczne

Schemat Hornera

Obliczanie wartości wielomianu za pomocą schematu Hornera

PythonPseudokodC++23Java 25

Wielomian w(x) = a_n * x^n + ... + a_1 * x + a_0 zapisujemy jako w(x) = (...((a_n * x + a_(n-1)) * x + a_(n-2)) * x + ...) * x + a_0. Wystarczy wtedy n mnożeń i n dodawań (bez liczenia potęg). Współczynniki podajemy od najwyższej potęgi, np. 2x^3 - 6x^2 + 2x - 1 -> [2, -6, 2, -1].

Wersja 1 · iteracyjnie
def horner(wsp, x):  # wsp = [a_n, a_(n-1), ..., a_1, a_0]
    wynik = 0
    for i in range(len(wsp)):
        wynik = wynik * x + wsp[i]
    return wynik


print(horner([2, -6, 2, -1], 3))  # 2*27 - 6*9 + 2*3 - 1 = 5
Wersja 2
#Recursive version - wywołanie: horner_rek(wsp, x, len(wsp) - 1)

def horner_rek(wsp, x, n):  # wartość wielomianu zbudowanego ze współczynników wsp[0..n]
    if n == 0:
        return wsp[0]
    return horner_rek(wsp, x, n - 1) * x + wsp[n]

Zastosowanie: zamiana liczby z systemu o podstawie b na dziesiętny

Cyfry liczby to współczynniki wielomianu, a podstawa b to argument, np. 1011 (2) = 1 * 2^3 + 0 * 2^2 + 1 * 2 + 1 = ((1 * 2 + 0) * 2 + 1) * 2 + 1 = 11.

Python
def na_dziesietny(liczba, b):  # liczba jako napis, np. na_dziesietny("1F", 16) == 31
    wynik = 0
    for znak in liczba:
        if "0" <= znak <= "9":
            cyfra = ord(znak) - ord("0")
        else:
            cyfra = ord(znak.upper()) - ord("A") + 10  # A = 10, B = 11, ...
        wynik = wynik * b + cyfra
    return wynik
↑
3.5

Algorytmy numeryczne

Pole pod wykresem funkcji

Obliczanie pola obszarów zamkniętych (metoda prostokątów i trapezów)

PythonPseudokodC++23Java 25

Liczymy przybliżone pole obszaru ograniczonego wykresem funkcji f (f(x) >= 0), osią OX i prostymi x = a, x = b. Przedział [a, b] dzielimy na n części o szerokości h = (b - a) / n i sumujemy pola prostokątów (wysokość f w lewym końcu części) albo trapezów (podstawy f w obu końcach części). Przykład: f(x) = x^2 na [0, 1], dokładne pole to 1/3.

Python
def f(x):
    return x * x


def prostokaty(a, b, n):  # n - liczba prostokątów
    h = (b - a) / n
    pole = 0
    for i in range(n):
        pole += f(a + i * h) * h
    return pole


def trapezy(a, b, n):  # n - liczba trapezów
    h = (b - a) / n
    pole = 0
    for i in range(n):
        x1 = a + i * h
        x2 = a + (i + 1) * h
        pole += (f(x1) + f(x2)) / 2 * h
    return pole


print(prostokaty(0, 1, 1000))  # ok. 0.33283
print(trapezy(0, 1, 1000))     # ok. 0.3333335
↑
4.1

Algorytmy na tekstach

Palindrom

Sprawdzanie, czy dany ciąg znaków tworzy palindrom

PythonPseudokodC++23Java 25
Wersja 1 · lista i wycinki
def is_palindrom(string):
    lista = list(string)
    if lista == lista[::-1]:
        return True
    return False
Wersja 2 · dwa napisy
def is_palindrom(string):
    wynik = ""
    for i in string[::-1]:
        wynik += i
    if wynik == string:
        return True
    return False
Wersja 3 · rekurencyjnie
def isPalindrom(string):
    if len(string) <= 1:  # pusty napis i napis jednoznakowy są palindromami
        return True
    if len(string) == 2:
        if string[0] == string[1]:
            return True
        return False
    return isPalindrom(string[1:-1]) if string[0] == string[-1] else False

# This code is contributed by Pixel
Wersja 4 · Iterated version (dwa wskaźniki: od początku i od końca)
def is_palindrom(string):
    i = 0
    j = len(string) - 1
    while i < j:
        if string[i] != string[j]:
            return False
        i += 1
        j -= 1
    return True
↑
4.2

Algorytmy na tekstach

Anagram

Sprawdzanie, czy dany ciąg znaków tworzy anagram

PythonPseudokodC++23Java 25

Dwa napisy są anagramami, jeżeli składają się z tych samych znaków, występujących tyle samo razy (np. "kebab" i "babek").

Wersja 1 · z sortowaniem
def is_anagram(string,string2):
    if sorted(string) == sorted(string2):
        return True
    return False
Wersja 2 · With own sorting
def sort_1(string):
    string = list(string)
    for i in range(len(string)):
        for j in range(len(string) - i - 1):
            if string[j] > string[j + 1]:
                string[j], string[j + 1] = string[j + 1], string[j]
    return "".join(string)


def is_anagram(string, pattern):
    if len(string) != len(pattern):
        return False

    string = sort_1(string)
    pattern = sort_1(pattern)
    for i in range(len(string)):
        if string[i] != pattern[i]:
            return False
    return True
Wersja 3 · Counting version (zliczanie wystąpień znaków w słowniku)
def is_anagram(string, pattern):
    if len(string) != len(pattern):
        return False

    licznik = {}
    for znak in string:
        licznik[znak] = licznik.get(znak, 0) + 1

    for znak in pattern:
        if licznik.get(znak, 0) == 0:  # znaku brak albo występuje za dużo razy
            return False
        licznik[znak] -= 1
    return True
↑
4.3

Algorytmy na tekstach

Porządek alfabetyczny

Porządkowanie alfabetyczne, (leksykograficzne)

PythonPseudokodC++23Java 25
Wersja 1 · Sortowanie liter bąbelkowo
slowo = "niezdammatury"


def bubble_sort(tab):
    tab = list(tab)
    for i in range(len(tab)):
        for j in range(len(tab) - i - 1):
            if tab[j] > tab[j + 1]:
                tab[j + 1], tab[j] = tab[j], tab[j + 1]
    return "".join(tab)


print(bubble_sort(slowo))
Wersja 2
#Porządek leksykograficzny słów (porównywanie napisów znak po znaku)

def mniejsze(s1, s2):  # czy s1 jest w słowniku przed s2
    i = 0
    while i < len(s1) and i < len(s2):
        if s1[i] != s2[i]:
            return s1[i] < s2[i]  # decyduje pierwszy różniący się znak
        i += 1
    return len(s1) < len(s2)  # jedno słowo jest początkiem drugiego, np. "kot" < "kotek"


def sortuj_slowa(slowa):  # sortowanie bąbelkowe listy słów
    slowa = slowa[:]
    for i in range(len(slowa)):
        for j in range(len(slowa) - i - 1):
            if mniejsze(slowa[j + 1], slowa[j]):
                slowa[j], slowa[j + 1] = slowa[j + 1], slowa[j]
    return slowa


print(sortuj_slowa(["kotek", "ala", "kot", "ma"]))  # ['ala', 'kot', 'kotek', 'ma']
↑
4.4

Algorytmy na tekstach

Wyszukiwanie wzorca w tekście

PythonPseudokodC++23Java 25

Algorytm naiwny: przykładamy wzorzec do każdej pozycji tekstu, od której jeszcze się mieści (i = 0 .. len(tekst) - len(pattern)), i porównujemy znak po znaku.

Python
def find_pattern(tekst, pattern):  # indeks pierwszego wystąpienia wzorca albo -1
    for i in range(len(tekst) - len(pattern) + 1):
        j = 0
        while j < len(pattern) and tekst[i + j] == pattern[j]:
            j += 1
        if j == len(pattern):
            return i
    return -1


def is_pattern(tekst, pattern):
    return find_pattern(tekst, pattern) != -1


def find_all(tekst, pattern):  # lista wszystkich pozycji wystąpień (także nachodzących na siebie)
    pozycje = []
    for i in range(len(tekst) - len(pattern) + 1):
        j = 0
        while j < len(pattern) and tekst[i + j] == pattern[j]:
            j += 1
        if j == len(pattern):
            pozycje.append(i)
    return pozycje


print(find_pattern("abrakadabra", "abra"))  # 0
print(find_all("abrakadabra", "abra"))      # [0, 7]
↑
4.5

Algorytmy na tekstach

Odwrotna notacja polska (ONP)

Obliczanie wartości wyrażenia w odwrotnej notacji polskiej (ONP)

PythonPseudokodC++23Java 25

W ONP operator stoi za argumentami, np. (3 + 4) * 2 zapisujemy jako 3 4 + 2 *. Nawiasy nie są potrzebne. Wyrażenie czytamy od lewej: liczbę wkładamy na stos, a operator zdejmuje ze stosu dwie liczby, wykonuje działanie i wkłada wynik na stos. Na końcu na stosie zostaje wynik.

Python
def onp(wyrazenie):  # elementy oddzielone spacjami, np. "3 4 + 2 *"
    stos = []
    for element in wyrazenie.split():
        if element in ["+", "-", "*", "/"]:
            b = stos.pop()  # najpierw zdejmujemy PRAWY argument
            a = stos.pop()
            if element == "+":
                stos.append(a + b)
            elif element == "-":
                stos.append(a - b)
            elif element == "*":
                stos.append(a * b)
            else:
                stos.append(a / b)
        else:
            stos.append(float(element))
    return stos.pop()


print(onp("3 4 + 2 *"))          # 14.0
print(onp("5 1 2 + 4 * + 3 -"))  # 14.0
↑
5.1

Algorytmy kompresji i szyfrowania

Kod prefiksowy (kompresja)

Kompresja danych (kod prefiksowy)

PythonPseudokodC++23Java 25

Kod prefiksowy (prefix free)

Kody znaków o zmiennej długości są w wymaganiach (przykłady: kod prefiksowy poniżej, kod Huffmana, alfabet Morse’a). Częste znaki dostają krótkie kody, a rzadkie - dłuższe.

Kod jest nazywany "prefix (free) code", jeżeli w systemie nie ma kodu słowa, który byłby prefixem (początkiem) innego kodu słowa. Dzięki temu ciąg bitów da się odkodować jednoznacznie, bez żadnych separatorów.

Załóżmy, że mamy plik z 100,000 znakami, jedyne znaki jakie występują w pliku to: a,b,c,d,e,f i chcemy zmniejszyć rozmiar tego pliku kompresją, gdzie każdy kod znaku ma różną długość.

abcdef
Częstość (w tysiącach)4513121695
Kod o stałej długości000001010011100101
Kod o zmiennej długości010110011111011100

Przy kodzie o stałej długości plik zajmie 100,000 * 3 = 300,000 bitów, a przy kodzie o zmiennej długości (45 * 1 + 13 * 3 + 12 * 3 + 16 * 3 + 9 * 4 + 5 * 4) * 1000 = 224,000 bitów.

Python · iteracyjnie
# kod prefiksowy: żaden kod nie jest początkiem innego
cipher = {'00': ' ', '010': 'a', '011': 'm', '100': 'n', '101': 'i', '110': 'e', '1110': 'z', '1111': 'd'}

text = "1001011100011101111010011"


def decrypt(cipher, text):  # zwraca None, jeżeli text jest niepoprawny
    res = ""
    bufor = ""
    for bit in text:
        bufor += bit
        if bufor in cipher:  # bufor jest pełnym kodem znaku
            res += cipher[bufor]
            bufor = ""
    if bufor != "":  # zostały bity, które nie tworzą żadnego kodu
        return None
    return res


to_code = "zdam"


def encrypt(cipher, text):  # zwraca None, jeżeli w text jest znak spoza słownika
    res = ""
    for char in text:
        if char in cipher.values():
            for k, v in cipher.items():
                if v == char:
                    res += k
        else:
            return None
    return res


print(decrypt(cipher, text))     # nie zdam
print(encrypt(cipher, to_code))  # 11101111010011
↑
5.2

Algorytmy kompresji i szyfrowania

Kod Huffmana

PythonPseudokodC++23Java 25

Kod Huffmana to optymalny kod prefiksowy: daje najkrótszy zakodowany tekst spośród kodów, w których każdy znak ma stały ciąg bitów. Budowa drzewa: każdy znak to liść o wadze równej liczbie jego wystąpień. Dopóki mamy więcej niż jedno drzewo, łączymy dwa drzewa o najmniejszych wagach w jedno (waga = suma wag). Kod znaku to ścieżka od korzenia do liścia: krok w lewo = 0, w prawo = 1. Do wybierania najlżejszych drzew używamy kolejki priorytetowej (moduł heapq).

Python
import heapq


def huffman(tekst):  # zwraca słownik: znak -> kod
    if tekst == "":
        return {}
    czestosc = {}
    for znak in tekst:
        czestosc[znak] = czestosc.get(znak, 0) + 1

    # element kolejki: (waga, numer, drzewo); numer rozstrzyga remisy wag
    # drzewo to znak (liść) albo para (lewe poddrzewo, prawe poddrzewo)
    kolejka = []
    numer = 0
    for znak in czestosc:
        heapq.heappush(kolejka, (czestosc[znak], numer, znak))
        numer += 1

    if len(kolejka) == 1:  # tylko jeden rodzaj znaku
        return {kolejka[0][2]: "0"}

    while len(kolejka) > 1:
        waga1, _, lewe = heapq.heappop(kolejka)   # dwa najlżejsze drzewa
        waga2, _, prawe = heapq.heappop(kolejka)
        heapq.heappush(kolejka, (waga1 + waga2, numer, (lewe, prawe)))
        numer += 1

    kody = {}
    przypisz_kody(kolejka[0][2], "", kody)
    return kody


def przypisz_kody(wezel, kod, kody):
    if isinstance(wezel, str):  # liść - znak
        kody[wezel] = kod
    else:
        przypisz_kody(wezel[0], kod + "0", kody)
        przypisz_kody(wezel[1], kod + "1", kody)


def koduj(tekst, kody):
    wynik = ""
    for znak in tekst:
        wynik += kody[znak]
    return wynik


def dekoduj(bity, kody):
    odwrotne = {}
    for znak in kody:
        odwrotne[kody[znak]] = znak
    wynik = ""
    bufor = ""
    for bit in bity:
        bufor += bit
        if bufor in odwrotne:
            wynik += odwrotne[bufor]
            bufor = ""
    return wynik


tekst = "abrakadabra"
kody = huffman(tekst)
zakodowany = koduj(tekst, kody)
print(kody)
print(zakodowany, len(zakodowany), "bitów zamiast", 8 * len(tekst))
print(dekoduj(zakodowany, kody))
↑
5.3

Algorytmy kompresji i szyfrowania

Alfabet Morse’a

PythonC++23Java 25

W zakodowanym tekście litery oddzielamy jedną spacją, a wyrazy znakiem " / ".

Python · słownik kodujący: znak -> kod Morse'a
morseEncode = {
    'a': '.-', 'b': '-...', 'c': '-.-.', 'd': '-..',
    'e': '.', 'f': '..-.', 'g': '--.', 'h': '....',
    'i': '..', 'j': '.---', 'k': '-.-', 'l': '.-..',
    'm': '--', 'n': '-.', 'o': '---', 'p': '.--.',
    'q': '--.-', 'r': '.-.', 's': '...', 't': '-',
    'u': '..-', 'v': '...-', 'w': '.--', 'x': '-..-',
    'y': '-.--', 'z': '--..', '1': '.----', '2': '..---',
    '3': '...--', '4': '....-', '5': '.....', '6': '-....',
    '7': '--...', '8': '---..', '9': '----.', '0': '-----',
}
# słownik dekodujący: kod Morse'a -> znak (odwrócony słownik kodujący)
morseDecode = {val: key for key, val in morseEncode.items()}

SEP = ' / '  # separator wyrazów


def morseCode(string, decode=False):
    if not decode:  # kodowanie
        wyrazy = []
        for wyraz in string.lower().split():
            litery = []
            for char in wyraz:
                litery.append(morseEncode.get(char, '*'))  # '*' dla nieznanych znaków
            wyrazy.append(' '.join(litery))
        return SEP.join(wyrazy)
    else:  # dekodowanie
        wyrazy = []
        for wyraz in string.split(SEP):
            litery = ''
            for kod in wyraz.split():
                litery += morseDecode.get(kod, '*')  # '*' dla nieznanych kodów
            wyrazy.append(litery)
        return ' '.join(wyrazy)


# test
string = "Keep learning"
coded = morseCode(string)
print("Coded:", coded)
decoded = morseCode(coded, decode=True)
print("Decoded:", decoded)
↑
5.4

Algorytmy kompresji i szyfrowania

Szyfr przestawieniowy

Transpozycyjny

PythonPseudokodC++23Java 25

Szyfry przestawieniowe dokonują przestawienia znaków w tekście. Tekst zaszyfrowany jest permutacją tekstu jawnego, tzn. zawiera wszystkie znaki tekstu jawnego, jednak ustawione w innej kolejności. Operacja taka nosi nazwę transpozycji.

Zamiana sąsiednich znaków

Zamieniamy miejscami znaki na pozycjach i oraz i + 1 dla i = 0, jump, 2 * jump, ... Dla jump >= 2 pary się nie nakładają, więc ta sama funkcja (z tym samym jump) służy do szyfrowania i odszyfrowania.

Python
tekst = "aMtruaz  nifromtayik ot inct rdungeo"  # jump = 3 to decrypt


def przes(tekst, jump):  # jump >= 2
    tekst = list(tekst)
    for i in range(0, len(tekst) - 1, jump):
        tekst[i], tekst[i + 1] = tekst[i + 1], tekst[i]
    return "".join(tekst)


print(przes(tekst, 3))  # Matura z informatyki to nic trudnego

Szyfr kolumnowy

Tekst wpisujemy wierszami do tabeli o k kolumnach, a odczytujemy kolumnami, np. dla k = 3 "ALA MA KOTA" -> "A TLMKAAAO".

Python
def szyfruj_kolumnowo(tekst, k):  # k - liczba kolumn
    wynik = ""
    for kolumna in range(k):
        for i in range(kolumna, len(tekst), k):  # znaki z jednej kolumny
            wynik += tekst[i]
    return wynik


def deszyfruj_kolumnowo(szyfr, k):
    tekst = [""] * len(szyfr)
    pozycja = 0
    for kolumna in range(k):  # wpisujemy znaki z powrotem w tej samej kolejności
        for i in range(kolumna, len(szyfr), k):
            tekst[i] = szyfr[pozycja]
            pozycja += 1
    return "".join(tekst)


print(szyfruj_kolumnowo("ALA MA KOTA", 3))    # A  TLMKAAAO
print(deszyfruj_kolumnowo("A  TLMKAAAO", 3))  # ALA MA KOTA
↑
5.5

Algorytmy kompresji i szyfrowania

Szyfr AtBash

PythonPseudokodC++23Java 25

Jest to monoalfabetyczny szyfr podstawieniowy, ograniczony. Zasada jego działania polega na podstawieniu zamiast danej litery, litery leżącej po drugiej stronie alfabetu w takiej samej odległości. Np. zamiast litery A powinniśmy podstawić literę Z, za literę C wstawiamy literę X. Ta sama funkcja szyfruje i odszyfrowuje.

Python
txt = "Nie zdam maturki elo"


def atbash(txt):
    txt = list(txt)
    for i in range(len(txt)):
        if "A" <= txt[i] <= "Z":  # wielkie litery
            txt[i] = chr(ord("Z") - (ord(txt[i]) - ord("A")))
        elif "a" <= txt[i] <= "z":  # małe litery
            txt[i] = chr(ord("z") - (ord(txt[i]) - ord("a")))
        # pozostałe znaki (spacje, cyfry, polskie litery) zostają bez zmian

    return "".join(txt)


print(atbash(txt))  # Mrv awzn nzgfipr vol
↑
5.6

Algorytmy kompresji i szyfrowania

Szyfr Cezara

PythonPseudokodC++23Java 25

Jest to rodzaj szyfru podstawieniowego, w którym każda litera tekstu jawnego (niezaszyfrowanego) zastępowana jest inną, oddaloną od niej o stałą liczbę pozycji w alfabecie.

Jeżeli przesunięcie będzie równe 13, uzyskamy szyfr ROT13.

Python
def koduj(wiadomosc, klucz):
    wynik = ""
    wiadomosc = wiadomosc.upper().strip().replace(" ", "")
    for i in wiadomosc:
        if "A" <= i <= "Z":
            wynik += chr((ord(i) + klucz - 65) % 26 + 65)  # 65 = ord("A")
        else:
            wynik += i  # znaki inne niż litery A-Z zostają bez zmian
    return wynik


def dekoduj(wiadomosc, klucz):
    klucz *= -1
    return koduj(wiadomosc, klucz)


print(koduj("Ala ma kota", 3))  # DODPDNRWD
print(dekoduj("DODPDNRWD", 3))   # ALAMAKOTA
↑
5.7

Algorytmy kompresji i szyfrowania

Szyfr Vigenère’a

PythonPseudokodC++23Java 25

Szyfr podstawieniowy wieloalfabetowy - to szyfr Cezara, w którym przesunięcie zmienia się co literę. Kolejne litery klucza (powtarzanego w kółko) mówią, o ile przesunąć kolejne litery tekstu: A = 0, B = 1, ..., Z = 25. Przy odszyfrowaniu przesuwamy w drugą stronę.

Python
def vigenere(tekst, klucz, deszyfruj=False):  # tekst i klucz: wielkie litery A-Z
    wynik = ""
    j = 0  # pozycja w kluczu
    for znak in tekst:
        if "A" <= znak <= "Z":
            przesuniecie = ord(klucz[j % len(klucz)]) - ord("A")
            if deszyfruj:
                przesuniecie = -przesuniecie
            wynik += chr((ord(znak) - ord("A") + przesuniecie) % 26 + ord("A"))
            j += 1
        else:
            wynik += znak  # inne znaki bez zmian (nie zużywają litery klucza)
    return wynik


szyfr = vigenere("ATTACKATDAWN", "LEMON")
print(szyfr)                                    # LXFOPVEFRNHR
print(vigenere(szyfr, "LEMON", deszyfruj=True))  # ATTACKATDAWN
↑
5.8

Algorytmy kompresji i szyfrowania

RSA i rozszerzony Euklides

RSA + rozszerzony algorytm Euklidesa

PythonPseudokodC++23Java 25

Rozszerzony algorytm Euklidesa

Oprócz d = nwd(a, b) znajduje liczby całkowite x, y, takie że a * x + b * y = d. Gdy nwd(e, m) = 1, to x mod m jest odwrotnością e modulo m, czyli (e * x) mod m = 1 - tego potrzebujemy w RSA.

Python · rekurencyjnie
def rozszerzony_nwd(a, b):  # zwraca (d, x, y), gdzie d = nwd(a, b) = a * x + b * y
    if b == 0:
        return a, 1, 0
    d, x1, y1 = rozszerzony_nwd(b, a % b)
    return d, y1, x1 - (a // b) * y1


def odwrotnosc_mod(e, m):  # liczba d taka, że (e * d) mod m == 1, albo None
    d, x, y = rozszerzony_nwd(e, m)
    if d != 1:
        return None  # odwrotność istnieje tylko, gdy nwd(e, m) == 1
    return x % m


print(rozszerzony_nwd(240, 46))  # (2, -9, 47), bo 240 * (-9) + 46 * 47 = 2
print(odwrotnosc_mod(17, 3120))  # 2753

RSA

Szyfr z kluczem jawnym (asymetryczny): klucz publiczny (e, n) służy do szyfrowania, a klucz prywatny (d, n) do odszyfrowania.

  1. Wybieramy dwie różne liczby pierwsze p i q, liczymy n = p * q oraz phi = (p - 1) * (q - 1).
  2. Wybieramy e względnie pierwsze z phi (nwd(e, phi) = 1).
  3. Liczymy d - odwrotność e modulo phi, czyli (e * d) mod phi = 1.
  4. Szyfrowanie liczby m (0 <= m < n): c = m^e mod n. Odszyfrowanie: m = c^d mod n.
Python
def nwd(a, b):
    while b:
        a, b = b, a % b
    return a


def rozszerzony_nwd(a, b):  # zwraca (d, x, y), gdzie d = nwd(a, b) = a * x + b * y
    if b == 0:
        return a, 1, 0
    d, x1, y1 = rozszerzony_nwd(b, a % b)
    return d, y1, x1 - (a // b) * y1


def generuj_klucze(p, q, e=None):  # p, q - różne liczby pierwsze
    n = p * q
    phi = (p - 1) * (q - 1)
    if e is None:  # najmniejsze e >= 3 względnie pierwsze z phi
        e = 3
        while nwd(e, phi) != 1:
            e += 2
    d = rozszerzony_nwd(e, phi)[1] % phi  # albo: d = pow(e, -1, phi) (Python 3.8+)
    return (e, n), (d, n)  # (klucz publiczny, klucz prywatny)


def szyfruj(m, klucz_publiczny):  # m - liczba, 0 <= m < n
    e, n = klucz_publiczny
    return pow(m, e, n)  # szybkie potęgowanie modularne


def deszyfruj(c, klucz_prywatny):
    d, n = klucz_prywatny
    return pow(c, d, n)


publiczny, prywatny = generuj_klucze(61, 53, 17)
print(publiczny, prywatny)  # (17, 3233) (2753, 3233)
c = szyfruj(65, publiczny)
print(c, deszyfruj(c, prywatny))  # 2790 65

# szyfrowanie tekstu - każdy znak osobno jako liczba (kod znaku < n)
zaszyfrowane = [szyfruj(ord(znak), publiczny) for znak in "MATURA"]
print("".join(chr(deszyfruj(c, prywatny)) for c in zaszyfrowane))  # MATURA
↑
6.1

Algorytmy geometryczne

Warunek trójkąta

Sprawdzanie warunku trójkąta

PythonPseudokodC++23Java 25

Z odcinków o długościach a, b, c da się zbudować trójkąt wtedy i tylko wtedy, gdy wszystkie długości są dodatnie, a suma każdych dwóch jest większa od trzeciej.

Python
def czy_trojkat(a, b, c):
    if a <= 0 or b <= 0 or c <= 0:
        return False
    return a + b > c and a + c > b and b + c > a
↑
6.2

Algorytmy geometryczne

Punkt względem prostej

Badanie położenia punktów względem prostej

PythonPseudokodC++23Java 25

Punkty zapisujemy jako pary (x, y). Położenie punktu C względem prostej przechodzącej przez A i B mówi znak wyznacznika (iloczynu wektorowego wektorów AB i AC):

det(A, B, C) = (xB - xA) * (yC - yA) - (yB - yA) * (xC - xA)

det > 0 - C leży po lewej stronie prostej (patrząc z A w stronę B), det < 0 - po prawej, det = 0 - C leży na prostej AB. Dwa punkty C i D leżą po tej samej stronie prostej AB, gdy det(A, B, C) i det(A, B, D) mają ten sam znak.

Python
def wyznacznik(A, B, C):  # iloczyn wektorowy AB x AC
    return (B[0] - A[0]) * (C[1] - A[1]) - (B[1] - A[1]) * (C[0] - A[0])


def polozenie(A, B, C):  # położenie punktu C względem prostej AB
    w = wyznacznik(A, B, C)
    if w > 0:
        return "po lewej"
    if w < 0:
        return "po prawej"
    return "na prostej"


def ta_sama_strona(A, B, C, D):  # czy C i D leżą po tej samej stronie prostej AB
    return wyznacznik(A, B, C) * wyznacznik(A, B, D) > 0


print(polozenie((0, 0), (2, 2), (0, 5)))  # po lewej
↑
6.3

Algorytmy geometryczne

Punkt na odcinku

Badanie przynależności punktu do odcinka

PythonPseudokodC++23Java 25

Punkt C należy do odcinka AB, gdy leży na prostej AB (wyznacznik równy 0) i jego współrzędne mieszczą się między współrzędnymi końców odcinka.

Python
def wyznacznik(A, B, C):  # iloczyn wektorowy AB x AC
    return (B[0] - A[0]) * (C[1] - A[1]) - (B[1] - A[1]) * (C[0] - A[0])


def na_odcinku(A, B, C):  # czy punkt C należy do odcinka AB
    if wyznacznik(A, B, C) != 0:
        return False
    return (min(A[0], B[0]) <= C[0] <= max(A[0], B[0])
            and min(A[1], B[1]) <= C[1] <= max(A[1], B[1]))


print(na_odcinku((0, 0), (4, 4), (2, 2)))  # True
print(na_odcinku((0, 0), (4, 4), (5, 5)))  # False
↑
6.4

Algorytmy geometryczne

Przecinanie się odcinków

PythonPseudokodC++23Java 25

Odcinki AB i CD przecinają się, gdy końce C i D leżą po przeciwnych stronach prostej AB, a jednocześnie końce A i B leżą po przeciwnych stronach prostej CD. Osobno sprawdzamy przypadki szczególne, gdy koniec jednego odcinka leży na drugim odcinku.

Python
def wyznacznik(A, B, C):  # iloczyn wektorowy AB x AC
    return (B[0] - A[0]) * (C[1] - A[1]) - (B[1] - A[1]) * (C[0] - A[0])


def na_odcinku(A, B, C):  # czy punkt C należy do odcinka AB
    if wyznacznik(A, B, C) != 0:
        return False
    return (min(A[0], B[0]) <= C[0] <= max(A[0], B[0])
            and min(A[1], B[1]) <= C[1] <= max(A[1], B[1]))


def przecinaja_sie(A, B, C, D):  # czy odcinki AB i CD mają punkt wspólny
    w1 = wyznacznik(A, B, C)
    w2 = wyznacznik(A, B, D)
    w3 = wyznacznik(C, D, A)
    w4 = wyznacznik(C, D, B)
    if w1 * w2 < 0 and w3 * w4 < 0:  # przypadek ogólny
        return True
    # przypadki szczególne: koniec jednego odcinka leży na drugim
    if na_odcinku(A, B, C) or na_odcinku(A, B, D) or na_odcinku(C, D, A) or na_odcinku(C, D, B):
        return True
    return False


print(przecinaja_sie((0, 0), (4, 4), (0, 4), (4, 0)))  # True
print(przecinaja_sie((0, 0), (1, 1), (2, 2), (3, 3)))  # False
↑
6.5

Algorytmy geometryczne

Punkt w wielokącie

Przynależność punktu do obszaru (wielokąta)

PythonPseudokodC++23Java 25

Metoda półprostej (ray casting): z punktu P prowadzimy poziomą półprostą w prawo i liczymy, ile boków wielokąta przecina. Nieparzysta liczba przecięć - punkt leży wewnątrz, parzysta - na zewnątrz. Działa także dla wielokątów wklęsłych. Punkt leżący na brzegu traktujemy jako należący do obszaru.

Python
def wyznacznik(A, B, C):  # iloczyn wektorowy AB x AC
    return (B[0] - A[0]) * (C[1] - A[1]) - (B[1] - A[1]) * (C[0] - A[0])


def na_odcinku(A, B, C):  # czy punkt C należy do odcinka AB
    if wyznacznik(A, B, C) != 0:
        return False
    return (min(A[0], B[0]) <= C[0] <= max(A[0], B[0])
            and min(A[1], B[1]) <= C[1] <= max(A[1], B[1]))


def w_wielokacie(P, wielokat):  # wielokat - lista kolejnych wierzchołków
    x, y = P
    n = len(wielokat)
    wewnatrz = False
    for i in range(n):
        A = wielokat[i]
        B = wielokat[(i + 1) % n]  # ostatni wierzchołek łączy się z pierwszym
        if na_odcinku(A, B, P):
            return True  # punkt na brzegu
        if (A[1] > y) != (B[1] > y):  # bok przecina poziomą prostą y = P.y
            x_przeciecia = A[0] + (y - A[1]) * (B[0] - A[0]) / (B[1] - A[1])
            if x_przeciecia > x:  # przecięcie leży na prawo od P
                wewnatrz = not wewnatrz
    return wewnatrz


kwadrat = [(0, 0), (4, 0), (4, 4), (0, 4)]
print(w_wielokacie((2, 2), kwadrat))  # True
print(w_wielokacie((5, 2), kwadrat))  # False
↑
6.6

Algorytmy geometryczne

Krzywa Kocha

PythonPseudokodC++23Java 25

Krzywa Kocha stopnia 0 to odcinek. Krzywą stopnia k otrzymujemy, dzieląc odcinek na 3 równe części i zastępując środkową częścią dwoma bokami trójkąta równobocznego - każdy z 4 nowych odcinków rysujemy jako krzywą stopnia k - 1. Trzy krzywe Kocha narysowane na bokach trójkąta równobocznego tworzą płatek Kocha.

Python
import turtle


def koch(dlugosc, stopien):
    if stopien == 0:
        turtle.forward(dlugosc)
        return
    dlugosc /= 3
    koch(dlugosc, stopien - 1)
    turtle.left(60)
    koch(dlugosc, stopien - 1)
    turtle.right(120)
    koch(dlugosc, stopien - 1)
    turtle.left(60)
    koch(dlugosc, stopien - 1)


turtle.speed(0)
turtle.penup()
turtle.goto(-200, 0)
turtle.pendown()
koch(400, 3)
# płatek Kocha: for _ in range(3): koch(400, 3); turtle.right(120)
turtle.done()
↑
6.7

Algorytmy geometryczne

Drzewo Pitagorasa

PythonPseudokodC++23Java 25

Rysujemy kwadrat, a na jego górnym boku trójkąt prostokątny równoramienny. Na przyprostokątnych tego trójkąta budujemy (rekurencyjnie) dwa mniejsze drzewa, każde z kwadratem o boku bok * √2 / 2. Funkcja zaczyna i kończy rysowanie w tym samym miejscu (lewy dolny róg kwadratu) i z tym samym kierunkiem żółwia - dzięki temu wywołania rekurencyjne nie psują sobie położenia.

Python
import turtle


def drzewo(bok, stopien):  # żółw stoi w lewym dolnym rogu kwadratu i patrzy "w górę" kwadratu
    if stopien == 0:
        return
    for _ in range(4):  # kwadrat rysowany w prawo od żółwia
        turtle.forward(bok)
        turtle.right(90)
    nowy_bok = bok * 2 ** 0.5 / 2
    turtle.forward(bok)              # lewy górny róg kwadratu
    turtle.left(45)
    drzewo(nowy_bok, stopien - 1)    # lewa gałąź
    turtle.right(90)
    turtle.forward(nowy_bok)         # wierzchołek trójkąta
    drzewo(nowy_bok, stopien - 1)    # prawa gałąź
    turtle.back(nowy_bok)            # powrót do punktu startu
    turtle.left(45)
    turtle.back(bok)


turtle.speed(0)
turtle.penup()
turtle.goto(-50, -250)
turtle.pendown()
turtle.left(90)  # żółw patrzy w górę
drzewo(100, 8)
turtle.done()
↑