Menemukan Pembagi Persekutuan Terbesar di Jawa

1. Ikhtisar

Dalam matematika, PBT dari dua bilangan bulat, yang bukan nol, adalah bilangan bulat positif terbesar yang membagi setiap bilangan bulat secara merata.

Dalam tutorial ini, kita akan melihat tiga pendekatan untuk menemukan Pembagi Persekutuan Terbesar (GCD) dari dua bilangan bulat. Selanjutnya, kita akan melihat implementasinya di Java.

2. Kekuatan Brute

Untuk pendekatan pertama kami, kami mengulangi dari 1 ke angka terkecil yang diberikan dan memeriksa apakah bilangan bulat yang diberikan dapat dibagi oleh indeks. Indeks terbesar yang membagi angka yang diberikan adalah PBT dari angka yang diberikan:

int gcdByBruteForce(int n1, int n2) { int gcd = 1; for (int i = 1; i <= n1 && i <= n2; i++) { if (n1 % i == 0 && n2 % i == 0) { gcd = i; } } return gcd; }

Seperti yang dapat kita lihat, kompleksitas dari implementasi di atas adalah O (min (n1, n2)) karena kita perlu melakukan iterasi pada loop sebanyak n kali (setara dengan angka yang lebih kecil) untuk mencari GCD.

3. Algoritma Euclid

Kedua, kita bisa menggunakan algoritma Euclid untuk menemukan GCD. Algoritma Euclid tidak hanya efisien tetapi juga mudah dipahami dan mudah diimplementasikan menggunakan rekursi di Java.

Metode Euclid bergantung pada dua teorema penting:

  • Pertama, jika kita mengurangi angka yang lebih kecil dari angka yang lebih besar, PBT tidak berubah - oleh karena itu, jika kita terus mengurangkan angka tersebut, kita akhirnya akan mendapatkan PBT mereka
  • Kedua, jika angka yang lebih kecil benar-benar membagi angka yang lebih besar, angka yang lebih kecil adalah PBT dari dua angka yang diberikan.

Perhatikan dalam implementasi kami bahwa kami akan menggunakan modulo daripada pengurangan karena pada dasarnya ini adalah banyak pengurangan sekaligus:

int gcdByEuclidsAlgorithm(int n1, int n2) { if (n2 == 0) { return n1; } return gcdByEuclidsAlgorithm(n2, n1 % n2); }

Perhatikan juga bagaimana kita menggunakan n2 pada posisi n1 dan menggunakan sisanya pada posisi n2 pada langkah rekursif dari algoritma .

Selanjutnya, kompleksitas algoritma Euclid adalah O (Log min (n1, n2)) yang lebih baik dibandingkan dengan metode Brute Force yang kita lihat sebelumnya.

4. Algoritma Stein atau Algoritma GCD Biner

Terakhir, kita dapat menggunakan algoritme Stein, juga dikenal sebagai algoritme Binary GCD , untuk mencari GCD dari dua bilangan bulat non-negatif. Algoritma ini menggunakan operasi aritmatika sederhana seperti pergeseran aritmatika, perbandingan, dan pengurangan.

Algoritme Stein berulang kali menerapkan identitas dasar yang terkait dengan GCD berikut untuk menemukan GCD dari dua bilangan bulat bukan negatif:

  1. gcd (0, 0) = 0, gcd (n1, 0) = n1, gcd (0, n2) = n2
  2. Jika n1 dan n2 keduanya adalah bilangan bulat genap, maka gcd (n1, n2) = 2 * gcd (n1 / 2, n2 / 2) , karena 2 adalah pembagi persekutuan
  3. Jika n1 adalah bilangan bulat genap dan n2 adalah bilangan bulat ganjil, maka gcd (n1, n2) = gcd (n1 / 2, n2) , karena 2 bukan pembagi persekutuan dan sebaliknya
  4. Jika n1 dan n2 keduanya adalah bilangan bulat ganjil, dan n1> = n2 , maka gcd (n1, n2) = gcd ((n1-n2) / 2, n2) dan sebaliknya

Ulangi langkah 2-4 sampai n1 sama dengan n2 , atau n1 = 0 . GCD-nya adalah (2n) * n2 . Di sini, n adalah berapa kali 2 ditemukan umum di n1 dan n2 saat melakukan langkah 2:

int gcdBySteinsAlgorithm(int n1, int n2) { if (n1 == 0) { return n2; } if (n2 == 0) { return n1; } int n; for (n = 0; ((n1 | n2) & 1) == 0; n++) { n1 >>= 1; n2 >>= 1; } while ((n1 & 1) == 0) { n1 >>= 1; } do { while ((n2 & 1) == 0) { n2 >>= 1; } if (n1 > n2) { int temp = n1; n1 = n2; n2 = temp; } n2 = (n2 - n1); } while (n2 != 0); return n1 << n; }

Kita dapat melihat bahwa kita menggunakan operasi pergeseran aritmatika untuk membagi atau mengalikan dengan 2. Selanjutnya, kita menggunakan pengurangan untuk mengurangi bilangan yang diberikan.

Kompleksitas algoritma Stein ketika n1> n2 adalah O ((log 2 n1) 2) sedangkan. ketika n1 <n2, itu adalah O ((log 2 n2) 2).

5. Kesimpulan

Dalam tutorial ini, kami melihat berbagai metode untuk menghitung GCD dari dua angka. Kami juga mengimplementasikannya di Java dan melihat sekilas kerumitannya.

Seperti biasa, kode sumber lengkap dari contoh kami di sini, seperti biasa, ada di GitHub.