A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Tento článok alebo jeho časť si vyžaduje úpravu, aby zodpovedal vyššiemu štandardu kvality. Prosím, pozrite si stránky pomocníka, odporúčanie pre encyklopedický štýl a článok vhodne upravte. |
Rozšírený Euklidov algoritmus je algoritmus, ktorým je možné nájsť Bézoutovú rovnosť, čiže vyjadriť najväčší spoločný deliteľ (NSD) dvoch kladných celých čísel ich lineárnou kombináciou.
Príklad
Nech sú dané dve kladné celé čísla m a n a nech d je ich najväčší spoločný deliteľ, t.j. d = NSD(m,n). Pomocou Euklidovho algoritmu je možné zistiť, že NSD(196,34) = 2:
i | ci | di | pi | zi |
---|---|---|---|---|
0 | 196 | 34 | 5 | 26 |
1 | 34 | 26 | 1 | 8 |
2 | 26 | 8 | 3 | 2 |
3 | 8 | 2 | 4 | 0 |
kde je iterácia, , , je celočíselný podiel , je zvyšok po delení , čiže platí , resp:
a pre každé je
Úlohou Rozšíreného Euklidovho algoritmu je nájsť dvojicu celých čísel a , spĺňajúcu rovnosť .
Nájdenie Bézoutovej rovnosti spätným dosadzovaním
V uvedenom príklade platí:
Dosadením ľavej strany rovnosti (5) do rovnosti (4) dostaneme:
a dosadením ľavej strany rovnosti (6) do rovnosti (7) dostaneme výsledok:
t.j. jednu z možností, ako vyjadriť najväčší spoločný deliteľ dvoch čísel ich lineárnou kombináciou.
Odvodenie
Nech je iterácia v Euklidovom algoritme, v ktorej bol nájdený najväčší spoločný deliteľ dvoch kladných celých čísel , čiže pre ktoré platí . Spätným dosadením vyjadríme najväčší spoločný deliteľ ako lineárnu kombináciu a postupne pre každé , t.j:
Dosadením (2) a (3) do (9) dostaneme:
a dosadením (1) do (10):
Amdalhove pravidlo
Baud
Bloomov filter
Boolova algebra
Cardano (platforma)
Chomského hierarchia
Dijkstrov algoritmus
Eratostenovo sito
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk