Пояснение к рекурсивной реализации Josephus prob
РЕДАКТИРОВАТЬ: 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;
}
Код настолько прост, насколько это возможно. Но почему-то я не могу понять эту проблему (что немного смущает, если честно).
То, как я пытаюсь понять это,
josephus (n, k) дает окончательное решение для населения размера n и размера шага k.josephus (n, k) можно вычислить, если мы знаем решение для josephus (n-1, k). Это, на мой взгляд, «оптимальное свойство субструктуры» динамического программирования.Я получаю, что нам нужно сделать MOD N, чтобы в случае, если число идет за n, он снова начинает считать с 1. (т.е. убедитесь, что сложение ведет себя так, как мы считаем в круге). Но почему мы добавили этот «к-1»?Главный вопрос: если мы знаем правильное решение Иосифа (n-1, k), как мы вычисляем решение для Иосифа (n, k). Мы фактически добавили еще одного человека к населению, и каким-то образом добавление этого значения k-1 дает мне правильное решение (давайте на минутку проигнорируем мод).
Может ли кто-нибудь объяснить мне, как оптимальное свойство субструктуры удерживается на каждом этапе проблемы?