Tipntrick-Computer

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.

public class Node { int isi=0;Node next=null; public Node(){isi =0;Node next=null;}public void displayNode(){System.out.println(isi);}}

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.

public class Node { String isi=0; Node next=null; public Node() { isi = “”; Node next=null; } public void displayNode() { System.out.println(isi); }}

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) :

import java.io.*;/*clas utama yang memanggil seluruh class ini melakukan pemanggilan terhadsap class Linkedlist*/ public class josephus{ public static void main(String[] args) throws IOException{ josephus josep=new josephus(); LinkedList list=new LinkedList(); int jumlah_orang=-1; int hitungan=-1; try { System.out.println("<<==PROGRAM JOSEPHUS PROBLEM==>>");BufferedReader input = new BufferedReader( new InputStreamReader(System.in)); System.out.print("Masukan Hitungan : "); hitungan=Integer.parseInt(input.readLine()); System.out.print("Masukan Jumlah Orang : "); jumlah_orang=Integer.parseInt(input.readLine()); for(int i=1;i<=jumlah_orang;i++){ System.out.print("Nama orang ke-"+i+" : "); list.AddLastCircular(input.readLine()); }<br /> int y=0; for(y=1;y<jumlah_orang;y++){ System.out.println(""); System.out.println("====Skenario ke-"+y+"======"); System.out.println("Yang Mati <"+list.bunuh(hitungan)+">");System.out.println("Yang Selamat : "); list.DisplayCircular(jumlah_orang-y); }<br /> System.out.println(""); System.out.print("--> yang bebas dari musuh adalah "); list.DisplayCircular(1);} catch ( Exception e ) { e.printStackTrace(); } <br /> }}<br />/*kelas Node untuk membuat LinkedList dalam hal ini dianalogikan sebagai nama orang*/ class Node {<br /> String isi; Node next; public Node(String nama){ isi=nama; Node next=null; } }/*program Josephus yang sebenarnya ada disini *meliputi fungsi-fungsi yang akan dijalankan pada fungsi main*/ class LinkedList { public Node head;private Node tail;private Node kursor;private Node bantuan; public void Display(){ kursor=head; while(kursor!=null){ System.out.println("<"+kursor.isi+">"); kursor=kursor.next; } } /*constructor untuk membangun LinkedlIst*/ public LinkedList() { head=null; tail=null; kursor=null; bantuan=null; } /*untuk menampilkan isi circular linkedlist dalam hal ini digunkan untuk menampilkan nama-nam yang selamat*/ public void DisplayCircular(int sum){ kursor=head; for(int y=1;y<=sum;y++){ System.out.println("<"+kursor.isi+">"); kursor=kursor.next; } } /*untuk membangun circular linkedlist*/ public Node AddLastCircular(String object ){ Node baru=new Node(object); if(head==null){ head=baru; tail=baru; tail.next=head; } else{ tail.next=baru; tail=baru; tail.next=head; } return(head); } /*pada josephus setiap kali selesai melakukan hitungan maka orang terakhir yang dihitung akan dibunuh*/ public String bunuh(int hitungan){ String Died=""; if(hitungan==0){ Died=head.isi; tail.next=head.next; head.next=null; head=tail.next; return(Died); } hitungan=hitungan-1; kursor=head; if(kursor.next==null) return("Mati Semua"); else{ for(int i=0;i<hitungan;i++){ kursor=kursor.next; } bantuan=kursor.next.next; Died=kursor.next.isi; kursor.next.next=null; kursor.next=bantuan; head=kursor; return(Died); } } }

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