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

希望我对您的理解是正确的-您想开始指望被删除的下一个人，而不是之前的那个人。类似的东西：

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
      }

至于第二个问题 - 你 return 删除的元素，就像这样打印它：

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

Answer 2

显示删除的播放器很容易修复。您的 delete() 方法 returns 已删除 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();

Java 中的约瑟夫游戏

Josephus Game in Java

java

josephus