Największy wspólny dzielnik z Javą
Znaczenie największego wspólnego dzieliny
Dzielenie to liczba całkowita (liczba całkowita), która wejdzie w inną liczbę całkowitą bez reszty. Największy wspólny dzielnik najlepiej wyjaśnić ilustracją. Poniższa tabela pokazuje dwie liczby: 60 i 108, z wszystkimi ich dzielnikami większymi niż 1.
W tabeli są dzielniki, które nie są wspólne zarówno dla 60 i 108. Jednak 2 jest wspólnym dzielnikiem zarówno liczb 60, jak i 108, ale nie jest to największy dzielnik wspólny dla 60 i 108. Divisor 3 jest podobnie opisany. Przez kontrolę tabeli największy dzielnik, który jest wspólny zarówno dla 60, jak i 108, jest 12. Żaden dzielnik powyżej 12 jest powszechny zarówno w 60, jak i 108. Więc 12 jest największym wspólnym dzielnikiem dla 60 i 108.
Celem tego artykułu jest wyjaśnienie, jak uzyskać największy wspólny dzielnik przez odejmowanie lub podział; z programowaniem wykonanym w Javie.
GCD przez odejmowanie
Przez kontrolę z powyższej tabeli GCD dla 60 i 108 wynosi 12. Oznacza to, że jeśli 12 będzie dodawane wielokrotnie, wynik stanie się 60, mniejszy z obu liczb. Jeśli dodanie 12 będzie kontynuowane, wynik stanie się 108, większa z obu liczb. To jest:
12 + 12 +12 +12 + 12 = 60
12 + 12 +12 +12 + 12 = 60 + 12 + 12 + 12 + 12 = 108
To jest:
60 + 12 + 12 + 12 + 12 = 108
Co znaczy:
60 + 48 = 108
Jeśli dodanie GCD może prowadzić do obu liczb, być może jakaś forma ciągłego odejmowania w dół może prowadzić do GCD. Jest to fakt, jak ilustruje następujące kroki, zaczynając od różnicy 108 i 60:
108 - 60 = 48
60 - 48 = 12
48 - 12 = 36
36 - 12 = 24
24 - 12 = 12
12 - 12 = 0
Od 60 do 108, 108 to większa liczba. Następnie różnica powstałej różnicy (48 dla pierwszego kroku) i podtrzesz (60 dla pierwszego kroku) jest uzyskiwana wielokrotnie, aż odpowiedź wyniesie zero. W etapach mniejsza liczba jest odejmowana, większa liczba. Na ostatnim kroku minuend i podtwórcy są takie same. Ta sama wartość jest największym wspólnym dzielnikiem.
Niech liczby, których GCD jest potrzebne, będą A i B. Jeśli liczby te nie mają GCD większe niż 1, oznacza to, że ich największym wspólnym dzielnikiem wynosi 1. W programowaniu złożoność czasu na znalezienie GCD przez odejmowanie wynosi O (A+B). Jeśli A to 1, a B to 5, wówczas kroki bez programowania będą:
5 - 1 = 4
4 - 1 = 3
3 - 1 = 2
2 - 1 = 1
1 - 1 = 0
GCD tutaj jest 1. Jest tu pięć kroków, a nie sześć kroków (A + B). Jednak w programowaniu maksymalna możliwa liczba operacji kodu jest tym, co jest traktowane jako złożoność czasu.
Kodowanie GCD przez odejmowanie
Klasa i metoda największego wspólnego dzielnika według odejmowania w Javie to:
klasa GCDSint gcds (int a, int b)
if (a == b)
zwrot a;
if (a> b)
return GCDS (A-B, B);
return GCDS (A, B-A);
Zaczyna się od stwierdzenia ostatniego etapu matematycznego, gdy obie wynikowe liczby są równe. Następne dwa instrukcje odejmują mniejszą liczbę od większej liczby rekurencyjnie. Główna klasa Java i główna metoda Java, aby przejść z powyższą klasą, to:
Klasa publiczna Mainpublic static void main (string args [])
Gcds obj = new gcds ();
int ret = obj.GCD (108, 60);
System.na zewnątrz.println (ret);
Wyjście to 12.
GCD według podziału
Powyższa tabela jest tutaj powtarzana dla łatwego odniesienia:
Dwie liczby, których potrzebny jest GCD, to 60 i 108, przy czym 108 jest większą liczbą. Powyższe wyjaśnienie odejmowania rozpoczęło się od:
12 + 12 +12 +12 + 12 = 60
12 + 12 +12 +12 + 12 = 60 + 12 + 12 + 12 + 12 = 108
To jest:
60 + 12 + 12 + 12 + 12 = 108
Co znaczy:
60 + 48 = 108
Dział Modulo jest podziałem, w którym odpowiedź jest częścią liczbową ilorazu, a reszta jest również brana pod uwagę. Rozważ resztę, dzieląc 108 przez 60 i resztki powstałych ilorazów i odpowiadających im dzielników.
108 % 60 = 48 (i.e 1 r 48)
60 % 48 = 12 (i.e 1 r 48)
48 % 12 = 0 (i.e 4 r 0)
Dział modułu kończy się, gdy reszta wynosi 0. GCD jest dzielnikiem ostatniego kroku. Z drugiej metody wiadomo było, że największy wspólny dzielnik to 12.
108 Mod 60 nie jest zerowy. Gdyby GCD od 60 do 108 musiała zostać znaleziona przez odejmowanie, pierwsza różnica dla GCD między 60 a 108 wynosiłaby 48 i można wykazać, że GCD między 60 a 108 jest 12 to 12. 60 mod 48 nie jest zero. Gdyby GCD od 60 do 48 (poprzednia pozostała część) musiała zostać znaleziona przez odejmowanie, pierwsza różnica dla GCD od 60 do 48 wynosiłaby 12 i można wykazać, że GCD między 60 a 48 to 12 to 12. 48 Mod 12 jest zero i ma 0 pozostałych. Gdyby GCD od 48 do 12 musiała zostać znaleziona przez odejmowanie, pierwsza różnica dla GCD między 48 a 12. 36 nie jest GCD między 48 a 12; Jednak 36 to wielokrotność 12, czyli GCD.
Używając dowolnych środków, czytelnik może udowodnić z powyższymi krokami, które biorąc pod uwagę, że GCD dla 60 i 108 wynosi 12, GCD dla 60 i 48 również wynosi 12; a GCD dla 48 i 12 jest nadal 12.
Rozważ inny przykład, aby znaleźć GCD według podziału. Problem jest teraz: znaleźć GCD według podziału dla liczb 18 i 30.
Rozwiązanie:
30 % 18 = 12 (i.mi. 1 r 12)
18 % 12 = 6 (i.mi. 1 r 6)
12 % 6 = 0 (i.mi. 2 R 0)
GCD to 6, odczytany z ostatniego wiersza, gdzie moduł to 0.
30 Mod 18 nie jest zero. Gdyby GCD od 30 do 18 musiała zostać znaleziona przez odejmowanie, pierwsza różnica dla GCD od 30 do 18 wynosiłaby 12 i można wykazać, że GCD między 30 a 18 to 6 to. 18 Mod 12 nie jest zero. Gdyby GCD od 18 do 12 musiała zostać znaleziona przez odejmowanie, pierwsza różnica dla GCD od 18 do 12 wynosiłaby 6 i można wykazać, że GCD między 18 a 12 to 6 to. 12 Mod 6 to zero. Gdyby GCD od 12 do 6 musiała zostać znaleziona przez odejmowanie, pierwsza różnica dla GCD od 12 do 6 wynosiłaby 6 i można wykazać, że GCD między 12 a 6 to 6 to. 6 jest również wielokrotnością 6, czyli GCD.
Korzystając z dowolnych środków, czytelnik może udowodnić powyższe kroki, które biorąc pod uwagę, że GCD dla 30 i 18 wynosi 6, GCD dla 18 i 12 jest również 6; a GCD dla 12 i 6 jest nadal 6.
Rozważ teraz GCD uzyskane z 1 i 5 według podziału:
5 % 1 = 0 (i.mi. 5 R 0)
Jest tutaj tylko jeden krok (jedna linia). Aby zakończyć tę sekcję, pamiętaj, że dzielnik na ostatnim wierszu, szukając GCD według podziału, jest GCD.
Zwróć również uwagę, że:
GCD (A, B) = GCD (B, R)
gdzie „a” i „b” to dwie różne liczby całkowitą, a „r” to reszta podziału między a i „b.„B” może być większe niż „A” lub „A” może być większe niż B. Oznacza to, że jeśli pozostała część podziału nie jest zerowa, wówczas największy wspólny dzielnik między dwiema liczbami jest taki sam jak największy wspólny dzielnik między dzielnikiem a resztą. Dowód tego stwierdzenia został zilustrowany powyżej.
Może to zejść w dół według podziału modulo, jak doświadczyła się powyżej, dopóki reszta wyniesie zero. Gdy reszta jest zerowa, ta powtarzająca się zasada nie utrzymuje. Ściśle mówiąc, w podziale modułu nie ma znaczenia, czy „A” jest większe niż B lub B, jest większe niż „A”; Pozostała część to ta sama pozytywna liczba całkowita.
Kodowanie GCD według podziału
Jeśli największy wspólny dzielnik od podziału między 60 a 108 jest wymagany matematycznie, wówczas kroki będą
108 % 60 = 48 (i.e 1 r 48)
60 % 48 = 12 (i.e 1 r 48)
48 % 12 = 0 (i.e 4 r 0)
Zauważ, że dzieli się większa liczba, mniejsza liczba. Klasa Java i metoda wykonania tego podziału to:
klasa gcddint gcdd (int a, int b)
if (a % b == 0)
powrót B;
Zwrot GCDD (B, A % B);
Pierwsze stwierdzenie w metodzie obejmuje ostatni krok matematyczny. Drugie stwierdzenie odbywa się w dziale modulo. Oba stwierdzenia wywołują metodę rekurencyjnie. Złożoność czasu dla GCD według podziału wynosi O (log (A + B)). Dobra klasa główna i główna metoda tego kodu to:
Klasa publiczna Mainpublic static void main (string args [])
Gcdd obj = new gcdd ();
int ret = obj.GCDD (108, 60);
System.na zewnątrz.println (ret);
Wyjście to 12.
Wniosek
Największy wspólny dzielnik można uzyskać, najpierw odejmując mniejszą liczbę od większej liczby, a następnie kontynuować odejmowanie minuend od różnicy lub różnicy od minuend, w zależności od tego, która liczba jest większa.
Największy wspólny dzielnik można również uzyskać, najpierw podzielenie większej liczby przez mniejszą liczbę za pomocą podziału modułu; a następnie kontynuowanie dzielenia reszty przez dzielnika lub dzielnika przez resztę, w zależności od tego, który jest większy, wciąż przez podział modułu. Ściśle mówiąc, w podziale modułu nie ma znaczenia, czy „A” jest większe niż B lub B, jest większe niż „A”; Pozostała część to ta sama pozytywna liczba całkowita.
Odbywa się to programowo rekurencyjnie.