Rozšířený Eukleidův algoritmus: Porovnání verzí
Smazaný obsah Přidaný obsah
→Příklad: {{přesnost|část}} |
→Příklad: Zavedení indexace cyklů algoritmu pro požadovanou jednoznačnost, oprava tabulky a smazání šablony {{přesnost|část}}. |
||
Řádek 2:
== Příklad ==
: Vstup: Přirozená čísla a, b, kde a ≥ b ≥ 0
: Výstup: d = NSD(a,b) a celá čísla α, β splňující podmínku d = α·a + β·b
# Je-li b = 0, položte d:=a, α:=1, β:=0 a skončete
# Položte i:= 0, α2<sub>0</sub>:= 1, α1<sub>0</sub>:= 0, β2<sub>0</sub>:= 0, β1<sub>0</sub>:= 1
# Dokud b > 0 dělejte následující: i:= i+1
## Spočtěte q a r tak, že a = q·b + r, 0 ≤ r < b
## Položte α2<sub>i</sub>:= α1<sub>i-1</sub>, α1<sub>i</sub>:= α2<sub>i-1</sub> - q*α1<sub>i-1</sub>, β2<sub>i</sub>:= β1<sub>i-1</sub>, β1<sub>i</sub>:= β2<sub>i-1</sub> - q*β1<sub>i-1</sub>
## Položte a:= b, b:= r
Položte d:= a, α:= α2<sub>i</sub>, β:= β2<sub>i</sub>
NSD(427, 133) = α · 427 + β · 133
Řádek 22:
{| class="wikitable"
|-
! i !! a !! b !! q !! r !! α2<sub>i</sub> !! α1<sub>i</sub> !! β2<sub>i</sub> !! β1<sub>i</sub>
|-
| 0 || 427 || 133 ||
|-
| 1 || 133 || 28 ||
|-
| 2 || 28 || 21 ||
|-
| 3 || 21 || 7 ||
|-
| 4 || 7 || 0 ||
|}
|