Bővített euklideszi algoritmus - Valaki le tudná vezetni?
Tehát, tudom, hogy a sima euklideszi algoritmussal meg tudjuk keresni két szám legnagyobb közös osztóját, a bővített euklideszi algoritmussal pedig felírjuk a két számot X + Y = valamennyi alakban, és egy általános megoldást tudunk adni. Ha lenne valaki olyan kedves, megcsinálni egy feladatot (lehetőleg papíron, hogy jobban átlátható legyen), és feltenné a netre a megoldást?
Előre is köszönöm!
a=225, b=111
válasza:225 = 111*2 +3 (hányados =2, maradék 3), ezután az előző sorban amivel osztottunk, elosztjuk a maradékkal:
111 = 3*37 +0.
A legnagyobb közös osztó az utolsó nem nulla maradék, azaz a 3.
válasza:Hát csak vissza kell helyettesítgetni (lényegében a 225x+111y=3 lin. diofantikus egyenletet kell megoldani) de ez adja magát, hiszen az első sor egyben az utolsó előtti is:
225= 111*2 +3 -> 1*225 -2*111 =3 tehát az x=1 y=-2 jó megoldás.
válasza:De nézzünk egy bonyolultabb példát: a=360 b=225
360= 225*1 +135
225= 135*1 +90
135= 90*1 +45
90= 45*2 +0
A legnagyobb közös osztó a 45 -> a 360x+225y=45 diofantikus egyenletet kell megoldani.
Ezt ha nem muszáj, nem részletezném ki, gondolom tanultátok, a lényeg, hogy ebből x=2+5k y=-3-8k
(tehát pl megoldás az x=2;y=-3).
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!