Realizace základních algoritmů

– Eukleidův algoritmus

a Eratosthenovo síto

Algoritmy tvoří základ informatického myšlení a programování. V této studii se zaměříme na dva klasické algoritmy, které reprezentují efektivní přístup k řešení aritmetických a číselných problémů:

Eukleidův algoritmus – efektivní metoda výpočtu největšího společného dělitele (NSD),

Eratosthenovo síto – algoritmus pro hledání všech prvočísel menších než dané číslo.

Pro každý z těchto algoritmů nejprve uvedeme teoretický základ, následně podrobný postup řešení krok za krokem a nakonec jednoduchou implementaci v jazyce Python.

Eukleidův algoritmus

Eukleidův algoritmus je jedním z nejstarších známých algoritmů, poprvé popsán v Eukleidových Základech (cca 300 př. n. l.). Je určen pro výpočet největšího společného dělitele (NSD) dvou kladných celých čísel. Využívá vlastnosti, že platí:

NSD(a,b) = NSD(b,a mod b)

a že:

NSD(a,0) = a

Postup krok za krokem

Zadaná čísla označme a a b, přičemž a ≥ b.

Vypočítej zbytek po dělení a % b.

Nahraď a hodnotou b a b hodnotou zbytku.

Opakuj, dokud b není rovno 0.

Výsledné a je hledaný NSD.

Python implementace


    def eukliduv_algoritmus(a, b):
        while b != 0:
            a, b = b, a % b
        return a

    # Ukázka použití
    print(eukliduv_algoritmus(252, 105))  # Výstup: 21

Eratosthenovo síto

Eratosthenovo síto (Sieve of Eratosthenes) je starověký algoritmus pro nalezení všech prvočísel menších než dané celé číslo n. Pochází od řeckého matematika Eratosthena z Kyrény (cca 200 př. n. l.).

Postup krok za krokem

Vytvoř seznam čísel od 2 do n.

Zvol nejmenší číslo p v seznamu, které ještě nebylo vyškrtnuto (na začátku p = 2).

Vyškrtej všechny násobky čísla p větší než p samotné.

Najdi další vyškrtnuté číslo větší než p a nahraď jím p.

Opakuj kroky 3–4, dokud p * p > n.

Zbylá čísla ve seznamu jsou prvočísla.

Python implementace


    def eratosthenovo_sito(n):
        if n < 2:
            return []

        je_prvocislo = [True] * (n + 1)
        je_prvocislo[0] = je_prvocislo[1] = False

        p = 2
        while p * p <= n:
            if je_prvocislo[p]:
                for i in range(p * p, n + 1, p):
                    je_prvocislo[i] = False
            p += 1

        return [i for i, is_prime in enumerate(je_prvocislo) if is_prime]

    # Ukázka použití
    print(eratosthenovo_sito(50))  # Výstup: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Srovnání algoritmů

Tyto dva algoritmy patří k základním stavebním kamenům algoritmického myšlení. Eukleidův algoritmus učí efektivní rekurzivní a iterativní přístup, zatímco Eratosthenovo síto ukazuje sílu předzpracování a práce s polem při řešení problému v číselné teorii. Porozumění těmto klasickým metodám je nezbytné pro další studium informatiky a teorie algoritmů.