Estoque Medio

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, numerados de 1 a N. O número M representa o tamanho do passo entre duas pessoas no círculo.

CST em Análise e Desenvolvimento de Sistemas - 2ª. Série - Construção de Algoritmos

Jeanne Dobgenski

Pág. 11 de 12

A Figura 2 apresenta um exemplo com 5 pessoas e passo 2: neste exemplo, o elemento restante é 3 (pessoa número 3).

Figura 2 – Configuração dos números com LEDs

Fonte: Figura extraída de <http://www.urionlinejudge.com.br/judge/problems/view/1030>. Acesso em: 07 abr. 2013.

Saída

Para cada caso de teste, haverá uma linha de saída no seguinte formato: Case N: M sempre com um espaço antes de N e M. Sendo M a pessoa que restou no círculo.

Exemplo

Quadro 4 – Exemplo de entrada e saída de um algoritmo correto que soluciona o problema.

Fonte: Desenvolvido pela autora.

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 apresentado no enunciado do problema e de outro escolhido pelo grupo para mostrar o funcionamento correto do algoritmo. Sugere-se usar desenhos e/ou representações gráficas sempre que possível.

Passo 3 (Equipe)

1. Incluir todas as informações vistas nos passos anteriores no Relatório 4 – Solução para o Problema 4. Entregar o relatório ao professor da disciplina conforme seu planejamento.

2. Reunir todas as informações vistas durante as etapas, referentes ao projeto proposto no desafio, e elaborar uma apresentação em Power Point.

3. Apresentar ao professor envolvido na ATPS e demais convidados a apresentação para a classificação final das equipes.

Exemplo de Entrada

Exemplo de Saída

4

5 2

10 3

100