Anda sedang menggunakan mode :

Mencari FPB dengan algoritma Euclid

0

Written on 03.00 by Muharrom, Muhammad Aji

     FPB (Faktor Persekutuan terBesar), bisa juga disebut GCD (Greatest Common Divisor) dari dua atau lebih bilangan bulat positif bukan nol, adalah bilangan bulat positif terbesar yang dapat membagi dua atau lebih bilangan bulat bukan nol tersebut tanpa sisa.

     Banyak metode yang dapat digunakan untuk mencari FPB. Di SD / SMP, metode yang umum digunakan ialah metode pagar dan metode pohon faktor. Metode pagar maupun metode pohon faktor efektif untuk bilangan-bilangan kecil. Jika bilangan yang dicari FPB-nya besar, maka lebih efektif menggunakan algoritma Euclid.

     Algoritma Euclid ialah algoritma yang dilaksanakan secara bertahap, step by step, di mana hasil yang didapat dari suatu tahap akan digunakan lagi pada tahapan selanjutnya. Prosedur pada algoritma Euclid ialah mencari sisa (remainder) dari pembagian bilangan yang lebih besar (kita misalkan a) dengan bilangan yang lebih kecil (misalkan b). Anggap sisa a dibagi b sebagai r1. Jika r1 bukan nol, langkah selanjutnya ialah mencari sisa dari b dibagi r1

     Jika sisanya masih bukan nol, maka selanjutnya mencari lagi sisa r1 dibagi r2 (r2 ialah sisa dari b dibagi r1). Jika masih belum nol, maka mencari lagi sisa r2 dibagi r3. Begitu seterusnya sampai sisa pembagian ialah 0. Misalnya ditemukan sisa dari rn-1 dibagi rn ialah 0, maka FPB dari dua bilangan yang tadi dicari (a dan b) ialah rn. Secara matematis, prosedur ini dapat ditulis sebagai :

(Ingat bahwa jika a mod b = r1 maka bisa diartikan bahwa a = qb + r1 )


Berarti, pada persamaan di atas FPB(a, b) = rn.  Yang perlu diingat pada algoritma Euclid ialah bahwa remainder atau sisa tidak boleh negatif, harus bernilai positif (mana ada sisa bernilai negatif, ya nggak? Tapi kalo menggunakan modular, nilai negatif bisa tercipta.)

     Sekarang setelah kita tahu teorinya, mari kita praktekkan (ini bagian yang paling mengasyikkan 'kan? :D). Misalnya bilangan yang "kecil" dulu deh, FPB(3456, 321).










     Di sini kita temukan bahwa sisa menjadi nol saat tahap ke-7, yaitu ketika mencari sisa 9 dibagi 3. Ini menandakan bahwa FPB(3456, 321) = 3. (Kalo tidak percaya, silahkan buktikan sendiri dengan metode pohon faktor atau metode pagar. Bisa ampe mbuki tuh, hehehe :D ).

     Nah, sekarang kita telah belajar untuk mencari FPB dua bilangan. Lantas, bagaimana jika bilangannya lebih dari satu? Misalnya ada tiga bilangan. Pada metode pagar sih mudah saja ya, tapi bagaimana dengan metode algoritma Euclid? Anggap bilangan-bilangan itu ialah a, b, dan c, maka FPB(a, b, c) = FPB( FPB(a, b), c). Dengan demikian, algoritma Euclid juga masih dapat digunakan untuk mencari FPB dua atau lebih bilangan bulat.

     Oke, sampai di situ dulu artikel kali ini. Selengkapnya bisa dilihat di wikipedia, yaitu di sini (tentang gcd) atau di sini (tentang algoritma Euclid)

If you enjoyed this post Subscribe to our feed

No Comment

Posting Komentar