Sunbelt Computer Software

PL/B Language Development and Support

Python_Algorithms/maths/josephus_problem.py at master · feitian19873000/Python_Algorithms · GitHub

130 lines (105 loc) · 3.92 KB

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

"""

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

"""

def 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.

"""

if (

not isinstance(num_people, int)

or not isinstance(step_size, int)

or num_people <= 0

or step_size <= 0

):

raise ValueError("num_people or step_size is not a positive integer.")

if num_people == 1:

return 0

return (josephus_recursive(num_people - 1, step_size) + step_size) % num_people

def 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

"""

return josephus_recursive(num_people, step_size) + 1

def 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

"""

circle = list(range(1, num_people + 1))

current = 0

while len(circle) > 1:

current = (current + step_size - 1) % len(circle)

circle.pop(current)

return circle[0]

if __name__ == "__main__":

import doctest

doctest.testmod()