Ehhez a témához először ismernie kell a legnagyobb közös osztót (GCD) és a MOD műveletet.
Legnagyobb közös osztó (GCD)
Két vagy több egész szám GCD-je a legnagyobb egész szám, amely az egész számokat úgy osztja fel, hogy a fennmaradó részük nulla legyen.
Íme egy példa:
20, 30 = 10 GCD
GCD 42, 120, 285 = 3 (3 a legnagyobb szám, amely 42, 120 és 285 osztja 0 maradékkal)
„Mod” művelet
A mod művelet megadja a maradékot, ha két pozitív egész szám fel van osztva. A következőképpen írjuk:
A mod B = R
Ez azt jelenti, hogy az A osztása B-vel megadja a maradék R-t. Ez különbözik az osztási műveletétől, amely megadja a hányadost.
Íme egy példa:
7 mod 2 = 1 (A 7 osztása 2-vel megadja a maradékot 1)
42 mod 7 = 0 (Ha elosztjuk 42-vel 7-et, a maradék 0-t adunk)
Ha megérted a fenti két fogalmat, könnyen megérted az euklideszi algoritmust.
Euklideszi algoritmus a legnagyobb közös osztóra (GCD)
Az euklideszi algoritmus megtalálja 2 szám GCD-jét.
Jobban meg fogja érteni ezt az algoritmust, ha működésében látja. Feltételezve, hogy ki akarja számítani az 1220 és 516 GCD értékét, alkalmazzuk az euklideszi algoritmust.
Az algoritmus álkódja:
1. lépés: Legyen a, ba két szám
2. lépés: a mod b = R
3. lépés: Hagyd a = bésb = R
4. lépés: Ismételje meg a 2. és 3. lépést, amíg a mod bnagyobb lesz, mint 0
5. lépés: GCD = b
6. lépés: Befejezés
Itt van a Javascript kód a GCD végrehajtásához:
function gcd(a, b) { var R; while ((a % b) > 0) { R = a % b; a = b; b = R; } return b; }Itt van a Javascript-kód a GCD végrehajtásához a rekurzió használatával:
function gcd(a, b) { if (b == 0) return a; else return gcd(b, (a % b)); }Használhatja az euklideszi algoritmust kétnél több számból álló GCD megkeresésére is. Mivel a GCD asszociatív, a következő művelet érvényes: GCD(a,b,c) == GCD(GCD(a,b), c)
Számítsa ki az első két szám GCD-jét, majd keresse meg az eredmény GCD-jét és a következő számot. Példa:GCD(203,91,77) == GCD(GCD(203,91),77) == GCD(7, 77) == 7
nUgyanígy megtalálhatja a számok GCD-jét is .