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.
Példa-
GCD 20-ból, 30 = 10 (10 a legnagyobb szám, amely osztja a 20-at és a 30-at, a fennmaradó rész pedig 0)
GCD 42, 120, 285 = 3 (3 a legnagyobb szám, amely osztja a 42, 120 és 285 maradékot 0-val)
"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 ha A-t elosztjuk B-vel, akkor megkapjuk a maradék R-t.
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)
A fenti két megértett fogalommal könnyen meg fogja érteni 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. Ha feltételezzük, hogy ki akarja számítani az 1220 és 516 GCD értékét, alkalmazhatja az euklideszi algoritmust:
Ha feltételezzük, hogy ki akarja számítani az 1220 és 516 GCD értékét, alkalmazhatja az euklideszi algoritmust:
Az algoritmus ál kódja-
1. lépés: Legyen a, b a két szám
2. lépés: a mod b = R
3. lépés: Hagyd a = b és b = R
4. lépés: Ismételje meg a 2. és 3. lépést, amíg a mod b nagyobb lesz, mint 0
5. lépés: GCD = b
6. lépés: Befejezés
JavaScript kód a GCD elvégzéséhez
function gcd(a, b) { var R; while ((a % b) > 0) { R = a % b; a = b; b = R; } return b; } JavaScript kód a GCD elvégzéséhez rekurzióval-
function gcd(a, b) { if (b == 0) return a; else return gcd(b, (a % b)); } C kód a GCD rekurzióval történő végrehajtásához
int gcd(int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return gcd(a-b, b); return gcd(a, b-a); } C ++ kód a GCD-hez
int gcd(int a,int b) { int R; while ((a % b) > 0) { R = a % b; a = b; b = R; } return b; } Python-kód a GCD végrehajtásához a rekurzió segítségével
def gcd(a, b): if b == 0: return a: else: return gcd(b, (a % b)) Java kód a GCD végrehajtásához a rekurzió használatával
static int gcd(int a, int b) { if(b == 0) { return a; } 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
n Ugyanígy megtalálhatja a számok GCD-jét is .
Mi az a kibővített euklideszi algoritmus?
Ez az euklideszi algoritmus kiterjesztése. Kiszámítja az x, y együtthatókat is úgy, hogy
ax + by = gcd (a, b)
x és y Bézout azonosságának együtthatójaként is ismertek.
c kiterjesztett euklideszi algoritmus kódja
struct Triplet{ int gcd; int x; int y; }; Triplet gcdExtendedEuclid(int a,int b){ //Base Case if(b==0){ Triplet myAns; myAns.gcd = a; myAns.x = 1; myAns.y = 0; return myAns; } Triplet smallAns = gcdExtendedEuclid(b,a%b); //Extended euclid says Triplet myAns; myAns.gcd = smallAns.gcd; myAns.x = smallAns.y; myAns.y = (smallAns.x - ((a/b)*(smallAns.y))); return myAns; }