www.wikidata.de-de.nina.az

Josephus Problem Das oder die Josephus Permutation ist ein theoretisches Problem aus der Informatik oder Mathematik Komb

Josephus-Problem

Das Josephus-Problem oder die Josephus-Permutation ist ein theoretisches Problem aus der Informatik oder Mathematik (Kombinatorik).

Es werden nummerierte Objekte im Kreis angeordnet; dann wird, beginnend mit der Nummer , jedes -te Objekt entfernt, wobei der Kreis immer wieder geschlossen wird. Die Reihenfolge der entfernten Objekte wird als Josephus-Permutation bezeichnet.

Ziel dieses Problems ist es, bei gegebenem und das letzte Objekt der Permutation zu bestimmen.

Geschichte Bearbeiten

Das Problem wurde nach dem jüdischen Historiker Flavius Josephus benannt, welcher sich 67 n. Chr. beim Kampf um die galiläische Stadt Jotapata mit 40 weiteren Männern in einer Höhle vor den Römern versteckt hielt (insgesamt also 41 Personen). Er berichtet darüber in seinem Buch Jüdischer Krieg (Buch 3, Kapitel 8). Als das Versteck verraten wurde, forderten die Römer sie auf, sich in Gefangenschaft zu ergeben. Seine Gefolgsleute zogen allerdings vor, durch kollektiven Suizid zu sterben, wobei das Los über die Reihenfolge entschied. Durch Glück waren Josephus und ein weiterer Mann die Letzten und ergaben sich. Später wurde daraus eine Denksportaufgabe gemacht, in dem sich alle im Kreis aufstellen und jeder 3. durch seinen rechten Nachbarn getötet werden sollte. Josephus stellte sich in diesem Spezialfall an die 16. Stelle, blieb damit als Vorletzter übrig und überwältigte den schwächeren Mann an der 31. Position. Beide ergaben sich den Römern und überlebten.

Nach Wilhelm Ahrens hat Gerolamo Cardano in seinem Werk Practica arithmeticae (1539) den Problemtyp Josephsspiel (Ludus Josephi) genannt, er war aber älter. Nach Moritz Cantor findet es sich in der Handschrift von Nicolas Chuquet La triparty en la science des nombres (Lyon 1484). Das Problem wird auch von Claude Gaspard Bachet de Méziriac (Problèmes plaisans et delectables, 1612) behandelt, der auch eine Variante angibt: 15 Türken und 15 Christen sind auf einem Schiff im Sturm. Der Kapitän muss 15 von ihnen opfern damit das Schiff nicht sinkt und lässt sie in einer Reihe aufstellen, wobei jeder neunte geopfert wird.

Lösung Bearbeiten

Das Problem wird hier gelöst für den Fall, dass jedes 2. Element entfernt wird (). Für den allgemeinen Fall folgt eine Lösung unten. Die Lösung wird mittels Rekursion hergeleitet. bezeichne das letzte Element der Permutation, wenn anfangs Elemente vorhanden waren (mit ). Im ersten Durchlauf werden alle geradzahligen Elemente entfernt. In der zweiten Runde werden die Elemente entfernt, die an der neuen 2., 4. usw. Position stehen, so als hätte es keine erste Runde gegeben. Wenn die Anfangsanzahl von Elementen gerade ist, dann war das Element aus der zweiten Runde in der ersten Runde an Position . Das Element war ursprünglich auf Position . Das ergibt folgende Rekursionsformel:

Wenn die Elementanzahl anfangs ungerade ist, dann wird in der zweiten Runde das ursprünglich erste Element entfernt, aber auch hier wird dann das neue 2., 4. usw. Element entfernt. In diesem Fall ergibt sich, dass Element in der ersten Runde an Position war. Daraus folgt die Rekursionsformel:

Wenn man die Werte für und tabellarisch darstellt, sieht man ein Muster:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1

Diese Tabelle lässt vermuten, dass eine aufsteigende Folge ungerader Zahlen ist, welche wieder mit startet, wenn der Index eine Zweierpotenz ist. Wenn man und so wählt, dass und , dann folgt . Es ist offensichtlich, dass die Werte aus der Tabelle diese Gleichung erfüllen. Nachfolgend erfolgt der Beweis durch vollständige Induktion.

Behauptung: Wenn und , dann folgt .

Beweis: Vollständige Induktion über . Der Fall ist wahr. Man betrachte die Fälle für gerades und ungerades getrennt.

Wenn gerade, dann wähle man und so, dass und . Es gilt . Wir haben , bei der die zweite Gleichung aus der Induktionsannahme folgt.

Wenn ungerade, dann wähle man und so, dass and . Es gilt . Wir haben , bei der die zweite Gleichung ebenfalls aus der Induktionsannahme folgt. Damit ist die Behauptung bewiesen.

Die eleganteste Form der Lösung folgt aus der binären Repräsentation von : kann durch eine 1-Bit-Linksrotation von selbst ermittelt werden. Wenn man binär als repräsentiert, dann ist die Lösung gegeben als . Der Beweis folgt aus der Repräsentation von als .

In geschlossener Form lautet die Lösung für den Fall :

mit der Gaußklammer (Abrundungsfunktion)

Es gibt auch eine Lösung in geschlossener Form für den Fall .

Die dynamische Programmierung ist der einfachste Weg, dieses Problem für den allgemeinen Fall zu lösen.

Diese Methode verwendet die Rekursionsformel:

welche offensichtlich ist, wenn man berücksichtigt, wie sich die Nummer des letzten Elements ändert, wenn man von nach wechselt. Diese Methode hat eine Laufzeit von , aber für kleine und große gibt es einen anderen Ansatz. Dieser zweite Ansatz verwendet auch die dynamische Programmierung, erfordert aber nur eine Laufzeit von . Er entfernt die k., 2k., …, . Elemente in einem Schritt und ändert dann die Nummerierung.

Implementierung Bearbeiten

Der folgende Algorithmus realisiert das Problem rekursiv nach der obigen Rekursionsformel für den Fall k=2 und besitzt eine Laufzeit von O(log(n)). 

int josephus(int n) { if(n == 1) return 1; if((n%2) == 0) return 2 * josephus(n / 2) - 1; if((n%2) == 1) return 2 * josephus((n - 1) / 2) + 1; }

Gemäß der geschlossenen Formel f(n)=2*l + 1 lässt sich der folgende nicht-rekursive Algorithmus angeben. Seine Laufzeit liegt in O(1). 

int josephus(int n) { m = floor( log2(n) ); l = n - 2^m; j = 2*l + 1; return j; }

Literatur Bearbeiten

Weblinks Bearbeiten

Einzelnachweise Bearbeiten

  1. Ahrens, Mathematische Unterhaltungen und Spiele, Teubner 1901, Kapitel 15, S. 286ff
  2. Moritz Cantor, Vorlesungen über die Geschichte der Mathematik, Band 2, S. 332
  3. Josephus problem, Mathworld
  4. Lorenz Halbeisen, Norbert Hungerbühler: The Josephus Problem, J. Théor. Nombres Bordeaux, Band 9, 1976, S. 303–318
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Das Josephus Problem oder die Josephus Permutation ist ein theoretisches Problem aus der Informatik oder Mathematik Kombinatorik Es werden n displaystyle n nummerierte Objekte im Kreis angeordnet dann wird beginnend mit der Nummer k displaystyle k jedes k displaystyle k te Objekt entfernt wobei der Kreis immer wieder geschlossen wird Die Reihenfolge der entfernten Objekte wird als Josephus Permutation bezeichnet Ziel dieses Problems ist es bei gegebenem n displaystyle n und k displaystyle k das letzte Objekt der Permutation zu bestimmen Inhaltsverzeichnis 1 Geschichte 2 Losung 3 Implementierung 4 Literatur 5 Weblinks 6 EinzelnachweiseGeschichte BearbeitenDas Problem wurde nach dem judischen Historiker Flavius Josephus benannt welcher sich 67 n Chr beim Kampf um die galilaische Stadt Jotapata mit 40 weiteren Mannern in einer Hohle vor den Romern versteckt hielt insgesamt also 41 Personen Er berichtet daruber in seinem Buch Judischer Krieg Buch 3 Kapitel 8 Als das Versteck verraten wurde forderten die Romer sie auf sich in Gefangenschaft zu ergeben Seine Gefolgsleute zogen allerdings vor durch kollektiven Suizid zu sterben wobei das Los uber die Reihenfolge entschied Durch Gluck waren Josephus und ein weiterer Mann die Letzten und ergaben sich Spater wurde daraus eine Denksportaufgabe gemacht in dem sich alle im Kreis aufstellen und jeder 3 durch seinen rechten Nachbarn getotet werden sollte Josephus stellte sich in diesem Spezialfall an die 16 Stelle blieb damit als Vorletzter ubrig und uberwaltigte den schwacheren Mann an der 31 Position Beide ergaben sich den Romern und uberlebten Nach Wilhelm Ahrens 1 hat Gerolamo Cardano in seinem Werk Practica arithmeticae 1539 den Problemtyp Josephsspiel Ludus Josephi genannt er war aber alter Nach Moritz Cantor 2 findet es sich in der Handschrift von Nicolas Chuquet La triparty en la science des nombres Lyon 1484 Das Problem wird auch von Claude Gaspard Bachet de Meziriac Problemes plaisans et delectables 1612 behandelt der auch eine Variante angibt 15 Turken und 15 Christen sind auf einem Schiff im Sturm Der Kapitan muss 15 von ihnen opfern damit das Schiff nicht sinkt und lasst sie in einer Reihe aufstellen wobei jeder neunte geopfert wird Losung BearbeitenDas Problem wird hier gelost fur den Fall dass jedes 2 Element entfernt wird k 2 displaystyle k 2 nbsp Fur den allgemeinen Fall k 2 displaystyle k neq 2 nbsp folgt eine Losung unten Die Losung wird mittels Rekursion hergeleitet f n displaystyle f n nbsp bezeichne das letzte Element der Permutation wenn anfangs n displaystyle n nbsp Elemente vorhanden waren mit k 2 displaystyle k 2 nbsp Im ersten Durchlauf werden alle geradzahligen Elemente entfernt In der zweiten Runde werden die Elemente entfernt die an der neuen 2 4 usw Position stehen so als hatte es keine erste Runde gegeben Wenn die Anfangsanzahl von Elementen gerade ist dann war das Element x displaystyle x nbsp aus der zweiten Runde in der ersten Runde an Position 2 x 1 displaystyle 2x 1 nbsp Das Element f 2 n displaystyle f 2n nbsp war ursprunglich auf Position 2 f n 1 displaystyle 2f n 1 nbsp Das ergibt folgende Rekursionsformel f 2 n 2 f n 1 displaystyle f 2n 2f n 1 nbsp Wenn die Elementanzahl anfangs ungerade ist dann wird in der zweiten Runde das ursprunglich erste Element entfernt aber auch hier wird dann das neue 2 4 usw Element entfernt In diesem Fall ergibt sich dass Element x displaystyle x nbsp in der ersten Runde an Position 2 x 1 displaystyle 2x 1 nbsp war Daraus folgt die Rekursionsformel f 2 n 1 2 f n 1 displaystyle f 2n 1 2f n 1 nbsp Wenn man die Werte fur n displaystyle n nbsp und f n displaystyle f n nbsp tabellarisch darstellt sieht man ein Muster n displaystyle n nbsp 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16f n displaystyle f n nbsp 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1Diese Tabelle lasst vermuten dass f n displaystyle f n nbsp eine aufsteigende Folge ungerader Zahlen ist welche wieder mit f n 1 displaystyle f n 1 nbsp startet wenn der Index n displaystyle n nbsp eine Zweierpotenz ist Wenn man m displaystyle m nbsp und l displaystyle l nbsp so wahlt dass n 2 m l displaystyle n 2 m l nbsp und 0 l lt 2 m displaystyle 0 leq l lt 2 m nbsp dann folgt f n 2 l 1 displaystyle f n 2 cdot l 1 nbsp Es ist offensichtlich dass die Werte aus der Tabelle diese Gleichung erfullen Nachfolgend erfolgt der Beweis durch vollstandige Induktion Behauptung Wenn n 2 m l displaystyle n 2 m l nbsp und 0 l lt 2 m displaystyle 0 leq l lt 2 m nbsp dann folgt f n 2 l 1 displaystyle f n 2l 1 nbsp Beweis Vollstandige Induktion uber n displaystyle n nbsp Der Fall n 1 displaystyle n 1 nbsp ist wahr Man betrachte die Falle fur gerades n displaystyle n nbsp und ungerades n displaystyle n nbsp getrennt Wenn n displaystyle n nbsp gerade dann wahle man l 1 displaystyle l 1 nbsp und m 1 displaystyle m 1 nbsp so dass n 2 2 m 1 l 1 displaystyle n 2 2 m 1 l 1 nbsp und 0 l 1 lt 2 m 1 displaystyle 0 leq l 1 lt 2 m 1 nbsp Es gilt l 1 l 2 displaystyle l 1 l 2 nbsp Wir haben f n 2 f n 2 1 2 2 l 1 1 1 2 l 1 displaystyle f n 2f n 2 1 2 2l 1 1 1 2l 1 nbsp bei der die zweite Gleichung aus der Induktionsannahme folgt Wenn n displaystyle n nbsp ungerade dann wahle man l 1 displaystyle l 1 nbsp und m 1 displaystyle m 1 nbsp so dass n 1 2 2 m 1 l 1 displaystyle n 1 2 2 m 1 l 1 nbsp and 0 l 1 lt 2 m 1 displaystyle 0 leq l 1 lt 2 m 1 nbsp Es gilt l 1 l 1 2 displaystyle l 1 l 1 2 nbsp Wir haben f n 2 f n 1 2 1 2 2 l 1 1 1 2 l 1 displaystyle f n 2f n 1 2 1 2 2l 1 1 1 2l 1 nbsp bei der die zweite Gleichung ebenfalls aus der Induktionsannahme folgt Damit ist die Behauptung bewiesen Die eleganteste Form der Losung folgt aus der binaren Reprasentation von n displaystyle n nbsp f n displaystyle f n nbsp kann durch eine 1 Bit Linksrotation von n displaystyle n nbsp selbst ermittelt werden Wenn man n displaystyle n nbsp binar als n b 0 b 1 b 2 b 3 b m displaystyle n b 0 b 1 b 2 b 3 dots b m nbsp reprasentiert dann ist die Losung gegeben als f n b 1 b 2 b 3 b m b 0 displaystyle f n b 1 b 2 b 3 dots b m b 0 nbsp Der Beweis folgt aus der Reprasentation von n displaystyle n nbsp als 2 m l displaystyle 2 m l nbsp In geschlossener Form lautet die Losung fur den Fall k 2 displaystyle k 2 nbsp 3 f n 1 2 n 2 1 log 2 n displaystyle f n 1 2n 2 1 lfloor log 2 n rfloor nbsp mit der Gaussklammer Abrundungsfunktion displaystyle lfloor dots rfloor nbsp Es gibt auch eine Losung in geschlossener Form fur den Fall k 3 displaystyle k 3 nbsp 4 Die dynamische Programmierung ist der einfachste Weg dieses Problem fur den allgemeinen Fall zu losen Diese Methode verwendet die Rekursionsformel f n k f n 1 k k 1 mod n 1 displaystyle f n k f n 1 k k 1 bmod n 1 nbsp mit f 1 k 1 displaystyle f 1 k 1 nbsp welche offensichtlich ist wenn man berucksichtigt wie sich die Nummer des letzten Elements andert wenn man von n 1 displaystyle n 1 nbsp nach n displaystyle n nbsp wechselt Diese Methode hat eine Laufzeit von O n displaystyle O n nbsp aber fur kleine k displaystyle k nbsp und grosse n displaystyle n nbsp gibt es einen anderen Ansatz Dieser zweite Ansatz verwendet auch die dynamische Programmierung erfordert aber nur eine Laufzeit von O k log n displaystyle O k log n nbsp Er entfernt die k 2k n k displaystyle lfloor n k rfloor nbsp Elemente in einem Schritt und andert dann die Nummerierung Implementierung BearbeitenDer folgende Algorithmus realisiert das Problem rekursiv nach der obigen Rekursionsformel fur den Fall k 2 und besitzt eine Laufzeit von O log n int josephus int n if n 1 return 1 if n 2 0 return 2 josephus n 2 1 if n 2 1 return 2 josephus n 1 2 1 Gemass der geschlossenen Formel f n 2 l 1 lasst sich der folgende nicht rekursive Algorithmus angeben Seine Laufzeit liegt in O 1 int josephus int n m floor log2 n l n 2 m j 2 l 1 return j Literatur BearbeitenPaul Yiu Recreational Mathematics Florida Atlantic University Department of Mathematics Als PDF in englischer Sprache verfugbar 868 kB Walter William Rouse Ball Harold Scott Macdonald Coxeter Mathematical Recreations and Essays Dover 1987 Seiten 32 36 ISBN 0 486 25357 0 Ronald L Graham Donald E Knuth und Oren Patashnik Concrete Mathematics A Foundation for Computer Science Massachusetts 1994 Seiten 8 16 ISBN 978 0 201 55802 9 James Dowdy Michael E Mays Josephus Permutations Journal of Combinatorial Mathematics and Combinatorial Computing Band 6 1989 S 125 130Weblinks BearbeitenLorenz J Halbeisen The Josephus Problem Abgerufen im 1 Januar 1 Josephus Flavius game bei Cut the knotEinzelnachweise Bearbeiten Ahrens Mathematische Unterhaltungen und Spiele Teubner 1901 Kapitel 15 S 286ff Moritz Cantor Vorlesungen uber die Geschichte der Mathematik Band 2 S 332 Josephus problem Mathworld Lorenz Halbeisen Norbert Hungerbuhler The Josephus Problem J Theor Nombres Bordeaux Band 9 1976 S 303 318 Abgerufen von https de wikipedia org w index php title Josephus Problem amp oldid 238445264