Algoritma Euclidean

Seperti yang sudah saya janjikan pada postingan sebelumnya.. yaitu membahas teori apa saja yang ada di dalam Matematika Diskrit..
Langsung saja .. berikut ini adalah penjelasan mengenai Algoritma Euclidean.

Algoritma Euclidean adalah salah satu metode yang mangkus dalam mencari Pembagi Bersama Terbesar (greates), disingkat menjadi PBB. Algoritma ini sudah dikenal sejak berabad-abad yang lalu. Euclid ,penemu Algoritma Euclidean, adalah seorang matematikawan yunani yang menuliskan algoritmanya tersebut dalam bukunya yang terkanal yang berjudul Element. Secara formal algoritma Euclidean dirumuskan sebagai berikut.

Misalkan m dan n adalah bilangan bulat

tak negatif dengan m ≥ n. Misalkan r0 = m

dan r1 = n , lakukan secara berturut –

turut pembagian seperti dibawah ini.

r0 = r1q1 + r2 0≤ r2 ≤ r1

            r1 = r2q2 + r3 0≤ r3 ≤ r2

           

           

Kemudian PBB dari m dan n (PBB(m,n)) adalah sisa terakhir dari pembagian tersebut. Singkatnya algoritma Euclidean akan dituliskan sebagai berikut.

Algoritma Euclidean

1.Jika n = 0 maka m adalah PBB(m,n); stop tetapi jika n ≠ 0 ,lanjutkan ke langkah 2.

2.Bagilah m dengan n dan misalkan r adalah sisanya.

3.Gantilah nilai m dengan nilai n dan nilai n dengan r, lalu ulang kembali ke langkah 1. Catatan : jika m ≤  ` n, maka pertukarkan nilai m dan n.

Masih ada beberapa algoritma lain yang ada pada matematika diskrit yang berhubungan dengan komputer..
tunggu saja dipostingan selanjutnya...

Semua Ada Disini