Linked List : Alur Cerita dari Algoritma “Joshepus Problem”

21 01 2010

4. Dengan kata-kata anda sendiri, jelaskan alur cerita dari algoritma Joshepus Problem!

(fungsi dasar apa sajakah yang dimiliki dan gambar permodelannnya)

Joshepus Problem (Josephus Permutation) adalah sebuah problem teoritis yang berkembang dalam ilmu computer dan matematika. Alur Akgoritma dari Josephus Problem bisa diceritakan sbb:

Algoritma josephus Problem digunakan untuk mengambil suatu objek dari sekumpulan objek dengan cara seperti undian, dimana objek terakhir yang bertahan dialah yang akan terpilih.

Sebagai contoh, misalnya ada sekelompok anak yang memperebutkan kue. Mereka ada lima anak A, B, C, D, E . Mereka semua telah bersepakat akan mengadakan undian dengan memakai kartu undian dimana anak terakhir yang bertahan (yang belum mendapat kartu) akan mendapatkan kue tersebut. Mereka menjalankan kartu tersebut dengan cara membentuk lingkaran sebagai berikut:

Dan aturan pengundian yang telah mereka sepakati sbb:

  1. Perpindahan kartu dilakukan searah jarum jam, dimulai dari anak pertama (A).
  2. Perpindahan kartu melewati 3 anak. Dan anak yang menerima kartu akan tereliminasi.
  3. anak yang bertahan paling akhir akan mendapatkan kue itu.

Berdasarkan aturan tersebut, perpindahan pertama dimulai dari A-B-C. Maka C tereliminasi pertama kali. Kemudian perpindahan kartu dilanjutkan dari D-E-A. Maka A tereliminasi. Selanjutnya B-D-E. Maka E tereliminasi. Selanjutnya B-D-B. Maka B tereliminasi dan yang tersisa adalah D. Jadi D-lah yang berhak mendapatkan kue tersebut.

Posted By : Evan Yofiyanto @ Evan’s Blog : Kuliah Informatika (kuliahinformatika.wordpress.com)

[FREAX]


Actions

Information

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: