Maaf kalau saya akan membahas teori terlebih dahulu. Untuk kalian yang cuma butuh kode program / source code-nya, scroll mouse kalian untuk menemukan bagian bawah halaman.
Algoritma Euclid
Untuk mencari FPB dengan algoritma Euclid kita harus memahami penggunaan operator modulus / sisa hasil bagi. Operator modulus menghasilkan pengurangan bilangan dengan bilangan terdekat yang bisa dibagi oleh pembagi.
- Misalnya, "26 mod 3 = 26 – 24 = ( 26 - ( 8 x 3 )) = 2".
Dalam bahasa C atau C++, operator modulus ditulis dengan tanda "%". Operatornya disebut dengan modulo. Untuk mempermudah penjelasan, saya akan gunakan "mod" untuk menuliskan operator modulus seperti penulisan dalam bahasa pascal dan tombol kalkulator.
Algoritma Euclid menggunakan operator mod untuk mencari sisa hasil bagi dari bilangan pertama dan kedua. Kemudian proses diulang dengan menukar bilangan kedua menjadi bilangan pertama dan hasilnya sebagai bilangan kedua. Proses diulang terus menerus dan bilangan pertama dibagi dengan bilangan kedua selama hasilnya belum sama dengan "0". Untuk lebih mudahnya perhatikan gambar di bawah ini.
Gambar di atas menunjukkan cara mencari FPB dari 120 dan 88. Berikut ini penerapan algoritma euclid untuk mencari FPB dari 2 bilangan dengan Bahasa C. Saya menggunakan 120 dan 88 sebagai bilangan yang dicari FPB-nya. Hasilnya seharusnya adalah 8 seperti contoh di atas.
#include <stdio.h>
int FPB(int a, int b){
int r = 0;
while(b!=0){
r = a % b;
a = b;
b = r;
}
return a;
}
int main(){
int a=120;
int b=88;
printf("FPB %d dan %d : %d", a, b, FPB(a, b));
return 0;
}
Mencari FPB Lebih dari 2 Bilangan
#include <stdio.h>
int FPB(int a, int b){
int r = 0;
while(b!=0){
r = a % b;
a = b;
b = r;
}
return a;
}
int main(){
int a[3];
int i, x, n;
a[0]=120;
a[1]=20;
a[2]=88;
i=1;n=3;
x=a[0];
while(i<n){
x=FPB(x, a[i]);
i++;
}
printf("FPB (%d, %d, %d) : %d", a[0], a[1], a[2], x);
return 0;
}
Contoh di atas menggunakan 3 bilangan yang disimpan dengan Array. Ubah ukuran array dan sesuaikan nilai variabel n jika kalian ingin menggunakan lebih banyak bilangan.
Menggunakan Array Dinamis
Kalian juga bisa menerapkannya untuk lebih dari 3 bilangan. Kalian bisa menggunakan Array statis ataupun dinamis. Jika kalian menggunakan array dinamis, kalian dapat mengubah program di atas menjadi seperti di bawah ini.
#include <stdio.h>
#include <stdlib.h>
int FPB(int a, int b){
int r = 0;
while(b!=0){
r = a % b;
a = b;
b = r;
}
return a;
}
int main(){
int *a;
int i, x, n;
printf("masukkan jumlah bilangan yang dicari FPB-nya : ");
scanf("%d", &n);
a=(int*)malloc(n*sizeof(int));
i=0;
while(i<n){
printf("bilangan ke %d : ", i+1);
scanf("%d", &a[i]);
i++;
}
i=1;
x=a[0];
while(i<n){
x=FPB(x, a[i]);
i++;
}
printf("FPB : %d", x);
free(a);
return 0;
}
Sekian penjelasan saya tentang cara mencari FPB. Jika ada kesalahan atau kekurangan mohon komentarnya.
Untuk kalian yang malas mengetik, source code-nya bisa kalian dapatkan di sini. Kalian bisa meng-compile dan menjalankannya dengan menggunakan Code::block.
3 comments
Klik di sini untuk berkomentarblog ente deh yang paleng lengkap penjelasan dari algo sampek ke coding nya. Semangat terus gan
JawabTerima kasih. :3
JawabMeski belum mengerti, tapi artikel ini benar-benar luar biasa, Bro.
Jawab