Тема: Задача Иосифа Флавия
Знаю, задача и ее решение уже обмусолены с разных сторон.
Меня интересует реализация решения за 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.
В теоретических материалах в сети не удалось найти подобных формулировок.