Algoritma untuk mencari Faktor Persekutuan Terbesar (FPB)
Kali ini akan disajikan beberapa algoritma untuk mencari Faktor Persekutuan Terbesar atau yang lazim disingkat FPB. FPB dari dua buah bilangan adalah bilangan terbesar yang dapat membagi habis kedua bilangan tersebut.
Contohnya:
- FPB dari 12 dan 18 adalah 6
- FPB dari 27 dan 54 adalah 27
- FPB dari 7 dan 5 adalah 1
Cara paling sederhana
Cara paling sederhana adalah dengan interasi setiap bilangan mulai dari bilangan yang lebih kecil dari kedua bilangan, hingga bilangan 2. Jika ditemukan bilangan yang membagi kedua bilangan tanpa sisa, iterasi dihentikan dan bilangan pembagi itulah FPB dari keduanya. Jika tidak ditemukan, maka FPB dari kedua bilangan adalah 1.
Berikut contoh kode berdasarkan algoritma di atas
Algoritma Euclid
Algoritma Euclid adalah algoritma yang sangat efisien untuk menemukan FPB dari buah bilangan. Nama algoritma ini berasal dari nama ahli matematika yunani Euclid, yang pertama kali menuliskannya pada karyanya Elements, sekitar 300 tahun sebelum masehi. Algoritma ini tergolong salah satu contoh algoritma tertua dalam sejarah manusia, yang mendemonstrasikan penggunaan langkah demi langkah yang sangat spesifik untuk melakukan kalkulasi. Pembahasan yang lebih detail tentang algoritma ini dapat dilihat di: wikipedia, MIT courseware.
Secara ringkas algoritma ini menyatakan bahwa FPB dari dua bilangan sama dengan FPB dari bilangan kedua dengan sisa pembagian antara keduanya. Atau FPB(a,b) = FPB(b,a mod b). Pernyataan ini kemudian dapat dikonversi menjadi sebuah fungsi rekursif seperti cuplikan di bawah.
def cari_fpb(a,b):
if b == 0:
return a;
else:
return cari_fpb(b,a%b)
Jalankan kode berikut untuk lebih jelasnya:
Semoga bermanfaat,
Salam
