Задача Йосипа (Флавія)

Умова

Нам задано натуральні числа $n$ і $k$. Усі натуральні числа від $1$ до $n$ записані по колу. Спочатку відлічуємо $k$-те число, починаючи з першого, і видаляємо його. Потім відлічуємо $k$ чисел, починаючи з наступного, і знову видаляємо $k$-те, і так далі. Процес зупиняється, коли залишається одне число. Потрібно знайти останнє число.

Коли підходить цей алгоритм?

• Чи виключення відбувається за фіксованим кроком $k$ по колу, а не за довільним правилом?
• Чи потрібна лише позиція останнього (або виключеного) елемента, а не повне моделювання процесу?
• Чи $k$ набагато менше за $n$ — тоді варто брати розв'язок за $O(k \log n)$ замість $O(n)$? (якщо потрібні проміжні стани → моделюй через дерево відрізків)

Цю задачу поставив Йосип Флавій у 1 столітті (щоправда, у дещо вужчому формулюванні: для $k = 2$).

Цю задачу можна розв'язати, змоделювавши описану процедуру. Моделювання повним перебором працюватиме за $O(n^{2})$. Використовуючи дерево відрізків, ми можемо покращити це до $O(n \log n)$. Проте ми хочемо щось краще.

Моделювання розв'язку за $O(n)$

Спробуємо знайти закономірність, яка виражає відповідь для задачі $J_{n, k}$ через розв'язки попередніх задач.

За допомогою моделювання повним перебором ми можемо побудувати таблицю значень, наприклад, таку:

$$\begin{array}{ccccccccccc} n\setminus k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 2 & 1 & 2 & 1 & 2 & 1 & 2 & 1 & 2 & 1 \\ 3 & 3 & 3 & 2 & 2 & 1 & 1 & 3 & 3 & 2 & 2 \\ 4 & 4 & 1 & 1 & 2 & 2 & 3 & 2 & 3 & 3 & 4 \\ 5 & 5 & 3 & 4 & 1 & 2 & 4 & 4 & 1 & 2 & 4 \\ 6 & 6 & 5 & 1 & 5 & 1 & 4 & 5 & 3 & 5 & 2 \\ 7 & 7 & 7 & 4 & 2 & 6 & 3 & 5 & 4 & 7 & 5 \\ 8 & 8 & 1 & 7 & 6 & 3 & 1 & 4 & 4 & 8 & 7 \\ 9 & 9 & 3 & 1 & 1 & 8 & 7 & 2 & 3 & 8 & 8 \\ 10 & 10 & 5 & 4 & 5 & 3 & 3 & 9 & 1 & 7 & 8 \\ \end{array}$$

І тут ми чітко бачимо таку закономірність:

$$J_{n,k} = \left( (J_{n-1,k} + k - 1) \bmod n \right) + 1$$ $$J_{1,k} = 1$$

Тут нумерація з одиниці робить формулу дещо громіздкою; якщо ж нумерувати позиції з нуля, то отримуємо дуже елегантну формулу:

$$J_{n,k} = (J_{n-1,k} + k) \bmod n$$

Отже, ми знайшли розв'язок задачі Йосипа, який працює за $O(n)$ операцій.

Реалізація

Проста рекурсивна реалізація (з нумерацією з одиниці)

C++

int josephus(int n, int k) {
    return n > 1 ? (josephus(n-1, k) + k - 1) % n + 1 : 1;
}

Python

import sys

# Рекурсія завглибшки O(n) — за потреби підіймаємо ліміт стека
sys.setrecursionlimit(10**6)

def josephus(n: int, k: int) -> int:
    return (josephus(n - 1, k) + k - 1) % n + 1 if n > 1 else 1

TypeScript

function josephus(n: number, k: number): number {
  return n > 1 ? ((josephus(n - 1, k) + k - 1) % n) + 1 : 1;
}

Go

func josephus(n, k int) int {
	if n > 1 {
		return (josephus(n-1, k)+k-1)%n + 1
	}
	return 1
}

Нерекурсивна форма:

C++

int josephus(int n, int k) {
    int res = 0;
    for (int i = 1; i <= n; ++i)
  	  res = (res + k) % i;
    return res + 1;
}

Python

def josephus(n: int, k: int) -> int:
    res = 0
    for i in range(1, n + 1):
        res = (res + k) % i
    return res + 1

TypeScript

function josephus(n: number, k: number): number {
  let res = 0;
  for (let i = 1; i <= n; ++i)
    res = (res + k) % i;
  return res + 1;
}

Go

func josephus(n, k int) int {
	res := 0
	for i := 1; i <= n; i++ {
		res = (res + k) % i
	}
	return res + 1
}

Цю формулу можна також вивести аналітично. Тут ми знову припускаємо нумерацію з нуля. Після того, як ми видалили перше число, залишається $n-1$ чисел. Коли ми повторюємо процедуру, ми починаємо з числа, що мало початковий індекс $k \bmod n$. $J_{n-1, k}$ було б відповіддю для решти кола, якби ми починали відлік з $0$, але оскільки насправді ми починаємо з $k$, маємо $J_{n, k} = (J_{n-1,k} + k) \ \bmod n$.

Моделювання розв'язку за $O(k \log n)$

Для відносно малих $k$ ми можемо придумати кращий розв'язок, ніж наведений вище рекурсивний розв'язок за $O(n)$. Якщо $k$ набагато менше за $n$, то за один прохід ми можемо видалити одразу кілька чисел ($\lfloor \frac{n}{k} \rfloor$), не зациклюючись. Після цього залишається $n - \lfloor \frac{n}{k} \rfloor$ чисел, і ми починаємо з $(\lfloor \frac{n}{k} \rfloor \cdot k)$-го числа. Тому нам треба зсунутися на таку кількість. Можна помітити, що $\lfloor \frac{n}{k} \rfloor \cdot k$ — це просто $-n \bmod k$. А оскільки ми видаляли кожне $k$-те число, нам треба додати кількість чисел, які ми видалили до результуючого індексу. Цю кількість можна обчислити, поділивши результуючий індекс на $k - 1$.

Також нам треба обробити випадок, коли $n$ стає меншим за $k$. У цьому випадку наведена вище оптимізація призвела б до нескінченного циклу.

Реалізація (для зручності з нумерацією з нуля):

C++

int josephus(int n, int k) {
    if (n == 1)
        return 0;
    if (k == 1)
        return n-1;
    if (k > n)
        return (josephus(n-1, k) + k) % n;
    int cnt = n / k;
    int res = josephus(n - cnt, k);
    res -= n % k;
    if (res < 0)
        res += n;
    else
        res += res / (k - 1);
    return res;
}

Python

def josephus(n: int, k: int) -> int:
    if n == 1:
        return 0
    if k == 1:
        return n - 1
    if k > n:
        return (josephus(n - 1, k) + k) % n
    cnt = n // k
    res = josephus(n - cnt, k)
    res -= n % k
    if res < 0:
        res += n
    else:
        res += res // (k - 1)
    return res

TypeScript

function josephus(n: number, k: number): number {
  if (n === 1) return 0;
  if (k === 1) return n - 1;
  if (k > n) return (josephus(n - 1, k) + k) % n;
  const cnt = Math.floor(n / k);
  let res = josephus(n - cnt, k);
  res -= n % k;
  if (res < 0) res += n;
  else res += Math.floor(res / (k - 1));
  return res;
}

Go

func josephus(n, k int) int {
	if n == 1 {
		return 0
	}
	if k == 1 {
		return n - 1
	}
	if k > n {
		return (josephus(n-1, k) + k) % n
	}
	cnt := n / k
	res := josephus(n-cnt, k)
	res -= n % k
	if res < 0 {
		res += n
	} else {
		res += res / (k - 1)
	}
	return res
}

Оцінимо складність цього алгоритму. Одразу зауважимо, що випадок $n < k$ розбирається старим розв'язком, який у цьому випадку працюватиме за $O(k)$. Тепер розглянемо сам алгоритм. Насправді після кожної ітерації замість $n$ чисел у нас залишається $n \left( 1 - \frac{1}{k} \right)$ чисел, тож загальну кількість ітерацій $x$ алгоритму можна приблизно знайти з такого рівняння:

$$n \left(1 - \frac{1}{k} \right) ^ x = 1,$$

прологарифмувавши обидві частини, ми отримуємо:

$$\ln n + x \ln \left(1 - \frac{1}{k} \right) = 0,$$ $$x = - \frac{\ln n}{\ln \left(1 - \frac{1}{k} \right)},$$

використовуючи розклад логарифма в ряд Тейлора, ми отримуємо наближену оцінку:

$$x \approx k \ln n$$

Таким чином, складність алгоритму насправді становить $O (k \log n)$.

Аналітичний розв'язок для $k = 2$

У цьому окремому випадку (саме в якому цю задачу поставив Йосип Флавій) задача розв'язується значно простіше.

У випадку парного $n$ ми отримуємо, що всі парні числа будуть викреслені, і тоді залишиться задача для $\frac{n}{2}$, тож відповідь для $n$ отримується з відповіді для $\frac{n}{2}$ множенням на два та відніманням одиниці (через зсув позицій):

$$J_{2n, 2} = 2 J_{n, 2} - 1$$

Аналогічно, у випадку непарного $n$ будуть викреслені всі парні числа, потім перше число, і залишиться задача для $\frac{n-1}{2}$, а з урахуванням зсуву позицій ми отримуємо другу формулу:

$$J_{2n+1,2} = 2 J_{n, 2} + 1$$

Цю рекурентну залежність ми можемо використати безпосередньо у нашій реалізації. Цю закономірність можна переписати в іншій формі: $J_{n, 2}$ являє собою послідовність усіх непарних чисел, яка «перезапускається» з одиниці щоразу, коли $n$ виявляється степенем двійки. Це можна записати однією формулою:

$$J_{n, 2} = 1 + 2 \left(n-2^{\lfloor \log_2 n \rfloor} \right)$$

Аналітичний розв'язок для $k > 2$

Попри просту форму задачі та велику кількість статей про неї та споріднені задачі, простого аналітичного представлення розв'язку задачі Йосипа досі не знайдено. Для малих $k$ деякі формули виведені, але, схоже, усі вони важко застосовні на практиці (наприклад, див. Halbeisen, Hungerbuhler "The Josephus Problem" та Odlyzko, Wilf "Functional iteration and the Josephus problem").

Відеоматеріали