Joseph ring problem JS

create by db on 2021-7-8 15:53:37

Recently revised in 2021-7-8 19:51:30

This article has participated in the call for good writing activities, click to view: back end, big front end double track submission, 20,000 yuan prize pool waiting for you to challenge!

Idle time to have a tight mind, busy time to have leisure fun

directory

• Topic describes
• Thought analysis
• AC code
• conclusion

Topic describes

Returns the directory

Question history

Legend has it that the Romans captured Chotapat and that 41 Jews were cornered in a cave. They refuse to be captured, and decided to collective suicide, we decided to a suicide plan, 41 people in a circle, clockwise by 1 individual number off, every count off for 3 people to commit suicide at once, and then by the next person to start from 1 count off, is still every count off for 3 people to commit suicide at once, loop in turn. Two of the Jews who didn’t want to commit suicide were the mathematician Joseph and his friend, who discovered the pattern of a suicide plan, chose two specific locations, and they were the only two left alive. So what are these two positions?

Problem description

This problem translates into a general problem to be solved: That is, the number of n people in a circle starts from 0 — (n-1), the first person (number 0) starts from 1, the person with number M leaves, and the next person starts from 1, the person with number M leaves, and the cycle continues until the last person (or the last two) is left. One less loop), then print out the number of the last person.

Thought analysis

Idea 1: Loop tags

Use an array to store the states of N people in the circle, all marked as 1, that is, all the elements of the array with length N are 1, use a counter to record the number of times, only the person identified as 1 can count, when the value of the counter is equal to m, let the person leave, then marked as 0. And let the variable that records the number of laps add 1, and then will count off zero, when the variable is equal to N-1, the game is over.

Idea 2: Recursive markup

The process is the same, but instead of the first loop, we use recursion.

Idea 3: Dynamic planning

The so-called dynamic programming is: find relations. The basic logic here is that when n people get one out of the game, the total number of people becomes n-1, and the problem we’re dealing with is actually n-1 people, and so on and so forth, we’re dealing with n = 2 problems, because when n = 1, the game is over. Then use an equation to express the solution process of n = 2: f(2,m) it is easy to see the rule: m is even left 0,m is singular left 1, use m%2 to represent the result (this is the basic condition of recursive algorithm). Then to find the correspondence between f(3,m) and f(2,m), or more precisely, f(n,m) and f(n-1,m), the steps are: first find the reference conditions, and then use a simple example to find the correspondence between F (n,m) and f(n-1,m).

Let’s start with some simple examples and find a pattern:

Here are the issues to deal with: N = 5, m = 2, 0, 1, 2, 3, 4 starting at the 0th digit, the first digit is 2, 0, 2, 3, 4 leaving the first person 2, 3, 4, 0 (*) the top digit could be written like this, because starting at the 2nd digit, 0, 1, 2, 3 (**), this is n = 4, M = 2, the problem to deal with, let's deal with this problem 0, 2, 3 leave the second person and compare the equations (*) and (**), you can find the pattern: (**)+2)%5 becomes (*) 2, 3, 0 (*) we can write the numbers like this, because we start with the second digit 0, 1, 2 (**) this is n = 3, m = 2, we're dealing with the problem, Let's deal with this problem. 0, 2 leave the third person and compare (*) with (**). You can find the pattern: (**)+2)%4 turns into (*) 2. 0 (*) we can write the numbers like this, because we start with the second digit 0. 1 (**) this is n =2, m=2, and we already know the answer, 2%2 = 0. You can find the rule :((**)+2)%3 is converted to (*) 0 leaves the fourth person, the game is over, so you need to go back to the top of the above formula can make (**) equivalent to (*), that is, to solve the problem in (**), the result, using this formula can get the result of (*)Copy the code

So we can get the corresponding formula: f(n,m) = (f(n-1,m)+m)%n

That is, when we have a solution for f(n-1,m), then we have a solution for f(n,m)

The idea of dynamic programming (recursion) is to break down from top to bottom and back up. When n is equal to 2 and m is equal to 2, we get a solution of 0, so when n is equal to 3 and m is equal to 2, we get a solution of 0 plus 2 %3 is equal to 2, so when n is equal to 4 and m is equal to 2, We get 2 plus 2 %4 is equal to 0, and we put that 0 into the formula, and we go back up one layer, so when n is equal to 5 and m is equal to 2, we get 0 plus 2 %5 is equal to 2, so we solved the f of 5, 2 problem.

AC code

Solution 1: Loop markers

/ * * *@param {number} The number of n *@param {number} M out of the loop tells the number *@return {number}* /
function josephRing(n, m) {
  // The game cannot proceed if the parameter does not meet the condition
  if (n <= 1 || m < 1) {
    console.log("you can't play Joseph's game. n must be bigger than 1, m must be bigger than 0")
    return
  }

  let arr = new Array(n).fill(1) // Array of length n, position from 0 to n-1, represents the number of n people, and set all elements of array to 1 to represent the uncircled
  let count = 0 // Record the number of laps
  let num = 0 / / count off

  // Set loop end condition: when count = n-1, i.e. only one person left, the game ends'
  while (count < n - 1) {
    for (let i = 0; i < arr.length; i++) {
      // Layer 2 loop, loop array
      if (arr[i] === 1) {
        // When the element in this position is 1, the following code is executed
        num++ // Increments the counter every time it passes a position with element 1
        if (num === m) {
          // When the counter is equal to m, the following code is executed
          arr[i] = 0 // Set the element at the position to 0 to indicate that the position has been circled
          count++ // Add one to the number of laps
          num = 0 // Reset the count counter
        }
        // If m = 1, the for loop will exit only if count = n, at which point all the elements in the array will be 0
        // When m = 1, the result is n. We can also treat m = 1 as a special case outside the while loop, so that m = 1 does not enter the loop
        if (count === n - 1) {
          break}}}}// Find the position of element 1 in the array and print that position
  let winner = arr.findIndex(item= > item === 1) + 1
  console.log(`${winner} is the winner`)}// Test the code above, and print the execution time so that it can be compared with other solutions
let start = new Date().getTime()
josephRing(10000.3)
let end = new Date().getTime()
console.log('= = = =' + (end - start) + '= = = =')
Copy the code

Solution 2: Recursion

/ * * *@param {number} The number of n *@param {number} M out of the loop tells the number *@return {number}* /
let count = 0 // Record the number of laps
let num = 0 / / count off
function josephRing(n, m, arr) {
  // The game cannot proceed if the parameter does not meet the condition
  if (n <= 1 || m < 1) {
    console.log("you can't play Joseph's game. n must be bigger than 1, m must be bigger than 0")
    return
  }
  // Create an array of length N, from 0 to n-1, representing n individual numbers, and set all elements of the array to 1 to represent uncircled elements
  if(! arr) { arr =new Array(n).fill(1)}// Set recursive end condition: when count = n-1, i.e. only one person left, the game ends and the winner is returned
  if (count === n - 1) {
    let winner = arr.findIndex(item= > item === 1) + 1
    console.log(`${winner} is the winner`)
    return
  }
  // Loop through the array to change the state
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === 1) {
      // When the element in this position is 1, the following code is executed
      num++ // Increments the counter every time it passes a position with element 1
      if (num === m) {
        // When the counter is equal to m, the following code is executed
        arr[i] = 0 // Set the element at the position to 0 to indicate that the position has been circled
        count++ // Add one to the number of laps
        num = 0 // Reset the count counter}}}// recursive call
  josephRing(n, m, arr);
}

// Test the code above, and print the execution time so that it can be compared with other solutions
let start = new Date().getTime()
josephRing(10000.3)
let end = new Date().getTime()
console.log('= = = =' + (end - start) + '= = = =')
Copy the code

Solution 3: Dynamic programming

,

/ * * *@param {number} The number of n *@param {number} M out of the loop tells the number *@return {number[]}* /
function josephRing(n, m) {
  if (n <= 1 || m < 1) {
    console.log("you can't play Joseph's game. n must be bigger than 1, m must be bigger than 0")
    return
  }

  let r = 0
  for (let i = 2; i <= n; i++) {
    // The result of n = 2 is calculated first, and the final r is the winner
    r = (r + m) % i
  }
  console.log(r + 1 + ' is the winner.')}// Test the code above, and print the execution time so that it can be compared with other solutions
let start = new Date().getTime()
josephRing(10000.3)
let end = new Date().getTime()
console.log('= = = =' + (end - start) + '= = = =')
Copy the code

conclusion

Returns the directory

The road ahead is long, and I see no end.

reference

• Joseph ring four solutions JS | zhihu – Growth61
• Joseph ring problem “js implementation” | CSDN – Floatwor green boat

Postscript: Hello friends, if you think this article is good, remember to give a thumbs-up or star, your thumbs-up and star is my motivation to write more and richer articles!Making the address

Document agreement

dbThe document library 由 dbusingCreative Commons Attribution – Non-commercial Use – Same way Share 4.0 International LicenseGrant permission.

Based on thegithub.com/danygitgitOn the creation of works.

Use rights other than those authorized by this License agreement may be obtained fromCreativecommons.org/licenses/by…Obtained.