Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como resolver o 'Josephus Problem' utilizando força bruta?

0 votos
6 visitas
perguntada Jun 6 em Ciência da Computação por Felipe Carneiro (16 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).

Compartilhe

1 Resposta

0 votos
respondida Jun 6 por Felipe Carneiro (16 pontos)  
editado Jun 7 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. Note que não será necessário que importemos nenhuma biblioteca específica.

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).

comentou Jun 8 por Pedro Henrique T (16 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.

Segue a implementação recursiva:

def josephus_recursiva(list_pessoas,n, passes,ind=1):
        
    if(n==1):
        print('Sobrevivente: ', list_pessoas[0])
    else:
        print(list_pessoas[ind])
        list_pessoas.pop(ind)        
        ind=(ind+passes)%(n-1)
        josephus_recursiva(list_pessoas,n-1, passes,ind)

list_pessoas=[1,2,3,4,5,6]
josephus_recursiva(list_pessoas, len(list_pessoas), 1)
...