Sådan bruges den euklidiske algoritme til at finde den største fælles skiller (GCD)

Til dette emne skal du først vide om den største fælles skillevæg (GCD) og MOD-operationen.

Greatest Common Divisor (GCD)

GCD på to eller flere heltal er det største heltal, der deler hvert af de helt tal, så deres resterende er nul.

Her er et eksempel:

GCD på 20, 30 = 10 (10 er det største tal, der deler 20 og 30 med resten af ​​0)

GCD på 42, ​​120, 285 = 3 (3 er det største tal, der deler 42, 120 og 285 med resten af ​​0)

“Mod” -drift

Mod-operationen giver dig resten, når to positive heltal er opdelt. Vi skriver det som følger:

A mod B = R

Det betyder, at dividere A med B giver dig resten R. Dette er anderledes end din divisionsoperation, som giver dig kvotienten.

Her er et eksempel:

7 mod 2 = 1 (At dividere 7 med 2 giver resten 1)

42 mod 7 = 0 (Opdeling 42 af 7 giver resten 0)

Hvis du forstår de to ovennævnte begreber, vil du let forstå den euklidiske algoritme.

Euklidisk algoritme for den største fælles skiller (GCD)

Den euklidiske algoritme finder GCD på 2 tal.

Du vil bedre forstå denne algoritme ved at se den i aktion. Forudsat at du vil beregne GCD på 1220 og 516, lad os anvende den euklidiske algoritme.

Pseudokode for algoritmen:

Trin 1: Lad a, bvære de to tal

Trin 2: a mod b = R

Trin 3: Lad a = bogb = R

Trin 4: Gentag trin 2 og 3, indtil den a mod ber større end 0

Trin 5: GCD = b

Trin 6: Afslut

Her er Javascript-koden til udførelse af GCD:

function gcd(a, b) { var R; while ((a % b) > 0) { R = a % b; a = b; b = R; } return b; }

Her er Javascript-koden til udførelse af GCD ved hjælp af rekursion:

function gcd(a, b) { if (b == 0) return a; else return gcd(b, (a % b)); }

Du kan også bruge den euklidiske algoritme til at finde GCD på mere end to tal. Da GCD er associerende, er følgende handling gyldig:  GCD(a,b,c) == GCD(GCD(a,b), c)

Beregn GCD for de første to tal, find derefter GCD for resultatet og det næste nummer. Eksempel:GCD(203,91,77) == GCD(GCD(203,91),77) == GCD(7, 77) == 7

Du kan finde GCD med ntal på samme måde.