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.


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

Manish Packers and Movers Pvt Ltd disse...

Manish Packers and Movers Pvt Ltd as a Services providing company can make all the difference to your Home Relocation experience. Indore based Company which offers versatile solutions, Right team that easily reduce the stress associated with a Household Shifting, Vehicle Transportation. we help things run smoothly and reduce breakages and offer you seamless, Affordable, Reliable Shifting Services, Compare Shifting Charges, Visit :
Manish Packers and Movers Ptv Ltd @ https://www.manishpackersmoversindore.in/
Packers and Movers Indore @ https://www.manishpackersmoversindore.in/packers-and-movers-indore.html
Manish Packers Indore @ https://www.manishpackersmoversindore.in/manish-packers-and-movers-indore.html
Packers and Movers Gurgaon @ https://www.manishpackersmoversindore.in/packers-movers-gurgaon.html
Packers and Movers Kolkata @ https://www.manishpackersmoversindore.in/packers-movers-kolkata.html
Packers and Movers Mumbai @ https://www.manishpackersmoversindore.in/packers-movers-mumbai.html
Packers and Movers Bhopal @ https://www.manishpackersmoversindore.in/packers-movers-bhopal.html
Packers and Movers Nagpur @ https://www.manishpackersmoversindore.in/packers-movers-nagpur.html
Packers and Movers Raipur @ https://www.manishpackersmoversindore.in/packers-movers-raipur.html
Packers and Movers Ahmedabad @ https://www.manishpackersmoversindore.in/packers-movers-ahmedabad.html

Manish Packers and Movers Pvt Ltd disse...

Packers and Movers Dewas Naka Indore
Packers and Movers Vijay Nagar Indore
Packers and Movers Scheme 54 Indore
Packers and Movers Delhi
Packers and Movers Pune
Packers and Movers Jodhpur
Packers and Movers Kanpur
Packers and Movers Ghaziabad
Packers and Movers Noida
Packers and Movers Navi Mumbai

Manish Packers and Movers Pvt Ltd disse...

Best Movers and Packers in India for Moving and Shifting Door to Door Transportation Services to all over India. Visit More :-
Manish Packers and Movers Pvt Ltd Blog
Packers and Movers Bhopal
Packers and Movers Jabalpur
Packers and Movers Vadodara
Packers and Movers Udaipur
Packers and Movers Jaipur
Packers and Movers Chandigarh
Packers and Movers Chennai
Packers and Movers Hyderabad
Packers and Movers in Indore

Manish Packers and Movers Pvt Ltd disse...

Hire Manish Packers and Movers Pvt Ltd in India for hassle-free Household Shifting, Office Relocation, Car Transportation, Loading Unloading, packing Unpacking at affordable Price Quotation. Top Rated Safe and Secure Service Providers who can help you with 24x7 and make sure a Untroubled Relocation Services at Cheapest/Lowest Rate. Visit More :-
Manish Packers and Movers Pvt Ltd
Packers and Movers Bangalore
Packers and Movers Gurgaon
Packers and Movers Indore
Packers and Movers Kolkata
Packers and Movers Mumbai
Packers and Movers Nagpur
Packers and Movers Ahmedabad
Manish Packers in Indore
Manish Packers and Movers Pvt Ltd Sitemap