Объяснение для рекурсивной реализации проблемы Иосифа

РЕДАКТИРОВАТЬ: N это количество человек. k - это k-й человек, которого исключают. Таким образом, при k = 2 каждый второй человек устраняется.

int josephus(int n, int k)
{
 if (n == 1)
  return 1;
else
   return (josephus(n - 1, k) + k-1) % n + 1;
}

Код настолько прост, насколько это возможно. Но почему-то я не могу понять эту проблему (что немного смущает, если честно).

То, как я пытаюсь понять это,

  1. josephus (n, k) дает окончательное решение для населения размера n и размера шага k.
  2. josephus (n, k) можно вычислить, если мы знаем решение для josephus (n-1, k). Это, на мой взгляд, "оптимальное свойство субструктуры" динамического программирования.
  3. Я понял, что нам нужно сделать MOD N, чтобы в случае, если число прошло n, он снова начнет считать с 1. (т.е. убедитесь, что сложение ведет себя так, как мы считаем по кругу). Но почему мы добавили этот "к-1"?

Главный вопрос: если мы знаем правильное решение Иосифа (n-1, k), как мы вычисляем решение для Иосифа (n, k). Мы фактически добавили еще одного человека к населению, и каким-то образом добавив это значение k-1, я получаю правильное решение (пусть на мгновение проигнорирует мод).

Может ли кто-нибудь объяснить мне, как оптимальное свойство субструктуры удерживается на каждом этапе проблемы?

Ответы

Ответ 1

Ключевое понимание, сделанное для этого решения, имеет смысл для меня: результат josephus(n, k) лучше всего не воспринимать как число, оставшееся в живых Иосифа Флавия, а скорее как индекс числа, который является Иосифом оставшийся в живых. Например, вызов josephus(5, 2) подскажет вам индекс человека из кольца из пяти, которое заканчивается выживанием.

С учетом этой интуиции подумайте о том, как работает Джозефус, глядя на конкретный пример. Предположим, мы хотим знать josephus(n, 2). Вы можете себе представить, что у нас есть русские люди, которые выстроились так:

1 2 3 4 5 ... n

Первое, что случается, это то, что человек 1 убивает человека 2, как показано здесь:

1 X 3 4 5 ... n

Теперь у нас есть подзадача следующего вида: осталось n-1 человек, каждый другой человек будет убит, а первым человеком, который будет совершать колоть, является человек 3. В другом слова, мы остаемся с кольцом людей в форме:

3 4 5 ... n 1

с k = 2. Теперь представьте, что мы делаем рекурсивный вызов josephus(n - 1, 2), так как мы имеем n - 1 человек. Это вернет индекс того, кто выживает в строке n - 1 человек. Учитывая, что у нас есть индекс человека, который выживет, и мы также знаем, кто является старшим, мы можем определить, кто из них останется. Вот как мы это сделаем.

Старшим в этой строке является лицо, которое приходит сразу после последнего человека. Это будет человек 3. 1-индексированная позиция оставшегося в живых в кольце четырех человек дается josephus(n - 1, 2). Таким образом, мы можем идти вперед josephus(n - 1, 2) - 1 позиции, обертывая кольцо, если необходимо, чтобы добраться до нашей конечной позиции. Другими словами, оставшийся в живых определяется положением

 (3 + josephus(n - 1, 2) - 1) % n

Однако проблема с этой выше формулой. Если мы действительно используем одноиндексирование, что произойдет, если последний выживший находится в положении n? В этом случае мы случайно возвращаем позицию 0 в качестве нашего ответа, но нам действительно нужна позиция n. В качестве исправления для этого мы будем использовать трюк для использования мода для обхода с помощью одноиндексации: мы возьмем внутреннее количество (одноиндексированное положение) и вычтем одно, чтобы получить позицию с нулевым индексом. Мы изменим это количество на n, чтобы получить нулевую индексную позицию, обернутую вокруг. Наконец, мы добавим обратно один, чтобы получить одноиндексированную позицию, обернутую вокруг. Это выглядит так:

(3 + josephus(n - 1, 2) - 2) % n + 1

Таким образом, 2-й член исходит из двух независимых -1: первый -1 - это потому, что josephus(n - 1, 2) возвращает индекс с одним индексом, поэтому, чтобы шаг вперед по правильному числу позиций, мы должны выполнить шаги josephus(n - 1, 2) - 1 вперед. Второе -1 происходит от того факта, что мы используем одноиндексирующую, а не нулевую индексацию.

Обобщите это, чтобы работать для любого k, а не только k = 2. Предположим, мы хотим знать josephus(n, k). В этом случае человек 1 будет убивать человека k, оставив нас с таким массивом:

1 2 3 ... k-1 X k+1 ... n

Теперь нам по существу нужно решить подзадачу, в которой человек k + 1 приходит первым:

k+1 k+2 ... n 1 2 ... k-1

Итак, мы вычисляем josephus(n - 1, k), чтобы получить одноиндексированный оставшийся в живых из кольца k людей, а затем переместиться вперед на эти много шагов:

(k+1 + josephus(n - 1, k) - 1)

Нам нужно беспокоиться о том, где мы обертываем, поэтому нам нужно mod по n:

(k+1 + josephus(n - 1, k) - 1) % n

Однако мы проиндексированы один раз, поэтому нам нужно использовать трюк вычитания 1 из внутренней величины, а затем добавить 1 в конец:

(k+1 + josephus(n - 1, k) - 2) % n + 1

что упрощается до

(k-1 + josephus(n - 1, k)) % n + 1

что эквивалентно

(josephus(n - 1, k) + k-1) % n + 1

как в коде решения.

Подводя итог: термин k-1 происходит от начала в позиции k + 1, добавляя в josephus(n - 1, k) - 1 для сдвига вперед соответствующую сумму, затем вычитая ее и добавляя обратно в конец, чтобы сделать правильное обертку.

Надеюсь, это поможет!