Algoritmo

Trabalhos, Monografias, Artigos, Exames, Resumos de livros, Dissertações

Trabalhos Gratuitos

Trabalho Completo ALgoritmo

ALgoritmo

Imprimir Trabalho!

Cadastre-se - Buscar 155 000+ Trabalhos e Monografias

Categoria: Tecnologia

Enviado por: tramos3 23 setembro 2013

Palavras: 615 | Páginas: 3

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.

A Figura 2 apresenta um exemplo

Passo 2 (Individual)

1 Ler e analisar atentamente o próximo e último problema proposto no concurso.

2 Descrever sua sugestão de solução para o problema, levando em consideração o estudo

bibliográfico realizado.

3 Indicar a estrutura de dados recomendada para o problema, justificando-a.

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.

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: 7 abr. 2013.

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

Jeanne Dobgenski

Pág. 10 de 10

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