Algoritma dan Source Code Josephus Problem dengan Linked List

Josephus Problem adalah suatu masalah pengeksekusimatian terpidana – terpidana mati pada jaman dahulu kala. Sebenarnya ini bisa dianalogikan dengan jenis permainan anak – anak.

Berikut adalah penjelasan Josephus Problem dengan pendekatan permainan anak – anak yang sejenis :

Ada sebuah permaian yang dilakukan oleh (n) orang secara melingkar. Permainan itu adalah membilang bilangan dari 1 – (r). Barangsiapa memperoleh girilan untuk membilang bilangan r, dia akan kalah dan tidak boleh ikut permainan lagi. Setelah itu penghitungan dilanjtkan mulai dari 1 oleh orang setelahnya. Penghitungan pertama dimulai di player ke-(st). Permainan akan berakhir jika dan hanya jika ada satu orang yang tidak kalah.

Algoritma Dasar :

–          Melakukan penghitungan dimulai dari player ke-n

–          Penghitungan dilanjutkan ke player sebelah kanannya (player.next)

–          Jika mencapai player ke-n, dilanjutkan dengan player pertama (circular)

–          Jika hitungan sudah mencapai range yang telah ditentukan, lakukan proses remove. Player.next dituju ke player sebelah kanan dari player yang tereliminasi. Begitu seterusnya sampai First = Last (tinggal 1 player).

Berikut adalah souce code penyelesaian Josephus Problem dengan menggunakan konsep linked list :

import java.util.ArrayList;

import java.util.List;

public class Josephus

{

public static void main(String[] args)

{ int captiveNumber = 7;

int startFrom = 1;

int runStep = 4;

CaptiveList list = new CaptiveList(startFrom, captiveNumber, runStep);

Link lastOne = list.runGame();

System.out.println("The survival: " + lastOne);

}

private static class CaptiveList

{ private Link dynamicHead;

private int  runStep;

public CaptiveList(int startFrom, int captiveNumber, int runStep)

{ this.runStep = runStep;

Link previous = null;

Link head = null;

for (int i = 1; i <= captiveNumber; i++)

{ Link tmpLink = new Link(i);

if (previous == null)

head = tmpLink;

else

previous.next = tmpLink;

previous = tmpLink;

if (i == startFrom)

dynamicHead = tmpLink;

}

previous.next = head;

}

private Link suicide()

{ Link current = dynamicHead;

Link previous = null;

int testPos = runStep;

while (--testPos >= 1)

{ previous = current;

current = current.next;

}

if (previous == current.next)

previous.next = null;

else

previous.next = current.next;

dynamicHead = current.next;

return current;

}

public Link runGame()

{ List killed = new ArrayList();

while (dynamicHead != null && dynamicHead.next != null)

killed.add(suicide());

for (int i = 0; i < killed.size(); i++)

{ Link kill = (Link) killed.get(i);

System.out.println("Killing: " + kill);

}

return dynamicHead;

}

}

private static class Link

{ private int number;

public Link next;

public Link(int number)

{ this.number = number; }

public String toString()

{ return String.valueOf(number);    }

}

}

 

4 thoughts on “Algoritma dan Source Code Josephus Problem dengan Linked List

  1. disimpen dengan nama pa neh?? ???.java,,coz paz di kompile g bisa,,error,,

    mohon pencerahannya . . .

  2. hai dewa..
    bisa minta tolong ga??
    punya source code algoritma EM ga??
    tolong bgt yak :)

  3. Ines Dwi Andini

    wah mas, makasi banyak :) sangat membantu dalam menjawab soal pendahuluan praktikum asd :)

Tinggalkan Jejak

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