Пояснение к рекурсивной реализации Josephus prob

Question

РЕДАКТИРОВАТЬ: 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 дает мне правильное решение (давайте на минутку проигнорируем мод).

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

Answer 1

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

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

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)

Нам нужно беспокоиться о случае, когда мы оборачиваемся, поэтому нам нужно изменить мод на 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 чтобы сдвинуть вперед соответствующую сумму, затем вычесть одну и добавить одну обратно в конце, чтобы сделать правильный переход.

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

Answer 2

Нам нужно отрегулировать положение на k-1 просто потому, что начальное положение было сдвинуто на k после удаления k-го (и первые k-1 повернуты до конца). То есть начальная позиция pos становится pos-k. Если k = 3, (n-1,k) вернул pos = 2, исходная позиция должна быть pos + k = 5.

Мы заменяем k на k-1 в формуле, потому что нам нужно mod(n): k = (k-1)% n + 1