[Algorithm] GCD - LCM / FPB - KPK
Categories: Algoritma, Programming | May 13th, 2008 | by Felix J | 2 CommentsCukup sudah intermezzo nya kali ini :), pada post ini yang akan kujelaskan disini adalah algoritma untuk menentukan FPB dan KPK. Sejauh ini, Algoritma tercepat untuk menghitung FPB adalah Euclid Algorithm (Algortima Euclid). Apakah maksud dari Algoritma ini? Euclid menemukan bahwa FPB(a, b) atau GCD(a, b) *dalam post ini, saya akan gunakan GCD / LCM saja 
* sama dengan GCD (b, a % b) dimana tanda ‘%’ adalah lambang dari modulo yaitu sisa pembagian.
Ok, selanjutnya kita coba cek Persamaan tersebut… kita ambil saja angka 24 dan angka 20
GCD (24, 20) = GCD(20 , 4) = GCD(4, 0)… Jika ada salah satu bilangan yang sudah mencapai angka 0, maka angka yang 1nya lagi adalah GCDnya… maka disini, GCDnya menurut Algoritma Euclid adalah 4… Apakah hal itu benar? Mari kita cek dengan Metode ‘Anak SD’ kita
24 = 2³ x 3
20 = 2² x 5
Maka FPBnya dengan metode ‘Anak SD’ adalah 2² yang berarti 4… Terbukti kan sekarang?
maka dengan ini, dengan logika diatas kita dapat membuat kodenya menjadi 2 versi…
1). Rekursi (Recursion Version)
2). Iterasi (Iteration Version)
wow… GCD nya simple banget… pernah coba bikin sih tp lbh panjang dari itu kyknya… LCM juga pernah bkn tp ga pake GCD nya sama sekali..
@ Hendri
^o^
ohh.. hehehe… iya, ini namanya Euclidean GCD
sebenarnya bs dibuat lebih singkat lg ^o^
int GCD(int a,int b) {
return (b==0) ? a : GCD(b,a%b);
}
^o^