segunda-feira, 5 de agosto de 2013

Josephus Problem




Flávio Josephus foi um historiador judeu famoso do primeiro século, no momento da destruição do Segundo Templo. Durante a guerra judaico-romana, ele ficou preso em uma caverna com um grupo de 40 soldados cercados pelos romanos. A lenda diz que eles preferia o suicídio do que serem capturados então os judeus decidiram formar um círculo e, procedendo à sua volta, para matar cada terceira pessoa restante até que ninguém foi deixado. Josephus, não queria de morrer, rapidamente encontrou o local seguro no círculo e assim permaneceu vivo.

Você pode tentar repetir o feito de Flávio no seguinte jogo:

Uma maneira simples de resolver este problema é utilizar a estrutura de dados fila e realizar uma simulação para descobrir qual é a posição do último a morrer no círculo formado.
  
Resultado
Outra maneira é definir a estrutura recursiva do problema:
f(n,k) = sobrevivente em um círculo com n pessoas e salto k começando na pessoa 1.

f(n,k) = ( k-1 + f(n-1,k)) %n + 1
f(1,k) = 1

O valor k-1 é adicionado ao valor de f(n-1,k) justamente para ajustar o círculo na posição k-1, lembrando que f(n-1,k) devolve a posição com relação primeiro, e o valor +1 é para ajustar corretamente na posição k.


6 comentários:

Jaguaraci Silva disse...

Parabéns pelo excelente trabalho que vocês estão fazendo em mostrar que o ensino da computação pode ser divertido, prático e criativo.

Jaguaraci Silva disse...

Parabéns pelo excelente trabalho que vocês estão fazendo em mostrar que o ensino da computação pode ser divertido, prático e criativo.

Fenando Henrique disse...

cara me explica direito essa solução recursiva posta o codigo em c

Abiya Carol disse...

Great post!I am actually getting ready to across this information,i am very happy to this commands.Also great blog here with all of the valuable information you have.Well done,its a great knowledge.

Informatica training in chennai

Packers Movers Hyderabad disse...


I cannot truly enable but admire your weblog, your weblog is so adorable and great.It has given me courage to try scarier things. I tend to steer clear of them but not anymore.
Packers And Movers Hyderabad

Packers And Movers hitechcity Hyderabad

meto mayo disse...

Lovely Website, Maintain the fantastic work. Thank you so much!

https://www.roknelbeet.com/نقل-اثاث-بجدة/
https://www.roknelbeet.com/نقل-اثاث-بالدمام/
https://www.roknelbeet.com/نقل-اثاث-بمكة/
https://www.roknelbeet.com/تخزين-اثاث-بالرياض/