[Algorithm] GCD - LCM / FPB - KPK
Categories: Algoritma, Programming | May 13th, 2008 | by Felix J | 10 CommentsMari kita mulai dengan versi Rekursi, Versi Rekursi dapat dengan mudah kita kode menjadi seperti ini:
1 2 3 4 5 6 7 | int GCD(int a, int b) { if (a%b==0) return b; else return GCD(b,a%b); } |
tapi karena versi Rekursi ini dapat menciptakan Recursion Tree, maka kita dapat mencoba mengubah kode diatas dengan versi iterasinya saja 
1 2 3 4 5 6 7 8 9 | int GCD(int a, int b) { while (b > 0) { a = a % b; // bisa juga ditulis menjadi a %= b; swap(a,b); } return a; } |
untuk kode swap diatas, akan saya bahas pada post berikutnya :).
Itu adalah Algoritma untuk GCD, bagaimana dengan algoritma untuk LCM? Silahkan buka halaman selanjutnya
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