Za ovu temu prvo morate znati o Najvećem zajedničkom djelitelju (GCD) i radu MORH-a.
Najveći zajednički djelitelj (GCD)
GCD od dvije ili više cijelih brojeva najveći je cijeli broj koji dijeli svaki od cijelih brojeva tako da je njihov ostatak jednak nuli.
Primjer-
GCD od 20, 30 = 10 (10 je najveći broj koji dijeli 20 i 30 s ostatkom kao 0)
GCD od 42, 120, 285 = 3 (3 je najveći broj koji dijeli 42, 120 i 285 s ostatkom kao 0)
"mod" rad
Mod operacija daje vam ostatak kada se podijele dvije pozitivne cijele vrijednosti. Mi to zapisujemo na sljedeći način-
A mod B = R
To znači da dijeljenjem A s B dobivate ostatak R, ovo je drugačije od vašeg dijeljenja koje vam daje količnik.
Primjer-
7 mod 2 = 1 (Podjelom 7 s 2 dobiva se ostatak 1)
42 mod 7 = 0 (Dijeljenje 42 sa 7 daje ostatak 0)
Uz gornja dva shvaćena pojma lako ćete razumjeti euklidski algoritam.
Euklidov algoritam za najveći zajednički djelitelj (GCD)
Euklidov algoritam pronalazi GCD od 2 broja.
Ovaj ćete algoritam bolje razumjeti ako ga vidite na djelu. Pod pretpostavkom da želite izračunati GCD 1220 i 516, dopustimo primjenu Euklidovog algoritma -
Pod pretpostavkom da želite izračunati GCD 1220 i 516, dopustimo primjenu Euklidovog algoritma -
Pseudo kôd algoritma-
Korak 1: Neka a, b budu dva broja
Korak 2: a mod b = R
Korak 3: Neka a = b i b = R
Korak 4: Ponavljajte korake 2 i 3 dok ne a mod b bude veće od 0
Korak 5: GCD = b
Korak 6: Završi
JavaScript kôd za izvođenje GCD-
function gcd(a, b) { var R; while ((a % b) > 0) { R = a % b; a = b; b = R; } return b; } JavaScript kôd za izvođenje GCD-a pomoću rekurzije-
function gcd(a, b) { if (b == 0) return a; else return gcd(b, (a % b)); } C kod za izvođenje GCD-a pomoću rekurzije
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 za izvođenje GCD-
int gcd(int a,int b) { int R; while ((a % b) > 0) { R = a % b; a = b; b = R; } return b; } Python kod za izvođenje GCD-a pomoću rekurzije
def gcd(a, b): if b == 0: return a: else: return gcd(b, (a % b)) Java kôd za izvođenje GCD-a pomoću rekurzije
static int gcd(int a, int b) { if(b == 0) { return a; } return gcd(b, a % b); } Također možete koristiti Euklidov algoritam da biste pronašli GCD više od dva broja. Budući da je GCD asocijativan, vrijedi sljedeća operacija - GCD(a,b,c) == GCD(GCD(a,b), c)
Izračunajte GCD prva dva broja, a zatim pronađite GCD rezultata i sljedeći broj. Primjer- GCD(203,91,77) == GCD(GCD(203,91),77) == GCD(7, 77) == 7
GCD n brojeva možete pronaći na isti način.
Što je Prošireni Euklidov algoritam?
Ovo je proširenje euklidskog algoritma. Također izračunava koeficijente x, y tako da
ax + by = gcd (a, b)
x i y poznati su i kao koeficijenti Bézoutova identiteta.
c kôd za Prošireni Euklidov algoritam
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; }