ATPS Construçao De Algortimo

ETAPA 4 (tempo para realização: 10 horas)

 Aula-tema: Estruturas de dados compostas unidimensionais, vetores. Conceito,

utilizações, exemplos e exercícios. Estruturas de dados compostas

multidimensionais, matrizes. Conceito, utilizações, exemplos e exercícios.

Esta atividade é importante para que você consolide sua habilidade em trabalhar com

vetores e matrizes sabendo qual usar corretamente nas aplicações encontradas.

Para realizá-la, devem ser seguidos os passos descritos.

Jeanne Dobgenski

Sistemas de Informação - 1a. Série - Construção de Algoritmos

PASSOS

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/0ByrqRhRetWzEcE1

5R19pUlZubkU>. Acessos em: 15 abr. 2013.

3. Ler e estudar o material: Problema de Josephus. Disponível em:

<https://drive.google.com/a/anhanguera.com/?tab=mo#folders/0ByrqRhRetWzEcE1

5R19pUlZubkU>. Acesso em: 15 abr. 2013.

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.

A Figura 2 apresenta um exemplo com 5 pessoas e passo 2: neste exemplo, o elemento

restante é 3 (pessoa número 3).

Pág. 10 de 12

Jeanne Dobgenski

Sistemas de Informação - 1a. Série - Construção de Algoritmos

Pág. 11 de 12

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

Exemplo de Entrada Exemplo de Saída

4

5 2

10 3

100 15

1345 143

Case 1: 3

Case 2: 4

Case 3: 42

Case 4: 1199

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

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