Josephus Problem, resolvendo-o de maneira simples

Josephus Problem é um problema bem legal que estudei no livro Concrete Mathematics.

Josephus foi um historiador judeu do primeiro século. A lenda conta que ele e 40 de seus homens estavam presos em uma caverna pelos Romanos. Eles decidiram suicidar-se à ser capturados. Formaram um circulo e começaram a se matar, da 3ª à 3ªa pessoa em ordem da fila. Como Josephus não queria morrer, ele foi capaz de escolher o melhor lugar, afim de sobreviver, e juntar-se os Romanos que o capturaram.

O Problema

Na prática o problema teria N pessoas em um círculo, iria ser percorrido M – 1 pessoas e o M iria ser morto, assim por diante, até sobrar uma única pessoa.

A Solução

Podemos representar a solução por uma função recursiva, para N par e M = 2:

e para N ímpar e M = 2, temos:

Não vou postar a solução genérica aqui pois exige uma grande explicação e esse não é o objetivo do post. Você pode ver na wikipedia ou então comprar o livro, caso queria saber mais.

O interessante é que o algoritmo para solução genérica é bem simples em C++. Usando listas ligadas(linked lists) é simples, fácil de entender e super rápido a execução do programa.

Josephus.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include <iostream>
#include <cstdlib>
 
struct Pessoa {
	int num;
	Pessoa *prox;
	Pessoa(int x, Pessoa *p) {
		num = x;
		prox = p;
	}
};
 
int main(int argc, char *argv[]) {
	//'a' recebe primeira pessoa criada
	//e 'a' é linkado para si mesmo
	//depois 'b' é criado apontado para 'a'
	int N = atoi(argv[1]), M = atoi(argv[2]);
	Pessoa *a = new Pessoa(1, 0);
	a->prox = a;
	Pessoa *b = a;
 
	// Aloca na memória todas as pessoas
	// e 'b' recebe a última(enésima pessoa)
	// pois a contagem começa pela primeira('a')
	for (int i = 2; i <= N; ++i)
		b = (b->prox = new Pessoa(i, a));
 
	// Loop enquanto 'b' não estiver apontado
	// o próximo para ele mesmo
	while (b != b->prox) {
		// 'b' recebe a emésima pessoa
		for (int i = 1; i < M; ++i)
			b = b->prox;
		a = b->prox;
		b->prox = a->prox;
		delete a; // 'a' é morto =/
	}
 
	// O sobrevivente _o/
	std::cout << b->num << std::endl;
}

Ou então se preferir um link para o pastebin.

Analisando o Resultado

após compilar

g++ -o Josephus Josephus.cpp

rode o programa com N = 10 e M = 2

./Josephus 10 2

O valor deu 5? Verifique com a função. Bateu os valores?
Agora vá testando para 1 <= N <= 16 e M = 2.

for n in `seq 16`; do echo -n “$n: “; ./Josephus $n 2; done

Saída do loop:

1: 1
2: 1
3: 3
4: 1
5: 3
6: 5
7: 7
8: 1
9: 3
10: 5
11: 7
12: 9
13: 11
14: 13
15: 15
16: 1

Perceberam um certo padrão entre as respostas? A função genérica usa justamente esse padrão binário para solução.

Ultimamente eu estou mais dedicado ao estudo de algoritmos, C++, C e Python(é claro). Depois pretendo postar uma analise desse algoritmo passo a passo.