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

Josephus Problem - Uma espécie de roleta russa

0 votos
29 visitas
perguntada Jul 6 em Sistemas de Informação por Victor Candido (21 pontos)  

Considere n pessoas em torno de u círculo numeradas de 1 a n.
Começando com a pessoa associada ao número 1, n os eliminamos todas
segundas pessoas até que só reste uma única pessoa no círculo.
Determine o n ́umero associado a pessoa que sobrevive. Por exemplo, se
n = 6, na primeira rodada, ao serem eliminadas as pessoas 2, 4 e 6. Na
segunda rodada será eliminada a pessoa inicialmente com o n ́umero 3 e
na ́ultima rodada a pessoa com o n ́umero 1, restando apenas a pessoa
numerada inicialmente com 5. Implemente a solução força bruta para
esse problema.

Compartilhe

1 Resposta

0 votos
respondida Jul 6 por Victor Candido (21 pontos)  

Podemos resolver esse problema com um código bem simples, como o abaixo:

#Definindo a função josephus, note que os argumentos são o número de pessoas e o número de estapas
def josephus(nbrPeople, stepSize):

index = stepSize - 1
stepSize -= 1

print('Pessoas que morreram:')
while (len(nbrPeople) > 1):
    print(nbrPeople.pop(index))
    index = (stepSize + index) % len(nbrPeople)
print('Sobrevivente: ', nbrPeople.pop(0))

nbrPeople = list(range(1, 10))
#Número de repetições que nosso algorítimo irá fazer
stepSize = 3

josephus(nbrPeople, stepSize)

O resultado, para n=10 pessoas participando é

Pessoas que morreram:
3
6
9
4
8
5
2
7
Sobrevivente: 1

E para n=20?

Pessoas que morreram:
3
6
9
12
15
18
2
7
11
16
1
8
14
4
13
5
19
10
Sobrevivente: 17

E para um n=30?

Pessoas que morreram:
3
6
9
12
15
18
21
24
27
1
5
10
14
19
23
28
4
11
17
25
2
13
22
7
20
8
29
16
Sobrevivente: 26

comentou Jul 6 por Edmar Rocha Pereira (21 pontos)  
Boa noite Victor!
Tentei rodar o código, mas deu um erro! Não sei se foi por que tentei rodar on line!

Abraços, Edmar
comentou Jul 10 por danielcajueiro (5,331 pontos)  
Acho que a parte de dentro da função não está justificada corretamente.
...