josephus(C语言

Josephus Problem in C

The Josephus problem is a theoretical problem related to a certain elimination game. Here's a C implementation that solves the Josephus problem:

#include <stdio.h>
#include <stdlib.h>
// Function to find the position of the last remaining person
int josephus(int n, int k) {
    if (n == 1)
        return 1;
    else
        // The position is returned in 1-based indexing
        return (josephus(n - 1, k) + k - 1) % n + 1;
}
int main() {
    int n, k;
    printf("Enter the number of people (n): ");
    scanf("%d", &n);
    printf("Enter the step size (k): ");
    scanf("%d", &k);
    int result = josephus(n, k);
    printf("The last remaining person is at position: %d\n", result);
    return 0;
}

Explanation:

1. Recursive Approach:

   • The function josephus(n, k) solves the problem recursively.
   • Base case: If there's only 1 person, they are the survivor (position 1).
   • Recursive case: The position of the survivor for n people is calculated based on the solution for n-1 people.

2. Mathematical Formula:

   • The recurrence relation used is: J(n, k) = (J(n-1, k) + k) % n (with 1-based indexing)
   • This formula accounts for the circular elimination pattern.

3. Input/Output:

   • The program asks for the number of people (n) and the step size (k).
   • It then prints the position of the last remaining person (1-based index).

Example Usage:

For n=7 and k=3:

Enter the number of people (n): 7
Enter the step size (k): 3
The last remaining person is at position: 4

Iterative Alternative:

Here's an iterative version for better performance with large n:

int josephus_iterative(int n, int k) {
    int result = 0; // For 0-based indexing
    for (int i = 1; i <= n; i++)
        result = (result + k) % i;
    return result + 1; // Convert to 1-based indexing
}

Both implementations solve the Josephus problem, with the recursive version being more intuitive and the iterative version being more efficient for large inputs.