maths.josephus_problem

The Josephus problem is a famous theoretical problem related to a certain counting-out game. This module provides functions to solve the Josephus problem for num_people and a step_size.

The Josephus problem is defined as follows: - num_people are standing in a circle. - Starting with a specified person, you count around the circle,

skipping a fixed number of people (step_size).

• The person at which you stop counting is eliminated from the circle.

• The counting continues until only one person remains.

For more information about the Josephus problem, refer to: https://en.wikipedia.org/wiki/Josephus_problem

Functions

find_winner(→ int)	Find the winner of the Josephus problem for num_people and a step_size.
josephus_iterative(→ int)	Solve the Josephus problem for num_people and a step_size iteratively.
josephus_recursive(→ int)	Solve the Josephus problem for num_people and a step_size recursively.

Module Contents

maths.josephus_problem.find_winner(num_people: int, step_size: int) → int

Find the winner of the Josephus problem for num_people and a step_size.

Args:

num_people (int): Number of people. step_size (int): Step size for elimination.

Returns:

int: The position of the last person remaining (1-based index).

Examples:

>>> find_winner(7, 3)
4
>>> find_winner(10, 2)
5

maths.josephus_problem.josephus_iterative(num_people: int, step_size: int) → int

Solve the Josephus problem for num_people and a step_size iteratively.

Args:

num_people (int): The number of people in the circle. step_size (int): The number of steps to take before eliminating someone.

Returns:

int: The position of the last person standing.

Examples:

>>> josephus_iterative(5, 2)
3
>>> josephus_iterative(7, 3)
4

maths.josephus_problem.josephus_recursive(num_people: int, step_size: int) → int

Solve the Josephus problem for num_people and a step_size recursively.

Args:

num_people: A positive integer representing the number of people. step_size: A positive integer representing the step size for elimination.

Returns:

The position of the last person remaining.

Raises:

ValueError: If num_people or step_size is not a positive integer.

Examples:

>>> josephus_recursive(7, 3)
3
>>> josephus_recursive(10, 2)
4
>>> josephus_recursive(0, 2)
Traceback (most recent call last):
    ...
ValueError: num_people or step_size is not a positive integer.
>>> josephus_recursive(1.9, 2)
Traceback (most recent call last):
    ...
ValueError: num_people or step_size is not a positive integer.
>>> josephus_recursive(-2, 2)
Traceback (most recent call last):
    ...
ValueError: num_people or step_size is not a positive integer.
>>> josephus_recursive(7, 0)
Traceback (most recent call last):
    ...
ValueError: num_people or step_size is not a positive integer.
>>> josephus_recursive(7, -2)
Traceback (most recent call last):
    ...
ValueError: num_people or step_size is not a positive integer.
>>> josephus_recursive(1_000, 0.01)
Traceback (most recent call last):
    ...
ValueError: num_people or step_size is not a positive integer.
>>> josephus_recursive("cat", "dog")
Traceback (most recent call last):
    ...
ValueError: num_people or step_size is not a positive integer.