1. Introduction

The Joseph ring is roughly described as follows: n people form a circle, the first person counts from 1, the person who calls M is out, the next person counts from 1, and so on until everyone is out. See here for details.

I think there are two ways to solve the Joseph ring problem.

  1. You only want the result, that is, you only want the last person to get out.

  2. The whole process, which is to figure out who goes out in each round.

2. Situation 1: Results only

Here are two special cases of Joseph’s problem: n stands for the total number of people, m stands for the number of people out, and the n people are numbered from 1 (note: number from 1 here for easy understanding).

2.1 Special case 1: n is a power of 2 and m is 2

  • When n is 2, the last person out (winner) is obviously 1.

  • When n is 4, the order of exits is 2, 4, 3, and the winner is 1.

  • When n is 8, the order of exits is 2, 4, 6, 8, 3, 7, 5, and the winner is 1.

  • .

It is not hard to see that in this particular case, the winner is always Number 1.

2.2 Special case 2: n is any number and m is 2

For example, when n is 12 and m is 2, its Joseph ring is shown in the following figure:

When 8 goes out, there are 8 people left, and 2 to the third is equal to 8, so this is going to be trueSpecial case 1. So the next digit of 8 is 9Special case 1Number one, so number nine is the winner.

So in summary, when m is 2, the way to solve the Joseph’s ring problem is to find out when the number of people left is a power of 2, and the next one is the winner.

2.3 Arbitrary case: n and m are arbitrary numbers

In this case, the solution is to use recursion.So for the sake of calculation, I’m going to start numbering at 0, 0 to n minus 1.. For example, when n = 7 (That is, the numbers are 0 to 6), when m=3, the situation of each outgoing call is shown in the figure below:Every time you’re out, you take the restShift to the leftM bits (where m is 3), so that each outgoing is marked by a yellow grid. Obviously, in any case, the position of the final winner (the scarlet letter) must be0So his position in the previous round (round 6) is (0+3)%2=1. So what this plus 3 means isMoves to the rightBecause he got to this round by moving to the left, and to get back to the previous round he would have to move to the right, but to take into account the transgression he has to mod n, which is the number of people left in that round. The position in round 5 is (1+3)%3=1, so the loop will determine the winner’s position at the beginning.

At this point, the calculation of Joseph ring results of the train of thought has been given, the implementation of Java code is given below.

2.4 Java code

public class Test01 {
    /** * Joseph ring problem, only the result *@paramN Number of people left in the round *@paramThe person with this number is out *@returnThe winner's index starts at 0 */
    public static int josephus(int n, int m) {
        if (m == 2) {       // m=2
            int k = 1;
            while (k <= n) {
                k = k << 1;
            }
            k = k >> 1;
            return (n - k) * 2;
        } else {            // In the general case, use recursion
            if (n == 1) {
                return 0;
            } else {
                return (josephus(n-1, m) + m) % n; }}}public static void main(String[] args) {
        // Since the function returns indices numbered from 0, we need to add 1
        System.out.println(josephus(7.3) + 1); }}Copy the code

Case 2: Complete process

3.1 train of thought

The solution is to simulate the outs with arrays. The general idea is as follows:

  • Define a count variable with an initial value of 1 for counting
  • Each time a new element is accessed, count increments. When count is equal to m, the element is marked, its position is printed, and count is set to 1
  • If the currently accessed element is already marked, the element is skipped and the next element is accessed
  • Repeat steps 2 and 3 above until all elements of the array are marked

3.2 Java code

public class Test02 {
    /** * Joseph ring problem, solve the whole process *@paramN Total number of people *@paramThe person with this number is out */
    public static void josephus(int n, int m) {
        int[] nums = new int[n + 1];
        int count = 1;
        int flag = 0;
        for (int i = 0; i < nums.length; i++) {
            nums[i] = i;
            flag += i;
        }
        while (flag > 0) {
            for (int i = 1; i <= n; i++) {
                if (nums[i] == 0) {
                    continue;
                }
                nums[i] = count;
                count++;
                if (nums[i] == m) {
                    System.out.printf(i + "");
                    count = 1;
                    nums[i] = 0;    // Mark the element and skip it in the next iterationflag -= i; }}}}public static void main(String[] args) {
        josephus(7.3); }}Copy the code

4. The conclusion

Thank you for your reading, I think some of the basic situation of Joseph ring problem has been all listed, need to pay attention to the code when the conversion of numbers. My ability is limited, the code may not be the best, but also please forgive!