Detailed explanation of Joseph problem

1. What is Joseph's problem

It has a number of 1,2,……,n Of n(n>0) A circle of individuals , From 1 Individual starts counting , To report for duty m Stop reporting when , newspaper m People out of circles , And then from his next person to report , To report for duty m Stop reporting when , newspaper m Out of the loop ,……, Go on like this , Until everyone is out of the circle . When any given n and m after , Design algorithm n The order in which individuals go out of circles .

2. Violence solution

The most direct method is to simulate the process of counting . simulation n-1 The process of counting off the number of times , Report data each time m personal , The first m Individuals are eliminated . Finally, check which number did not check in , This number is the result .# Learning goals ：

But the time complexity is O(m*n). So when m and n When you're older , The running time of the program will be very long .

3. Recursive formula solution

Step one : Definition f(n)

take n Personal count , newspaper m The problem of people out of the circle is regarded as f(n,m) problem , And let the solution of the problem be f(n). that n-1 Personal count , newspaper m The problem of people out of the circle is regarded as f(n-1,m) problem , And let the solution of the problem be f(n-1).

f(n,m)	n Personal count , newspaper m People out of circles
f(n-1,m)	n-1 Personal count , newspaper m People out of circles
…	…
f(1,m)	1 Personal count , newspaper m People out of circles

Step two find f(n) And f(n-1) The relationship between

Assume that at the beginning, everyone's serial number is ：

1 2 3 … n-1 n

So after the first count off , Only the following people are left ：

1 2 3 … m-1 m+1 … n-1 n

And after the next count off , from m+1 Start counting , So the serial number should change to ：

m+1 m+2 …n-1 n 1 2 3 … m-1
( Let the serial number here be x)

Map the above serial number to the following serial number ：

1 2 3 … n-2 n-1
( Let the serial number here be y)

be x and y What's the relationship ：

x=(y+m)%n

among , The serial number here x It stands for f(n,m) The serial number in , Serial number y It stands for f(n-1,m) The serial number in . that f(n) And f(n-1) What's the relationship

f(n) =( f(n-1)+m )%n
f(n-1)=( f(n-2)+m )%(n-1)
f(n-2)=( f(n-3)+m )%(n-2)
…
f(2)=( f(1)+m )%2
f(1)=1

f(1)=1 Because there is only one person , It must be the last one left , Serial number is 1.

Step three Write code according to recurrence formula

According to the recurrence formula ,f(1)=1 after , Then you can get the answer from the bottom up . Get it first f(2). Ask again f(3) until f(n). So here's the code .

int yuesefu(int n, int m) {
    
        int x = 1;
        for (int i = 2; i <= n; i++) {
    
            x = (x + m) % i;
        }
        return x;
    }