Implementasi Euclid’s Algorithm di Scala


Scala

Scala

Dalam matematika kita sering menghadapi bilangan pecahan misal 1/2 atau 3/4. Dan kadang-kadang kita sering menemui bilangan pecahan dengan nilai besar yang sebenarnya bisa disederhanakan, misal 90/100, bisa disederhanakan menjadi 9/10 atau 25/15 bisa disederhanakan menjadi 5/3.

Untuk menyederhakanan sebuah pecahan, kita perlu mencari pembagi terbesar yang bisa membagi pembilang dan penyebut, kita bisa menggunakan algoritma Euclid, dimana bunyi algoritmanya sebagai berikut

Compute the greatest common divisor of two nonnegative integers p and q as follows: If q is 0, the answer is p. If not, divide p by q and take the remainder r. The answer is the greatest common divisor of q and r.

Misal 25/15 artinya p = 25 dan 1 = 15

  • 1. Cek apakah q adalah 0: q = 15, lanjutkan
  • 2. r = (p % q) = (25 % 15) = 10
  • 3. Ulangi lagi dengan nilai p = q dan q = r
  • 4. p = 15, q = 10
  • 5. Cek apakah q adalah 0; q = 10, lanjutkan
  • 6. r = (p % q) = (15 % 10) = 5
  • 7. Ulangi lagi dengan nilai p = q dan q = r
  • 8. p = 10, q = 5
  • 9. Cek apakah q adalah 0; q = 5, lanjutkan
  • 10. r = (p % q) = (10 % 5) = 0
  • 11. Ulangi lagi dengan p = q dan q = r
  • 12. p = 5, q = 0
  • 13. Cek apakah q adalah 0: q = 0, hasilnya adalah p
  • 14. greatest common divisor = p = 5

Dari proses itu telah didapat bahwa hasil penyederhana terbesar adalah 5, sehingga jika 25/15 bisa disederhakanan dengan dibagi 5, 25 : 5 = 5 dan 15 : 5 = 3, hasilnya adalah 5/3

Jika di Scala, kita bisa membuat kode seperti dibawah ini untuk implementasinya :

Contoh penggunaannya sebagia berikut :

Iklan

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s