Problema Josephus

Passo 2 (Aluno)

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

Passo 1 (Aluno)

Fazer as atividades apresentadas a seguir.

1. Retomar o estudo, em alguma bibliografia complementar - apresentadas na Etapa 1, dos capítulos referentes às variáveis compostas unidimensionais e multidimensionais.

2. Assistir ao vídeo: VisuALG - Aula 08 (Matrizes). Disponível em: <http://www.youtube.com/watch?v=gmtZSoyy0UI>. Disponível também em: <https://drive.google.com/a/anhanguera.com/?tab=mo#folders/0ByrqRhRetWzEcE15R19pUlZubkU>. Acessos em: 15 abr. 2013.

3. Ler e estudar o material: Problema de Josephus. Disponível em: <https://drive.google.com/a/anhanguera.