# Using Java to realize Joseph problem

Introduction:

Joseph problem (sometimes called Josephus replacement) is a problem in computer science and mathematics. In the algorithm of computer programming, the similar problem is also called Josephus ring. Also known as "the problem of losing handkerchief."

example:

len makes a circle and plays the game of losing handkerchief. Start from the k-th person and count from 1. When you count to m, the person who counts m will quit the circle, when there is only one person left in the circle.

Problem analysis and algorithm design

Joseph's problem is not difficult, but there are many ways to solve it, and there are many forms of the problem. Here is an implementation method.

In the title, len individual is surrounded by a circle, so we are inspired to use a cyclic chain to express, and we can use structural array to form a cyclic chain. There are two members in the structure, one is the head node pointing to the first child, and the other is the node temp (responsible for running the Dragon suit) as the judgment node.

Specific code:

```
package demo11;
/**
* Joseph's problem, turning into losing a handkerchief
*
* @author tianq Idea: set up a Child class and a circular list class: cyclink
*/
public class demo11 {
public static void main(String[] args) {
CyclLink cyclink = new CyclLink();
cyclink.setLen(15);
cyclink.createLink();
cyclink.setK(2);
cyclink.setM(2);
cyclink.show();
cyclink.play();
}
}
// Create a child class first
class Child {
// Children's logo
int no;
Child nextChild;// Point to the next child
public Child(int no) {
// Constructor gives child an id
this.no = no;
}
}
class CyclLink {
// First define a reference to the first child in the list
// Reference to the first child, can't move
Child firstChild = null;
Child temp = null;
int len = 0;// How many children are there
int k = 0; //Children at the beginning
int m = 0; //How many launches
// Set m
public void setM(int m) {
this.m = m;
}
// Set the size of the linked list
public void setLen(int len)
{
this.len = len;
}
// Set to count from the first person
public void setK(int k) {
this.k = k;
}
// Start play
public void play() {
Child temp = this.firstChild;
// 1. Find the person who starts counting first
for (int i = 1; i < k; i++) {
temp = temp.nextChild;
}
while (this.len != 1) {
// 2. Under several m eters
for (int j = 1; j < m; j++) {
temp = temp.nextChild;
}
// Find the last kid to circle
Child temp2 = temp;
while (temp2.nextChild != temp) {
temp2 = temp2.nextChild;
}
// 3. Count the children to m and quit
temp2.nextChild = temp.nextChild;
// Let temp point to the next counting child
temp = temp.nextChild;
// this.show();
this.len--;
}
// Last child
System.out.println("Last circle" + temp.no);
}
// Initialize ring list
public void createLink() {
for (int i = 1; i <= len; i++) {
if (i == 1) {
// Create first child
Child ch = new Child(i);
this.firstChild = ch;
this.temp = ch;
} else {
if (i == len) {
// Create first child
Child ch = new Child(i);
temp.nextChild = ch;
temp = ch;
temp.nextChild = this.firstChild;
} else {
// Continue to create children
Child ch = new Child(i);
temp.nextChild = ch;
temp = ch;
}
}
}
}
// Print the circular list
public void show() {
Child temp = this.firstChild;
do {
System.out.print(temp.no + " ");
temp = temp.nextChild;
} while (temp != this.firstChild);
}
}
public class Test10 {
public static void main(String[] args) {
/*
* First, let's talk about my idea of doing this:
* 1,Create a collection of 100 elements from 1 to 100. (corresponding to 100 people respectively)
* 2,Counting a circle from 1 to 14 is equivalent to walking 99 circles, removing one element from the set for each circle.
* 3,After 99 laps, the last element in the collection is the last one
*
* The key here is to find the subscript of the element removed from the set every time.
*/
//Create a collection all, the elements in the collection are 1, 2, 3 , 100, for all
List<Integer> all = new LinkedList<Integer>();
for(int i = 1;i <= 100;i++){
all.add(i);
}
//The following code represents 99 cycles, one element is removed from the collection at a time, representing the number of the person who exits
//i indicates the subscript of the person who exits in the all set
int i = 0;
//99 cycles
for(int n = 1;n < 100;n++){
//At each cycle, find the subscript of the person to exit in the set
i = (i + 13) % all.size();
//Remove the element representing this person from the collection
all.remove(i);
}
//Circle 99 times, delete 99 people, the last one is you
System.out.println("The last thing left is No " + all.get(0) + " personal");
/*
* The core of this problem is to find the subscript of the element to be deleted in each cycle.
*/
}
}
```

There is little code, but the complexity is not low. In order to facilitate the understanding of the above, detailed comments are made.