Последовательность Иосифа

Ответ 1

Чтобы получить последовательность исполняемых лиц и оставшихся в живых, вам просто нужно с самого начала имитировать весь процесс. Учитывая описание процедуры, это было бы довольно простой задачей. Формула, которую вы представляете, - это всего лишь ярлык, чтобы проверить, кто выживет и быстро получить ответ.

Описание того, как это сделать в O (n log n) с использованием Range Trees, приведено здесь: http://pl.scribd.com/doc/3567390/Rank-Trees

Более подробный анализ можно найти здесь: http://www.imt.ro/romjist/Volum12/Number12_1/pdf/02-MCosulschi.pdf

Ответ 2

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

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

Ответ 3

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

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

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

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

Ответ 4

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

Ответ 5

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

Ссылка kkonrad на Деревья Диапазонов дает хорошее решение 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