MAC324 - Estruturas de Dados para Engenharia

Poli/Elétrica - 1o. Semestre de 1999

Desafio - O Problema de Josephus

Vimos como resolver o problemas de Josephus com parâmetros m e n com um algoritmo que tem tempo de execução proporcional a mn. Lembremos que n é o número de pessoas e que executamos cada m-ésima pessoa ainda viva.

O desafio, valendo meia-dúzia de Toblerones, é encontrar um algoritmo com tempo de execução proporcional a n log n (em particular, isto é independente de m). Note que, por exemplo, se m é algo como raiz quadrada do número de pessoas, este algoritmo é muito mais rápido que aquele visto em sala, pelo menos para um número grande de pessoas.


Página principal de MAC324 (Poli - 1o. semestre de 1999).
Página de aulas de MAC324 (Poli - 1o. semestre de 1999).
Netscape-HTML Checked!
Y. Kohayakawa <yoshi@ime.usp.br>

Last modified: Mon Mar 1 02:45:48 EST 1999