Problema de Josephus: o sobrevivente de um círculo
Informe quantas pessoas formam o círculo e de quantas em quantas uma é eliminada: veja a posição do sobrevivente e a posição que sobreviveria em cada tamanho menor de círculo.
- Roda no seu navegador
Resultado
O resultado aparece aqui.
Como o sobrevivente é encontrado
J(1) = 0; J(i) = (J(i − 1) + passo) mod i; sobrevivente = J(n) + 1
Num círculo de n pessoas, conta-se de uma em uma e a pessoa na posição do passo é eliminada, até restar uma. A posição do sobrevivente segue uma recorrência simples, calculada aqui para todos os tamanhos de círculo de 1 até n.
Exemplo com 41 pessoas e passo 3
| Tamanho do círculo | Posição do sobrevivente |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 2 |
| 4 | 1 |
| 5 | 4 |
| 6 | 1 |
| 7 | 4 |
| 8 | 7 |
| 9 | 1 |
| 10 | 4 |
| 11 | 7 |
| 12 | 10 |
Cuidados com o problema de Josephus
- Posições numeradas de 1 a n a partir de quem começa a contagem; a contagem recomeça na pessoa seguinte à eliminada.
- Com passo 1, o sobrevivente é sempre o último da roda.
- A tabela mostra a posição que sobreviveria em cada tamanho de círculo, de 1 até n.
- A ordem em que cada pessoa é eliminada não é calculada por esta ferramenta.
Nota: Resultado matemático do problema clássico; a história de Josephus é só a ilustração.
Perguntas frequentes
Qual é o problema de Josephus?
Pessoas em círculo são eliminadas de k em k até restar uma; o problema pede a posição do sobrevivente.
Em que posição ficar para sobreviver ao círculo de eliminação?
Com 41 pessoas e passo 3, fique na posição 31.
Como calcular o sobrevivente de Josephus com passo k?
Use J(i) = (J(i − 1) + k) mod i, com J(1) = 0, e some 1 ao final.