Joseph problem

Source of problem

The Josephus problem is named after Flavio Josephus, a 1st century Jewish historian who wrote in his diary that he and 40 of his comrades were surrounded in caves by Roman troops. They discussed whether to kill themselves or to be captured, and finally decided to kill themselves and draw lots to decide who to kill. Joseph and another man were the last two left behind. Joseph convinced the man that they would surrender to the Roman army and not commit suicide. Joseph attributed his survival to luck or providence; he didn’t know which.

Joseph problem is a problem that occurs in computer science and mathematics. In computer programming algorithms, similar problems are called Joseph rings.

People stand in a circle waiting to be executed. The count begins at a specified point in the circle and proceeds around the circle in a specified direction. After skipping a specified number of people, the next person is executed. Repeat the process with the remaining people, starting with the next person and jumping over the same number of people in the same direction until only one person remains and is released.

The problem is, given the number of people, the starting point, the direction, and the number to skip, choose the position in the initial circle to avoid execution.

Problem description

N soldiers numbered 1 to N stand in a circle (numbered 1, 2, 3… N), counting the soldiers numbered k in turn (1,2… M), soldiers who count to m will step out, and those who follow will count from 1. Until the last soldier is left, and this is the soldier number.

solution

A simpler approach is to simulate the entire process with a circular singly linked list. As shown in the figure below, it consists of 5 nodes in a circle, numbered 1,2,3,4,5 respectively.

For example, count three numbers from number 2, namely 1,2,3, then number 4 will go round;

Continue counting 3 numbers from no. 5, i.e. 1,2,3, then no. 2 will go round; And so on, the last node is number five.

Code implementation

Head pointer to node 1; tail pointer to node 5; current pointer to node 5; Continue traversing backwards m times to find the node before the loop-out node, so that the loop-out node can be deleted, and so on…..

public class JosephusCycle {

    // point to the first node
    private Node first;

    // points to the last node
    private Node last;

    public boolean add(Integer item) {
        // create a node
        Node newNode = new Node(item, null);

        // Check whether it is the first node
        if(first == null && last == null) {
            // Next of the new node points to itself
            newNode.next = newNode;
            first = newNode;
            last = newNode;

        }else {
            newNode.next = last.next;
            last.next = newNode;
            last = newNode;
        }
        return true;
    }

    /** * Joseph problem * eg. * 1, 2, 3, 4, 5 start from node 2 and count from 1 to 3 * in the order of 4, 2, 1, 3, 5 *@paramN To sum up the number of points, each node has a number, starting at 1 *@paramK is k. Start counting. One, two, three... *@paramThe node from m to m is looped */
    public void josephus(int n, int k, int m) {
        if(n < 1) {
            throw new IllegalArgumentException("The number of nodes n cannot be less than 1.");
        }
        if(k > n) {
            throw new IllegalArgumentException("The parameter k cannot be greater than n.");
        }

        for(int i = 1; i <= n; i++) {
            this.add(i);
        }

        // find the previous node whose id is k
        Node tmp = last;
        for(int j = 0; j < k-1; j++) {
            tmp = tmp.next;
        }
        System.out.println(String.format("Starting at %s and counting backwards %s", tmp.next.item, m));

        while (true) {
            // Count back to 1... m
            // Find the previous node to delete
            for(int i = 0; i < m-1; i++) {
                tmp = tmp.next;
            }

            if(tmp.next == tmp) {
                System.out.println("The last node out of the loop =" + tmp.next.item);
                break;
            }
            System.out.println("Node out of the loop =" + tmp.next.item);

            // Delete the nodetmp.next = tmp.next.next; }}private static class Node {

        private Integer item;

        private Node next;

        public Node(a) {}public Node(Integer item, Node next) {
            this.item = item;
            this.next = next; }}}Copy the code

“More exciting content please pay attention to the public number geekyMV, like please share to more friends oh”