## 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; } } }`