Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
Stránky: 1
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...
Offline
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.
Offline
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
Offline
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?
Offline
↑ 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...
Offline
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 :(
Offline
Stránky: 1