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 MSN und W3Schools.

Eingabe:

6
14 2
15 2
16 2
17 2
50 7
100 13

Ausgabe:

Case #0: 12
Case #1: 14
Case #2: 0
Case #3: 2
Case #4: 45
Case #5: 58

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?

let n = 42;
arr = [];  // leeres Array
for (let i=0; i<n; i++) {
  arr.push(i);  // Element hinten hinzufügen
}

let n = 42;
arr = new Array(n).fill(null).map((element, index)=>index);

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]

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-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.

Doppelt verkettete Liste.

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

Implementation: 2 Arrays.

Formel zur direkten Berechnung heraustüfteln und anwenden.