PROGRAM ALGORITMA EUCLID DAN ARITMATIKA MODULO

Algoritma Euclidean merupakan algoritma yang digunakan untuk mencari gcd(greatest common divisor) atau FPB. Algoritma ini ditemukan oleh Euclid ahli matematika yunani yang tertulis pada bukunya Elements. Berikut ini algoritmanya:

1. a dan b merupakan bilangan bulat positif yang akan kita cari FPB nya.
2. hitung a mod b simpan di r. mod merupakan operasi sisa hasil bagi.
3. jika r=0, maka a merupakan FPB dari a dan b.
4. jika tidak, a diberi nilai b, dan b diberi nilai r, ulangi langkah ke 2.

Algoritma Euclid merupakan algoritma yang efisien untuk mencari FPB. Mungkin muncul pertanyaan, kenapa dengan algoritma yang simple ini kita dapat mencari FPB dengan benar.

Logika dari algoritma ini simple,

1. operasi a mod b = r, dapat kita tuliskan a= b*n + r. dimana n merupakan bilangan sembarang yang memenuhi persamaan.
2. jika r=0, maka b merupakan kelipatan dari a, jadi b merupakan FPB
3. jika r tidak sama dengan 0, maka suatu angka yang habis membagi a maupun b pasti habis membagi a - b*n = r
4. dan suatu angka yang habis membagi b dan r pasti habis membagi b*n + r = a

Jadi himpunan pembagi dari {a,b} sama dengan himpunan pembagi dari {b,r}. Misalkan FPBnya x:

• a=(x*p)
• b=(x*q)
• a-b*n=r
• (x*p)-(x*q)*n=r
• Jadi, x(p-q*n)=r
• b*n+r=a
• (x*q)*b+r=(x*p)

Source Code :

Dim a, b As Integer

Function faktor(n, m As Integer)

If n > m Then

z = n

Else

z = m

End If

Do

a = a + 1

X = n Mod a

Y = m Mod a

If X = 0 Then Text5.Text = Text5.Text & "[" & a & "]"

If Y = 0 Then Text6.Text = Text6.Text & "[" & a & "]"

If X = 0 And Y = 0 Then Text7.Text = a

Loop Until a = z

End Function

Private Sub Command1_Click()

a = 0

Call faktor(Val(Text1.Text), Val(Text2.Text))

Text3 = Val(Text1.Text) / Val(Text2.Text)

Text4.Text = Val(Text1.Text) Mod Val(Text2.Text)

End Sub

Private Sub Command2_Click()

Text1.Text = ""

Text2.Text = ""

Text5.Text = ""

Text6.Text = ""

Text7.Text = ""

Text1.SetFocus

End Sub

Private Sub Command3_Click()

pesan = MsgBox("Anda Yakin Ingin Keluar?", vbYesNo, "KELUAR")

If pesan = vbYes Then

End

End If

End Sub

semoga bermanfaat

Read More