java - Java 中的约瑟夫斯游戏

Question

我在 Josephus 游戏中遇到了一些问题。我的第一个问题是，我不知道如何从每轮被淘汰的人左边的人开始计数(游戏按顺时针方向进行)。它删除正确，但从被删除的人右边的人开始计数。我的第二个问题是我不知道如何打印每轮被淘汰的人。我已经掌握了大部分算法，但我无法弄清楚这些小细节。任何帮助，将不胜感激!

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