Teste De Algoritimo

Emulação de sistemas reais

• Levantamento de estatísticas

– Não envolve pessoas/sistemas reais

– Situações extremas podem ser testadas

– Intervalos de tempo “irreais” podem ser avaliados

Simulação

• 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

eliminada2

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.

Simulação

Problema de Josephus – Solução 1

• Pessoas: elementos em uma lista ligada

• Cada passe da batata é uma operação next em um

iterator da lista ligada.3

Simulação

Problema de Josephus - Implementação

public static int josephus( int people, int passes) {

Collection theList = new LinkedList();

for (int i=1;i<=people;i++)

theList.add(new Integer(i));

Iterator its = theList.iterator();

while (people -- !=1) {

for (int i=0;i<=passes;i++) {

if (!itr.hasNext())

itr=theList.iterator();

itr.next();

}

itr.remove();

}

itr.theList.iterator();

return ((Integer) itr.next()).intValue();

}

O(MN)

Simulação

Problema de Josephus – Solução 2

•