Az euklideszi algoritmus használata a legnagyobb közös osztó (GCD) megtalálásához

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 .