Algoritma Euclid untuk Menentukan KPK dan FPB

Oleh Unknown

Saturday 25 May 2013

Bagikan :

Tweet

Algoritma ini telah berusia cukup lama. Algoritma Euclid sudah ditulis sejak 3 abad sebelum masehi, dan sampai sekarang masih digunakan di dunia komputasi.

GCD atau FPB dari dua buah bilangan adalah suatu bilangan terbesar yang dapat membagi habis kedua bilangan tersebut (tanpa meninggalkan sisa). FPB biasanya dipelajari di matematika saat SD. Cara konvensionalnya biasanya adalah seperti pembahasan berikut.

Misalkan, ditanya: Berapa FPB dari 24 dan 30? Kalau zaman saya dulu, guru saya mengajarkan untuk menuliskan seluruh faktor yang ada dari kedua bilangan tersebut, kemudian mencari angka terbesar yang sama-sama dimiliki oleh kedua bilangan tersebut.

Faktor dari 24:
1, 2, 3, 4, [6], 8, 12 dan 24
Faktor dari 30:
1, 2, 3, 5, [6], 10, 15 dan 30

Seperti yang bisa pembaca lihat di atas, jadi berapa FPB dari 24 dan 30? Dari faktor yang telah diuraikan dari kedua bilangan tersebut, bilangan terbesar yang sama-sama dimiliki oleh kedua bilangan tersebut adalah 6. Berarti, 6 adalah FPB dari 24 dan 30.

Masalah di atas mungkin mudah diselesaikan jika angkanya relatif kecil, tetapi bagaimana kalau angkanya besar?

Kalau secara algoritmik, tentu akan sulit jika program yang dibuat harus mendata terlebih dahulu faktor-faktor dari masing-masing bilangan kemudian mencari angka terbesar yang sama-sama terdapat di daftar faktor dari kedua bilangan tersebut. Selain dibutuhkan variabel tambahan, tentu waktu komputasinya akan lebih lama. Karena itu butuh cara lain untuk menyelesaikannya.

Deskripsi dari Algoritma Euclidean ini adalah sebagai berikut:

Misalkan terdapat dua buah bilangan yaitu m dan n, maka GCD/FPB dari kedua bilangan tersebut dapat dihitung dengan langkah berikut:

Bagi bilangan m dengan n dan anggap r adalah sisa bagi dari kedua bilangan tersebut. Nilai dari r akan memenuhi 0 <= r < n.
Jika nilai r = 0, maka algoritma selesai. n adalah solusinya. Tapi jika ternyata tidak, maka:
Set nilai m menjadi n, dan nilai n menjadi r, kemudian kembali ke langkah 1.

m = 24, n = 30
gcd(m, n):
24 / 30 = 0, r = 24
r tidak sama dengan 0, maka
m = n, n = r -> m = 30, n = 24
gcd(m, n):
30 / 24 = 1, r = 6
r tidak sama dengan 0, maka
m = n, n = r -> m = 24, n = 6
gcd(m, n):
24 / 6 = 0, r = 0
karena r = 0, maka hasilnya adalah n.
Jadi gcd(24, 30) = gcd(30, 24) = gcd(24, 6) = 6

Bagaimana dengan KPK? KPK adalah hasil kali kedua buah bilangan dibagi dengan FPB. contoh:
FPB dari 8 dan 12 adalah 4
KPK := (8*12)/4 = 24

nih contoh kode dari ane :

#include <iostream>
using namespace std;
int fpb(int x, int y){
    if(x==0){
        return y;
    }else if(y==0){
        return x;
    }else{
        return fpb(y, x%y);
    }
}
int kpk(int x, int y){
    return (x*y)/fpb(x,y);
}
int main(){
    int x,y;
    while(1){
        cout<<"variabel x = "; cin>>x;
        cout<<"variabel y = "; cin>>y;
        cout<<"FPB dari "<<x<<" dan "<<y<<" adalah "<<fpb(x, y)<<endl; 
        cout<<"KPK dari "<<x<<" dan "<<y<<" adalah "<<kpk(x, y)<<endl<<endl;
    }
    return 0;
} 

referensi :
http://imamhidayatsite.wordpress.com/2012/06/30/menghitung-faktor-persekutuan-terbesar-menggunakan-algoritma-euclid-implementasi-dalam-bahasa-c-dan-pascal/
http://newidea39.blogspot.com/2013/03/algoritma-fpb-dan-kpk-algoritma-euclid.html

Tag : Cplus-plus, Programming