Das Josephus-Problem

1. Aufgabe

Schreiben Sie ein C#-Programm, das mit elementaren Sprachmitteln der Programmiersprache C# eine Lösung des Josephus-Problems ermittelt. Eine ausführliche Beschreibung des Josephus-Problems finden Sie hier vor. Für bestimmte Eigenschaften des Problems, wie zum Beispiel die Gesamtanzahl der Rebellen zu Beginn des Widerstands oder aber der Abstand zweier Rebellen im Kreis, der bei einer bestimmten Decimatio angewendet wurde, bieten sich Eigenschaften / Properties (etwa Count, PassBy) an. Das Ritual selbst kann durch eine oder mehrere Methoden nachgestellt werden, wie etwa EliminateNextSoldier oder auch EliminateAll. Das Endergebnis des Rituals wiederum kann in Eigenschaften des Simulationsobjekts abgelegt werden, zum Beispiel LastAlive und auch LastEliminated.

2. Lösung

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

Zur Vertiefung bzw. Wiederholung elementarer programmiersprachlicher C#-Konstrukte stellen wir auf Basis des objekt-orientierten Entwurfs zunächst eine Schnittstelle IJosephus vor. Dazu können wir eine unvollständige Realisierung in Gestalt einer Klasse Josephus anbieten, die ihrerseits als Basis zweier konkreter Klassen JosephusArrayImpl und JosephusLinkedListImpl fungiert. Beginnen wir in Listing 1 mit der Schnittstelle IJosephus:

01: interface IJosephus
02: {
03:     // properties
04:     int Count { get; }           // total number of soldiers
05:     int Alive { get; }           // number of alive soldiers
06:     int LastEliminated { get; }  // last eliminated soldier
07:     int LastAlive { get; }       // number of surviving soldier
08:     int PassBy { get; set; }     // "decimatio"
09: 
10:     // methods
11:     bool EliminateNextSoldier();
12:     void EliminateAll();
13: }

Beispiel 1. Schnittstelle IJosephus.


Weiter geht es in Listing 2 mit einer abstrakten Basisklasse Josephus. Die zahlreichen Eigenschaften der IJosephus-Schnittstelle lassen sich hier zentral zusammenfassen:

01: abstract class Josephus : IJosephus
02: {
03:     protected const int DefaultPassBy = 10;  // default "decimatio"
04: 
05:     protected int count;            // total number of soldiers
06:     protected int alive;            // number of alive soldiers
07:     protected int lastEliminated;   // last eliminated soldier
08:     protected int lastAlive;        // number of surviving soldier
09:     protected int passby;           // "decimatio"
10: 
11:     // c'tor
12:     public Josephus (int count)
13:     {
14:         this.count = count;
15:         this.alive = this.count;
16:         this.lastEliminated = 0;
17:         this.lastAlive = 0;
18:         this.passby = DefaultPassBy;
19:     }
20: 
21:     // properties
22:     public int Count
23:     {
24:         get
25:         {
26:             return this.count;
27:         }
28:     }
29: 
30:     public int Alive
31:     {
32:         get
33:         {
34:             return this.alive;
35:         }
36:     }
37: 
38:     public int LastEliminated
39:     {
40:         get
41:         {
42:             return this.lastEliminated;
43:         }
44:     }
45: 
46:     public int PassBy
47:     {
48:         get
49:         {
50:             return this.passby;
51:         }
52: 
53:         set
54:         {
55:             this.passby = value;
56:         }
57:     }
58: 
59:     public abstract int LastAlive { get; }
60: 
61:     // methods
62:     abstract public bool EliminateNextSoldier();
63: 
64:     public void EliminateAll()
65:     {
66:         while (this.EliminateNextSoldier())
67:             ;
68:     }
69: }

Beispiel 2. Abstrakte Basisklasse Josephus.


Mit Hilfe eines eindimensionalen Felds (vom Typ bool) kann eine einfache Realisierung der Methode EliminateNextSoldier erfolgen (Listing 3):

001: class JosephusArrayImpl : Josephus
002: {
003:     private bool[] soldiers;   // root of soldiers
004:     private int current;       // current soldier
005: 
006:     // c'tors
007:     public JosephusArrayImpl() : this(41)
008:     {
009:         this.alive = this.count;
010:     }
011: 
012:     public JosephusArrayImpl(int count) : base (count)
013:     {
014:         this.soldiers = new bool[count];
015:         for (int i = 0; i < count; i++)
016:             soldiers[i] = true;
017: 
018:         this.current = 0;
019:     }
020: 
021:     // properties
022:     public override int LastAlive
023:     {
024:         get
025:         {
026:             if (this.lastAlive == 0)
027:             {
028:                 this.MoveToNextAliveSoldier();
029:                 this.lastAlive = this.current + 1;
030:             }
031: 
032:             return this.lastAlive;
033:         }
034:     }
035: 
036:     // public interface
037:     public override bool EliminateNextSoldier()
038:     {
039:         // more than one soldier?
040:         if (this.alive == 1)
041:             return false;
042: 
043:         for (int i = 0; i < this.passby - 1; i++)
044:         {
045:             this.MoveToNextAliveSoldier();
046: 
047:             // skip found alive soldier
048:             this.MoveToNext();
049:         }
050: 
051:         this.MoveToNextAliveSoldier();
052: 
053:         // eliminate 'n'.th soldier
054:         this.soldiers[this.current] = false;
055:         this.alive--;
056:         this.lastEliminated = this.current + 1;
057: 
058:         return true;
059:     }
060: 
061:     // overrides
062:     public override String ToString()
063:     {
064:         String s = "[";
065: 
066:         int save = this.current;  // save current state of position index
067:         this.current = 0;
068: 
069:         int count = 0;
070:         do
071:         {
072:             this.MoveToNextAliveSoldier();
073:             s += String.Format("{0}", this.current + 1);
074: 
075:             count++;
076:             if (count < this.Alive)
077:                 s += String.Format (",");
078:             this.MoveToNext();
079:         }
080:         while (count < this.Alive);
081:         s += ']';
082: 
083:         this.current = save;  // restore current state of position index
084: 
085:         return s;
086:     }
087: 
088:     // private helper methods
089:     private void MoveToNextAliveSoldier()
090:     {
091:         while (this.soldiers[current] == false)
092:         {
093:             // move index to next entry
094:             this.MoveToNext();
095:         }
096:     }
097: 
098:     private void MoveToNext()
099:     {
100:         // move index to next entry
101:         this.current++;
102:         if (this.current >= this.count)
103:             this.current = 0;
104:     }
105: }

Beispiel 3. Klasse JosephusArrayImpl.


Eine alternative Lösung des Josephus-Problems ist mit verketteten Listen möglich. Dazu bedarf es allerdings einer Hilfsklasse Soldier (Listing 4), die in der verketteten Liste ein einzelnes Listenelement darstellt:

01: using System;
02: 
03: class Soldier
04: {
05:     private int number;
06: 
07:     // c'tor
08:     public Soldier(int number)
09:     {
10:         this.number = number;
11:         this.Next = null;
12:     }
13: 
14:     // properties
15:     public Soldier Next { get; set; }
16: 
17:     public int Number
18:     {
19:         get
20:         {
21:             return this.number;
22:         }
23:     }
24: }

Beispiel 4. Klasse Soldier.


Auf Basis der Klasse Soldier in Listing 4 und einer verketteten Liste lässt sich der letzte überlebende Soldat nun wie folgt ermitteln (Listing 5):

01: using System;
02: 
03: class JosephusLinkedListImpl : Josephus
04: {
05:     private Soldier root;      // root of soldiers
06:     private Soldier current;   // current soldier
07: 
08:     // c'tors
09:     public JosephusLinkedListImpl() : this(41) {}
10: 
11:     public JosephusLinkedListImpl(int count) : base (count)
12:     {
13:         this.CreateList();
14:     }
15: 
16:     // properties
17:     public override int LastAlive
18:     {
19:         get
20:         {
21:             return this.root.Number;
22:         }
23:     }
24: 
25:     // public interface
26:     public override bool EliminateNextSoldier()
27:     {
28:         // more than one soldier?
29:         if (this.alive == 1)
30:             return false;
31: 
32:         // locate soldier
33:         for (int i = 0; i < this.passby - 1; i++)
34:             this.current = this.current.Next;
35: 
36:         // remove soldier from list
37:         Soldier node = this.current.Next;
38:         this.current.Next = node.Next;
39: 
40:         // take care, if root object is removed
41:         if (this.root == node)
42:             this.root = this.root.Next;
43: 
44:         this.alive --;
45:         this.lastEliminated = node.Number;
46: 
47:         return true;
48:     }
49: 
50:     // overrides
51:     public override String ToString()
52:     {
53:         String s = "[";
54:         Soldier tmp = root;
55: 
56:         do
57:         {
58:             s += String.Format("{0}", tmp.Number);
59:             if (tmp.Next != root)
60:                 s += ",";
61:             tmp = tmp.Next;
62:         }
63:         while (tmp != root);
64:         s += "]";
65: 
66:         return s;
67:     }
68: 
69:     // private helper methods
70:     private void CreateList()
71:     {
72:         // create first soldier
73:         this.root = new Soldier(1);
74:         Soldier tmp = this.root;
75: 
76:         // create remaining soldiers
77:         for (int i = 1; i < count; i++)
78:         {
79:             Soldier s = new Soldier(i + 1);
80: 
81:             // link previous soldier with current one
82:             tmp.Next = s;
83:             tmp = s;
84:         }
85: 
86:         // link last soldier with first one
87:         tmp.Next = this.root;
88: 
89:         // initialize enumeration reference
90:         this.current = tmp;
91:     }
92: }

Beispiel 5. Klasse JosephusLinkedListImpl.


Mit folgendem Testrahmen kommen wir nun dem Rätsel auf die Spur, an welche Stelle im Kreis sich Josephus gestellt hat:

public static void JosephusSolver()
{
    IJosephus j = new JosephusArrayImpl(41);
    j.PassBy = 3;

    Console.WriteLine("Josephus Problem: Number of soldiers: {0}", j.Count);
    Console.WriteLine("Eliminating: Each {0}", j.PassBy);
    Console.WriteLine();

    while (j.Alive > 1)
    {
        j.EliminateNextSoldier();
        Console.WriteLine("Removed {0,2}", j.LastEliminated);
    }

    Console.WriteLine();
    Console.WriteLine("Last soldier: {0}", j.LastAlive);
    Console.WriteLine("Last eliminated: {0}", j.LastEliminated);
}

Ausgabe des Programms:

Josephus Problem: Number of soldiers: 41
Eliminating: Each 3

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
Last eliminated: 16

Der Legende nach stellte Josephus sich an die 16. Stelle und blieb damit als Vorletzter übrig. Er konnte auf diese Weise den letzten, schwächeren Mann an der 31. Position überwältigen. Beide ergaben sich den Römern und konnten auf diese Weise ihr Leben retten.