Problema de Josephus

CÓDIGO-FONTE:
https://github.com/r-bauer/josephus/archive/master.zip


Na matemática um exemplo famoso de recorrência é atribuído a Flavius Josephus, um famoso historiador do primeiro século, que durante a guerra Judaica, se encontrava entre um bando de 41 judeus rebeldes encurralados pelos romanos em uma caverna.

Sem chance de fuga o grupo decide pela morte ao invés do aprisionamento, os rebeldes formam um circulo e começariam a partir de certo ponto pular duas pessoas e a matar a terceira pessoa numa direção fixa, a eliminação procede em torno do circulo que irá se tornando menor conforme as pessoas mortas são removidas, até não restar alguém vivo.

Conta à lenda que graça ao talento matemático de Josephus o mesmo conseguiu escapar desta tolice quanto ao suicídio ao encontrar o local no circulo inicial em que será o ultimo.

Determinada a tarefa, para buscar uma solução simples, podemos analisar a simulação grafica, com o seguinte circulo inicial:

Através da imagem percebe-se que a representação ideal para este tipo dado seria criar uma fila circular como primeiro passo.

Após o primeiro ciclo encontramos a fila circular com os elementos removidos, com as setas apontando para o elemento seguinte que continua na fila, associando assim ao tratamento de remoção feito por uma lista encadeada.

Uma lista pode armazenar o valor de forma mais intuitiva do que um vetor, que adicionaria um tratamento para mover os valores de índice no circulo inicial a cada exclusão, através da lista encadeada cada elemento mantém como informação o valor da posição original, descartando qualquer operação que não seja a de remover.

A solução reside no valor armazenado no ultimo nó a permanecer na lista encadeada

Ultimo ponto deve ser considerado antes programar a solução, Flavius Josephus atribui em sua biografia que devido à sorte ou a mão de Deus, ele e outro homem resolveram se entregar aos romanos, fato que inclui uma variação no problema, uma vez que historiadores consideram o tal homem como um cúmplice de Josephus, como a morte era administrada pela próxima escolha na fila, a forma de Josephus evitar o ato de assassinar um colega implica que ele colocou alguém de comum acordo para se render na penúltima posição.

Fugindo do tópico, gostaria de deixar indicado o filme cômico A vida de Brian feito pelo Monty Python narrando às engraçadas desventuras de um pobre judeu ante aos romanos, motivo pelo qual a fuga de Josephus sempre me faz associar com está película.

Para o código exemplo a ser apresentado, será utilizadas as rotinas mostradas em lista encadeada genérica parte 1 e parte 2, com a devida adaptação, a primeira é o formato do nó a ser utilizado que irá manter o numero da posição inicial no circulo, sua declaração no arquivo llapp.h resulta em:

// A lista de noh consiste em: typedef struct tagSNODEDATA {     unsigned int uPos;     // posicaoh da pessoa na fila }SNODEDATA;

                Para resolver o problema, ao criar a lista para simulação os dados que serão inseridos com a função a rotina AddNodeAtHead com valores já ordenados.

L = CreateLList(  CreateData,                         DeleteData,                         DuplicatedNode,                         NodeDataCmp);       for (iCount = 1; iCount <= iPerson; ++iCount)             AddNodeAtHead(L, &iCount);

                Tendo a criação da lista sido concluída, o resultado que se tem na memória é:

Head

41

40

39

38

37

36

35

......

7

6

5

4

3

2

1

Tail

O que descarta as operações de comparação, duplicados e ordenação da lista que devem ser incluídas no arquivo llapp.c, DuplicateNode e NodeDataCmp, não serão chamadas, enquanto que DeleteData não precisa de processamento adicional pelo tipo simples de dados armazenado.

BOOL  DeleteData(void *data) {     free( data );     return TRUE; } int   DuplicatedNode(SLINK slkNewNode, SLINK slkListNode) {     return 2; // nunca serah chamada } int   NodeDataCmp(void *first, void *second) {     return ( 0 );       // nunca serah chamada }

               

Somente a implementação de CreateData será necessária.

void *CreateData(void *data) {       SNODEDATA *pNewData;       // aloca sua estrutura de dados       pNewData = (SNODEDATA *) malloc(sizeof(SNODEDATA));       // move os valores para a estrutura de dados       pNewData->uPos = *((int *) data);       // retorna o endereco da estrutura       return (pNewData); }

                Agora resta percorrer a lista como se está fosse um circulo, para tanto o seguinte trecho do código demonstra como a tarefa será efetivada.

slQueue = L->slkTail; while (1) {       // avancah para o proximo noh       slQueue = slQueue->prior;       // terminou de percorrer a lista       if (slQueue == NULL)             // transforma a lista em uma fila circular             slQueue = L->slkTail; }

                Dentro deste laço será incluído o contador de eliminação iCount que ao atingir o valor iSeq exclui o nó, reiniciando a contagem, processo que irá se repetir até o momento que eliminar todos os nós da lista, controlado pela variável L->uiCount que armazena o total de nós presentes.

Ao tornar a lista em uma fila circular, os ponteiros que indicam inicio (L->slkHead) e fim (L->slkTail) deveriam apontar-se entre si, como tal mudança implicaria em alterar as rotinas genéricas para este tipo de suporte, foi descartada, outra opção também ignorada seria fazer verificações quanto ao elemento ser de inicio ou fim. A solução mais simples foi incluir a variável slDel para indicar o elemento a ser excluído, funcionando como ponteiro para a posição previa.

slQueue = L->slkTail; iCount = 1; while (L->uiCount) {       slDel = slQueue;       slQueue = slQueue->prior;       if (slQueue == NULL)             slQueue = L->slkTail;       // conta ateh achar o valor da sequencia       if (iCount++ == iSeq) {             // reinicia a contagem             iCount = 1;             // elimina o numero da lista             DeleteNode(L, slDel);       } }

                Para armazenar a solução da ultima e penúltima posição nos ponteiros pLast e pSecLast, dentro da condicional que elimina os nós incluímos a outra verificação na variável que controla o total de nós na lista.

if (L->uiCount == 1)       *pLast = ((pND) slDel->pdata)->uPos; else if (L->uiCount == 2)       *pSecLast = ((pND) slDel->pdata)->uPos;

                A rotina completa recebe como entrada a quantidade de pessoas e a sequencia de eliminação através da linha de comando para o programa, e irá utilizar os ponteiros pLast e pSecLast para retornar as duas ultimas posições e imprimir o resultado na tela.

BOOL Josephus(int iPerson, int iSeq, int *pLast, int *pSecLast) {       SLIST *L;       int iCount;       SLINK slQueue, slDel;       L = CreateLList(CreateData,                         DeleteData,                         DuplicatedNode,                         NodeDataCmp);       for (iCount = 1; iCount <= iPerson; ++iCount)             AddNodeAtHead(L, &iCount);       slQueue = L->slkTail;       iCount = 1;       while (L->uiCount) {             slDel = slQueue;             slQueue = slQueue->prior;             if (slQueue == NULL)                   slQueue = L->slkTail;             if (iCount++ == iSeq) {                   iCount = 1;                   if (L->uiCount == 1)                         *pLast = ((pND) slDel->pdata)->uPos;                   else if (L->uiCount == 2)                         *pSecLast = ((pND) slDel->pdata)->uPos;                   DeleteNode(L, slDel);             }       }       return (TRUE); } int LLDriver(int argc, char *argv[]) {       int iPerson, iSeq, iLast, iSecLast;       iPerson = atoi(argv[1]);       iSeq = atoi(argv[2]);       Josephus(iPerson, iSeq, &iLast, &iSecLast);       printf("penultimo: %d\n", iSecLast);       printf("ultimo:    %d\n", iLast);       return (EXIT_SUCCESS); }

                Ao criar e rodar o projeto, o resultado na tela se apresentara da seguinte forma:

C:\Projects\Josephus\Debug>Josephus 41 3 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 1 2 4 5 7 8 10 11 13 14 16 17 19 20 22 23 25 26 28 29 31 32 34 35 37 38 40 41 2 4 7 8 11 13 16 17 20 22 25 26 29 31 34 35 38 40 2 4 8 11 16 17 22 25 29 31 35 38 2 4 11 16 22 25 31 35 2 4 16 22 31 35 4 16 31 35 16 31 16 31 31 31 penultimo: 16 ultimo:    31 C:\Projects\Josephus\Debug>Josephus 10 2 1 2 3 4 5 6 7 8 9 10 1 3 5 7 9 1 5 9 5 5 penultimo: 9 ultimo:    5

Todos os arquivos deste projeto se encontram armazenados no github,  o problema de Josephus permite outro caminho através da permutação fornecendo uma reposta  mais elegante comparada a simples simulação da contagem envolvendo lista encadeada, assunto que voltara a pauta com a postagem de recursividade.