Skip to content

Latest commit

 

History

History
26 lines (18 loc) · 1.77 KB

josephus.md

File metadata and controls

26 lines (18 loc) · 1.77 KB

#Josephus Problem

##Problem Description In computer science and mathematics, the Josephus Problem (or Josephus permutation) is a theoretical problem related to a counting out game.

There are people standing in a circle waiting to be executed. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom.

The task is to choose the place in the initial circle so that you are the last one remaining. Reference: Wikipedia

##History The problem is named after Flavius Josephus, a Jewish historian living in the 1st century. According to Josephus' account of the siege of Yodfat, he and his 40 soldiers were trapped in a cave, the exit of which was blocked by Romans. They chose suicide over capture and decided that they would form a circle and start killing themselves using a step of three. Josephus states that by luck or possibly by the hand of God, he and another man remained the last and gave up to the Romans.

##Assignment

###Before starting to code: In a groups, talk about how to solve the problem.

  • Inputs: circle size, starting position, number of people to skip
  • Output: last position left standing

Have different people take on documenting each of the following:

  • identify the structures that you will need to use
  • list multiple examples of inputs and their respective outputs
  • identify test cases that need to be addressed
  • create pseudocode for how you will solve the problem

###Code in your specific intern language!