sequenza Josephus

Question

Descrizione: Ci sono persone in piedi in un cerchio che aspettano di essere giustiziate. Il conteggio inizia in un punto del cerchio e procede intorno al cerchio in una direzione fissa. In ogni fase, un certo numero di persone viene saltato e viene eseguita la persona successiva. L'eliminazione procede attorno al cerchio (che diventa sempre più piccolo man mano che le persone giustiziate vengono rimosse), fino a quando rimane l'ultima persona, a cui viene data libertà.

I Ho cercato su Google questo "problema Josephus" e il colpo di Wikipedia mi dà una soluzione di programmazione dinamica: f(n,k)=((f(n-1,k)+k-1) mod n)+1, with f(1,k)=1, ma questo produce solo l'ultimo sopravvissuto. Come posso ottenere la sequenza delle persone giustiziate? Dì, p (5, 3) = {3,1,5,2,4}.

Inoltre, esiste una soluzione O(nlogn) invece di una O(nk)?

Answer 1

Per ottenere la sequenza delle persone giustiziate e l'ultimo sopravvissuto è sufficiente simulare l'intero processo dall'inizio. Data la descrizione della procedura, questo sarebbe un compito abbastanza facile. La formula che presenti è solo una scorciatoia per verificare chi sopravviverà e ottenere rapidamente la risposta.

Descrizione su come farlo in O (n log n) utilizzando Gamma Alberi è qui: analisi http://pl.scribd.com/doc/3567390/Rank-Trees

più dettagliate si possono trovare qui: http://www.imt.ro/romjist/Volum12/Number12_1/pdf/02-MCosulschi.pdf

Answer 2

Le persone saranno memorizzati in serie di taglia n. Se la persona dell'indice i è stata eseguita ora, la successiva sarà data da (i+k)%m dove m è il numero di persone rimanenti. Dopo ogni iterazione, la dimensione dell'array diminuirà di 1 e gli elementi rimanenti verranno spostati di conseguenza.

ingresso: La gente [0..n-1], n, k, i (= indice di prima persona eseguita)

Il codice pseudo sarebbe qualcosa di simile:

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

Stimolare il programma è possibile utilizzare una struttura che contiene il nome del giocatore e un tag che mantiene la traccia se il giocatore è attivo o meno. Ogni volta in un nuovo round salti un determinato numero di giocatori, quindi usa un loop e un'istruzione condizionale in modo che tutti i giocatori che sono fuori dal gioco vengano ignorati e vengano contati solo quelli del gioco. E naturalmente aggiungere istruzioni printf per stampare lo stato corrente.

Answer 4

La struttura di dati più naturale per rappresentare le persone è un buffer circolare. La mia soluzione crea una lista collegata, lega la coda della lista alla testa, poi conta ripetutamente attorno al buffer alla persona successiva da eseguire, rimuove quella persona dal buffer e continua fino a quando la coda del buffer punta a se stessa .

(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))) 

Ad esempio:

> (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) 

Si può leggere una spiegazione più esauriente a my blog, che dà tre diverse soluzioni. Oppure puoi eseguire il programma allo http://programmingpraxis.codepad.org/RMwrace2.

Answer 5

Per rispondere a questa domanda di emissione della sequenza di esecuzione, è necessaria una simulazione. Ciò significa complessità O (nk).È impossibile ottenere la sequenza di esecuzione [che è O (n)] mentre si cerca la complessità temporale di O (nlogn) allo stesso tempo. Perché devi produrre ogni persona da eseguire, che è O (n).

Il riferimento di kkonrad a Range Trees produce una buona soluzione di O (nlogn). Come altri hanno sottolineato, una lista circolare collegata è una struttura dati efficiente per questo problema. Trovo che la soluzione Java di 200_success di Code Review sia molto elegante e leggibile.

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)); 
    } 
} 

Ci sono altri dettagli su Wikipedia per questo problema di Josephus (k = 2).

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