Største vanlig divisor med Java

“Den største vanlige divisoren, forkortet GCD, er også kjent som den høyeste vanlige faktoren, forkortet H.C.F.”

Betydning av største felles divisor

En divisor er et helt tall (heltall) som vil gå inn i et annet hele nummer uten resten. Den største vanlige divisoren forklares best med en illustrasjon. Følgende tabell viser to tall: 60 og 108, med alle delene sine større enn 1.

Det er delinger i tabellen som ikke er vanlig for både 60 og 108. Imidlertid er 2 en vanlig divisor til både nummer 60 og 108, men det er ikke den største divisoren som er felles for 60 og 108. Divisor 3 er på samme måte beskrevet. Ved inspeksjon av bordet er den største divisoren som er vanlig for både 60 og 108 12. Ingen divisor over 12 er vanlig i både 60 og 108. Så 12 er den største vanlige divisoren for 60 og 108.

Målet med denne artikkelen er å forklare hvordan man får størst felles divisor ved subtraksjon eller ved inndeling; med programmering gjort i Java.

GCD ved subtraksjon

Ved inspeksjon fra tabellen ovenfor er GCD for 60 og 108 12. Dette betyr at hvis 12 blir lagt til gjentatte ganger, vil resultatet bli 60, den mindre av begge tallene. Hvis tillegget av 12 fortsetter, vil resultatet bli 108, den større av begge tallene. Det er:

12 + 12 +12 +12 + 12 = 60

12 + 12 +12 +12 + 12 = 60 + 12 + 12 + 12 + 12 = 108

Det er:

60 + 12 + 12 + 12 + 12 = 108

Som betyr:

60 + 48 = 108

Hvis tillegg av GCD kan føre til begge tall, kan kanskje en form for kontinuerlig subtraksjon nedover føre til GCD. Dette er et faktum, som illustrert av følgende trinn, som begynner med forskjellen på 108 og 60:

108 - 60 = 48
60 - 48 = 12
48 - 12 = 36
36 - 12 = 24
24 - 12 = 12
12 - 12 = 0

Mellom 60 og 108, 108 er det større antallet. Etter det oppnås forskjellen på den resulterende forskjellen (48 for det første trinnet) og subtrahend (60 for første trinn) gjentatte ganger til svaret er null. I trinnene trekkes det mindre antallet fra, det større antallet. På det siste trinnet er minuend og subtrahend den samme. Denne samme verdien er den største vanlige divisoren.

La tallene hvis GCD er nødvendig være A og B. Hvis disse tallene ikke har noen GCD større enn 1, betyr det at deres største vanlige divisor er 1. I programmering er tidskompleksiteten for å finne GCD ved subtraksjon O (A+B). Hvis A er 1 og B er 5, vil trinnene uten programmering være:

5 - 1 = 4
4 - 1 = 3
3 - 1 = 2
2 - 1 = 1
1 - 1 = 0

GCD -en her er 1. Det er fem trinn her og ikke seks trinn av (A + B). Imidlertid er det maksimalt mulig antall kodeoperasjoner i programmering som tidskompleksiteten som er tatt som tidskompleksiteten.

Koding GCD ved subtraksjon

Klassen og metoden for den største vanlige divisoren ved subtraksjon i Java er:

klasse GCDer
int gcds (int a, int b)
if (a == b)
return a;
if (a> b)
Returner GCD-er (A-B, B);
return GCDS (A, B-A);

Det begynner med en uttalelse for det siste matematiske trinnet når begge resulterende tall er like. De to neste uttalelsene trekker det mindre antallet fra det større antallet rekursivt. En Java hovedklasse og Java hovedmetode, for å gå med klassen ovenfor, er:

offentlig klasse Main
public static void main (String args [])
GCDs obj = new GCDS ();
int ret = obj.GCD -er (108, 60);
System.ute.println (ret);

Utgangen er 12.

GCD etter divisjon

Tabellen ovenfor gjentas her for enkel referanse:

De to tallene hvis GCD er nødvendig er 60 og 108, med 108 det større tallet. Ovennevnte forklaring på subtraksjon begynte med:

12 + 12 +12 +12 + 12 = 60

12 + 12 +12 +12 + 12 = 60 + 12 + 12 + 12 + 12 = 108

Det er:

60 + 12 + 12 + 12 + 12 = 108

Som betyr:

60 + 48 = 108

Modulo Division er en divisjon der svaret er hele antallet del av kvotienten, og resten blir også tatt i betraktning. Tenk på resten når du deler 108 med 60 og rester av de resulterende kvotientene og deres tilsvarende deling.

108 % 60 = 48 (i.E 1 R 48)
60 % 48 = 12 (i.E 1 R 48)
48 % 12 = 0 (i.E 4 R 0)

Modulusdivisjonen slutter når resten er 0. GCD er divisoren for det siste trinnet. Det var allerede kjent, fra den andre metoden ovenfor, at den største vanlige divisoren er 12.

108 Mod 60 er ikke null. Hvis GCD mellom 60 og 108 måtte finnes ved subtraksjon, ville den første forskjellen for GCD mellom 60 og 108 være 48, og det kan vises at GCD mellom 60 og 108 er 12. 60 Mod 48 er ikke null. Hvis GCD mellom 60 og 48 (den forrige resten) måtte bli funnet ved subtraksjon, ville den første forskjellen for GCD mellom 60 og 48 være 12, og det kan vises at GCD mellom 60 og 48 er 12. 48 Mod 12 er null og har 0 resterende. Hvis GCD mellom 48 og 12 måtte finnes ved subtraksjon, ville den første forskjellen for GCD mellom 48 og 12 være 36. 36 er ikke GCD mellom 48 og 12; Imidlertid er 36 et multiplum av 12, som er GCD.

Ved å bruke noen måter kan leseren bevise med de ovennevnte trinnene som gitt at GCD for 60 og 108 er 12, GCD for 60 og 48 er også 12; og GCD for 48 og 12 er fortsatt 12.

Tenk på et annet eksempel for å finne GCD etter divisjon. Problemet nå er: å finne GCD etter divisjon for tallene 18 og 30.

Løsning:

30 % 18 = 12 (i.e. 1 r 12)
18 % 12 = 6 (i.e. 1 r 6)
12 % 6 = 0 (i.e. 2 r 0)

GCD er 6, lest fra den siste linjen, der modulen er 0.

30 Mod 18 er ikke null. Hvis GCD mellom 30 og 18 måtte bli funnet ved subtraksjon, ville den første forskjellen for GCD mellom 30 og 18 være 12, og det kan vises at GCD mellom 30 og 18 er 6. 18 Mod 12 er ikke null. Hvis GCD mellom 18 og 12 måtte finnes ved subtraksjon, ville den første forskjellen for GCD mellom 18 og 12 være 6, og det kan vises at GCD mellom 18 og 12 er 6. 12 Mod 6 er null. Hvis GCD mellom 12 og 6 måtte bli funnet ved subtraksjon, ville den første forskjellen for GCD mellom 12 og 6 være 6, og det kan vises at GCD mellom 12 og 6 er 6. 6 er også et multiplum av 6 selv, som er GCD.

Ved å bruke noen måter kan leseren bevise med de ovennevnte trinnene som gitt at GCD for 30 og 18 er 6, GCD for 18 og 12 er også 6; og GCD for 12 og 6 er fortsatt 6.

Tenk nå på GCD oppnådd fra 1 og 5 ved divisjon:

5 % 1 = 0 (i.e. 5 r 0)

Det er bare ett trinn (en linje) her. For å avslutte denne delen, må du merke deg at divisoren på den siste linjen, når du leter etter GCD etter divisjon, er GCD.

Legg også merke til at:

GCD (A, B) = GCD (B, R)

Hvor “A” og “B” er to forskjellige hele tall og “R” er resten av divisjonen mellom A og “B.”“ B ”kan være større enn“ A ”eller“ A ”kan være større enn B. Dette betyr at hvis resten av en divisjon ikke er null, så er den største vanlige divisoren mellom de to tallene den samme som den største vanlige divisoren mellom divisoren og resten. Beviset for denne uttalelsen er illustrert ovenfor.

Dette kan gå helt ned av Modulo Division, som opplevd ovenfor til resten er null. Når resten er null, holder ikke denne gjentatte regelen. Strengt tatt, i Modulus Division, spiller det ingen rolle om “A” er større enn B eller B er større enn “A”; resten er det samme positive heltallet.

Koding GCD etter divisjon

Hvis den største vanlige divisoren av divisjonen mellom 60 og 108 er påkrevd matematisk, ville trinnene være

108 % 60 = 48 (i.E 1 R 48)
60 % 48 = 12 (i.E 1 R 48)
48 % 12 = 0 (i.E 4 R 0)

Legg merke til at det er det større antallet som deler seg, det mindre antallet. Java -klassen og metoden for å gjøre denne divisjonen er:

klasse GCDD
int gcdd (int a, int b)
if (a % b == 0)
return b;
returner GCDD (B, A % B);

Den første uttalelsen i metoden står for det siste matematiske trinnet. Den andre uttalelsen gjør Modulo Division. Begge uttalelsene kaller metoden rekursivt. Tidskompleksiteten for GCD etter divisjon er O (log (A + B)). En god hovedklasse og hovedmetoden for denne koden er:

offentlig klasse Main
public static void main (String args [])
Gcdd obj = new GCDD ();
int ret = obj.GCDD (108, 60);
System.ute.println (ret);

Utgangen er 12.

Konklusjon

Den største vanlige divisoren kan oppnås ved først å trekke fra det mindre antallet fra det større antallet og deretter fortsette å trekke fra minuend fra forskjellen eller forskjellen fra minuend, avhengig av hvilket antall som er større.

Den største vanlige divisoren kan også oppnås ved først å dele det større tallet med det mindre antallet ved bruk av modulusdivisjon; og fortsetter å dele resten av divisoren eller divisoren med resten, avhengig av hvilken som er større, fremdeles etter modulavdeling. Strengt tatt, i Modulus Division, spiller det ingen rolle om “A” er større enn B eller B er større enn “A”; resten er det samme positive heltallet.

Dette gjøres programmatisk rekursivt.