Решение:
Рассмотрим задачу Иосифа, когда n человек стоят в кругу и каждый k‑й человек выбывает. Для поиска номера последнего оставшегося человека можно использовать рекуррентную формулу. Обозначим через J(n, k) индекс (считая с 0) последнего оставшегося человека при n людях и шаге k. Тогда:
\tJ(1, k) = 0
\tJ(n, k) = (J(n – 1, k) + k) mod n при n > 1
Так как в условии номера людей даны от 1 до n, окончательный ответ будет равен J(n, k) +
1.
Пошаговое рассуждение:
- Начинаем с того, что при n = 1 единственный человек имеет индекс...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
Что нужно знать по теме:
Что нужно знать по теме
Алгоритм решения
Топ 3 ошибок
Что спросит препод
Похожие задачи