I'm having a couple issues with the Josephus game. My first issue is that I can't figure out how to start counting at the person to the left of the person eliminated each round (game goes clockwise). It deletes correctly, but starts counting at the person to the right of the deleted person. My second issue is that I can't figure out how to print the eliminated person each round. I have the algorithm down for the most part, but I can't figure out these small details. Any help would be appreciated!
import java.io.*;
////////////////////////////////////////////////////////////////
class Link
{
public int iData; // data item (key)
public Link next; // next link in list
// -------------------------------------------------------------
public Link(int id) // constructor
{ iData = id; }
// -------------------------------------------------------------
public void display() // display ourself
{ System.out.print(iData + " "); }
} // end class Link
////////////////////////////////////////////////////////////////
class CircList
{
private Link current; // ref to current link
private int count; // # of links on list
// -------------------------------------------------------------
public CircList() // constructor
{
count = 0; // no links on list yet
current = null;
}
// -------------------------------------------------------------
public boolean isEmpty()
{ return count==0; }
// -------------------------------------------------------------
public int getSize()
{ return count; }
// -------------------------------------------------------------
public void insert(int id) // insert after current link
{ // make new link
Link newLink = new Link(id);
if(count == 0) // if first one
{
current = newLink; // current points to it
current.next = current; // next one is us
}
else
{
newLink.next = current.next; // downstream of new link
current.next = newLink; // upstream of new link
}
count++; // one more link
}
// -------------------------------------------------------------
public Link delete() // delete link following currrent
{
Link tempLink;
switch(count)
{
case 0: // current is already null
tempLink = current;
break;
case 1: // delete ourself
tempLink = current;
current = null;
count--;
break;
default: // delete the next one
tempLink = current.next;
current.next = tempLink.next;
count--;
break;
}
return tempLink;
}
// -------------------------------------------------------------
public Link find(int key) // find link with given key
{ // at one past current
int getHome = count;
while(getHome > 0) // while not back to
{ // beginning
if(current.next.iData == key) // found it?
return current.next; // return next one
else // not found
{ // go to next link
current = current.next;
getHome--; // one item closer to home
}
}
return null; // can't find it
}
// -------------------------------------------------------------
public Link delete(int key) // delete link with given key
{
Link nextLink = find(key); // find it
if(nextLink != null) // if found,
{
current.next = nextLink.next; // delete it
count--;
}
return nextLink; // return null or link
}
// -------------------------------------------------------------
public void display() // display the list
{
for(int j=0; j<count; j++)
{
current.next.display();
current = current.next;
}
System.out.println("");
}
// -------------------------------------------------------------
public void step()
{
if(count != 0)
current = current.next; // go to next link
}
// -------------------------------------------------------------
public Link peek()
{ return current.next; }
// -------------------------------------------------------------
} // end class CurcList
////////////////////////////////////////////////////////////////
class CircApp
{
public static void main(String[] args) throws IOException
{
int j, nPlayers, nSkips, startNo;
CircList theList = new CircList(); // make list
putText("Enter the number of players: ");
nPlayers = getInt();
for(j=nPlayers; j>0; j--) // number 10, 20, ...
theList.insert(j);
putText("Players: ");
theList.display();
putText("Enter the the number of spaces to skip: ");
nSkips = getInt();
putText("Enter the the starting player's number: ");
startNo = getInt();
// Add your code here
int m = 1, n;
while(m != startNo)
{
theList.step();
m++;
}
putText("Players: ");
theList.display();
while(theList.getSize() > 1){
n = 0;
while(n != nSkips){
theList.step();
n++;
}
theList.delete();
theList.display();
}
}
// end main()
// -------------------------------------------------------------
public static void putText(String s)
{
System.out.print(s);
System.out.flush();
}
// -------------------------------------------------------------
public static String getString() throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
// -------------------------------------------------------------
public static char getChar() throws IOException
{
String s = getString();
return s.charAt(0);
}
//-------------------------------------------------------------
public static int getInt() throws IOException
{
String s = getString();
return Integer.parseInt(s);
}
// -------------------------------------------------------------
} // end class CircApp
Displaying the deleted player is a very easy to fix. Your delete() method returns the deleted Link, so you just need to use it when it's returned. Instead of just calling theList.delete() use something like:
theList.delete().display(); //start line
System.out.println("is eliminated"); //finish line
As for starting to the left of the deleted player, you need a way to move backwards through your circle. In small circles one way to do this is to step() one time fewer than the number of players (since stepping one time for each player makes a full trip around the circle back to the current player). So after the above code add
for(int i=0; i<theList.getSize()-1; i++)
theList.step();