Java中的Josephus游戏

Question

我对约瑟夫斯的比赛有一些意见。我的第一个问题是，我不知道如何开始计数的人左边的人每一轮被淘汰(游戏顺时针方向进行)。它正确地删除，但开始在被删除的人的右边的人计数。我的第二个问题是，我不知道如何打印每一轮被淘汰的人。我大部分时间都把算法写下来了，但我不知道这些小细节。任何帮助都将不胜感激！

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

Answer 1

显示已删除的播放器是一个非常容易修复。delete()方法返回已删除的Link，因此在返回时只需要使用它。不要仅仅调用theList.delete()，而要使用以下内容：

theList.delete().display(); //start line
System.out.println("is eliminated"); //finish line

至于从被删除的播放器的左边开始，你需要一种在你的圆圈中向后移动的方法。在小圆圈中，一种方法是step()比玩家数量少一倍(因为每一位玩家步进一次，就会在圆圈内来回一圈，返回到当前的玩家)。所以在上面的代码后面添加

for(int i=0; i<theList.getSize()-1; i++)
   theList.step();

Answer 2

我希望我对你的理解是正确的--你想要开始指望下一个被删除的人，而不是以前的那个。就像这样：

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
         current = current.next;        //move to the next person
         count--;
         }

      return nextLink;            // return null or link
      }

至于第二个问题-返回已删除的元素，只需按如下方式打印：

Link retVal = theList.delete();
if (retVal != null) {
    retVal.display();
}