Das Josephus-Problem

1. Aufgabe

Das Meisterwerk des Historikers Flavius Josephus ist seine geschichtliche Darstellung des Jüdischen Krieges. Einer Legende zufolge war er während dieses Krieges Mitglied einer 41-köpfigen jüdischen Rebellenbande, die im Jahre 67 n. Chr. in der galiläischen Stadt Jotopata ein Zentrum des antirömischen Widerstandes bildete. Nach 47-tägiger Belagerung gelang es den Römern unter der Führung ihres Kaisers Vespasian jedoch, die Stadt einzunehmen. Die Rebellen beschlossen, den Freitod einer Gefangenschaft vorzuziehen. Vergebens beschwor Josephus seine Mitstreiter, davon abzulassen. Um wenigstens sich zusammen mit einem unbekannten Mitverschwörer vor dieser Freitod-Orgie zu retten, schlug er als Tötungsritual den alten römischen Brauch der Decimatio (Dezimierung) vor: Zuerst mussten sich die Rebellen in einem Kreis herum aufzustellen, danach sollte sich jeder dritte nacheinander im Kreis das Leben nehmen. Josephus jedoch konnte Dank seiner mathematischen Begabung schnell ausrechnen, wo er und sein Freund im Kreis stehen mussten, um als Letzte übrig zu bleiben und somit dem Tode zu entkommen.

Schreiben Sie ein Programm, dass berechnet, an welche Stelle des Kreises Josephus sich und seinen Freund stellte, um zu überleben? Zum Entwurf einer Lösung können sehr unterschiedliche Datenstrukturen zum Einsatz kommen. Investieren Sie zunächst genügend Zeit in die Ausgestaltung eines Entwurfs, bevor Sie mit der Implementierung anfangen.

Bei 17 Soldaten sollte die Ausgabe des Programms wie folgt aussehen, wenn jeder dritte Soldat ausgesondert wird:

Number of soldiers: 17
Eliminating: Each 3. soldier

Removed  3  [1,2,4,5,6,7,8,9,10,11,12,13,14,15,16,17]
Removed  6  [1,2,4,5,7,8,9,10,11,12,13,14,15,16,17]
Removed  9  [1,2,4,5,7,8,10,11,12,13,14,15,16,17]
Removed 12  [1,2,4,5,7,8,10,11,13,14,15,16,17]
Removed 15  [1,2,4,5,7,8,10,11,13,14,16,17]
Removed  1  [2,4,5,7,8,10,11,13,14,16,17]
Removed  5  [2,4,7,8,10,11,13,14,16,17]
Removed 10  [2,4,7,8,11,13,14,16,17]
Removed 14  [2,4,7,8,11,13,16,17]
Removed  2  [4,7,8,11,13,16,17]
Removed  8  [4,7,11,13,16,17]
Removed 16  [4,7,11,13,17]
Removed  7  [4,11,13,17]
Removed 17  [4,11,13]
Removed 13  [4,11]
Removed  4  [11]

Last soldier: 11
Last eliminated: 4

Die Ausgabe kann durch das nachfolgende Codefragment erzeugt werden. Sie dürfen hiervon abweichen und eigene Vorstellungen umsetzen:

void main()
{
    Josephus j(17);
    j.SetPassBy(3);

    cout << "Number of soldiers: " << j.Count() << endl;
    cout << "Eliminating: Each " << j.PassBy() << ". soldier";
    cout << endl << endl;

    while (j.Alive() > 1)
    {
        j.EliminateNextSoldier();
        cout << "Removed ";
        cout.width(2);
        cout << j.LastEliminated() << "  " << j  << endl;
    }

    cout << endl;
    cout << "Last soldier: " << j.LastAlive() << endl;
    cout << "Last eliminated: " << j.LastEliminated() << endl;
}

Wie lautet nun die Antwort des Josephus-Problems in seiner historisch überlieferten Version? Es handelt sich dabei – einschließlich Josephus – um 41 Soldaten und es wird jeweils jeder dritte Soldat getötet.

2. Lösung

Quellcode: Siehe auch github.com/peterloos/Cpp_Josephus.git.

Zur Lösung des Problems bieten sich bzgl. des Einsatzes von Datenstrukturen prinzipiell zwei Möglichkeiten an: Entweder der Aufbau einer einfach verketteten Liste, in der jeder Knoten einen Soldaten der Rebellenbande darstellt. Oder aber ein dynamisch allokiertes Array vom Typ bool, das pro Rebell einen Eintrag besitzt. Für beide Varianten stellen wir eine Lösung vor.

2.1. Verkettete Liste

Ordnen Sie n nummerierte Soldaten in einer einfach verketteten Liste an. Wenn Sie den Knoten des letzten Soldaten auf den Knoten des ersten Soldaten zeigen lassen, kommen Sie der Realität sehr nahe! Dann wird, beginnend mit dem ersten Soldaten, jeder m-te Soldat (Knoten) aus der Liste entfernt, wobei der Kreis geschlossen bleibt. Auf diese Weise erkennt man, welche zwei Soldaten als letztes überleben!

Beispiel des Josephus-Problems mit 12 Rebellen und Auszählabstand 3 – Datenstruktur verkettete Liste.

Abbildung 1. Beispiel des Josephus-Problems mit 12 Rebellen und Auszählabstand 3 – Datenstruktur verkettete Liste.


Am Beispiel aus Abbildung 1 können Sie die Arbeitsweise des „Auszählens“ nachverfolgen. 12 Soldaten sind hier in einem Kreis angeordnet. Nacheinander bringt sich jeder dritte um. Soldat 1 stirbt zuerst, danach Soldat 4 usw. Neben den Soldaten steht die jeweilige Nummer in der Eliminationsreihenfolge. Am Schluss bleiben die Soldaten 3 und 8 übrig.

Entwerfen Sie zwei Klassen Josephus und Soldier. Instanzen der Klassen Soldier repräsentieren einen nummerierten Soldaten. Ein Josephus-Objekt verwaltet eine verkettete Liste mit allen Soldier-Objekten und stellt entsprechende Methoden zur Verfügung, um das Auszählen durchzuführen.

01: class Soldier
02: {
03: friend ostream& operator<< (ostream&, const Soldier&);
04: 
05: public:
06:     // c'tor
07:     Soldier (int number);
08: 
09:     // member data
10:     int      m_number;
11:     Soldier* m_next;
12: };

Beispiel 1. Klasse Soldier: Schnittstelle.


01: #include <iostream>
02: using namespace std;
03: #include "Soldier.h"
04: 
05: Soldier::Soldier(int number) : m_number(number), m_next ((Soldier*) 0)
06: {
07: }
08: 
09: ostream& operator<< (ostream& os, const Soldier& s)
10: {
11:     os << s.m_number;
12:     return os;
13: }

Beispiel 2. Klasse Soldier: Implementierung.


01: class Josephus
02: {
03: private:
04:     static const int DefaultPassBy = 10;  // default "decimatio"
05: 
06: private:
07:     // root of soldiers
08:     Soldier*  m_root;      // root of linked list of soldiers
09:     Soldier*  m_current;   // current soldier
10: 
11:     int m_count;           // total number of soldiers
12:     int m_alive;           // number of alive soldiers
13:     int m_lastEliminated;  // last eliminated soldier
14:     int m_passby;          // "decimatio"
15: 
16: public:
17:     // c'tor(s), d'tor
18:     Josephus ();
19:     Josephus (int);
20:     ~Josephus ();
21: 
22:     // getter/setter
23:     int Count () const { return m_count; }
24:     int Alive () const { return m_alive; }
25:     int LastEliminated () { return m_lastEliminated; }
26:     int LastAlive () { return m_current -> m_number; }
27:     int PassBy () { return m_passby; }
28:     void SetPassBy (int passby) { m_passby = passby; }
29: 
30:     // public interface
31:     bool EliminateNextSoldier();
32:     void EliminateAll();
33: 
34: private:
35:     // private helper methods
36:     void CreateLinkedList();
37: 
38:     // operators
39:     friend ostream& operator<< (ostream&, const Josephus&);
40: };

Beispiel 3. Klasse Josephus: Schnittstelle.


001: #include <iostream>
002: using namespace std;
003: #include "Soldier.h"
004: #include "Josephus.h"
005: 
006: // c'tor(s), d'tor
007: Josephus::Josephus()
008:     : m_count(41), m_alive(41), m_lastEliminated(0)
009: {
010:     m_passby = Josephus::DefaultPassBy;
011:     CreateLinkedList();
012: }
013: 
014: Josephus::Josephus(int count)
015:     : m_count(count), m_alive(count), m_lastEliminated(0)
016: {
017:     m_passby = Josephus::DefaultPassBy;
018:     CreateLinkedList();
019: }
020: 
021: Josephus::~Josephus()
022: {
023:     Soldier* soldier = m_root;
024:     
025:     // delete each single element
026:     do 
027:     {
028:         // store current node pointer
029:         Soldier* current = soldier;
030:     
031:         // advance to next node
032:         soldier = soldier -> m_next;
033:     
034:         // delete 'current' node pointer
035:         delete current;
036:     }
037:     while (soldier != m_root);
038: }
039: 
040: // public interface
041: bool Josephus::EliminateNextSoldier()
042: {
043:     // more than one soldier?
044:     if (m_alive == 1)
045:         return false;
046:         
047:     // locate next soldier
048:     for (int i = 0; i < m_passby - 1; i ++)
049:         m_current = m_current -> m_next;
050: 
051:     // remove soldier from list
052:     Soldier* node = m_current -> m_next;
053:     m_current -> m_next = node -> m_next;
054: 
055:     // take care, if root object is removed
056:     if (m_root == node)
057:         m_root = m_root -> m_next;
058: 
059:     m_lastEliminated = node -> m_number;
060:     delete node;
061:     m_alive --;
062: 
063:     return true;
064: }
065: 
066: void Josephus::EliminateAll()
067: {
068:     while (EliminateNextSoldier())
069:         ;
070: }
071: 
072: // private helper methods
073: void Josephus::CreateLinkedList()
074: {
075:     // create first soldier
076:     m_root = new Soldier(1);
077:     m_current = m_root;
078: 
079:     for (int i = 1; i < m_count; i ++)
080:     {
081:         Soldier* s = new Soldier(i + 1);
082: 
083:         // link previous Soldier with current one
084:         m_current -> m_next = s;
085:         m_current = s;
086:     }
087: 
088:     // link last soldier with first one
089:     m_current -> m_next = m_root;
090: }
091: 
092: // output
093: ostream& operator<< (ostream& os, const Josephus& j)
094: {
095:     os << '[';
096:     Soldier* tmp = j.m_root;
097:     do
098:     {
099:         os << *tmp;
100:         if (tmp -> m_next != j.m_root)
101:             os << ',';
102:         tmp = tmp -> m_next;
103:     }
104:     while (tmp != j.m_root);
105:     os << ']';
106:     return os;
107: }

Beispiel 4. Klasse Josephus: Implementierung.


Testrahmen:

void main()
{
    Josephus j(41);
    j.SetPassBy(3);

    cout << "Number of soldiers: " << j.Count() << endl;
    cout << "Eliminating: Each " << j.PassBy() << ". soldier" << endl << endl;

    while (j.Alive() > 1)
    {
        j.EliminateNextSoldier();
        cout << "Removed ";
        cout.width(2);
        cout << j.LastEliminated() << endl;
    }

    cout << endl;
    cout << "Last soldier: " << j.LastAlive() << endl;
}

Ausgabe:

Number of soldiers: 41
Eliminating: Each 3. soldier

Removed  3
Removed  6
Removed  9
Removed 12
Removed 15
Removed 18
Removed 21
Removed 24
Removed 27
Removed 30
Removed 33
Removed 36
Removed 39
Removed  1
Removed  5
Removed 10
Removed 14
Removed 19
Removed 23
Removed 28
Removed 32
Removed 37
Removed 41
Removed  7
Removed 13
Removed 20
Removed 26
Removed 34
Removed 40
Removed  8
Removed 17
Removed 29
Removed 38
Removed 11
Removed 25
Removed  2
Removed 22
Removed  4
Removed 35
Removed 16

Last soldier: 31

Am letzten Testrahmen können Sie die Lösung des Josephus-Problems erkennen: Die beiden Rebellen an Position 31 und 16 haben überlebt.

2.2. Array

In einem Array vom Typ bool können Sie mit den beiden Werten true und false hinterlegen, ob der i.-te Soldat während des Auszählens noch am Leben ist oder nicht. Das Auszählen selbst erfolgt durch geschicktes Traversieren des Arrays, wobei Sie im Wesentlichen nur darauf achten müssen, keine Zugriffsverletzung mit einem unzulässigen Index zu erzeugen. Zur Illustration finden Sie in Abbildung 2 dasselbe Beispiel mit 12 Soldaten wie in Abbildung 1 vor, dieses Mal nur auf der Basis eines Arrays dargestellt. Am Ende bleiben in dem Feld zwei Einträge mit einem true-Wert übrig, es handelt sich wiederum um die Soldaten 3 und 8.

Beispiel des Josephus-Problems mit 12 Rebellen und Auszählabstand 3 – Datenstruktur Array.

Abbildung 2. Beispiel des Josephus-Problems mit 12 Rebellen und Auszählabstand 3 – Datenstruktur Array.


Aus Listing 5 und Listing 6 können Sie das Redesign der Klasse Josephus entnehmen, um auf der Basis eines Arrays das Problem zu lösen:

01: class Josephus
02: {
03: public:
04:     static const int DefaultPassBy = 10;  // default "decimatio"
05: 
06: private:
07:     bool* m_soldiers;       // array of boolean states: alive or not
08:     int m_current;          // current index into array
09:     
10:     int m_count;            // total number of soldiers
11:     int m_alive;            // number of alive soldiers
12:     int m_lastEliminated;   // last eliminated soldier
13:     int m_lastAlive;        // number of surviving soldier
14:     int m_passby;           // "decimatio"
15: 
16: public:
17:     // c'tor(s), d'tor
18:     Josephus ();
19:     Josephus (int);
20:     ~Josephus ();
21:     
22:     // getter/setter
23:     int Count () const { return m_count; }
24:     int Alive () const { return m_alive; }
25:     int LastEliminated () { return m_lastEliminated; }
26:     int LastAlive ();
27:     int PassBy () { return m_passby; }
28:     void SetPassBy (int passby) { m_passby = passby; }
29: 
30:     // public interface
31:     bool EliminateNextSoldier();
32:     void EliminateAll();
33: 
34: private:
35:     // private helper methods
36:     void MoveToNextAliveSoldier();
37:     void NextIndex();
38:     void Init();
39: 
40:     // output
41:     friend ostream& operator<< (ostream&, Josephus&);
42: };

Beispiel 5. Klasse Josephus: Schnittstelle.


001: #include <iostream>
002: using namespace std;
003: #include "Soldier.h"
004: #include "Josephus.h"
005: 
006: // c'tor(s), d'tor
007: Josephus::Josephus() : m_count(41), m_alive(41), m_lastEliminated(0)
008: {
009:     Init();
010: }
011: 
012: Josephus::Josephus(int count) : m_count(count), m_alive(count), m_lastEliminated(0)
013: {
014:     Init();
015: }
016: 
017: void Josephus::Init()
018: {
019:     m_soldiers = new bool[m_count];
020:     for (int i = 0; i < m_count; i ++)
021:         m_soldiers[i] = true;
022: 
023:     m_passby = Josephus::DefaultPassBy;
024:     m_lastAlive = 0;
025:     m_current = 0;
026: }
027: 
028: Josephus::~Josephus()
029: {
030:     delete[] m_soldiers;
031: }
032: 
033: // public interface
034: bool Josephus::EliminateNextSoldier()
035: {
036:     // more than one soldier?
037:     if (m_alive == 1)
038:         return false;
039: 
040:     for (int i = 0; i < m_passby - 1; i ++)
041:     {
042:         MoveToNextAliveSoldier();
043:         NextIndex();  // skip found alive soldier
044:     }
045: 
046:     MoveToNextAliveSoldier();
047: 
048:     // kill 'n'.th soldier
049:     m_soldiers[m_current] = false;
050:     m_alive --;
051:     m_lastEliminated = m_current + 1;
052: 
053:     return true;
054: }
055: 
056: void Josephus::EliminateAll()
057: {
058:     while (EliminateNextSoldier())
059:         ;
060: }
061: 
062: int Josephus::LastAlive ()
063: {
064:     if (m_lastAlive == 0)
065:     {
066:         MoveToNextAliveSoldier();
067:         m_lastAlive = m_current + 1;
068:     }
069: 
070:     return m_lastAlive;
071: }
072: 
073: // private helper methods
074: void Josephus::MoveToNextAliveSoldier()
075: {
076:     while (m_soldiers[m_current] == false)
077:         NextIndex(); // move index to next entry
078: }
079: 
080: void Josephus::NextIndex()
081: {
082:     // move index to next entry
083:     m_current ++;
084:     if (m_current >= m_count)
085:         m_current = 0;
086: }
087: 
088: // output
089: ostream& operator<< (ostream& os, Josephus& j)
090: {
091:     os << '[';
092:     int save = j.m_current;  // save current state of position index
093:     j.m_current = 0;
094: 
095:     int count = 0;
096:     do
097:     {
098:         j.MoveToNextAliveSoldier();
099:         os << (j.m_current + 1);
100: 
101:         count ++;
102:         if (count < j.Alive())
103:             os << ',';
104:         j.NextIndex();
105:     }
106:     while (count < j.Alive());
107: 
108:     os << ']';
109:     j.m_current = save;  // restore current state of position index
110:     return os;
111: }

Beispiel 6. Klasse Josephus: Implementierung.