PTA monkey chooses King (Joseph Ring problem)

 

Catalog

subject

Violent solution  

  Application of Joseph Ring formula

---

subject

---

 

Violent solution  

At first I realized that this was a Joseph Ring problem , So I thought about whether I could solve the problem violently by marking the array .

The idea at the beginning

• First, I define an array to represent this group of monkeys , The initial values of the array are 1（ At the beginning, all the monkeys were in the circle , If the value of an element in the array is 0, It means that the monkey is no longer in the circle ）
• Then define a counter （ Indicates the current reported number ）, Whenever the number reaches 3 when , Assign the array element value corresponding to the current monkey as 0（ It means not in the circle , Note the number of monkeys exiting ）, At the same time, the number is reassigned to 0（ Start counting again ）
• Finally, when the number of monkeys exiting is the total number of monkeys minus one , The king was chosen

The code is as follows ：

import java.util.*;
public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) 
            a[i] = 1; //  At the beginning, the array element values are 1, All monkeys are in the circle 
        int num = n; //  The number of monkeys remaining in the circle 
        int count = 0; //  The serial number of each round of monkeys 
        int flag = 0; //  Monkey King's number 
        while (num != 1) {
            for (int i = 0; i < n; ++i) {
                
                if (a[i] == 1) {
                    count++;
                    flag = i;
                }
                if (count == 3) {
                    a[i] = 0; //  Not in the circle , Start counting again 
                    count = 0;
                    --num; //  To report for duty 3 The monkey of left the circle 
                }
            }
        }
        System.out.println(flag + 1);
    }
}

But when I submit it （ heartache ）

 

Because I can't find the wrong point , I can only change my mind —— At this time, I found that the original problem is the Joseph Ring problem  

As for Joseph Ring, as long as we remember the recurrence formula of Joseph Ring on the basis of understanding , This topic becomes simple in an instant

---

  Application of Joseph Ring formula

 

Let's briefly review the Joseph Ring problem

Finding the last number in a circle can be called the Joseph Ring problem  

 

  It means

• f(n,m) The value of means yes 0,1,2,... n - 1, this n The last remaining number after Joseph operation （ That is, the remaining King ）
• f(n - 1, m) The value of means yes 0,1,2,... n - 2, this n - 1 The remaining number after Joseph operation

There are the following recurrence formulas

 

This is recursion ？ 

If you don't understand Joseph Ring, you can take a look at this article —— Depth analysis of Joseph Ring  

The code is as follows

import java.util.*;
public class Main {
    public static int func(int n, int m) { 
        if (n == 1) return 0;
        int flag = (func(n - 1, m) + m) % n; // flag After Joseph Ring operation , The last remaining number 
        return flag;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int flag = func(n, 3); // flag The serial number of the last monkey after Joseph Ring operation 
        System.out.println(flag + 1); //  Because the serial number is from 1 At the beginning , Add one to all 
    }
}

 

  But recursion efficiency because there's a round-trip procedure , It's less efficient than direct iteration , You can also iterate from front to back ：

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int flag = 0;// Push backward , It is known that the last round of Monkey King is numbered 0, Push to the penultimate round , Count down three rounds ... All the way to the initial position .
        //flag It means the last monkey （ Monkey King ） In each round （ Count down to the last 1 round , Find the penultimate round ,...） Own serial number in    
        //i Means the last i round 

        for (int i = 2; i <= n; ++i) { //  there i It is equivalent to... In recursion n,3 Namely m
            flag = (flag + 3) % i;    // flag The serial number of the last monkey after Joseph Ring operation 
            //  The number of monkeys in the current circle changes dynamically , Recursion is when n be equal to 1 Exit from time , We from n==2 The process of traversing from front to back is equivalent to a recursive operation 
        }                          
        System.out.println(flag + 1); //  Because the serial number is from 1 At the beginning , Add one to all 
    }
}