Problema de Josephus

Declaração

Recebemos os números naturais $n$ e $k$. Todos os números naturais de $1$ a $n$ são escritos em um círculo. Primeiro, conte o $k$-ésimo número a partir do primeiro e exclua-o. Em seguida, os $k$ números são contados a partir do próximo e o $k$-ésimo é removido novamente e assim por diante. O processo para quando um número permanece. É necessário encontrar o último número.

Esta tarefa foi definida por Flavius ​​Josephus no século I (embora em uma formulação um pouco mais restrita: para $k = 2$).

Esse problema pode ser resolvido modelando o procedimento. A modelagem de força bruta funcionará em $O(n^{2})$. Usando uma árvore segmentária, podemos melhorá-la para $O(n \log n)$. Queremos algo ainda melhor.

Modelando uma solução $O(n)$

Vamos tentar encontrar um padrão que expresse a resposta para o problema $J_{n, k}$ através da solução dos problemas anteriores.

Usando a modelagem de força bruta, podemos construir uma tabela de valores, por exemplo, o seguinte:

$$\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}$$

E aqui podemos ver claramente o seguinte padrão:

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

Aqui, a indexação 1 cria uma fórmula um pouco confusa; se numerar as posições de 0, é possível obter uma fórmula muito mais elegante(top-notch):

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

Então, encontramos uma solução para o problema de Josephus, trabalhando com $O(n)$ operações.

Implementação

Implementação recursiva simples (1-indexing)

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

Não-recursiva :

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

Essa fórmula também pode ser encontrada analiticamente. Novamente, aqui assumimos a indexação 0. Depois de excluir o primeiro número, temos os $n-1$ números restantes. Quando repetimos o procedimento, começaremos com o número que originalmente tinha o índice $k \bmod m$. $J_{(n-1), k}$ seria a resposta para o círculo restante se começássemos a contar com 0, mas como na verdade começamos com $k$ temos $J_ {n, k} = (J _ {(n-1), k} + k) \ \bmod n$.

Modelando uma solução $O(k \log n)$

Fara $k$'s relativamente pequenos, podemos encontrar uma solução melhor do que a solução recursiva acima em $O(n)$. Se $k$ é muito menor que $n$, podemos excluir vários números ($\lfloor \frac{n}{k} \rfloor$) em uma execução sem repetir o loop. Depois, temos $n - \lfloor \frac{n}{k} \rfloor$ números restantes, e começamos com o $(\lfloor \frac{n}{k} \rfloor \cdot n)$-ésimo número. Então, temos que mudar por esse tanto. Podemos notar que $\lfloor \frac{n}{k} \rfloor \cdot n$ é simplesmente $n \bmod k$. E como removemos todo $k$-ésimo número, precisamos adicionar o número de números que removemos antes do índice resultante.

Além disso, precisamos lidar com o caso quando $n$ se torna menor que $k$. Nesse caso, a otimização acima causaria um loop infinito.

Implementação:

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

Vamos estimar a complexidade desse algoritmo. Observe imediatamente que o caso $n < k$ é analisado pela solução antiga, que funcionará nesse caso por $O(k)$. Agora considere o próprio algoritmo. De fato, após cada iteração, em vez de $n$ números, ficamos com $n \left( 1 - \frac{1}{k} \right)$ números, portanto, o número total de iterações $x$ do algoritmo pode ser encontrado aproximadamente a partir da seguinte equação:

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

tomando logaritmo de ambos os lados, obtemos:

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

usando a decomposição do logaritmo em séries de Taylor, obtemos uma estimativa aproximada:

$$x \approx k \ln n$$

Assim, a complexidade do algoritmo é $O (k \log n)$.

Solução analítica para $k = 2$

Nesse caso em particular (no qual essa tarefa foi definida por Josephus Flavius), o problema é resolvido com muito mais facilidade.

No caso de um $n$ par, obtemos que todos os números pares serão riscados e, em seguida, haverá um problema restando para $\frac{n}{2}$, e a resposta para $n$ será obtida pela resposta usando $\frac{n}{2}$ multiplicando por dois e subtraindo um (trocando a posição):

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

Da mesma forma, no caso de um $n$ , ímpar, todos os números pares serão riscados, e então o primeiro número, e permanecerá o problema para $\frac{n-1}{2}$, e, levando em consideração a mudança de posições, obtemos a segunda fórmula:

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

Podemos usar essa dependência recorrente diretamente em nossa implementação. Esse padrão pode ser traduzido para outra forma: $J_{n, 2}$ representa uma sequência de todos os números ímpares, "reiniciando" a partir de um, sempre que $n$ for uma potência de dois. Isso pode ser escrito como uma fórmula única:

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

Solução analítica para $k > 2$

Apesar da forma simples do problema e de um grande número de artigos sobre esse e outros problemas relacionados, ainda não foi encontrada uma representação analítica simples da solução do problema de Josephus. Para pequenos $k$, derivam-se algumas fórmulas, mas aparentemente todas são difíceis de aplicar na prática (por exemplo, consulte Halbeisen, Hungerbuhler "The Josephus Problem" e Odlyzko, Wilf "Functional iteration and the Josephus problem").