Three Methods of JavaScript to Solve the Problem of Joseph's Ring

Catalog Overview
Problem description
Cyclic linked list
Ordered array
Mathematical recursion
Summarize

Overview

Joseph's ring problem, also known as Joseph's killing problem or throwing handkerchief problem, is a classic algorithm problem. There are many variations in problem description, but the general idea of solving problems is the same. This paper will solve the Joseph ring problem in three ways: circular linked list, ordered array and mathematical recursion.

Problem description

First, let's look at what is Joseph's ring problem.

After the Romans occupied Jotapat, Thirty-nine Jews hid in a hole with Josephus and his friends. Thirty-nine Jews decided to die rather than be caught by the enemy, so they decided on a suicide method. Forty-one people lined up in a circle, and the first person began to count. Every time they counted to the third person, they had to commit suicide, and then the next one counted again until everyone committed suicide. However, Josephus and his friends don't want to comply. Start with one person, cross k-2 person (because the first person has been crossed), and kill the first k person. Then, pass over the k-1 person and kill the k person. This process goes straight along Circle 1 until there is only one person left, and this person can continue to live. The question is, given the sum, where should 1 start to stand to avoid being executed.

Today, the description of Joseph's ring problem has become:

There are N people in one room, all of whom start counting clockwise in a circle, and those who report for M quit the game every time. The next person who quits the game starts to report again, and the person who reports for M quits again. According to this cycle, until there is only one person left in the game, what is the number of the last person?

Cyclic linked list

The problem-solving idea of circular linked list is relatively simple, and only the problem description needs to be converted into code. N individuals in the room form a linked list with a length of N, which is connected end to end to form a circular linked list. The value of each item in the list is the number of each person. When counting to M, this item (recorded as x) is eliminated, that is, next of the first item of this item no longer points to x, but x. next. Traverse the linked list according to this rule until there is only one item left in the linked list.

Let's look at the code implementation under 1.

function createList(num) {
    // Data structure of linked list nodes 
    function createNode(value) {
        return {
            value: value,
            next: ''
        }
    }
    // Linked list header node 
    let head = createNode(1);
    let node = head;
    // Create an association between nodes after the head node 
    for (let i = 2; i <= num; i++) {
        node.next = createNode(i);
        node = node.next;
    }
    // Finally 1 Nodes point to the head node, forming a circular linked list 
    node.next = head;
    return head;
}
function deleteListNode(num, nth) {
    // Create data with a length of num Circular linked list of 
    let node = createList(num);
    // Length of linked list >1 Continue when 1 Wheel 
    while (num > 1) {
        for (let i = 1; i <= nth - 1; i++) {
            if (i == nth - 1) {
                //i For nth-1 , then node.next That is, the first nth Nodes. Cull node.next
                node.next = node.next.next;
                // Length of linked list --
                num--;
            }
            node = node.next;
        }
    }
    // The last remaining 1 Node of value Value is the last 1 Person number 
    return node.value
}
//deleteListNode(m,n) The final result can be obtained 

Ordered array

The circular linked list is simulated by an ordered array, and the remaining array items after the first traversal elimination of the array are formed into a new array, and then the new array is eliminated by a new round of traversal, and then the loop is carried out until the length of the array is 1.

Let's look at the code implementation under 1.

function jhonRing(num, nth) {
    let arr = [];
    // Create an ordered array 
    for (let i = 1; i <= num; i++) {
        arr[i - 1] = i;
    }
    // When the array length is greater than nth The array can find the data to be culled without iterating 
    while (arr.length >= nth) {
        let newArr = [];
        // Move the remaining data at the end of the array to the front of the new array, and the new 1 Round traversal starts with the data that was born 
        let times = arr.length - arr.length % nth;
        newArr = arr.slice(times)
        arr.slice(0, times).map((item, index) => {
            // Add data other than culled data to the new array 
            if ((index + 1) % nth !== 0) {
                newArr.push(item)
            }
        })
        arr = newArr;
    }
    // When the array length is less than nth When, the array needs to be iterated to find the data to be culled, and the number of iterations can be reduced by taking remainder operation 
    while (arr.length > 1) {
        // Get the subscript of the data to be culled by taking remainder 
        let index = nth % arr.length - 1;
        // Eliminate the second half of the data and the first half to form a new array 
        let newArr = arr.slice(index + 1).concat(arr.slice(0, index));
        arr = newArr;
    }
}
//jhonRing(num, nth) The final result can be obtained 

The operation of simulating linked list with ordered array looks similar to linked list, the time complexity looks like 1, and even the code is not as concise as linked list, but why still put forward this way? The advantages of this method are reflected in M > > In the case of N, the ordered linked list effectively reduces the number of times to loop through the array by taking the remainder. Taking N as 3 and M as 100 as an example, the linked list needs to be iterated 100/3 +1 times, while the ordered array directly obtains the data subscript to be eliminated as 0 according to the result of remainder operation 100/3-1=0.

Mathematical recursion

When solving Joseph's ring problem with mathematical problems, it is easy to find an effective route to summarize the law. The following example is M=3 to tell the detour when summarizing the law. (You can skip the invalid ideas and read the valid ideas directly below)

Compare the results when the amount of data is small for many times (Image)

When N=1, f (1, 3) = 1;
When N=2, f (2, 3) = 2;
When N=3, f (3, 3) = 2;
When N=4, f (4, 3) = 1;
When N=5, f (5, 3) = 4;
When N=6, f (6, 3) = 1;
When N=7, f (7, 3) = 4;
When N=8, f (8, 3) = 7;
When N=9, f (9, 3) = 1;
When N=10, f (10, 3) = 4;

Through examples, it is found that the final result is not always between certain numbers, and there is 7 besides 1, 2 and 4, so the subsequent result may have a similar situation, that is, the final result is not always limited to a certain number. f (3, 3), f (6, 3), f (9, 3) and other cases where N is a multiple of M do not get the same result, so there is no special relationship between the final result and the multiple of 3. Therefore, it is not appropriate to find a regular scheme by accumulating and comparing the results when the amount of data is small.

Compare the relationship between the previous culling data (V.)

//Number N individuals from 1-N
1, 2, 3, 4...... N-2, N-1, N
//The number of the first rejection is M or M% N, which can be summarized as M% N and denoted as K. The sequence at the second cull becomes
K+1,K+2,.......N,1,2......K-1
//The number of the second rejection is K+M% (N-1) M% (N-1)-(N-K-1)
According to this, we can get the law
When N-(K+1) > At M% (N-1), f (n) = f (n-1) + M% (N-(n-1))
When N-(K+1) < At M% (N-1), f (n) = M% (N-(n-1))-(N-f (n-1)-1)

According to this law, it will be found that the result obtained without the second lap is correct, and the result after the second lap is wrong. The fundamental reason is that the data after entering the second lap is no longer continuous, and the data eliminated during the first lap will affect the results of the second lap traversal, so the scheme is inappropriate.

Analyze problems from top to bottom and solve problems from bottom to top

The problem of Joseph's ring is analyzed by recursion. Take N=10 and M=3 as examples.

//Number 10 people from 0 (explain why you can't start from 1 later)
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
//Record the number of the last person out as f (10, 3)
//After 10 people are numbered, after the first person leaves the queue, a new queue and number will be obtained
3, 4, 5, 6, 7, 8, 9, 0, 1
//In order to keep the numbers of the new queue continuous, we can write the new queue as A, writing
3, 4, 5, 6, 7, 8, 9, 10%10, 11%10
//If a 9-person general cohort is written as B, and the final result of writing 0, 1, 2, 3, 4, 5, 6, 7, 8 is written as f (9, 3), the result of the new cohort A can be expressed as (f (9, 3) +3)% 10
//The 9-person queue A is obtained after eliminating one person from the 10-person queue, so the result of the 9-person queue after playing according to the rules of N=9, M=3 and initial number 3 must be the same as that of the last person in the queue with N=10, M=3 and initial number 0.
//Therefore, there is a relationship between the last person number in the 10-person queue and the person number in the 9-person queue f (10, 3) = (f (9, 3) +3)% 10

Based on the above, it can be concluded that f (N, M) = (f (N-1, M) + M)% N. The result of the final number is f (N, M) +1.
Why can't the number start from 1? Because the return result of the remainder operation starts from 0.

function Josephus(num,nth){
    if(num==1){
        return 0;
    }else{
        return (Josephus(num-1,nth)+nth)%num
    }
}
//Josephus(N,M)+1 That is, the final number 

Optimize the recursive function 1 times

function JosephusR(num,nth){
    let value = 0;
    for(let i=1;i<=num;i++){
        // Here is a pair i Take the remainder, in the above recursion num Is also getting smaller, so here it is i Instead of num
        value=(value+nth)%i;
    }
    return value+1;
}
//JosephusR(N,M) That is, the final number 

Summarize

The time complexity of the Joseph ring problem is reduced from the original O (mn) to O (n) through the optimization of mathematical recursion. It is really the fastest and easiest way to solve problems by circulating linked lists, but this mathematical recursive way is more valuable to solve such algorithm problems.