Como resolver o 'Josephus Problem' utilizando força bruta? - PRorum.com
Como resolver o 'Josephus Problem' utilizando força bruta?
perguntada Jun 6, 2018 em Ciência da Computação por Felipe Carneiro (76 pontos)
Considere n pessoas em torno de um círculo numeradas de 1 a n. Começando com a pessoa associada ao número 1, nós eliminamos todas segundas pessoas até que só reste uma única pessoa no círculo. Determine o número associado a pessoa que sobrevive. Por exemplo, se n = 6, na primeira rodada serão eliminadas as pessoas 2, 4 e 6. Na segunda rodada será eliminada a pessoa inicialmente com o número 3 e na última rodada a pessoa com o número 1, restando apenas a pessoa numerada inicialmente com 5. Implemente a solução força bruta para esse problema. Gere figuras que ajudem ao entendimento do problema (e apresente os códigos usados para isso).
respondida Jun 6, 2018 por Felipe Carneiro (76 pontos)
editado Jun 18, 2018 por Felipe Carneiro
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)
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:
plotly.tools.set_credentials_file(username='Felipe1303', api_key='QUn3U7DhJF5jzVs0SRGg')
data_matrix = [[1, 2, 3, 4, 5, 6],
[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.
comentou Jun 8, 2018 por Pedro Henrique T (21 pontos)
Ótima implementação!!
A título de curiosidade, eu implementei a versão recursiva deste problema.
Para que a recursão se tornasse factível, eu precisei adicionar o parâmetro "n" - que representa o comprimento da lista - e o parâmetro ind, que tem default igual a 1, mas pode ter seu valor definido pelo usuário caso o "passes" seja diferente de 1.