 |
 |
||||||||||||||||||||||||||||||||||||||||||
The Josephus ProblemFlavius Josephus was a Jewish historian in the first century A.D. He is known for having authored three important volumes of the history of the Jews shortly after the time Jesus of Nazareth was causing the Romans fits. (In fact he claimed to be the son of Matthias, the latent disciple of Jesus who replaced Judas Iscariot after Judas betrayed Jesus to the authorities and then killed himself. There is no shortage of suicides in this paper.) The Romans didn't want much at all to do with the Jews or the people who would eventually call themselves Christians; they reluctantly tolerated the religious as long as they didn't threaten the authority of the emperor. The rumor goes that Flavius and thirty-nine of his closest friends were surrounded by Romans soldiers who sought to arrest them. When he suggested surrendering, his idea was rejected, and so he came up with another plan: They'd all stand in a circle and assign themselves sequential numbers starting with one. Every other person would kill himself until there was no one living. Being a clever man, the story goes that Flavius positioned himself in the circle in such a way that he would be the last to die, and his best friend the second last. After all but the two had killed themselves, Josephus and his cohort surrendered to the Romans. Whether or not this actually happened, the mathematics fascinated people, especially if the scenario could be adapted to arbitrary numbers of people and stepping (e.g. how would this work out differently if there had been forty-one people and every third was killing himself?), and so the extended problem (where people (n) ≠ 40 and stepping (k) ≠ 2) was named the Josephus Problem. In every round, someone's getting killed off, so we can say that for n people in n rounds, everybody dies, or generically, for n rounds, n people die. What makes the problem interesting is the order in which people are eliminated. There is a recurrence relation that describes this for k = 2. Using the included source code in C++, the first twenty rounds eliminate the even-numbered people and complete the first pass around the circle. So we might consider the following pseudocode:
The first pass eliminations look like this:
What's left are the odd numbers, but now we could just as well renumber them as consecutive integers; the order of the eliminations would not be any different. (This is where the recurrence relation comes in). It's important not to double-count; it's not possible to kill a man who's already dead1. If we had bothered to renumber these remaining people, we'd see the problem is revised such that people (n) = 20 and stepping (k)= 2. In this case, predictably the even numbered people are killed off in the second pass through the circle, but how does this relate to the original problem if we'd not renumbered anything? If we don't renumber for the second pass through the circle, the sequence of eliminations is:
What can we say for these numbers? First off, recall that the first pass through the circle eliminated everyone whose number could be described as 2q for some integer q. The second pass is described by 2(2q) – 1:
...and so on. In the third pass, people are eliminated by a similar formula:
And we could conjecture that the fourth pass will conform to:
The recursion for each successive pass through the circle is derived by multiplying the expression of the previous pass by two and subtracting one. Consider x as another pass through the circle, and the eliminations are described by this recursive function:
Ω Footnotes.
Works Cited.
Source Code (C++ Implementation #1) /*
Sample Josephus Problem Implementation in C++
User is prompted to provide values for n and k. The algorithm is based on the
Java implementation at http://webspace.ship.edu/deensley/mathdl/Joseph.html.
The C++ implementation is my work.
*/
#include <iostream>
#include <iomanip>
using namespace std;
int murder(int, int, int);
int main();
int murder (int people, int stepping, int round) {
int victim = stepping * round;
while (victim > people) {
// Force floating point, but this will get truncated:
victim = (stepping * (victim - people) - 1.0 ) / (stepping - 1.0);
}
// And today's winner is.....
return(victim); // Mmm...! Fresh meat!
}
int main() {
int people, stepping, round;
cout << "How many people are there to kill? ";
cin >> people;
cout << "Every k'th person dies. What is k? ";
cin >> stepping;
int elimination[people]; /* This is the order of the elimination */
/* The meat of the program. Load the array with murderous values */
for (round = 1; round <= people; round++) {
elimination[round - 1] = murder(people, stepping, round);
}
/* Display the results */
cout << " Round Eliminated\n";
cout << "---------- ----------\n";
for (round = 1; round <= people; round++) {
cout << setw(10) << right << round
<< setw(12) << right << elimination[round - 1] << endl;
}
cout << endl;
return 0;
}
Source Code (C++ Implementation #2) /*
Kills people using a linked list. This is my work.
*/
#include <iostream>
#include <iomanip>
using namespace std;
int main();
int main() {
int n, k, i;
int j = 1;
int kills = 0;
struct node {
int person;
bool alive;
node *next;
};
cout << "How many people are there for killing? ";
cin >> n;
cout << "Killing every k'th person. What is k? ";
cin >> k;
node circle[n];
node *current = &circle[0];
for (i = 0; i < n - 1; i++) {
circle[i].person = i + 1;
circle[i].alive = true;
circle[i].next = &circle[i + 1];
}
circle[n - 1].person = n;
circle[n - 1].alive = true;
circle[n - 1].next = current;
while (kills < n) {
if (j == k) { // time to kill
current->alive = false;
kills++;
cout << "Killed " << current->person << endl;
}
if (kills == n) {
exit(0);
}
do {
current = current->next;
} while (current->alive == false);
j++;
if (j > k) {
j = 1;
}
}
return 0;
}
Perl source code is coming soon, especially so I can serve it through CGI. I don't know anything about C++'s CGI libs, but I'm good with Perl's. |
|||||||||||||||||||||||||||||||||||||||||||
Copr. © 2010 Piradian Null Devices |