Algoritmos

Problema 4

O Problema de Josephus é definido como mostrado a seguir. Vamos supor que N pessoas

estão organizadas em um círculo, e que temos um inteiro positivo M ≤ N. Começando com

uma primeira pessoa designada, prosseguimos em torno do círculo, removendo cada

M-ésima pessoa. Depois que cada pessoa é removida, a contagem prossegue em torno do

círculo restante. Esse processo continua até todas as M pessoas terem sido removidas. A

ordem em que as pessoas são removidas do círculo define a permutação de Josephus de (N,

M) dos inteiros 1, 2, ... , N.

Entrada

Definir como NC (1 ≤ NC ≤ 30) os casos de teste. Em cada caso de teste de entrada haverá um

par de números inteiros positivos N (1 ≤ N ≤ 10000) e M (1 ≤ M ≤ 1000). O número N

representa a quantidade de pessoas do círculo, numeradas de 1 a N. O número M representa

o tamanho do passo entre duas pessoas no círculo.

Passo 2 (Equipe)

Discutir as sugestões de solução para o problema, elegendo a que será apresentada no

concurso. Compilar a solução definida, considerando os itens a seguir.

1. Identificar os dados e variáveis.

2. Descrever o algoritmo em pseudo-linguagem usando módulos.

3. Apresentar o passo a passo do exemplo numérico dado no enunciado do problema e de

outro escolhido pelo grupo para mostrar o funcionamento correto do algoritmo. Sugerese

usar desenhos e/ou representações gráficas sempre que possível.

Passo 3 (Equipe)

Incluir todas as informações vistas nos passos anteriores no Relatório 4 – Solução para o

Problema 4. Esse relatório fará parte do relatório final.