Algoritma Mencari FPB dan KPK

FPB dan KPK, masih pada ingat kan apa ini? :D

FPB adalah Faktor Persekutuan terBesar atau dalam bahasa inggrisnya Greatest Common Divisor (GCD) sering dikelan juga dengan sebutan Greatest Common Factor (GCF) atau Highest Common Factor (HCF).  Dalam matematika, FPB dari dua bilangan adalah bilangan positif terbesar yang dapat membagi habis kedua bilangan itu.

Contoh mencari FPB dari 12 dan 20:

  • Faktor dari 12 = 1, 2, 3, 4, 6 dan 12
  • Faktor dari 20 = 1, 2, 4, 5, 10 dan 20
  • FPB dari 12 dan 20 adalah faktor sekutu (sama) yang terbesar, yaitu 4.

KPK adalah Kelipatan Persekutuan Terkecil (bukan Komisi Pemberantasan Korupsi lho) atau dalam bahasa Inggrisnya Least Common Multiple (LCM). Sering juga disebut sebagai Lowest Common Multiple (LCM) atau Smallest Common Multiple (SCM) . Dalam aritmatika dan teori bilangan, KPK dari dua bilangan adalah bilangan bulat terkecil yang habis dibagi oleh kedua bilangan itu.

Contoh mencari KPK dari 12 dan 20:

  • Kelipatan dari 12 = 12, 24, 36, 48, 60, 71, 84, …
  • Kelipatan dari 20 = 20, 40, 60, 80, 100, 120, 140, …
  • KPK dari 12 dan 20 adalah kelipatan sekutu (sama) yang terkecil, yaitu 60.

Jika kita yang mencari KPK mungkin masih bisa mencari dengan cara seperti di atas. Namun bagaimana caranya kita memerintahkan komputer untuk mencari FPB dan KPK?? Eits, ada triknya lho :)

Mencari FPB

Coba lihat potongan kode yang ditulis dalam pseudo-code di bawah ini:

Diasumsikan terdapat tiga buah variabel a,b, dan c. a dan b bernilai suatu angka yang ingin dicari fpbnya

selama (b taksama 0)

c = a mod b

a = b

b = c
akhir

coba kita perhatikan. Jika a adalah 24 dan b adalah 6 maka kita bisa menyebutkan bahwa FPB nya adalah 6. Sekarang kita lihat pada kode di atas. Kode akan mengevaluasi variabel-variabel yang kita sebutkan. Dalam perulangan di atas, kita mengevaluasi variabel b hingga bernilai 0. Jika kita ikuti alur program kita dapat memperhatikan:

dalam perulangan 1:

kondisi a = 24 dan b = 6

c akan diisi dengan 24 dimodulus (sisa bagi) dengan 6 menghasilkan nilai 0

a akan diisi dengan nilai 6

b diisi dengan nilai 0

perulangan kedua:

b bernilai 0 sehingga a adalah fpbnya.

Masih penasaran? Kita coba lagi dengan bilangan lain. Misal a = 28 dan b = 22. Cari dulu FPBnya? ketemu 2 kan? :D

Sekarang kita lihat di algoritma kita

perulangan pertama:

a bernilai 28 dan b bernilai 22

c diisikan nilai 28 dimodulus 22 yaitu 6 (28 dibagi 22 akan menghasilkan 1 dan menyisakan 6)

a akan bernilai 22

b bernilai c yaitu 6

perulangan kedua:

a bernilai 22 dan b bernilai 6

c diisikan nilai 22 dimodulus 6 yaitu 4 (22 dibagi 6 akan menghasilkan 3 dan menyisakan 4)

a akan bernilai 6

b bernilai c yaitu 4

perulangan ketiga:

a bernilai 6 dan b bernilai 4

c diisikan nilai 6 dimodulus 4 yaitu 2 (6 dibagi 4 akan menghasilkan 1 dan menyisakan 2)

a akan bernilai 4

b bernilai c yaitu 2

perulangan keempat:

a bernilai 4 dan b bernilai 2

c diisikan nilai 4 dimodulus 2 yaitu 0 (4 dibagi 2 akan menghasilkan 2 dan menyisakan 0)

a akan bernilai 2

b bernilai c yaitu 0

perulangan kelima:

b bernilai 0 sehingga fpbnya adalah a (bernilai 2)

Secara singkat begitu. Jika dilihat lebih lanjutkita dapat menuliskan seperti ini, dengan a=28 dan b = 22:

28 = 1 x 22 + 6
22 = 3 x 6 + 4
6 = 1 x 4 + 2
4 = 2 x 2 + 0 angka 2 yang bercetak tebal adalah hasil.

Mudah bukan? :D

Mencari KPK

Mencari KPK ternyata juga sederhana. Bagaimana caranya? Misal kita punya angka 4 dan 6.

4 = 2 x 2

6 = 2 x 3

Jika secara manual kita akan mendapatkan KPK bernilai 12 atau 2 x 2 x 3

Coba lihat lagi dengan saksama dan dalam tempo sesingkat-seingkatnya (bukan proklamasi pak!). Berapa FPB dari 4 dan 6? OK karena cuman 4 dan 6 kita bisa jawab dengan cepat, 2 ! Sadarkah teman-teman kalau 2 x KPK itu adalah hasil kali dari kedua bilangan?

4 x 6 = 24

atau

(2 x 2) x (2 x 3) = 2 x 2 x 2 x 3

Membagi 24 dengan FPB akan menghasilkan KPK

2 x 2 x 2 x 3 : 2 = 12

Sederhana bukan??

About these ads

5 Comments

  1. Nice share gan
    saya juga baru belajar bahasa c ne
    maba 2011 ne. saya kuliah di poltek batam.
    mohon bimbinganya ya tentang algoritma :D

  2. verry good gan,..
    saya juga maba di sebuah perguruan tinggi negeri dan banyak tugas berkaitan dengan kpk,..
    thx dah share gan, (^_^)

  3. sangat bermanfaat.

    post yg lebih banya lg tutorial bahasa C

    thx gan.

  4. Try Utomo

    sgt bermanfaat
    Mohon dikulas lebih dalam lagi bahasa C nya termasuk Logartmax
    trims atas infonya gan :)

  5. anyip

    iya mudah ternyata

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 38 other followers

%d bloggers like this: