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:

http://www.cut-the-knot.org/recurrence/flavius.shtml

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

input:

10 3

output:

morreu 3
morreu 6
morreu 9
morreu 2
morreu 7
morreu 1
morreu 8
morreu 5
morreu 10
Sobrevivente 4

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.