Belajar Algoritma Euclid
Belajar Algoritma Euclid
Algoritma Eucid merupakan suatu algoritma yang digunakan untuk mencari Greatest Common Divisor (GCD) atau biasa dikenal dengan Fator Persekutuan Terbesar (FPB) dari dua bilangan. Salah satu kelebihan dari cara ini adalah tidak perlu mencari faktor prima dari kedua bilangan tersebut, hal ini tentu akan sangat membantu terutama saat mencari FPB dari bilangan-bilangan yang sangat besar.
Misalkan ada dua bilangan a dan b, untuk mencari FPB dari dan adalah dengan membagi bilangan yang lebih besar dengan bilangan yang lebih kecil (misal a > b). Dari hasil pembagian tersebut didapat hasil bagi dan sisa atau dapat dinotasikan dengan h untuk hasil dan s untuk sisa, sehingga didapat:
a : b = h + s ? a = h . b + s
Jika s = 0, maka FPBnya adalah b. tetapi jika s tidak sama dengan 0, maka
prosesnya diulang lagi dengan membagi b dengan s. Proses tersebut dilakukan seterusnya sampai menghasilkan sisa pembagian 0 dan FPBnya adalah sisa pembagian sebelumnya.
Contoh:
Tentukan FPB dari 3456 dan 246
Jawab:
3456 = 14 . 246 + 12
246 = 20 . 12 + 6
12 = 2 . 6 + 0
Sehingga diperoleh FPB (3456, 246) adalah 6.
Algoritma Eucid merupakan suatu algoritma yang digunakan untuk mencari Greatest Common Divisor (GCD) atau biasa dikenal dengan Fator Persekutuan Terbesar (FPB) dari dua bilangan. Salah satu kelebihan dari cara ini adalah tidak perlu mencari faktor prima dari kedua bilangan tersebut, hal ini tentu akan sangat membantu terutama saat mencari FPB dari bilangan-bilangan yang sangat besar.
Misalkan ada dua bilangan a dan b, untuk mencari FPB dari dan adalah dengan membagi bilangan yang lebih besar dengan bilangan yang lebih kecil (misal a > b). Dari hasil pembagian tersebut didapat hasil bagi dan sisa atau dapat dinotasikan dengan h untuk hasil dan s untuk sisa, sehingga didapat:
a : b = h + s ? a = h . b + s
Jika s = 0, maka FPBnya adalah b. tetapi jika s tidak sama dengan 0, maka
prosesnya diulang lagi dengan membagi b dengan s. Proses tersebut dilakukan seterusnya sampai menghasilkan sisa pembagian 0 dan FPBnya adalah sisa pembagian sebelumnya.
Contoh:
Tentukan FPB dari 3456 dan 246
Jawab:
3456 = 14 . 246 + 12
246 = 20 . 12 + 6
12 = 2 . 6 + 0
Sehingga diperoleh FPB (3456, 246) adalah 6.
0 Response to "Belajar Algoritma Euclid"
Post a Comment