Implementation of Josephous Joseph Ring Problem in Java

Preface

  • Language: Java
  • Environment: IntelliJ IDEA
  • JDK Version: 1.8
  • Source code: GitHub

Summary of problems

N individuals form a circle and the number of reports is M. The first person will report from the beginning, and the person who reports to M will be killed. Then the next person will continue to report from 1. In this circle, the last one will be killed. Ask for the order of the murdered and the number of the last survivor

Solution Based on Link List

To solve the problem with linked list, the first thing we want to think about is that the problem is circular reporting, so we should principle circular lists, because the reporting only needs to report in the same direction, so we don't need to consider bidirectional circular lists.

If a circular list is used, then each node on the list will hold participant information, such as number. We stipulate that the number of participants is size and the number of reported deaths is k. Then we need to consider the following issues:

  • How to complete the count: Use a num variable count to reset num when it is k
  • How to Delete Dead Persons: Deleting a node from a one-way list requires an auxiliary pointer and points to the previous node of the node to be deleted. We define it as a pre pointer.
  • How to determine the number of people who have died and report back from the next member: We define it as the target pointer, which points to the number of people who report.

The process is as follows: first create a circular list, the node of the list saves the number of participants, and the number of nodes is size. During the creation process, let the pre pointer always point to the newly created node, so that after the completion of the creation, the pre points to the last node, let the target point to the first node created by the list, and keep the pre always pointing to the front of the target. A node. At the beginning of the process, num counts. When num is k, the dead node is deleted by pre, and the target points to the next node of the dead node. Repeat this process until the node deletes the remaining one, and finally the node, preand target, points to him, that is, the next of the node points to itself, the end of the game.

    /**
     * Realization Based on Link List
     * @param size Number of participants
     * @param k Newspaper number
     */
    public static void josephousLinked(int size,int k){
        Node first = null;  //Pointer to a person numbered 0
        Node pre = null;    //A pointer to a person who is about to die
        Node target = null; //Pointer to the dying person
        int num = 0;    //Counter, 0~k
        if(size>0){ //Initialize the first person
            first = new Node(0);
            pre = first;
        }
        for(int i = 1;i<size;i++){  //Initialize the rest of the people, and eventually pre point to the last person numbered
            Node node = new Node(i);
            pre.next = node;
            pre = node;
        }
        target = first; //Initialize the target pointer to start counting from number 0
        pre.next = target;  //Connect linked lists to circular linked lists
        while(target!=pre){ //When target and pre point to the same person, the game ends and the person pointing to survives
            num++;  //Number off
            if(num==k){ //Death of the person who reported to k
                System.out.println("The first"+target.id+"Number One Death");   //Print information
                pre.next = target.next; //Remove this person from the list
                target = pre.next;
                num = 0;    //Counter zeroing
                continue;   //By the end of this report, target had pointed to the next person who had died.
            }
            target = target.next;   //If no number is reported to k, move target to the next person
            pre = pre.next; //If no number is reported to k, move pre to the next person (the previous person of the target)
        }
        System.out.println("Survivors"+target.id+"Number");
    }
    static class Node{
        int id;
        Node next;
        public Node(int id){
            this.id = id;
        }
    }

Array-based Solution

Using the array solution, we first construct an array of size size for the number of participants. We use the array index to represent the number of these people. The state of each person is stored in this array. Since the value of the array is 0 when it was first constructed, we stipulate that if the value of the array is 0, the person will survive. If it is 1, the person will die and the number of people reported to be k will die until there is only one person alive in the array, and the corresponding array value of the person index is 0, then the game ends. We need to consider the following issues:

  • How to complete the count: Use a num variable count to reset num when it is k
  • How to delete the deceased person: Set the array value corresponding to this person's index to 1, and traverse to the person whose array value is 1, only increase the index, not increase the counter num
  • How to determine the number of deaths after the death, from the next member re-report: index of deaths + 1, need to take into account the array crossing the boundary, so need to take the model
    /**
     * Array-based Implementation
     * @param size Number of participants
     * @param k Newspaper number
     */
    public static void josephousArray(int size,int k){
        int num = 0;    //Counter, 0~k
        int index = 0;  //cursor
        int sur = size; //Number of survivors
        int[] array = new int[size];    //An array of all people
        while(true){
            if(array[index%size] == 1){ //If this person is dead, the next one begins.
                index++;
                continue;
            }
            num++;//Current number of personnel
            if(num==k){ //If the count reaches k, the person dies.
                array[index%size] = 1;  //Marked death
                System.out.println("The first"+index%size+"Number One Death");  //Print information
                num = 0;    //Reset counter
                sur--;  //Decrease in survivors
            }
            if(sur==1&&array[index%size]==0){   //Stop counting at the end of the game.
                break;
            }
            index++;
        }
        System.out.println("Survivors"+index%size+"Number");
    }

Recursive-based Solution

Before using recursion, we first need to find the rules in Joseph rings, if there are the following arrays:

0,1,2,3,4

If the number of reported deaths is 3, the first person to die must be No. 2. That is to say, given the size of a total number of persons and the number of reported deaths, the number of dead persons must be (k-1)%size. Considering that the reported number k-1 may be larger than the size, the model should be taken. When No. 2 died, we rearranged the array:

3,4,0,1

We renumber the new array to

0,1,2,3

We can understand that if we ask for 0, 1, 2, 3 number of last dead people (that is, survivors), we can deduce 3, 4, 0, 1 survivors through a certain correspondence relationship, then we can ask for 0, 1, 2, 3 number of last dead people, and we can analogize the first practice, rearrange. In order, only 0, 1, 2 of the last person to die, until the analogy to find only one person in the array 0 of the last person to die, it is obvious that the array only 0, regardless of the number reported, the last person to die is him, or the survivor is him. Let's first find a simple solution:

F(1) = 0 (size=5,k=3)

F(2) = 1 (size=5,k=3)

F(2) =( F(1)+k)%size

We get a recursive formula: F(size) = (F(size-1)+k)%size. For example, we only need to know the number of the n-1 person and the n-1 person who died when the number of the n-1 person is required.

    /**
     * Realization Based on Recursion
     * @param size Number of participants
     * @param k Newspaper number
     */
    public static void josephousRecursion(int size,int k){
        for(int i = 1;i<size;i++){  //Calling a recursive method actually eliminates the need for this loop if only the last survivor is required.
            System.out.println("The first"+recursion(size,k,i)+"Number One Death");
        }
        System.out.println("Survivors"+recursion(size,k,size)+"Number");
    }

    /**
     * Recursive Method
     * @param size Number of people in the current circle
     * @param k Newspaper number
     * @param i The first person to die
     * @return  Return to the location of the person who died the first time in the size
     */
    private static int recursion(int size,int k,int i){
        if(i==1){
            return (k-1)%size;
        }else{
            return (recursion(size-1,k,i-1)+k)%size;
        }
    }
}

Tags: Programming Java IntelliJ IDEA JDK github

Posted on Thu, 05 Sep 2019 23:49:59 -0700 by rivka