Algoritma Euclid untuk Menentukan KPK dan FPB

Mei 25, 2013

<div><div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
 
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. 
 
<blockquote class="tr_bq">
Faktor dari 24: 
1, 2, 3, 4, [6], 8, 12 dan 24 
Faktor dari 30: 
1, 2, 3, 5, [6], 10, 15 dan 30</blockquote>
 
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. 
 
<blockquote>
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</blockquote>
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 : 
 
<pre class="brush:cpp">#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;
} </pre>
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://i44.tinypic.com/5dpgs2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://i44.tinypic.com/5dpgs2.png" /></a></div>
 
referensi : 
<a href="http://imamhidayatsite.wordpress.com/2012/06/30/menghitung-faktor-persekutuan-terbesar-menggunakan-algoritma-euclid-implementasi-dalam-bahasa-c-dan-pascal/">http://imamhidayatsite.wordpress.com/2012/06/30/menghitung-faktor-persekutuan-terbesar-menggunakan-algoritma-euclid-implementasi-dalam-bahasa-c-dan-pascal/</a> 
<a href="http://newidea39.blogspot.com/2013/03/algoritma-fpb-dan-kpk-algoritma-euclid.html">http://newidea39.blogspot.com/2013/03/algoritma-fpb-dan-kpk-algoritma-euclid.html</a></div>
</div>

Tidak ada komentar

Fudanshi

Algoritma Euclid untuk Menentukan KPK dan FPB

Recent Big Posts

Categories

Tags Cloud

Comments

Latest

Random

Flickr

4/Food

Popular Posts