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.