sábado, 18 de outubro de 2014

C++ - Josephus Problem

Olá pessoal, nesse post nós iremos falar sobre o problema de Josephus (Josephus Problem), em português você encontrará "Problema de Josefo".

Para saber um pouco mais sobre a história:


Basicamente o problema é determinar qual a última pessoa que restará em um círculo de pessoas dado um salto.

Exemplo: 1, 2, 3, 4, 5

Vamos supor um salto "k" com o valor 2 e "n" com o valor 5 (cinco pessoas). A primeira pessoa a ser removida é a de número 2 (começa a contar a partir do 1).

Foi removida a pessoa 2, então restam: 1, 3, 4, 5

A pessoa corrente é 1 porque a pessoa 2 foi eliminada, então a corrente passa a ser a pessoa de número imediatamente anterior.

A próxima pessoa a ser eliminada é a 4. A pessoa corrente passa a ser a pessoa 3. A próxima a ser eliminada é a 1. A pessoa corrente passa a ser a 5.

A próxima eliminada é a 4, a pessoa corrente e a única restante é a pessoa 3 que é a resposta para f(5,2). Vamos ao código (não explicarei o código, pois o mesmo está devidamente comentado).



Nenhum comentário: