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.


8 comentários:

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

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

Unknown disse...

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

Unknown 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

reda 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/تخزين-اثاث-بالرياض/

Packers And Movers Pune disse...


Superb post, we enjoyed each and everything as per written in your post. Thank you for this informative article because it’s really helpful, I really like site.
Please visit our website: Packers And Movers Pune

Packers and Movers Gurgaon disse...

Really impressive post. I read it whole and going to share it with my social circules. I enjoyed your article and planning to rewrite it on my own blog Packers And Movers Gurgaon
Packers And Movers Mirpur Gurgaon
Packers And Movers Khor Gurgaon
Packers And Movers Jawasi Gurgaon
Packers And Movers Indir Mewat Gurgaon
Packers And Movers Dlf Ph-ii Gurgaon