01_jednoduche_algoritmy

Jednoduché algoritmy 

Rozklad na prvočísla.  
Nejmenší společný násobek.  
Největší společný dělitel 
Výpočet odmocniny 
Vlk, koza, zelí;  
misionáři a kanibalové 

Společní dělitelé, Nejmenší společný násobek a největší společný dělitel 

Největší společný dělitel (greatest common divisor) 

-  největší číslo, které bezezbytku dělí oba parametry dělení 

-  krácení zlomků 

-  dává smysl pro celočíselné parametry 

-  např. 1 je dělitelná pouze sama sebou (její uvažování jako dělitele nedává smysl) 

čísla 12 a 21 mají společného dělitele 3 (jediný dělitel) 

čísla 12 a 24 mají společného dělitele 12 (ale také 2, 3, 4, 6 ) 

čísla 23 a  529 mají jediného společného dělitele 23 (529 = 23*23) 

-   

Hrubá síla: zkusit vše od začátku do konce 

Vylepšení: maximum je polovina (?) nebo odmocnina (?) 

Je lepší začít od největšího nebo od nejmenšího čísla? 
 

Euklidův algoritmus 

-  využívá vlastnosti, že po odečtení menšího dělitele od většího zůstane největší společný dělitel 

stejný (představu dává grafické řešení – násobení je plocha obdélníku). 
NSD(u,v) = NSD(v, u – qv)

 – q je celočíselný násobek, u,v jsou vstupní celá čísla 

-  Násobení je obdélník. Společný násobek dává čtvercový rastr tohoto obdélníku. Pokud 

odečteme kratší stranu (která je v rastru) od delší, společný násobitel se nezmění (rastr zůstane) 

-  vstup je u,v (z u-qv plyne, že u je to větší z dvojice u, v) 

dokud v není nula 
    r = zbytek po celočíselném dělení u / v 
    u = v 
    v = r 
výsledek je v u 

Nejmenší společný násobek (least common multiple)