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); }
}
}
|
