ATIVIDADES PRTICAS SUPERVISIONADAS

CST em Anlise e Desenvolvimento de Sistemas

2 Srie Construo de Algoritmos A atividade prtica supervisionada (ATPS) um procedimento metodolgico

de ensino-aprendizagem desenvolvido por meio de um conjunto de etapas

programadas e supervisionadas e que tem por objetivos:

Favorecer a aprendizagem.

Estimular a corresponsabilidade do aluno pelo aprendizado eficiente e

eficaz.

Promover o estudo, a convivncia e o trabalho em grupo.

Desenvolver os estudos independentes, sistemticos e o autoaprendizado.

Oferecer diferentes ambientes de aprendizagem.

Auxiliar no desenvolvimento das competncias requeridas pelas Diretrizes

Curriculares Nacionais dos Cursos de Graduao.

Promover a aplicao da teoria e conceitos para a soluo de problemas

prticos relativos profisso.

Direcionar o estudante para a busca do raciocnio crtico e a emancipao

intelectual.

Para atingir estes objetivos, a ATPS prope um desafio e indica os passos a

serem percorridos ao longo do bimestre para a sua soluo.

A sua participao nesta proposta essencial para que adquira as

competncias e habilidades requeridas na sua atuao profissional.

Aproveite esta oportunidade de estudar e aprender com desafios da vida

profissional.

AUTORIA

Jeanne Dobgenski

Anhanguera Educacional

CST em Anlise e Desenvolvimento de Sistemas 2 Srie - Construo de Algoritmos

Jeanne Dobgenski

Pg. 2 de 10

COMPETNCIAS E HABILIDADES

Ao concluir as etapas propostas neste desafio, voc ter desenvolvido as competncias e habilidades que constam nas Diretrizes Curriculares Nacionais descritas a seguir.

Identificar, analisar, documentar e solucionar problemas e necessidades passveis de soluo via computao.

Desenvolver pesquisa cientfica e tecnolgica. Saber conciliar teoria e prtica.

Produo Acadmica Relatrios parciais, com os resultados das pesquisas realizadas nas Etapas 1 a 4. Relatrio 1: Soluo para o Problema 1. Relatrio 2: Soluo para o Problema 2. Relatrio 3: Soluo para o Problema 3. Relatrio 4: Soluo para o Problema 4. Relatrio final em arquivo .doc para postagem e avaliao.

Participao Esta atividade ser, em parte, desenvolvida individualmente pelo aluno e, em parte,

pelo grupo. Para tanto, os alunos devero: organizar-se, previamente, em equipes de quatro a oito participantes; entregar seus nomes, RAs e e-mails ao tutor presencial da disciplina e observar, no decorrer das etapas, as indicaes: Individual e Equipe.

Padronizao O material a ser produzido neste desafio deve ser estruturado de acordo com as

normas da ABNT1, com o seguinte padro: em pginas de formato A4; com margens esquerda e superior de 3cm, direita e inferior de 2cm; fonte Times New Roman tamanho 12, cor preta; espaamento de 1,5 entre linhas; se houver citaes com mais de trs linhas, devem ser em fonte tamanho 10, com

um recuo de 4cm da margem esquerda e espaamento simples entre linhas; com capa, contendo:

logo da Anhanguera Educacional Uniderp; nome de sua Unidade de Ensino, Curso e Disciplina; nome e RA de cada participante; ttulo da atividade; nome do tutor a distncia da disciplina; cidade e data da entrega, apresentao ou publicao.

1 Consulte o Manual para Elaborao de Trabalhos Acadmicos. Unianhanguera. Disponvel em:

.

CST em Anlise e Desenvolvimento de Sistemas 2 Srie - Construo de Algoritmos

Jeanne Dobgenski

Pg. 3 de 10

DESAFIO

A Sociedade Brasileira de Computao (SBC) promove desde 1996, anualmente, a Maratona de Programao. Seu surgimento derivou das competies regionais classificatrias para as finais mundiais do concurso de programao do ACM (Association for Computing Machinery), o ACM International Collegiate Programming Contest, e parte da regional brasileira do concurso. A competio promove nos alunos da rea da Computao a criatividade, a capacidade de trabalho em equipe, a busca de novas solues de software e a habilidade de resolver problemas sob presso.

Tendo em vista que vrias universidades do Brasil desenvolvem concursos locais para escolher os melhores times para participar da Maratona de Programao, dentre os quais os melhores sero selecionados para participar das Finais Mundiais do evento, considere que voc e sua equipe esto se preparando para se candidatarem ao concurso local de sua instituio de ensino, para represent-la na etapa nacional dessa competio. Dessa forma, participaro de um concurso de Construo de Algoritmos que compreender a elaborao de algoritmos que solucionem problemas de baixa, mdia e alta complexidade no contexto de seu nvel escolar.

Objetivo do Desafio Analisar e resolver problemas de programao e sistemas computacionais,

apresentando um conjunto de relatrios sobre o estudo efetuado, com o propsito de vencer o concurso de Construo de Algoritmos.

ETAPA 1

Esta atividade importante para que voc desenvolva a capacidade de compreender e solucionar problemas por meio do emprego de conceitos, tcnicas e recursos computacionais, construindo algoritmos corretamente.

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

PASSOS

Passo 1 (Individual)

1 Estudar, na bibliografia recomendada ao final deste passo, os captulos que se referem aos contedos: Lgica de Programao, Tpicos Preliminares e Estruturas de Controle.

2 Assistir ao vdeo indicado a seguir:

VisuALG - Aula 01 (Princpios Bsicos). Disponvel em: . Compartilhado em: . Acesso em: 15 abr. 2013.

3 Ler o Manual do VisualALG. Disponvel em:

. Compartilhado em:

CST em Anlise e Desenvolvimento de Sistemas 2 Srie - Construo de Algoritmos

Jeanne Dobgenski

Pg. 4 de 10

EcE15R19pUlZubkU>. Acesso em: 15 abr. 2013.

Bibliografia complementar

PIVA JUNIOR, Dilermando (Org.). Algoritmos e Programao de Computadores. Vila Flor: Elsevier, 2012. (Livro-texto da disciplina).

MANZANO, Jos Augusto N. Garcia. Algoritmos: Lgica para Desenvolvimento de Programao de Computadores. 21. ed. So Paulo: rica, 2008.

FORBELLONE, A. L. Lgica de Programao. So Paulo: Pearson, 2008.

ASCNCIO, Ana Fernanda Gomes; CAMPOS, Edilene A. V. de. Fundamentos da Programao de Computadores: algoritmos, pascal e C/C++. So Paulo: Pearson, 2003.

Passo 2 (Individual)

1 Ler e analisar atentamente o primeiro problema proposto no concurso.

2 Descrever sua sugesto de soluo para o problema, tendo em considerao o contedo bibliogrfico estudado.

Problema 1 Definir um nmero inteiro N, que ser o nmero de casos de teste. Cada caso de teste uma linha que contm dois nmeros inteiros X e Y. O problema se resume em imprimir a soma de todos os valores mpares entre os dois nmeros inteiros, excetuando-os.

Entrada A primeira linha de entrada um nmero inteiro N, que o nmero de casos de teste a serem solucionados. Cada caso de teste uma linha contendo dois inteiros X e Y.

Sada Imprimir a soma de todos os nmeros mpares entre X e Y.

Exemplo

Quadro 1 Exemplo de entrada e sada de um algoritmo correto que soluciona o problema Fonte: Desenvolvido pela Autora da ATPS.

Passo 3 (Equipe)

Discutir entre os integrantes da equipe as sugestes de soluo para o problema, elegendo a que ser apresentada no concurso. Compilar a soluo definida, considerando os itens a seguir. 1. Identificar os dados e variveis. 2. Apresentar tabelas verdades.

Exemplo de Entrada Exemplo de Sada 5 2 5 6 8 3 5 10 13 10 20

3 7 0 11 75

CST em Anlise e Desenvolvimento de Sistemas 2 Srie - Construo de Algoritmos

Jeanne Dobgenski

Pg. 5 de 10

3. Descrever o algoritmo em representao grfica e em pseudo-linguagem2. 4. Demonstrar o passo a passo do exemplo numrico apresentado no enunciado do

problema e de outro escolhido pelo grupo para mostrar o funcionamento correto do algoritmo. Sugere-se usar desenhos e/ou representaes grficas sempre que possvel.

Passo 4 (Equipe)

Incluir todas as informaes vistas nos Passos 1, 2 e 3 no Relatrio 1 Soluo para o Problema 1, seguindo as orientaes descritas no item Padronizao da ATPS. Guardar esse relatrio para composio do relatrio final.

ETAPA 2

Esta atividade importante para que voc aprenda a analisar e resolver problemas apresentando sua soluo por meio da estruturao de um algoritmo, especificando-o de maneira detalhada e realizando testes que o validem.

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

PASSOS

Passo 1 (Individual)

1 Buscar, nas referncias bibliogrficas complementares apresentadas na Etapa 1, subsdios para auxili-lo na compreenso do Problema 2. Por exemplo, ler os captulos 1 e 2 do livro indicado a seguir.

MANZANO, Jos Augusto N. Garcia. Algoritmos: Lgica para Desenvolvimento de Programao de Computadores. 21. ed. So Paulo: rica, 2008.

2 Assistir ao vdeo a seguir indicado:

VisuALG - Aula 02 (Se, Conectivos, Lgico). Disponvel em: . Compartilhado em: . Acesso em: 15 abr. 2013.

3 Assistir ao vdeo indicado:

VisuALG - Aula 03 (Caso, Aleatrio, Repita). Disponvel em: . Compartilhado em: . Acesso em: 15 abr. 2013.

Passo 2 (Individual)

1 Ler e analisar atentamente o prximo problema proposto no concurso Problema 2.

2 Descrever sua sugesto de soluo, baseando sua proposio nos estudos realizados.

2 A pseudo-linguagem (ou pseudo-cdigo) uma maneira intermediria, entre a linguagem natural e uma linguagem de

programao, de representar um algoritmo.

CST em Anlise e Desenvolvimento de Sistemas 2 Srie - Construo de Algoritmos

Jeanne Dobgenski

Pg. 6 de 10

Problema 2 Andreia est aprendendo Programao de Computadores. Ela acha tudo muito fcil, muito simples. Ela vai fazer um pequeno programa que l os nomes de seus amigos e a distncia de sua casa at a casa de cada um deles. Portanto, ela simplesmente quer calcular qual a distncia mdia entre a sua casa e a casa dos amigos (em metros). Mas Francisco, um programador mais experiente, avisou que s vezes o que parece simples pode ter alguns detalhes, dependendo da linguagem de programao usada para a implementao.

Entrada A entrada deve conter vrios casos de teste. Cada caso de teste composto por duas linhas. A primeira linha contm o nome de um amigo de Andreia. A segunda linha contm um nmero inteiro que indica a distncia mdia entre a casa de Andreia e a casa de um amigo.

Sada A sada deve ser um nmero com um dgito aps a vrgula e que indica a distncia mdia entre a casa de Andreia e a casa de seus amigos, como o exemplo a seguir.

Exemplo

Quadro 2 Exemplo de entrada e sada de um algoritmo correto que soluciona o problema Fonte: Desenvolvido pela Autora da ATPS.

Passo 3 (Equipe)

Discutir entre os integrantes da equipe as sugestes de soluo para o problema, elegendo a que ser apresentada no concurso. Compilar a soluo definida, considerando os itens a seguir. 1. Identificar os dados e variveis. 2. Apresentar tabelas verdades. 3. Descrever o algoritmo em representao grfica e em pseudo-linguagem. 4. Apresentar o passo a passo do exemplo numrico constante do enunciado do problema e

de outro escolhido pelo grupo para mostrar o funcionamento correto do algoritmo. Sugere-se usar desenhos e/ou representaes grficas sempre que possvel.

Nota No item 3, apresentar o pseudo-cdigo usando mdulos.

Passo 4 (Equipe)

Incluir todas as informaes vistas nos Passos 1, 2 e 3 no Relatrio 2 Soluo para o Problema 2, seguindo as orientaes descritas no item Padronizao da ATPS. Reservar esse relatrio parcial para composio do relatrio final.

Exemplo de Entrada Exemplo de Sada Mariana Oliveira 350 Joo Alberto 900 Flvia Marcondes 120 Horcio Dias 10

345.0

CST em Anlise e Desenvolvimento de Sistemas 2 Srie - Construo de Algoritmos

Jeanne Dobgenski

Pg. 7 de 10

ETAPA 3

Esta atividade importante para que voc desenvolva sua habilidade em trabalhar com vetores e matrizes como estruturas de dados.

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

PASSOS

Passo 1 (Individual)

1 Estudar, em alguma bibliografia complementar apresentada na Etapa 1, os captulos referentes s variveis compostas unidimensionais e multidimensionais.

2 Assistir ao vdeo a seguir indicado:

VisuALG - Aula 04 (Porcentagem, Substituir, Breakpoint). Disponvel em: . Compartilhado em: . Acesso em: 15 abr. 2013.

3 Assistir ao vdeo indicado:

VisuALG - Aula 07 (Vetores). Disponvel em: . Compartilhado em: . Acesso em: 15 abr. 2013.

Passo 2 (Individual)

1 Ler e analisar atentamente o prximo problema proposto no concurso.

2 Descrever sua sugesto de soluo para o problema, levando em considerao o estudo bibliogrfico realizado.

3 Indicar o uso de vetores ou matrizes, justificando a escolha.

Problema 3 Joo quer montar um painel contendo diferentes nmeros de LEDs. Como no h muitos, no tem certeza se vai ser capaz de montar o nmero desejado. Considerando-se a configurao dos LEDs conforme o exemplo da Figura 1, fazer um algoritmo que ajude Joo a descobrir quantos LEDs so necessrios para montar o nmero. Fonte: < http://www.urionlinejudge.com.br/judge/problems/view/1168 >. Acesso em: 7 abr. 2013.

Figura 1 Configurao dos nmeros com LEDs

Fonte: Figura extrada de . Acesso em: 7 abr. 2013.

CST em Anlise e Desenvolvimento de Sistemas 2 Srie - Construo de Algoritmos

Jeanne Dobgenski

Pg. 8 de 10

Entrada A entrada contm um nmero inteiro N (1 N 2000) correspondente ao nmero de casos de teste, seguido por N linhas, cada linha contendo um nmero (1 V 10100) que corresponde ao valor que Joo quer representar com LEDs.

Sada Para cada caso de teste, imprimir uma linha contendo o nmero de LEDs que Joo precisa para representar o valor desejado, seguido da palavra "leds".

Exemplo

Quadro 3 Exemplo de entrada e sada de um algoritmo correto que soluciona o problema Fonte: Desenvolvido pela Autora da ATPS.

Passo 3 (Equipe)

Discutir entre os integrantes da equipe as sugestes de soluo para o problema, elegendo a que ser apresentada no concurso. Compilar a soluo definida, considerando os itens a seguir. 1. Identificar os dados e variveis. 2. Descrever o algoritmo em pseudo-linguagem usando mdulos. 3. Apresentar o passo a passo do exemplo numrico dado no enunciado do problema e de

outro escolhido pelo grupo para mostrar o funcionamento correto do algoritmo. Sugere-se usar desenhos e/ou representaes grficas sempre que possvel.

Passo 4 (Equipe)

Incluir todas as informaes vistas nos Passos 1, 2 e 3 no Relatrio 3 Soluo para o Problema 3, seguindo as orientaes descritas no item Padronizao da ATPS. Esse relatrio far parte do relatrio final.

ETAPA 4

Esta atividade importante para que voc consolide sua habilidade em trabalhar com vetores e matrizes, sabendo qual usar corretamente nas aplicaes encontradas.

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

PASSOS

Passo 1 (Individual)

1 Retomar o estudo, em alguma bibliografia complementar apresentada na Etapa 1, dos

Exemplo de Entrada Exemplo de Sada 5 45 89 100 1010 134290

9 leds 13 leds 14 leds 16 leds 28 leds

CST em Anlise e Desenvolvimento de Sistemas 2 Srie - Construo de Algoritmos

Jeanne Dobgenski

Pg. 9 de 10

captulos referentes s variveis compostas unidimensionais e multidimensionais.

2 Assistir ao vdeo indicado a seguir:

VisuALG - Aula 08 (Matrizes). Disponvel em: . Compartilhado em: . Acesso em: 15 abr. 2013.

3 Ler e estudar o material a seguir indicado:

Problema de Josephus. Disponvel em: . Acesso em: 15 abr. 2013.

Passo 2 (Individual)

1 Ler e analisar atentamente o prximo e ltimo problema proposto no concurso.

2 Descrever sua sugesto de soluo para o problema, levando em considerao o estudo bibliogrfico 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 esto organizadas em um crculo, e que temos um inteiro positivo M N. Comeando com uma primeira pessoa designada, prosseguimos em torno do crculo, removendo cada M-sima pessoa. Depois que cada pessoa removida, a contagem prossegue em torno do crculo restante. Esse processo continua at todas as M pessoas terem sido removidas. A ordem em que as pessoas so removidas do crculo define a permutao 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 nmeros inteiros positivos N (1 N 10000) e M (1 M 1000). O nmero N representa a quantidade de pessoas do crculo, numeradas de 1 a N. O nmero M representa o tamanho do passo entre duas pessoas no crculo. A Figura 2 apresenta um exemplo com 5 pessoas e passo 2: neste exemplo, o elemento restante 3 (pessoa nmero 3).

Figura 2 Configurao dos nmeros com LEDs Fonte: Figura extrada de .

Acesso em: 7 abr. 2013.

CST em Anlise e Desenvolvimento de Sistemas 2 Srie - Construo de Algoritmos

Jeanne Dobgenski

Pg. 10 de 10

Sada Para cada caso de teste, haver uma linha de sada no seguinte formato: Case N: M sempre com um espao antes de N e M. Sendo M a pessoa que restou no crculo.

Exemplo

Quadro 4 Exemplo de entrada e sada de um algoritmo correto que soluciona o problema Fonte: Desenvolvido pela Autora da ATPS.

Passo 2 (Equipe)

Discutir as sugestes de soluo para o problema, elegendo a que ser apresentada no concurso. Compilar a soluo definida, considerando os itens a seguir. 1. Identificar os dados e variveis. 2. Descrever o algoritmo em pseudo-linguagem usando mdulos. 3. Apresentar o passo a passo do exemplo numrico dado no enunciado do problema e de

outro escolhido pelo grupo para mostrar o funcionamento correto do algoritmo. Sugere-se usar desenhos e/ou representaes grficas sempre que possvel.

Passo 3 (Equipe)

Incluir todas as informaes vistas nos passos anteriores no Relatrio 4 Soluo para o Problema 4. Esse relatrio far parte do relatrio final.

Passo 4 (Equipe e Individual)

1 Elaborar o Relatrio final com todos os relatrios parciais, uma concluso do que foi elaborado, seguindo as orientaes do item Padronizao desta ATPS.

2 Postar, individualmente, o relatrio final no ambiente virtual de aprendizagem (AVA), para avaliao e validao da nota pelo tutor a distncia.

Livro-Texto da Disciplina

PIVA JUNIOR, Dilermando (Org.). Algoritmos e Programao de Computadores. Vila Flor: Elsevier, 2012.

Critrios de Avaliao

Cumprimento das etapas da ATPS. Utilizao de bibliografia sugerida. Utilizao dos relatrios parciais para elaborao do relatrio final. Coerncia da teoria e prtica para finalizao do desafio.

Exemplo de Entrada Exemplo de Sada 4 5 2 10 3 100 15 1345 143

Case 1: 3 Case 2: 4 Case 3: 42 Case 4: 1199