Joseph Circle Problem
    November 21, 2023

    A description, analysis and solution for joseph circle problem.

    Problem Description

    The Josephus problem is a classic mathematical problem that describes the following scenario:

    There are nn people standing in a circle. Starting from a certain person, they count off in sequence, and every mm-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 n=7n=7 and m=3m=3, the order of elimination is: 3,6,2,7,5,13, 6, 2, 7, 5, 1. The last person remaining is at position 44.

    Solution

    The Josephus problem can be solved using either recursion or mathematical formulas. The recursive solution assumes knowledge of the solution for n1n-1 people, denoted as f(n1,m)f(n-1, m), and then calculates the solution for nn people using the formula:

    f(n,m)=(f(n1,m)+m)%nf(n, m) = (f(n-1, m) + m) \% n

    Here, %\% denotes the modulo operation. The base case is f(1,m)=0f(1, m) = 0, 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:

    f(n,m)=(f(n1,m)+m)%nf(n, m) = (f(n-1, m) + m) \% n

    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:

    #include <stdio.h>
    
    int josephus(int n, int m) {
        int dp[n + 1];
        dp[1] = 0; // Initial position when there is only one person
    
        for (int i = 2; i <= n; i++) {
            dp[i] = (dp[i - 1] + m) % i;
        }
    
        return dp[n];
    }
    
    int main() {
        int n = 7; // Total number of people
        int m = 3; // Count off to m for elimination
    
        int lastPerson = josephus(n, m);
        printf("The last person remaining is: %d\n", lastPerson + 1); // Adding 1 due to 0-based indexing
    
        return 0;
    }
    

    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.

    Share with the post url and description