josephus problem

Origin of the problem

It is said that the famous Jewish historian Josephus had the following story: after the Romans occupied jotapat, 39 Jews hid in a cave with Josephus and his friends. 39 Jews decided that they would rather die than be caught by the enemy, so they decided a way of suicide. 41 people lined up in a circle, counting from the first person. Every time they counted to the third person, they had to commit suicide, Then count off again from the next until everyone commits suicide. However, Josephus and his friends did not want to comply. Start with one person, Over k-2 people (because the first person has been crossed) and kill the k-th person. Then, cross the k-1 person and kill the k-th person. The process continues along the circle until there is only one person left, and the person can continue to live. The problem is, given and, where to stand in the first place to avoid execution. Josephus asked his friends to pretend to obey first, He arranged his friends and himself in the 16th and 31st positions, so he escaped the death game.

Loop linked list for simulation

Because the Joseph problem is a ring, it is also called Joseph Ring. Its structure is similar to the circular linked list, so it can be simulated with the circular linked list.

thinking

• Create node

  class Person
  {
      //Serial number
      private int num;
      //Subsequent pointer to the next node
      private Person next;
  
      public Person(int num) {
          this.num = num;
      }
  
      public int getNum() {
          return num;
      }
  
      public void setNum(int num) {
          this.num = num;
      }
  
      public Person getNext() {
          return next;
      }
  
      public void setNext(Person next) {
          this.next = next;
      }
  }
  

• Create a one-way circular linked list

  1. First create the first header node, and make the first pointer point to the node and the next pointer point to itself to form a ring.

  2. After each new node is created, it is added to the existing ring linked list.

  /**
   * One way circular linked list
   */
  class CircleSingleLinkedList
  {
      /**
       * Create a first node
       */
      private Person first;
  
      /**
       * Add nodes to build a ring linked list
       * @param nums Number of nodes to create
       */
      public void addPerson(int nums)
      {
          if (nums < 1)
          {
              System.out.println("nums Incorrect value!");
              return;
          }
          //Help build circular linked list
          Person temp = null;
          //Use for to create our circular linked list
          for (int i = 1; i <= nums ; i++)
          {
              //Create node by number
              Person person = new Person(i);
              //Head node
              if (i == 1)
              {
                  first = person;
                  //Form a ring
                  first.setNext(first);
                  //Let the pointer point to the first node
                  temp = first;
                  continue;
              }
              temp.setNext(person);
              person.setNext(first);
              temp = person;
          }
      }
  }    
  

• Traverse circular linked list

  1. Let an auxiliary pointer temp point to the first header node first
  2. Traverse the ring linked list through the while loop

  public void list()
  {
      if (first == null)
      {
          System.out.println("Empty linked list");
          return;
      }
      //The head node cannot move, and the auxiliary pointer is used to traverse
      Person temp = first;
      while (true)
      {
          System.out.printf("number:%d\n",temp.getNum());
          //Traversal complete
          if (temp.getNext() == first)
          {
              break;
          }
          //Pointer backward
          temp = temp.getNext();
      }
  }
  

• Calculate the output order of each node

  1. Create an auxiliary pointer end to point to the last node of the linked list

  2. According to the start position startNum, let the first and end pointers move startNum-1 times at the same time

  3. Start counting. Each time you count, move the first and end pointers backward countNums-1 times

  4. Finally, the node pointed to by the first pointer is the node to be listed

  5. Remove the node and repeat step 34.

     

  /**
   * Calculate the order of people out of the circle according to the user's input
   * @param startNum     Indicates the number of people to count off from
   * @param countNums    It means counting several times at a time
   * @param personNums  Indicates how many people were there at first
   */
  public void play(int startNum,int countNums,int personNums)
  {
      if (first == null || startNum < 1 || startNum > personNums)
      {
          System.out.println("Error in parameter input, please re-enter");
          return;
      }
  
      //Create auxiliary pointer
      Person end = first;
      //Before starting counting, let the end pointer point to the last node
      while (true)
      {
          if (end.getNext() == first)
          {
              break;
          }
          end = end.getNext();
      }
      
      //Before counting, let first and end calibrate according to startNum
      for (int i = 0; i < startNum - 1; i++)
      {
          first = first.getNext();
          end = end.getNext();
      }
      
      //When counting, let the first and end pointers move (countnum-1) times at the same time
      while (true)
      {
          //There is only one node in the circle
          if (end == first)
          {
              break;
          }
          for (int i = 0; i < countNums - 1; i++)
          {
              first = first.getNext();
              end = end.getNext();
          }
          System.out.printf("Out of circle number:%d\n",first.getNum());
          first = first.getNext();
          end.setNext(first);
      }
      System.out.printf("The last number left in the circle is:%d\n",first.getNum());
  }
  

test

public class Josephu
{
    public static void main(String[] args) {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        //Add node
        circleSingleLinkedList.addPerson(6);
        //Traversal linked list
        circleSingleLinkedList.list();
        //Calculate the cycle order and output
        circleSingleLinkedList.play(1,5,6);
    }
}
-------------------------------------------------------------------------------------------------------------------
//Output results:
number:1
 number:2
 number:3
 number:4
 number:5
 number:6
 Out of circle number:5
 Out of circle number:4
 Out of circle number:6
 Out of circle number:2
 Out of circle number:3
 The last number left in the circle is: 1
5->4->6->2->3->1

If there are errors or deficiencies, please comment and correct.