01_jednoduche_algoritmy
Níže je uveden pouze náhled materiálu. Kliknutím na tlačítko 'Stáhnout soubor' stáhnete kompletní formátovaný materiál ve formátu PDF.
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)