Differences

This shows you the differences between two versions of the page.

--- lehrkraefte:blc:informatik:ffprg2-2024:josephus-problem [2024/08/07 18:52] – Ivo Blöchliger
+++ lehrkraefte:blc:informatik:ffprg2-2024:josephus-problem [2024/08/12 13:07] (current) – [Array befüllen] Ivo Blöchliger
@@ Line 1: / Line 1: @@
+====== 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>
+2
+2
+2
+2
+7
+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.