Matematické Fórum

Dayman · 27. 01. 2011 15:39

ahojte, furt mi nejde ze skript se naučit rozšířený euklidův algoritmus a to by mi stačilo jen pár sekund kdyby mi někdo řekl jak na to, jelikož je to primitivní, jenže už si nepamatuju postup...hlavně jde o pravou stranu ...to A,B to nechapu jak se pocita, prosim poradte...

chtelo by to nejaky navod z ktereho bych to hned pochopil, ve skriptech je to dost neprehledny...

Jookyn · 27. 01. 2011 22:24

Pokusim se to nějak srozumitelně popsat. Číslo/písmeno v závorce za názvem sloupce bude značit číslo řádku, číslování začíná od 0. Taktéž předpokládám, že víte, co je mod (modulo) a div (celočíselné dělení)

První dva řádky se vyplní na základě vstupu.

a,b(0) a a,b(1) jsou čísla jejichž NSD chceme zjistit, přičemž a,b(0) >= a,b(1)
A(0) = 1, B(0) = 0
A(1) = 0, B(0) = 1

A ostatní věci lze spočítat z těchto vztahů:
q(i) = a,b(i-1) div a,b(i)
a,b(i+1) = a,b(i-1) mod a,b(i)
A(i+1) = A(i-1) - q(i) * A(i)
B(i+1) = B(i-1) - q(i) * B(i)

tzn, kdybych to měl popsat nějak slovy, tak hodnotu ve sloupci:

a,b získáme tak, že se podíváme na 2 předchozí řádky a uděláme jejich modulo.
q získáme tak, že vezmeme hodnotu a,b o řádek výše a celočíselně ji vydělíme hodnotou a,b v aktuálním řádku
A získáme tak, že vezmeme hodnotu A o dva řádky výše a od toho odečteme q-násobek hodnoty A z předchozího řádku
B analogicky jako A

A pokud dostaneme v a,b(i) nulu, tak vrátíme hodnoty a,b; A; B z předchozího řádku.

Dayman · 27. 01. 2011 22:37 — Editoval Dayman (27. 01. 2011 22:37)

Jookyn napsal(a):
Pokusim se to nějak srozumitelně popsat. Číslo/písmeno v závorce za názvem sloupce bude značit číslo řádku, číslování začíná od 0. Taktéž předpokládám, že víte, co je mod (modulo) a div (celočíselné dělení)

První dva řádky se vyplní na základě vstupu.

a,b(0) a a,b(1) jsou čísla jejichž NSD chceme zjistit, přičemž a,b(0) >= a,b(1)
A(0) = 1, B(0) = 0
A(1) = 0, B(0) = 1

A ostatní věci lze spočítat z těchto vztahů:
q(i) = a,b(i-1) div a,b(i)
a,b(i+1) = a,b(i-1) mod a,b(i)
A(i+1) = A(i-1) - q(i) * A(i)
B(i+1) = B(i-1) - q(i) * B(i)

tzn, kdybych to měl popsat nějak slovy, tak hodnotu ve sloupci:

a,b získáme tak, že se podíváme na 2 předchozí řádky a uděláme jejich modulo.
q získáme tak, že vezmeme hodnotu a,b o řádek výše a celočíselně ji vydělíme hodnotou a,b v aktuálním řádku
A získáme tak, že vezmeme hodnotu A o dva řádky výše a od toho odečteme q-násobek hodnoty A z předchozího řádku
B analogicky jako A

A pokud dostaneme v a,b(i) nulu, tak vrátíme hodnoty a,b; A; B z předchozího řádku.

diky moc, moc mi to pomohlo :) konecne to chapu, ja to delal trochu jinak...ja pocital to A a B zpusobem, ze napr. B(i+1)=A(i)-B(i)*q(i) :D a ono to vychazelo, ale byli vyjimky :D ...ted uz vim, jeste jednou diky

Dayman · 28. 01. 2011 18:16 — Editoval Dayman (28. 01. 2011 18:17)

jeste se chci zeptat, jak pocitam gcd, kdyz jeden z prvku je zaporny?napriklad gcd(10,-4).nevim jak to v te tabulce pocitat pak...to ho tam napisu proste jako kladny?a co pak delam kdyz je vlastne v tom sloupci a,b na prvnim radku mensi cislo nez na druhym?

Jookyn · 28. 01. 2011 22:23

↑ Dayman:
Co se týká získání samotného GCD, tak určitě nevadí vzít z daných čísel absolutní hodnotu a provédst Euklidův alg. s kladnými čísly. Pak ale vyjdou Bezoutovy koeficienty (tady značeno A a B) tak, že platí: GCD(a,b) = |a| * A + |b| * B.

Jinak se to dá všechno nadefinovat přesněji, pak to funguje pro všechny Euklidovské obory (kam patří i celá čísla), neni už to pak ale tak intuitivní, jestli je zájem, tak to sem můžu všechno napsat...

Dayman · 29. 01. 2011 15:21 — Editoval Dayman (29. 01. 2011 15:34)

diky,nejsem si ale jisty jestli mi to uplne pomohlo,ja to hlavne potrebuji kvuli prikladum kterym nerozumim zde, tak se kdyztak podivej, treba mi opet pomuzes...

http://forum.matweb.cz/viewtopic.php?pid=166923#p166923

ted jsem skusil spocitat pres euklida tuto rovnici 10x-4y=26

jen GCD bez rozsireni a takle mi to vychazelo

a,b q
-4 -
10 0
-4 -2
2 -2
0

je to dobre ?vim ze gcd(10,-4)=2 ale spis mi jde o to jestli mam dobre ten postup...kdyz jsem to delal se zapornym cislem
ale ted koukam ze mi pak nevychazi to rozsireni...tak nvm :(

Matematické Fórum

#1 27. 01. 2011 15:39

Rozšířený euklidův algoritmus

#2 27. 01. 2011 22:24

Re: Rozšířený euklidův algoritmus

#3 27. 01. 2011 22:37 — Editoval Dayman (27. 01. 2011 22:37)

Re: Rozšířený euklidův algoritmus

Jookyn napsal(a):

#4 28. 01. 2011 18:16 — Editoval Dayman (28. 01. 2011 18:17)

Re: Rozšířený euklidův algoritmus

#5 28. 01. 2011 22:23

Re: Rozšířený euklidův algoritmus

#6 29. 01. 2011 15:21 — Editoval Dayman (29. 01. 2011 15:34)

Re: Rozšířený euklidův algoritmus

Zápatí