Algoritma Greedy untuk Pecahan Mesir

Fibonacci telah menunjukkan bahwa setiap bilangan rasional positif dapat dituliskan sebagai pecahan Mesir, yakni jumlah dari pecahan-pecahan satuan yang berbeda. Lalu bagaimana caranya kita menemukan representasi pecahan Mesir dari suatu bilangan rasional? Salah satu caranya adalah dengan menerapkan identitas dekomposisi pecahan berikut

\frac{p}{pq-1}=\frac{1}{q}+\frac{1}{q(pq-1)}

\frac{1}{n}=\frac{1}{n}+\frac{1}{n(n+1)}

Namun, menggunakan identitas di atas akan memerlukan waktu yang cukup lama jika nilai penyebut dan pembilangnya sangat besar. Akan tetapi ini bukan suatu masalah besar, sebab Fibonacci memiliki cara lain untuk mencari representasi pecahan Mesir dari suatu bilangan rasional positif, yang dikenal sebagai Algoritma Greedy. Di dalam kajian optimisasi, algoritma greedy sangat populer digunakan dalam masalah pencarian nilai optimum. Kata greedy memang cukup aneh jika diterjemahkan ke dalam bahasa Indonesia, yang mana memiliki arti rakus atau tamak. Jadi padanan kata dari algoritma greedy adalah algoritma rakus. Sebab prinsip dari algoritma ini adalah: “Take what you can get now!”.

greedy1.jpg

Penerapan algoritma Greedy ini sangat luas, jadi kita kerucutkan penggunaannya dalam menentukan pecahan Mesir saja. Nah, bagaimana algoritma ini bekerja?

Syarat agar algoritma greedy bekerja untuk pecahan p/q adalah q>p. Algoritma-nya sangat sederhana. Pertama, tentukan pecahan satuan terbesar yang kurang dari p/q, misalkan didapat 1/x. Lalu cari selisih dari p/q-1/x, hasilnya merupakan suatu bilangan rasional positif, katakanlah a/b. Jika a/b merupakan pecahan satuan, maka langkah kita selesai. Jika tidak, ulangi cara yang serupa pada pecahan a/b. Agar lebih jelasnya, perhatikan contoh berikut:

Misalkan kita ingin menentukan representasi pecahan Mesir dari bilangan 11/12.

Langkah I: Menentukan pecahan satuan yang kurang dari 11/12. Pandang pecahan 12/11, kemudian kita ambil ceiling dari 12/11, yakni \left\lceil 12/11\right\rceil =2. Karenanya pecahan satuan terbesar yang kurang dari 11/12 adalah 1/2.

Langkah II: Menentukan selisih. Kita peroleh 11/12-1/2=5/12.

Langkah III: Karena 5/12 bukan merupakan pecahan satuan, maka kita ulangi Langkah I pada pecahan 5/12, yakni menentukan pecahan satuan terbesar yang kurang dari 5/12. Perhatikan bahwa \left \lceil 12/5 \right\rceil= \left \lceil 2,4 \right \rceil = 3. Jadi pecahan satuan terbesar yang kurang dari 5/12 adalah 1/3.

Langkah IV: Kita peroleh selisih 5/12-1/3=1/12.

Langkah V: Karena 1/12 merupakan pecahan satuan, maka langkah kita selesai sampai di sini. Jadi kita dapatkan representasi pecahan Mesir dari bilangan 11/12 sebagai

11/12=1/2+1/3+1/12

*Jika Anda tertarik untuk mempelajari algoritma greedy dalam masalah optimisasi, sila baca di sini.


Sumber Gambar

http://www.cartoon-clipart.com/cartoon_clipart_images/clip_art_image_of_a_happy_man_running_with_a_fist_full_of_money_0521-1011-0416-5202.html

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 )

Foto Google

You are commenting using your Google 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 )

Connecting to %s