Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

### Euklidův algoritmus

Euklidův algoritmus je postup (algoritmus), kterým lze určit největšího společného dělitele dvou přirozených čísel, tzn. nejvyšší číslo takové, že beze zbytku dělí obě čísla.

Algoritmus (pomocí rekurze):

    function gcd(a, b)
    if b = 0 return a
    else return gcd(b, a mod b)

Algoritmus (pomocí iterace):

    function gcd(a, b)
    while b ≠ 0
    t := b
    b := a mod b
    a := t
    return a

Algoritmus (jednoduchý ale neefektivní):

    function gcd(a, b)
    while b ≠ 0
    if a > b
    a := a - b
    else
    b := b - a
    return a

Doba provádění programu je závislá na počtu průchodů hlavní smyčkou. Ten je maximální tehdy, jsou-li počáteční hodnoty u a v rovné dvěma po sobě jdoucím členům Fibonacciho posloupnosti. Maximální počet provedených opakování je tedy . Průměrný počet kroků pak je o něco nižší, přibližně .