1 Отредактировано Anton (2012-01-25 10:06:12)

Тема: Задача Иосифа Флавия

Знаю, задача и ее решение уже обмусолены с разных сторон.
Меня интересует реализация решения за k(log(n)). Хочу полностью понять логику.
Разбираю функцию построчно:
1. if (n == 1)  return 0; //  это понятно
2. if (k == 1)  return n-1; //  это понятно
3. if (k > n)  return (joseph (n-1, k) + k) % n; //  это понятно
*4. int cnt = n / k; //  сколько k-ых бойцов в кругу
*5. int res = joseph (n - cnt, k); // считаем для ситуации после экзекуции всех k-ых бойцов
*6. res -= n % k; // - ?
*7. if (res < 0)  res += n; // - ?
*8. else  res += res / (k - 1); // - ???

Хотелось бы полуить комментарии по строкам 4-8.
В теоретических материалах в сети не удалось найти подобных формулировок.

Anton.Hola

2

Re: Задача Иосифа Флавия

да, в строках 4-5 мы "убиваем" всех k-ых бойцов и вызываемся от меньшей подзадачи размера n-cnt.
однако результат res вызова подзадачи ещё нужно исправить:
1) после экзекуции cnt бойцов мы на самом деле остановились на (k*cnt-1)-ом бойце, а не на 0-ом.
скажем, если бы n%k==0, то мы бы действительно следующим шагом попали в 0-го бойца.
но во всех остальных случаях, т.е. когда n%k>0, результат res надо уменьшить на n%k - именно на столько надо "прокрутить" номера бойцов.
2) после этого исправления нумерации у нас два принципиальных случая:
2а) если res<0, то это означает, что ответом является боец, первоначально находившийся в числе последних n%k человек. Тогда ответ на задачу - это res+n
2б) в противном случае, нам надо сдвинуть res на сколько-то, потому что мы должны учесть номера убитых cnt бойцов - для этого мы прибавляем res / (k-1) - именно столько k-ых бойцов оказалось раньше res-го.

P.S. Мне сейчас кажется на самом деле, что вариант 2б) на самом деле покрывает вариант 2a), т.е. можно убрать строки 6 и 7. Но я не уверен в этом.

3 Отредактировано Anton (2012-01-26 02:35:02)

Re: Задача Иосифа Флавия

Спасибо за разъяснения! Почти всё встало на свои места, все рассуждения очень логичные.
Маленький вопрос касательно финального сдвига на res / (k-1), его логический смысл мне ясен, не понимаю аналитическую часть - почему k-ых бойцов до позиции res ровно res / (k-1) ?
Я пробовал рассматривать разные примеры, допустим n=6, k=3. Выписываю их индексы (в 0-индексации):
0 1 2 3 4 5
     ^      ^
k-ые бойцы - 2 и 5. Теоретически (чисто теоретически) подзадача с n=4, k=3 возвращает нам ответ в диапозоне [0;4]; диапозон, который соответствует случаю 2б), - [0;4]. Допустим, если подзадача вернула 4 то res / (k-1) = 2. То есть до бойца с позиции 4 стоит 2 k-ых бойца, но это ведь не так ...
Подскажите, пожалуйста, какие рассуждения я провожу не верно ?

Кстати, попробовал обойтись только вариантом 2б) на последнем шаге (без строчек 6 и 7) - увы, не выходит. Это можно увидеть, к примеру, при n=3, k=2.

Anton.Hola

4

Re: Задача Иосифа Флавия

Нет, при n=6, k=3 подзадача будет вызываться от n=4, поэтому будет возвращать в отрезке [0;3]. После нормализации в строках 5-8 res=0 и res=1 останутся без изменений, а res=2 и res=3 увеличатся на 1.

Насчет случая 2а - да, пожалуй, технически он необходим, хотя я всё же верю, что эти два случая можно объединить в одну формулу.