Josephus sekwencji

Question

Opis: Są ludzie stojący w kręgu czeka na wykonanie. Odliczanie rozpoczyna się w pewnym punkcie koła i krąży po okręgu w ustalonym kierunku. W każdym kroku pewna liczba osób jest pomijana, a następna osoba jest wykonywana. Eliminacja przebiega wokół koła (które staje się coraz mniejsze, gdy usuwane są egzekucje), dopóki pozostanie tylko ostatnia osoba, której przyznano wolność.

I Przeglądam ten "problem z Józefem", a hit w Wikipedii daje mi rozwiązanie do programowania dynamicznego: f(n,k)=((f(n-1,k)+k-1) mod n)+1, with f(1,k)=1, ale to tylko daje ostatnią szansę na przetrwanie. Jak mogę uzyskać sekwencję wykonanych egzekucji? Powiedz: p (5, 3) = {3,1,5,2,4}.

Czy istnieje również rozwiązanie O(nlogn) zamiast O(nk)?

Answer 1

Aby uzyskać sekwencję wykonanych osób i ostatniego ocalałego, wystarczy zasymulować cały proces od samego początku. Biorąc pod uwagę opis procedury, byłoby to dość łatwe zadanie. Formuła, którą prezentujesz, jest tylko skrótem, aby sprawdzić, kto przetrwa i szybko uzyskać odpowiedź.

opis, w jaki sposób to zrobić w czasie O (n log n) używając Zakres Drzewa jest tutaj: http://pl.scribd.com/doc/3567390/Rank-Trees

Bardziej szczegółową analizę można znaleźć tutaj: http://www.imt.ro/romjist/Volum12/Number12_1/pdf/02-MCosulschi.pdf

Answer 2

Ludzie będą przechowywane w tablicy o wielkości n. Jeśli osoba z indeksem i została teraz wykonana, następna będzie nadana przez (i+k)%m, gdzie m jest liczbą pozostałych osób. Po każdej iteracji rozmiar tablicy zmniejszył się o 1, a pozostałe elementy zostaną odpowiednio przesunięte.

wejściowe Ludzie [0..N-1], n, k, I (= wskaźnik pierwszej osoby Wykonane)

kod pseudo wyglądałby:

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

stymulowanie program można użyć struktury, która zawiera nazwę gracza i znacznik, który utrzymuje ścieżkę, jeśli gracz jest aktywny, czy nie. Za każdym razem w nowej rundzie pomijasz określoną liczbę graczy, więc użyj pętli i warunkowego oświadczenia, aby wszyscy gracze, którzy wyszli z gry, zostali zignorowani i liczeni są tylko ci w grze. I oczywiście dodaj instrukcje printf, aby wydrukować bieżący status.

Answer 4

Najbardziej naturalną strukturą danych reprezentującą ludzi jest bufor cykliczny. Moje rozwiązanie tworzy listę połączoną, wiąże ogon listy z powrotem do głowy, a następnie wielokrotnie zlicza wokół bufora do następnej osoby, która ma być wykonana, usuwa tę osobę z bufora i kontynuuje, aż koniec bufora wskazuje na siebie .

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

Na przykład:

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

można przeczytać wyjaśnienie w my blog pełniejsze, co daje trzy różne rozwiązania. Lub możesz uruchomić program pod numerem http://programmingpraxis.codepad.org/RMwrace2.

Answer 5

Aby odpowiedzieć na pytanie o wykonanie sekwencji wykonania, wymagana jest symulacja. Oznacza to złożoność O (nk).Nie można uzyskać sekwencji wykonania [która jest O (n)], jednocześnie poszukując złożoności czasu O (nlogn). Ponieważ musisz wypisać każdą osobę, która ma zostać wykonana, czyli O (n).

Odniesienie kkonrad do drzew zakresów daje dobre rozwiązanie O (nlogn). Jak zauważyli inni, powiązana lista jest wydajną strukturą danych dla tego problemu. Uważam, że 200_success "rozwiązanie Java z Code Review jest bardzo eleganckie i czytelne.

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

Jest więcej szczegółów na temat tego problemu z Józefem Flawiuszem (k = 2).

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