lehrkraefte:blc:informatik:ffprg2-2024:josephus-problem [https://fginfo.ksbg.ch Fachgruppe Informatik der KSBG]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Wiederholtes Abzählen ======
$n$ Personen stehen im Kreis und sind von $0$ bis $n-1$ der Reihe nach durchnummeriert.
Die Person mit der Zahl 0 beginnt und schickt die Person, die neben ihr steht (d.h. die Person mit der Nummer 1) aus dem Kreis.

Dann wird eine Person weitergegangen (also zur Nummer 2) und diese schickt die nächste Person (also Nummer 3) aus dem Kreis.

Dieser Prozess wird so lange wiederholt, bis nur noch eine Person übrig bleibt. Welche?

Der oben beschriebene Prozess wird mit $s=2$ beschrieben (Abstand zwischen zwei eliminierten Personen).

JavaScript Hinweis: Mit der Array-Methode ''splice'' können Elemente aus einem Array entfernt werden. Siehe [[https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/splice|MSN]] und [[https://www.w3schools.com/jsref/jsref_splice.asp|W3Schools]].

Eingabe:
<code text>
6
14 2
15 2
16 2
17 2
50 7
100 13
</code>

Ausgabe:
<code text>
Case #0: 12
Case #1: 14
Case #2: 0
Case #3: 2
Case #4: 45
Case #5: 58
</code>



===== Fall $s=2$ =====
Generieren Sie den Text für den Input für alle $n$ von 0 bis 130 für $s=2$.
Berechnen Sie die Lösungen. Finden Sie eine Gesetzmässigkeit?


===== Nützliches JavaScript =====
==== Array befüllen ====
=== Klassisch ===
<code javascript>
let n = 42;
arr = [];  // leeres Array
for (let i=0; i<n; i++) {
  arr.push(i);  // Element hinten hinzufügen
}
</code>
=== Mit Arrayfunktionen fill und map ===
<code javascript>
let n = 42;
arr = new Array(n).fill(null).map((element, index)=>index);
</code>

==== length und splice ====
<code javascript>
arr = [1,1,2,3,5,8];
console.log(arr.length);  // liefert 6 
arr.splice(4,1); // 1 Element an Position 4 löschen
console.log(arr);  // liefert [1, 1, 2, 3, 8]
</code>

===== Mögliche Lösungsansätze =====
==== Array mit Einträgen von 0 bis n-1 ====
Dank ''splice'' eine einfache Implementation. 

Aber jedesmal ein neues Array «zu bauen» ist speicher- und rechenintensiv. Langsam für grosse Arrays (Aufwand proportional zur Grösse vom Array).
==== Array mit true / false ====
Array-Länge bleibt fix, zuerst alle Einträge ''true'', eliminierte Positionen werden mit ''false'' markiert.

Nachteil: Sind schon viele Personen eliminiert, muss das Array lange nach dem/den nächsten Einträgen durchsucht werden.

==== Effizienter für kleine s ====
Doppelt verkettete Liste.

Idee: für jede Person Vorgänger und Nachfolger speichern. Beim Eliminieren updaten.

Implementation: 2 Arrays.
==== Noch viel effizienter ====
Formel zur direkten Berechnung heraustüfteln und anwenden.