Josephus Sequenz

Question

Beschreibung: Es stehen Menschen in einem Kreis und warten darauf, ausgeführt zu werden. Das Auszählen beginnt an einem Punkt im Kreis und verläuft in einer festen Richtung um den Kreis herum. In jedem Schritt wird eine bestimmte Anzahl von Personen übersprungen und die nächste Person wird ausgeführt. Die Eliminierung geht um den Kreis herum (der mit der Entfernung der hingerichteten Menschen immer kleiner wird), bis nur noch die letzte Person übrig bleibt, der die Freiheit gegeben ist.

Ich googelte dieses "Josephus-Problem" und der Wikipedia-Treffer gibt mir eine dynamische Programmierlösung: f(n,k)=((f(n-1,k)+k-1) mod n)+1, with f(1,k)=1, aber dies ergibt nur den letzten Überlebenden. Wie kann ich die Reihenfolge der Leute ausführen? Sprich, p (5, 3) = {3,1,5,2,4}.

Gibt es auch eine O(nlogn) Lösung anstelle einer O(nk) eins?

Answer 1

Um die Reihenfolge der ausgeführten Personen und des letzten Überlebenden zu erhalten, müssen Sie nur den gesamten Prozess von Anfang an simulieren. Angesichts der Beschreibung des Verfahrens wäre dies eine recht einfache Aufgabe. Formel, die Sie präsentieren, ist nur eine Abkürzung, um zu überprüfen, wer überleben wird und um schnell eine Antwort zu erhalten.

Beschreibung, wie dies in O tun (n log n) Bereich Baum benutzt ist hier: http://pl.scribd.com/doc/3567390/Rank-Trees

Detailliertere Analyse kann hier gefunden werden: http://www.imt.ro/romjist/Volum12/Number12_1/pdf/02-MCosulschi.pdf

Answer 2

Die Menschen in Array gespeichert werden würden von Größe n. Wenn die Person mit dem Index i jetzt ausgeführt wird, würde die nächste durch (i+k)%m gegeben, wobei m die Anzahl der verbleibenden Personen ist. Nach jeder Iteration würde die Array-Größe um 1 verringert und die verbleibenden Elemente werden entsprechend verschoben.

Input: Menschen [0..n-1], n, k, i (= Index der ersten Person ausgeführt)

Der Pseudo-Code wäre so etwas wie sein:

Print People[i] 

While (n > 1) 
do 
    n = n - 1 
    for j = i to n-1 
    People[j] = People[j+1] 
    i = (i+k) % n 
    print People[i] 
done 

Answer 3

zu stimulieren Das Programm kann eine Struktur verwenden, die den Namen des Spielers und ein Tag enthält, das die Spur behält, wenn der Spieler aktiv ist oder nicht. Jedesmal, wenn du in einer neuen Runde eine bestimmte Anzahl von Spielern überspringst, benutze eine Schleife und eine bedingte Anweisung, so dass alle Spieler, die nicht im Spiel sind, ignoriert werden und nur diejenigen im Spiel gezählt werden. Und natürlich fügen Sie printf-Anweisungen hinzu, um den aktuellen Status zu drucken.

Answer 4

Die natürlichste Datenstruktur zur Darstellung der Personen ist ein Ringpuffer. Meine Lösung erstellt eine verkettete Liste, bindet das Ende der Liste zurück an den Kopf, zählt dann wiederholt den Puffer zu der nächsten auszuführenden Person, entfernt diese Person aus dem Puffer und fährt fort, bis das Ende des Puffers auf sich selbst zeigt .

(define (cycle xs) 
    (set-cdr! (last-pair xs) xs) xs) 

(define (josephus n m) 
    (let loop ((k (- m 1)) (alive (cycle (range 0 n))) (dead '())) 
    (cond ((= (car alive) (cadr alive)) 
      (reverse (cons (car alive) dead))) 
      ((= k 1) 
      (let ((dead (cons (cadr alive) dead))) 
       (set-cdr! alive (cddr alive)) 
       (loop (- m 1) (cdr alive) dead))) 

Zum Beispiel:

> (josephus 41 3) 
(2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 
40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15 30) 

Sie können eine ausführlichere Erklärung bei my blog, lesen die drei verschiedene Lösungen gibt. Oder Sie können das Programm unter http://programmingpraxis.codepad.org/RMwrace2 ausführen.

Answer 5

Um diese Frage der Ausgabesequenz zu beantworten, ist eine Simulation erforderlich. Dies bedeutet O (nk) -Komplexität.Es ist unmöglich, die Ausführungsreihenfolge zu erhalten (das ist O (n)), während gleichzeitig die O (nlogn) -Zeitkomplexität gesucht wird. Weil Sie jede auszuführende Person ausgeben müssen, also O (n).

kkonrad Referenz Trees: Range einen schönen O (n log n) -Lösung ergeben. Wie andere bereits festgestellt haben, ist eine zirkulär verknüpfte Liste eine effiziente Datenstruktur für dieses Problem. Ich finde 200_success 'Java Lösung von Code Review sehr elegant und lesbar.

public class CircularGunmenIterator<T> implements Iterator<T> { 

    private List<T> list; 
    private Iterator<T> iter; 

    public CircularGunmenIterator(List<T> list) { 
    this.list = list; 
    this.iter = list.iterator(); 
    } 

    @Override 
    public boolean hasNext() { 
    // Continue as long as there is a shooter and a victim 
    return this.list.size() >= 2; 
    } 

    @Override 
    public T next() { 
    if (!this.iter.hasNext()) { 
     // Wrap around, creating the illusion of a circular buffer 
     this.iter = this.list.iterator(); 
    } 
    return this.iter.next(); 
    } 

    @Override 
    public void remove() { 
    this.iter.remove(); 
    } 

    public static void main(String[] args) { 
    // Create the gunmen 
    List<Integer> gunmen = new LinkedList<Integer>(); 
    for (int i = 1; i <= 100; i++) { 
     gunmen.add(i); 
    } 

    // Shootout! 
    Iterator<Integer> ringIter = new CircularGunmenIterator<Integer>(gunmen); 
    while (ringIter.hasNext()) { 
     Integer shooter = ringIter.next(); 
     Integer victim = ringIter.next(); 
     System.out.printf("%2d shoots %2d\n", shooter, victim); 
     ringIter.remove(); // Bang! 
    } 
    System.out.println("Last one alive: " + gunmen.get(0)); 
    } 
} 

Es gibt einige weitere Details auf Wikipedia für dieses Josephus-Problem (k = 2).

http://en.wikipedia.org/wiki/Josephus_problem