Problema Flavia

O problema de Josephus

Segue uma cópia do Program 3.9, p.94, do Sedgewick:

#include <stdlib.h>

// O programa abaixo constroi uma lista encadeada circular para

// representar uma "roda" de N pessoas numeradas de 1 a N.

// Em seguida, elimina cada M-ésima pessoa da lista a partir da

// primeira. Imprime o número da pessoa que sobrar.

int main (int argc, char *argv[])

{

int i, N = atoi(argv[1]), M = atoi(argv[2]);

link t, x;

x = t = malloc(sizeof (struct node));

t->item = 1;

t->next = t;

for (i = 2; i <= N; i++) {

x->next = malloc(sizeof (struct node));

x = x->next;

x->item = i;

x->next = t;

}

while (x != x->next) {

for (i = 1; i < M; i++)

x = x->next;

printf("%d morre\n", x->next->item);

x->next = x->next->next;

}

printf("sobrou %d\n", x->item);

return 0;

}

A rigor, eu deveria ter usado a função free para a liberar memória alocada por malloc quando ela não é mais necessária.

A propósito, vários livros de Flavius Josephus podem ser encontrados no Projeto Gutenberg. Eu até copiei o "The Antiquities of the Jews". É claro que isso é uma tradução do latin para o inglês: a língua inglesa não existia quando o livro foi escrito . . .

Exercícios

Resolva o problema de Josephus usando um vetor em lugar de uma lista. Discuta as vantagens e desvantagens.

Implemente o crivo de Eratóstenes usando uma lista no lugar do vetor a. Discuta as vantagens e desvantagens.

Escreva um função que imprima o conteúdo (campo item) de uma lista encadeada circular como a usada no problema de Josephus.

[Sedg 3.24, p.95] Escreva uma função que, ao receber o endereço de um nó de uma lista encadeada circular, devolva o número de nós da lista.

[Sedg 3.27, p.96] Dados (os endereços de) nós x e t de uma lista encadeada circular, desloque o nó seguinte a t para a posição que segue o nó x. Escreva um fragmento de código que faça o serviço.

[Sedg 3.28, p.96] O programa 3.9 de Sedgewick faz duas vezes mais atribuições de links que o necessário porque insiste em manter uma lista circular no início de cada iteração durante a fase de construção da lista. Modifique o programa para que evitar esse trabalho extra.

[South Pacific Contest, 1993] Um problema de Josephus é "de ordem M" se as pessoas são eliminados da roda de M em M. Dados inteiros positivos N1 e N2, decidir qual o menor k tal que a pessoa k não será a sobrevivente de um problema de Josephus de ordem 15 qualquer que seja N no intervalo fechado [N1,N2]. (O problema pode não ter solução). Versão mais complicada: o processo de eliminação pode acontecer tanto no sentido crescente (ou seja, a contagem é 1, 2, 3, . . . quanto no sentido decrescente (ou seja, a contagem é N, N-1, N-2, . . . ).

[Transformar vetor em lista] Escreva uma função recursiva que receba um vetor de inteiros a[p..r] e construa uma lista encadeada com o mesmo conteúdo do vetor. A lista deve terminar com NULL (ou seja, não deve ser circular).

Inversão de lista

A função abaixo é cópia do Program 3.10, p.98, do Sedgewick.

typedef struct node *link;

struct node {

int item;

link next;

};

// A função reverse recebe o endereço do primeiro nó de

// uma lista encadeada cujo último nó aponta para NULL.

// A função inverte a lista (ou seja, faz com que o último nó

// seja o primeiro, o penúltimo seja o segundo etc.) e devolve

// o endereço do primeiro nó da nova lista.

link reverse (link x)

{

link t, y = x, r = NULL;

while (y != NULL) {

t = y->next;

y->next = r;

r = y;

y = t;

}

return r;

}

Invariante: No começo de cada iteração, imediatamente antes da comparação de y com NULL,

y é o começo de um segmento final da lista original e

r é o resultado da inversão do correspondente segmento inicial da lista original.

Exercícios

[Sedgewick 3.61, p.115] Escreva uma função que faça um serviço análogo ao do programa de busca de palavra em um texto mas use listas encadeadas para representar o texto e a palavra. Suponha que cada nó da lista contém um caracter. Para testar sua função, escreva uma main que encontre todas as ocorrências de uma palavra um texto. Melhor: troque todas