Ява — последовательность Иосифа

Наиболее естественной структурой данных для представления людей является круговой буфер. Мое решение создает связанный список, связывает хвост списка с заголовком, затем многократно считает вокруг буфера следующего человека, который будет выполнен, удаляет этого человека из буфера и продолжается до тех пор, пока хвост буфера не укажет на себя ,

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

Например:

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

Вы можете прочитать более полное объяснение на мой блог, который дает три разных решения. Или вы можете запустить программу на http://programmingpraxis.codepad.org/RMwrace2.

Люди будут храниться в массиве размером n. Если человек в указателе i был выполнен сейчас, следующий будет дан (i+k)%m где m — количество оставшихся людей. После каждой итерации размер массива будет уменьшаться на 1, а остальные элементы будут соответственно смещаться.

Входные данные: Люди [0..n-1], n, k, i (= индекс первого выполненного лица)

Псевдокод будет выглядеть примерно так:

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

Для стимулирования программы вы можете использовать структуру, которая содержит имя игрока и тег, который отслеживает, активен игрок или нет. Каждый раз в новом раунде вы пропускаете определенное количество игроков, поэтому используйте цикл и условное выражение, чтобы все игроки, которые вышли из игры, игнорировались и учитывались только те, кто в игре. И, конечно, добавьте операторы printf для печати текущего статуса.

Чтобы ответить на этот вопрос вывода последовательности выполнения, требуется симуляция. Это означает сложность O (nk). Невозможно получить последовательность выполнения [которая является O (n)], одновременно ища O (nlogn) временную сложность одновременно. Потому что вы должны выводить каждого человека, который будет казнен, а это O (n).

Ссылка kkonrad на Range Trees дает хорошее решение O (nlogn). Как уже отмечали другие, круговой связанный список является эффективной структурой данных для этой проблемы. Я нахожу решение Java 200_success из Code Review очень элегантным и читабельным.

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

В Википедии есть еще несколько деталей для этой проблемы Иосифа (k = 2).

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