Ajuda com problema de Josephus.

[kassuy]

Então galera, sou iniciante na área de programação, e me deparei com o seguinte problema:

 

O problema de Josephus é um jogo que simula um suicídio em massa: n pessoas, numeradas de 1 a n, estão sentadas em um círculo. Começando na pessoa 1, um revólver é passado de mão em mão para as pessoas subsequentes. Após m passos, a pessoa que estiver segurando o revólver comete suicídio e seu corpo é removido, a lista se reconfigura (diminuindo de tamanho) e o revólver passa para a pessoa seguinte à que morreu. Haverá apenas um sobrevivente ao final do jogo.

 

Exemplo: se m = 0 e n = 5, então os suicídios são cometidos em ordem e o sobrevivente é a pessoa número 5.

Se m = 1 e n = 5, então a ordem dos suicídios é 2, 4, 1, 5 e o sobrevivente é a pessoa número 3.

 

Aí então que vem minha dúvida. Eu preciso simular este jogo, em linguagem C, lendo M e N do teclado, montando uma lista circular de N nomes. Onde eu preciso, no final, no "mostrar fila", exibir a sequencia em que os nomes são removidos da lista, que no caso são os suicídios, e o nome do último sobrevivente.

 

O máximo que eu consegui fazer foi o seguinte:

#include<stdio.h>#include<malloc.h>#include<stdlib.h>typedef struct caixa {    int valor;    struct caixa* prox;} Caixa;typedef struct fila {    Caixa* inicio;    Caixa* fim;} Fila;Fila* fila;int primeiro = 1;void inicializa_fila() {    fila = (Fila*) malloc(sizeof(Fila));    if(fila == NULL) {        printf("Memoria insuficiente\n");        exit(1);    }    fila->inicio = NULL;    fila->fim = NULL;}void enqueue(int elemento) {    if(primeiro == 1) {        Caixa* caixa = (Caixa*) malloc(sizeof(Caixa));        fila->inicio = caixa;        fila->fim = caixa;        caixa->prox = NULL;        caixa->valor = elemento;        primeiro = -123;    } else {        Caixa* caixa = (Caixa*) malloc(sizeof(Caixa));        caixa->valor = elemento;        caixa->prox = NULL;        Caixa* aux = fila->fim;        aux->prox = caixa;        fila->fim = caixa;    }}int dequeue() {    int elemento;    Caixa* aux = fila->inicio;    elemento = aux->valor;    if(fila->inicio == fila->fim) {        fila->fim = NULL;    }    fila->inicio = aux->prox;    free(aux);    return elemento;}void mostrar_fila() {    Caixa* aux = fila->inicio;    while(aux != NULL) {        printf("%d ", aux->valor);        aux = aux->prox;    }    printf("\n");}void main() {}

Será que alguém poderia me dar uma força?

Para fazer a fila virar circular eu tenho que apontar para o final da lista em vez de NULL?

Como eu implemento este problema no que já foi feito até agora?
Sugestões, por favor.
Obrigado desde já!

[ScreenBlack]

Segue:

#include<stdio.h>#include<malloc.h>#include<stdlib.h>typedef struct tCaixa{    int valor;    int status;    struct tCaixa* prox;} Caixa;typedef struct tFila{    int quantidade;    int ativos;    struct tCaixa *inicio;} Fila;/*    Cria um elemento fila e define valores padrões*/Fila * inicializar_fila(void){    Fila *fila = malloc( sizeof(Fila) );    if ( fila == NULL )    {        printf("Memoria insuficiente\n");        exit(1);    }    fila->quantidade = 0;    fila->ativos = 0;    fila->inicio = NULL;    return fila;}/*    Remove todas os elementos da fila circular (geralmente só o sobrevivente)*/Fila * finalizar_fila(Fila *fila){    int tmp = 0;    Caixa *tmpCaixa = NULL;    for ( tmp = 0; tmp < fila->quantidade; tmp++ ) // Remoção dos elementos da fila    {        tmpCaixa = fila->inicio;        fila->inicio = fila->inicio->prox;        free(tmpCaixa);    }    free(fila); // Liberação do controlador da fila    return NULL;}/*    Insere elementos na fila circular*/void enfileirar(Fila *fila){    Caixa *caixa = NULL;    Caixa *tmpCaixa = fila->inicio;    if ( fila->inicio == NULL ) // Insere primeiro elemento caso fila esteja vazia    {        fila->inicio = malloc( sizeof(Caixa) );        fila->quantidade++;        fila->ativos++;        fila->inicio->valor = fila->quantidade;        fila->inicio->status = 1;        fila->inicio->prox = fila->inicio;    }    else // Insere novos elementos na última posição controlada pela variável quantidade    {        while ( tmpCaixa->valor < fila->quantidade )            tmpCaixa = tmpCaixa->prox;        caixa = malloc( sizeof(Caixa) );        fila->quantidade++;        fila->ativos++;        caixa->valor = fila->quantidade;        caixa->status = 1;        caixa->prox = tmpCaixa->prox;        tmpCaixa->prox = caixa;    }}/*    Remoção dos elementos da fila baseada na quantidade de passos, até sobrar um sobrevivente*/void desenfileirar(Fila * fila, int qtdPassos){    int passos = 0;    Caixa *tmpCaixa = fila->inicio;    while ( fila->ativos > 1 ) // Enquanto tiver mais de um sobrevivente    {        if ( tmpCaixa->status == 1 ) // Se a pessoa estiver viva, conta o passo a ser dado            passos++;        while ( passos < qtdPassos + 1 ) // Percorre a fila até alcançar a quantidade de passos        {                tmpCaixa = tmpCaixa->prox;                if ( tmpCaixa->status == 1 )                    passos++;        }        if ( fila->ativos == 1 ) // Se houver apenas uma pessoa ativa (viva), será a sobrevivente            printf("Pessoa %d sobreviveu\n", tmpCaixa->valor );        else        {            printf("Pessoa %d morreu\n", tmpCaixa->valor );            tmpCaixa->status = 0;            fila->ativos--;        }        passos = 0;    }}/*    Lista o estado das pessoas (vivas ou mortas)*/void mostrar_fila(Fila *fila){    int tmp = 0;    Caixa *tmpCaixa = fila->inicio;    for ( tmp = 0; tmp < fila->quantidade; tmp++ ) // Percorre a fila baseado na quantidade    {        printf("Pessoa: %d - Status: %d \n", tmpCaixa->valor, tmpCaixa->status ); // Status 1: Viva - Status 0: Morta        tmpCaixa = tmpCaixa->prox;    }}/*    Lista apenas as pessoas vivas*/void mostrar_fila_ativa(Fila *fila){    int tmp = 0;    Caixa *tmpCaixa = fila->inicio;    for ( tmp = 0; tmp < fila->quantidade; tmp++ )    {        if ( tmpCaixa->status == 1 )            printf("Caixa: %d\n", tmpCaixa->valor);        tmpCaixa = tmpCaixa->prox;    }}/*    Demonstração de que a fila realmente está circular    Lista as 20 posições sequenciais*/void mostrar_fila_20(Fila *fila){    int tmp = 0;    int tmp_2 = 0;    Caixa *tmpCaixa = fila->inicio;    for ( tmp = 0; tmp < 4; tmp++ ) // Mostra 4 linhas    {        for ( tmp_2 = 0; tmp_2 < 5; tmp_2++ ) // Mostra 5 pessoas por linha (5 x 4 = 20)        {            if ( tmp != 4 && tmp_2 != 5 )                printf(" Caixa: %d -> ", tmpCaixa->valor);            else                printf(" Caixa: %d", tmpCaixa->valor);            tmpCaixa = tmpCaixa->prox;        }        printf("\n");    }}int main(void){    int qtdPessoas = 0;    int qtdPassos = 0;    int tmp = 0;    Fila *fila = inicializar_fila();    printf("Quantidade de participantes: ");    scanf("%d", &qtdPessoas);    printf("Quantidade de passos: ");    scanf("%d", &qtdPassos);    for ( tmp = 0; tmp < qtdPessoas; tmp++ )        enfileirar( fila );    printf("-- Inicio --\n");    mostrar_fila( fila );    desenfileirar(fila, qtdPassos);    printf("-- Fim --\n");    mostrar_fila( fila );    fila = finalizar_fila(fila);    return 0;}

OBS: Tópico relacionado com: http://forum.clubedohardware.com.br/forums/topic/1095050-ajude-me-a-comentar-o-c%C3%B3digo/