Problem Description
 The
"Josephus" problem is to identify the position to stand in a
circle of 41 men if every 3rd man will be successively eliminated around
the circle and you want to be the last remaining man.
Background & Techniques
The story is that the Jewish historian/mathematician, Josephus, was
running from the Romans during some Roman-Jewish war, sometime around 500
years ago. They followed him to a cave where we found 40 Jewish
soldiers and which the Romans placed under siege. Seeing no hope of
escape and unwilling to surrender, the group decided that suicide was the
best way out. Josephus and one other fellow weren't too happy about
the plan so he suggested the circle with every third man committing
suicide (or being executed in some versions), until only one man was
left. He was smart enough to figure out where he and his buddy
should stand initially so they were the last two standing. The rest
of the story is that Josephus was known thereafter as Josephus Flavius
after the family that adopted him when surrendered to the Romans.
These counting-elimination games have been traced back at least to the
12th century. In the USA most kids learn the selection game that
starts "One potato, two potato, three potato four...."
which selects one person for each round.
Mathematically, the problem is quite simple, especially if you have a
computer as a helper. This version of the program has some simple
animation. User can select the number of people in the circle
and the increment between selected victims. Selecting your
location in the circle starts the elimination process and lists victims in
the order of their selection.
Non-programmers are welcome to read on, but may
want to skip to the bottom of this page to
download executable version of the program.
The main programming challenge was getting the
"smileys" and numbers positioned correctly in a circle and
identifying which one was clicked to start the process. An
array of people numbers is maintained by eliminating entries as selected
and incrementing the pointer the the next selection using modular
arithmetic based on the numbr of people currently remaining in the
circle.
Two sizes of smileys are available and the
distance between images determines whether the larger or smaller is
used. There are 4 smileys of each size - normal alive, normal
dead, player selected position alive, and player selected position dead.
Addendum October 15,2008: Version
2 was posted today. It solves an "inverse" version of Josephus; we
are given the final location and must determine where to start counting
for the selection process. Numbering relative to 1, the starting
location may be calculated as:
Start=(A - F(N,K) +N - 1) mod N + 1
where
 |
N=number
of people |
|
|
K= choose
every Kth person |
|
|
A=
desired final person chosen |
|
|
F(N,K) is
a recursive function defined as:
 |
F(N,K)
= (F(N-1,K) -K) mod N for N>1 |
|
|
F(1,K) = 0 for N=1
|
|
Running/Exploring the Program
Suggestions for Further Explorations
The bmp Smiley images should be incorporated into
a resource file, but I would have had to look up the code to do it, so
they are just included are separate files and loaded as required.
I'll bet the whole process of combining images into a "res" file could be automated into an interactive program.
Hmmm.
| Original Date: July 10, 2005 |
Modified:
November 07, 2008
|
|
