Problem Description
The Josephus problem is a classic mathematical problem that describes the following scenario:
There are people standing in a circle. Starting from a certain person, they count off in sequence, and every -th person steps out of the circle. The counting and elimination process continues, looping back to the next person when the end of the circle is reached. This continues until only one person remains. The problem is to determine the initial position of the last person remaining in the circle.
For example, when and , the order of elimination is: . The last person remaining is at position .
Solution
The Josephus problem can be solved using either recursion or mathematical formulas. The recursive solution assumes knowledge of the solution for people, denoted as , and then calculates the solution for people using the formula:
Here, denotes the modulo operation. The base case is , representing the solution when there is only one person.
The mathematical formula solution is derived based on the recurrence relation, resulting in the same formula:
Programming Implementation
When it comes to solving the Josephus problem, dynamic programming is an effective approach. Here is an example C code implementing dynamic programming to solve the Josephus problem:
In the above code, we use a dynamic programming array dp
to store the next position after each person is eliminated. Through iteration, we can find the initial position of the last person remaining in the circle. In the main
function, we set the total number of people n
and the count to m
for elimination. Then, we call the josephus
function to calculate the position of the last person remaining and print the result.
Note that we assume people's positions start from 1, while array indices start from 0. Therefore, when printing the position of the last person remaining, we need to add 1.
Using dynamic programming provides an efficient solution to the Josephus problem, avoiding the repetitive calculations of recursion and improving code performance.