Logika FPB (Faktor Persekutuan Terbesar)




Masih ingat pelajaran matematika tentang FPB...?

FPB merupakan singkatan dari Faktor Persekutuan Terbesar dalam bahasa inggris sering disebut GCD (Common Greatest Divisor).

FPB  dari dua bilangan bulat positif adalah bilangan bulat positif terbesar yang membagi habis kedua bilangan tersebut.






Sebagai Contoh : 

Faktor pembagi dari angka 10 yaitu 1, 2, 5, 10. Perhatikan bahwa faktor pembagi angka 10 = 1, 2, 5, 10, maksudnya adalah angka 10 habis dibagi dengan angka 1, angka 10 habis dibagi angka 2, angka 10 habis dibagi angka 5, dan angka 10 habis dibagi oleh angka 10.


Contoh soal :
Tentukan FPB dari 12 dan 18
Faktor 12 = 1, 2, 3, 4, 6, 12.
Faktor 18 = 1, 2, 3, 6, 9, 18.

Perhatikan faktor pembagi diatas, yang sama dari kedua bilangan adalah 1,2,3 dan 6, maka yang paling besar adalah 6. sehingga FPB dari 12 dan 18 adalah 6


Algoritma Euclid

Euclid adalah seorang matematikawan yunani, lahir pada tahun 350 M, dalam bukunya yang berjudul Element, Euclid menuliskan langkah-langkah untuk menemukan pembagi bersama terbesar dari dua buah bilangan bulat positif.

Misalnya :
Berapakah FPB dari 80 dan 12 ?
Jika kita mengerjakan secara manual, kita hanya perlu mencari faktor pembagi dari tiap bilangan saja, yaitu:

Faktor 80 = 1,2,4,5,8,10,20,40,80
Faktor 12 = 1,2,3,4,6,12

Hasilnya adalah 4

Bagiamana jika kita ingin menerapkannya pada komputer?

Mari kita pelajari langkah-langkahnya untuk diterapkan dengan bahasa pemrograman.

  1. Tentukan mana bilangan terbesar dari 2 buah bilangan yang diberikan (dalam contoh soal 80)
  2. Cek apakah dari kedua bilangan sama dengan 0, jika ada maka hasilnya pasti 0
  3. Modulo bilangan yang paling besar dengan yang terkecil jika hasilnya 0 maka jawabannya bilangan terkecil, jika tidak lanjutkan proses modulo.
Contoh dari soal diatas.

80 modulo 12 = 6, sisa 8
12 modulo 8 = 1, sisa 4
8 modulo 4 = 2, sisa 0

Karena pembagian terakhir menghasilkan 0, maka jawabannya adalah 4 (ingat langkah no.3)


Catatan: 
Modulo adalah sisa dari pembagian (biasanya dalam bahasa pemrograman disimbolkan dengan % atau mod [lihat dokumntasi bahasa yang digunakan]).
Sebagai Contoh:

10 % 2? 

maksudnya adalah 10 dibagi 2 sisa berapa ? 10/2 = 5 sisa 0 karena 2 x 5 = 10, sehingga 10-10 = 0

10 % 3?

10 dibagi 3 = 3 sisa 1 karena 3x3 = 9, sehingga 10-9 = 1


Implementasi Bahasa C


#include "stdio.h"
#include "conio.h"

int fpb(int a, int b);

void main() {
 int a,b,tmp;
 clrscr();
 printf("Menghintung FPB dari dua buah bilangan\n");
 printf("======================================\n");
 printf("Input bilangan cth : 4 3 = ");scanf("%d %d",&a,&b);

 printf("FPB(%d,%d) = %d",a,b,fpb(a,b));
 getche();
}

int fpb(int a, int b) {
 int tmp;
 tmp=0;

 //mengecek apakah bilangan pertama lebih besar
 //dari bilangan ke dua
 if(a < b) {
  tmp=a;
  a=b;
  b=tmp;
 }

 //mengecek apakah salah satu bilangan sama dengan 0
 if(a==0 || b==0) {
  return 0;
 }

 //proses pencarian FPB
 while(b != 0 ){
  if(a%b==0){
   return b;
  }
  tmp=a%b;
  a=b;
  b=tmp;
 }

   return tmp;
}

Implementasi Bahasa GO


package main

import (
 "fmt"
)

func main() {
 a := 0
 b := 0

 fmt.Println("Menghitung FPB dari dua buah bilangan")
 fmt.Println("=====================================")
 fmt.Print("Input bilangan bulat positif [contoh: 4 3 ]")
 fmt.Scanln(&a, &b)
 fmt.Printf("FPB(%d, %d) = %d", a, b, fpb(a, b))
}

func fpb(a, b int) int {
 tmp := 0

 // cek apakah bilangan pertama lebih kecil dari bilangan kedua
 // jika ya tukarkan
 if a < b {
  a, b = b, a
 }

 // mengecek apakah salah satu bilangan sama dengan 0
 if a == 0 || b == 0 {
  return 0
 }

 // proses FPB
 for b != 0 {
  if a%b == 0 {
   return b
  }
  tmp = a % b
  a, b = b, tmp
 }
 return tmp
}


Logika FPB (Faktor Persekutuan Terbesar) Logika FPB (Faktor Persekutuan Terbesar) Reviewed by jc on September 11, 2018 Rating: 5

No comments:

Powered by Blogger.