Mencari FPB dengan Algoritma Euclid

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. 

Ada beberapa cara untuk mencari FPB, misalnya dengan pohon faktor atau cara-cara lain yang mengharuskan untuk menyimpan nilai. Tapi, cara tersebut tidak efesien untuk diterapkan di dalam pemrograman. Algoritma Euclid menjadi cara yang paling efisien karena tidak butuh array jika angka yang yang dicari FPB-nya hanya ada 2.

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

Kalian harus mencari FPB 2 bilangan terlebih dahulu, jika dengan ingin mencari FPB 3 bilangan. Jika yang kalian cari adalah FPB dari 4 bilangan maka kalian harus mencari FPB 3 bilangan lainnya, dan seterusnya.

FPB dari "n-1 bilangan" dan Bilangan ke-n adalah FPB bilangan ke-n. Contohnya, jika kalian sudah menemukan FPB 2 bilangan kalian dapat menggunakannya sebagai bilangan pertama dan bilangan ke-3 dijadikan bilangan ke-2.

Mungkin kalian pusing dengan penjelasan saya. Karena itu lebih baik kalian perhatikan gambar di bawah ini supaya lebih mudah di pahami.

Pada gambar di atas FPB dicari dengan cara mencari FPB 2 bilangan. Perhatikan gambar! Bilangan yang belum digunakan untuk mencari FPB selalu dianggap sebagai bilangan ke-2. Untuk FPB 3 bilangan kalian bisa menggunakan "FPB dari bilangan pertama dan ke-2" sebagai Bilangan pertama. Untuk mencari FPB 4 bilangan kalian bisa menggunakan FPB 3 bilangan yang sudah diketahui, dan seterusnya.

Seperti saya jelaskan sebelumnya, untuk mencari "FPB n bilangan" kalian harus mencari "FPB n-1 bilangan". Jika "n=5" maka kalian harus mencari FPB 4 bilangan terlebih dahulu. Karena jika n=5, maka n-1=5-1 = 4).

kalian bisa mulai dengan mencari FPB 2 bilangan, berapapun bilangan yang kalian cari FPB-nya. Jika belum jelas perhatikan gambar di bawah ini dan bandingkan dengan gambar di atas.

Pada contoh di atas saya mengganti semua hurufnya dengan angka. Semoga penjelasan saya sudah cukup jelas dengan gambar di atas.

Berikutnya saya akan menjelaskan penerapannya dalam pemrograman dengan C++.  Kalian bisa menuliskan kode program seperti di bawah ini untuk mencari FPB 3 bilangan atau lebih.

#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.

• Tweet
• Share
• Share
• Share