PROBLEMA DE JOSEPHUS

BREVIÁRIO ACADÊMICO #2

Trago um algoritmo bastante simples feito na Linguagem de Programação C, que soluciona um problema proposto pelo matemático Flavius Josephus em meados do ano 64. De acordo com lenda, um grupo de rebeldes, dentre eles Josephus, foram encurralados em uma caverna pelo exército inimigo. Preferindo o suicídio à captura, os rebeldes decidiram formar um círculo em que o primeiro deveria matar o soldado diretamente ao seu lado até sobrar apenas um, que sozinho, tiraria a própria vida. Josephus era o único que não queria morrer, e era impossível convencer os demais a se entregar. Então a única saída seria descobrir qual a posição do soldado que iria sobreviver. A solução pode ser obtida resolvendo o problema manualmente, simulando as mortes uma por uma, mas se o número de soldados for muito grande então a contagem fica inviável. Para encontrar tal solução com um número arbitrário de soldados basta conhecer alguns conceitos de potenciação, recorrências e indução finita.

A solução é bastante conhecida e está detalhada em diversos artigos e matérias na internet. O algoritmo a seguir trás todas as soluções de 1 até n, que representa o número de soldados que você escolher. Dessa forma, é possível notar o padrão e visualizar melhor a solução.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(){	
	int n, i, j, m[2][10000];
	printf("n = ");
	scanf("%i", &n);
	for(i = 2; i <= n; i++){
		m[0][i] = i;
		for(i = 2; i <= n; i++)
			for(j = 0; j < i; j++){	
				if(pow(2,j) <= i)
					m[1][i] = (2*(i - pow(2,j)) + 1);
			}
		printf("\nRESPOSTA: %i\n\n", m[1][n]);

		for(i = 2; i <= n; i++){
			printf("%i\t", i);
			printf("%i\n", m[1][i]);
		}
	}
	getch();
}

Inicialmente é definido n como o número de soldados, em seguida é calculado a maior potência de base 2 menor ou igual a número de soldados, chamaremos de J.

Ao conhecer J , basta fazer, 2(n – J) + 1.