O problema de Joseph

• Problema de Josephus

– N pessoas (numeradas de 1 a N) sentadas em um círculo

– Começando pela pessoa 1, uma batata quente é passada

para a pessoa do lado.

– Depois de M passes, a pessoa que está com a batata

quente é eliminada do círculo.

– A batata recomeça a ser passada pela pessoa ao lado da

eliminada

Simulação

Problema de Josephus

• M=0

– Pessoas eliminadas na ordem a partirda pessoa 1. Ganha a

última pessoa.

• M=1

– A ordem de eliminação de pessoas não é tão intuitiva.

– N=5, M=1:

• Começa com 1, passa para 2 que é eliminado

• 3 pega a batata, passa para 4 que é eliminado

• 5 pega a batata, passa para 1 que é eliminado

• 3 pega a batata, passa para 5 que é eliiminado. 3 ganha.

SOLUÇÃO COM LISTA LIGADA CIRCULAR :

(N ta definindo o numero de pessoas e M o numero de passes)

#include <stdio.h>

#include <stdlib.h>

#define N 5

#define M 0

struct cel {

int info;

struct cel *prox;

};

typedef struct cel Celula;

void insere (int, Celula **);

void mostra_vencedor (Celula *);

void josephus (Celula **);

void encontra (Celula **p);

void elimina (Celula **p);

int main () {

int cont;

Celula *pessoa = NULL;

printf("%d pessoas.\n", N);

printf("%d passes.\n", M);

for (cont = 1; cont <= N; ++cont)

insere (cont, &pessoa);

josephus (&pessoa);

mostra_vencedor (pessoa);

return EXIT_SUCCESS;

}

void insere (int num, Celula **p) {

Celula *nova;

nova = (Celula *) malloc (sizeof (Celula));

nova->info = num;

if