[Algorithm] GCD - LCM / FPB - KPK
Categories: Algoritma, Programming | May 13th, 2008 | by Felix J | 10 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^
wew..ada pak felix ni ye….
mo tanya dung tpi….klo a<b apa gak crash ya prognya?thx b4…
@vedro,
Gk dunk, dengan jelas kita tahu bahwa jika a<b maka tentu aja di step rekursi selanjutnya akan dirubah a itu menjadi b, dan b menjadi a… liat contoh ini :
sebut saja jika kita memanggil, GCD(7,13), maka Karena B adalah 13, GCD(7,13) akan return GCD(13,7%13).
Kita tahu bahwa jika a < b, maka a%b = a. maka dari itu, GCD(13,7%13), ekuivalen dengan GCD(13,7) ( See? A > B sekarang
).
Proses berlanjut sampe b == 0, Gitu aja
interesting post, will come back here, bookmarked your site
ternyata GCD pake rekursi simple..
@boen,
yup… GCD bisa dicari dengan cara diatas
You write awsome article, bookmarked
Bung Felix, nyari GCD pake algoritma tadi ada kelemahannya g?
mhon dijawab butuh buat tugas nih
@adi belajar TI,
sayangnya… Tak ada