[Algorithm] GCD - LCM / FPB - KPK
Categories: Algoritma, Programming | May 13th, 2008 | by Felix J | 2 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^