The First Algorithm is the solution to the Josephus Problem.
The problem is based on a tale during the Roman Empire, 41 jews were hiding in a cave and were about to be captured by the Romans but the jews preferred suicide over surrender and hence devised a strategy. They all would stand in a circle and every third person would be killed. Josephus did not want to commit suicide and as he was a smart man he calculated the exact position where he should stand so he is the last man standing.
The Modern problem is based on a similar lines but instead of 41, n people are given and instead of every third person to be killed every k person is killed. You have to find the safe position
Say n = 5 and k = 2, then the order of killing is 2,4,1,5
Here we observe that after the first kill i.e the killing of second person we have n1 people and so the problem can be considered as finding the safe position with n1 people when person on k position is executed. So, the problem has a nice recursive structure but the only problem is after the first kill the k+1 position person assumes the first position which can be adjusted as \[k \% n + 1\]
Algorithm:
1 2 3 4 5 

For a nice visualisation of the Josephus Problem visit the following link: Josephus
Problem Loading...
Note Loading...
Set Loading...
Comments
There are no comments in this discussion.