A linguagem utilizada para implementação da solução do problema foi Python 3.6.
A solução do Josephus Problem, utilizando um algoritmo força bruta, é de relativa fácil implementação para n = 6.
Podemos pensar esse problema também como o problema da "batata-quente". Cada pessoa faz um certo número de passes (o problema considera que as pessoas estão em círculo), e com isso deixa a "batata-quente" na mão de alguém - o que faz com que esta seja eliminada. Deste modo, começamos definindo uma função josephus(list_pessoas, passes)
, onde o primeiro argumento é a lista de pessoas e o segundo a quantidade de passes. Utilizamos o comando list_pessoas.pop(i)
para excluir cada "vítima" (e obter sua posição) em um loop. Então, nós apenas temos que nos preocupar em envolver os índices, o que pode ser feito simplesmente pegando o índice pulado e modificando o número de pessoas remanescentes.
Assim, a solução se torna:
def josephus(list_pessoas, passes):
i = passes
while len(list_pessoas) > 1:
print(list_pessoas.pop(i)) # elimina a pessoa em i
i = (i + passes) % len(list_pessoas)
print('Sobrevivente: ', list_pessoas[0])
Testando para o problema da questão, onde:
josephus([1,2,3,4,5,6],1)
Temos como resultado:
2
4
6
3
1
Sobrevivente: 5
Observe que o comando list_pessoas.pop(i)
nos dá em sequência quais serão as pessoas eliminadas - dada certa quantidade de passe(s) - até que sobre uma única sobrevivente, nesse caso n=5 (a solução final).
Gerei uma tabela que tenta simbolizar como as eliminações são feitas:
import plotly
plotly.tools.set_credentials_file(username='Felipe1303', api_key='QUn3U7DhJF5jzVs0SRGg')
import plotly.plotly as py
import plotly.figure_factory as ff
data_matrix = [[1, 2, 3, 4, 5, 6],
[1, 1, 1, 1, 1, 1],
[1, 0, 1, 0, 1, 0],
[1, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 1, 0]]
table = ff.create_table(data_matrix)
py.iplot(table)
Os rótulos da coluna simbolizam cada pessoa (1 a 6), já os valores binários (0 ou 1) em cada locus da matriz representam se a pessoa foi eliminada (0) ou é sobrevivente (1). Observe novamente que as pessoas estão organizadas em círculo; é possível constatar na última linha da tabela que o sobrevivente de fato é a pessoa número 5.

Obs.: Note que para utilizar o pacote plotly é necessário criar uma conta em seu site - as imagens são geradas em seu perfil cadastrado.