June 12, 2009 thumb Josephus Problem

Josephus Problem dengan LinkedList menggunakan Jav a.
Linkedlist adalah salah satu bentuk struktur data yang memilki setidaknya dua element yaitu isi atau data yang disimpan kemudian sebuah pointer untuk mendeklarasikan elemen linkedlist lain. Setiap elemen dalam linkedlist disebut dengan Node. Dan pada akhir linked;ist (Node terakhir), referensi pointer node terakhir menunjuk ke null (tidak ada isinya). Dalam programming node pertama dalam linkedlist disebut dengan Head, sedangkan bagian terakhir dari linkedlist disebut dengan tail.
Dalam perkembanganya linkedlist dibedakan atas berbagai jenis antara lain single linkedlist (linkedlist yang hanya memilki satu pointer untuk menunjuk element), double linkedlist (yaitu linkedlist yang memiliki 2 pointer penunjuk elemen yaitu elemen sebelumnya dan elemen sesudahnya), linear linkedlist (linkedlist yang berbentuk memanjang) dan circular linkedlist (yaitu linkedlist yang memutar, bagian head menyambung dengan tail).
Dalam pemrograman, maka struktur yang menempati urutan paling rendah adalah Node, kemudian linkedlist dituunkan dari sebuah Node. Berikut ini adalah deklarasi sebuah Node.

Penjelasanya sebagai berikut, isi yang bertipe int merupakan sebuah data atau informasi yang akan disimpan dalam sebuah linkedlist, dalam hal ini penulis hanya menggunakan sebuah elemen yang akan disimpan, faktanya dalam programming elemen yang disimpan bisa lebih dari satu, misalnya node tentang identitas sesorang, bisa berisi String nama, String alamat, Date tanggal lahir, dan satu yang wajib yaitu elemen penunjuk node berikutnya, dalam contoh dinamakan Next.
Untuk menyelesaikan permasalahan Josephus problem maka kita terlebih dahulu harus mengerti tentang hal ini, josephus adalah seorang komandan perang, suatu ketika ia bersama anak buahnya dikepung oleh musuh, kemudian josephus dan anak buahnya diperintah untuk melakukan sebuah permainan bunuh diri. Dengan aturan kelompok orang tersebut membentuk melingkar, kemudian sebagai kapten, josephus ditunjuk sebagai orang pertama yang menjadi acuan, kemudian dihitung berdasarkan hitungan yang telah ditetapkan, jika hitungan selesai, maka orang yang terakhir dalam hitungan melingkar tersebut dibunuh, kemudian hitungan dilanjutkan lagi dari orang yang berada sebelum orang yang terbunuh tadi, dihitung lagi, kemudian seperti yang tadi, yang terkhir dibunuh lagi begitu seterusnya hingga tersisa satu orang yang selamat, dan yang selamat ini akan dibebaskan oleh musuh. Sehingga jika ada sepuluh ornag misalnya maka penghitungan akan dilakukan sebanyak sembilan kali karena tiap hitungan selesai akan membunuh satu orang, sedangkan para penjahat meminta tersisa satu orang.
Dengan analisis diatas, kita dapat mengumpamakan orang adalah sebuah node dan lingkaran tersebut dideklarasikan menggunkan circular linkedlist dan dalam hal ini tugas sang programmer adalah menentukan siapa yang selamat, dengan input jumlah orang, nama-nama mereka, dan hitungan tiap sesi. Kemudian output yang dihasilkan adalah nama yang selamat dan nama yang mati. Sehingga deklarasi node dapat diubah menjadi.

Simpan dengan nama Node.java, perbedaanya terdapat pada isi yang awalnya bertipe integer sekarang bertipe String, karena berupa nama orang yang akan dimainkan. Secara lengkap Source Code Program Josephus sebagai berikut, penulis menggunkan JCreator v 3.0, tulis source code berikut dan simpan dengan nama josephus.java (karena java bersifat case sensitive maka perhatikan huruf besar dan kecil dalam penamaan variable dan methodenya) :

Compile dan lakukan Run hasil akan diatampilak dalam bentuk Comand Prompt seperti dalam gambar

Comments

total comments