Algoritmo apostila1

  • Published on
    14-Jun-2015

  • View
    2.263

  • Download
    1

Embed Size (px)

Transcript

<ul><li> 1. Algoritmo CENTRO FEDERAL DEEDUCAO TECNOLGICA DE CAMPOS Curso Tcnico de Informtica Industrial Apostila de Algoritmos 20071</li></ul><p> 2. EMENTA:Estudo das formas para representao do pensamento lgico atravs detcnicas de desenvolvimento de algoritmos. Representao e manipulao dedados. Construes de algoritmos seqenciais, condicionais e com estruturas derepetio. Manipulao de estruturas de dados homogneas e heterogneas eutilizao de sub-rotinas.OBJETIVOS: Fornecer elementos e tcnicas que capacitem o aluno a construir algoritmos,atravs da identificao dos passos ou aes necessrios para transformar umconjunto de dados de entrada em informaes de resultado, promovendo dessaforma, um ambiente de prtica da lgica de programao.CONTEDO PROGRAMTICO:1. Algoritmo Bsico 1.1. Pascal2. Conceitos Bsicos 2.1. Lgica(problemas, soluo e resultado)3. Definio de Algoritmo e Pseudocdigo4. Algoritmo cotidiano X Algoritmos Computacionais5. Conceitos bsicos do funcionamento do computador e da memria6. Defini~]ao de variveis, constantes e tipos primitivos7. Estruturas Seqenciais e Estruturas de Seleo 7.1. Comando de Atribuio 7.2. Operadores aritmticos e funes matemticas 7.3. Comandos de entrada e sada 7.4. Operadores relacionais e operadores lgicos 7.5. Estrutura de seleo simples 7.6. Estrutura de seleo composta 7.7. Estrutura de mltipla escolha8. Estrutura de repetio 8.1. Conceito de contador e acumulador 8.2. Repetio com teste no incio (enquanto) 8.3. Repetio com teste no fim (repita) 8.4. Repetio com varivel de controle (para)9. Tipos Estruturados Homogneos (vetores e matrizes)BIBLIOGRAFIA BSICA (LIVROS TEXTOS):Manzano, J. A.; Oliveira, J. F.: Algoritmos - Lgica para desenvolvimento deProgramao. rica. SP. pp. 265. 1996.Forbellone, A. L. V; Eberspcher, H. F. Lgica de Programao. So Paulo,Ed. McGraw-Hill, 1993.Lages, G.: Algoritmos e Estruturas de Dados. So Paulo, Ed. LTC,1988.Tremblay, B.: Cincia dos Computadores. Uma abordagem Algortmica. So Paulo, Ed.McGraw-Hill, 1985. 3. AlgoritmoCRONOGRAMA DAS AULAS: Cada aula eqivale a 2 perodos (sujeito a alteraes)Aula 1-18 - Noes de Lgica. Fatores a serem considerados na construo dosAlgoritmos.- Mtodo para construir um algoritmo. Exerccios de fixao.- Tipos de Informaes, Dados (tipos primitivos de dados), Constantes xVariveis, - Variveis: uso, nomenclatura, declarao e atribuio.- Operadores matemticos, funes matemticas.- Instrues (comandos ) bsicos: entrada e sada, blocos de programas.- Portugus estruturado. Exerccios de fixao. Algoritmos seqenciais.- Estruturas de controle - Algoritmos com seleo- Desvio condicional simples. - Desvio condicional composto e aninhados.- Mltiplas opes - Operadores lgicos . Exerccios de fixao.- Algoritmos propostos - exerccios. Esclarecimento de dvidas. Prova 1.Aula 19-30 - Estruturas de repetio - Algoritmos com repetio.- Tipos de Laos de repetio- Contador, acumulador e Exerccios.- Algoritmos propostos e exerccios. Esclarecimento de dvidas. Prova 2.Aula 31-45 - Estruturas de Dados Homogneas-Matrizes de uma dimenso (vetores). Algoritmos propostos. - Matrizes de mais umadimenso. Algoritmos propostos.- Estruturas de Dados Heterogneas- Registros. Exerccios- Subalgoritmos- Utilizao de funes e procedimentos. Variveis globais e locais. -Esclarecimento de dvidas. Prova 3. 3 4. Algoritmo Introduo Noes de LgicaLgica a forma correta de organizar os pensamentos e demonstrar o raciocnio de maneira correta. Autilizao da lgica a melhor forma de solucionar problemas e atingir objetivos. Sempre que se querpensar, falar ou escrever corretamente, deve-se colocar os pensamentos em ordem. Exemplo:- Todo mamfero animal- Todo cavalo mamfero- Portanto, todo cavalo animalA lgica muito importante em nossa vida, no dia - a - dia. Veja os exemplos abaixo:a) A gaveta est fechada.A bala est na gaveta.Preciso primeiro abrir a gaveta, para depois pegar a bala.b) Moramos em trs pessoas. Nenhum de ns dois quebrou o vaso de porcelana. Quem quebrou o vaso? AlgoritmosAlgoritmo a forma organizada de expressar uma seqncia de passos que visam atingir um objetivodefinido. Algoritmo a lgica necessria para o desenvolvimento de um programa.Apesar do nome estranho, os algoritmos so muito comuns no nosso cotidiano, como por exemplo, emuma receita de bolo. Nela esto escritos os ingredientes necessrios e a seqncias de passos ou aes aserem cumpridos para que se consiga fazer um determinado tipo de bolo.Em um modo geral, um algoritmo segue um determinado padro de comportamento, com objetivo dealcanar a soluo de um problema.Padro de comportamento: imagine a seqncia de nmeros: 1, 6, 11, 16, 21, 26, ... Para determinar qualser o stimo elemento dessa srie, precisamos descobrir qual a sua regra de formao, isto , qual o seupadro de comportamento.Como a seqncia segue uma certa constncia, facilmente determinada, somos capazes de determinar qualseria o stimo termo ou outro termo qualquer.Descrevemos ento uma atividade bem cotidiana: trocar uma lmpada. Apesar de parecer bvia demais,muitas vezes fazemos este tipo de atividade inconscientemente, sem percebermos os pequenos detalhes.Vejamos como seria descrev-la passo a passo:- pegar uma escada;- posicionar a escada embaixo da lmpada;- buscar uma lmpada nova;- subir na escada;- retirar a lmpada velha;- colocar a lmpada nova. 4 5. AlgoritmoPara se trocar a lmpada, seguida uma determinada seqncia de aes, representadas atravs dessealgoritmo. Como isso pode ser seguido por qualquer pessoa, estabelece-se a um padro de comportamento. Asequencializao tem por objetivo reger o fluxo de execuo, determinando qual ao vem a seguir.O algoritmo anterior tem um objetivo bem especfico: trocar uma lmpada. E se a lmpada no estiverqueimada? O algoritmo faz com ela seja trocada do mesmo modo, no prevendo essa situao. Parasolucionar este problema, podemos efetuar um teste seletivo, verificando se a lmpada est ou noqueimada:- pegar uma escada;- posicionar embaixo da lmpada;- buscar uma lmpada nova;- ligar o interruptor;- se a lmpada no acender, ento:- subir na escada;- retirar a lmpada velha;- colocar a lmpada nova.Dessa forma, algumas aes esto ligadas condio (lmpada no acender). Nocaso da lmpada acender, as trs linhas: - subir na escada; - retirar a lmpada velha; - colocar a lmpada nova.no sero executadas.Em algumas situaes, embora o algoritmo resolva o problema proposto, a soluo pode no ser a maiseficiente. Exemplo: trs alunos devem resolver um determinado problema:- O aluno A conseguiu resolver o problema executando 35 linhas de programa. - Oaluno B resolveu o problema executando 10 linhas de programa- O aluno C resolveu o problema executando 54 linhas de programa.Obviamente, o algoritmo desenvolvido pelo aluno B menor e mais eficiente que os demais. Isso significa queh cdigo desnecessrio nos demais programas.Dessa forma, podemos otimizar o algoritmo anterior, uma vez que buscamos a escada e a lmpada sem saber sesero necessrias:- ligar o interruptor;- se a lmpada no acender, ento:- pegar uma escada;- posicionar a escada embaixo da lmpada;- buscar uma lmpada nova;- subir na escada;- retirar a lmpada velha;- colocar a lmpada nova.Podemos considerar ainda que a lmpada nova pode no funcionar. Nesse caso devemos troc-lanovamente, quantas vezes for necessrio, at que a lmpada acenda:- ligar o interruptor;- se a lmpada no acender, ento:- pegar uma escada;- posicionar a escada embaixo da lmpada; 5 6. Algoritmo- buscar uma lmpada nova;- subir na escada;- retirar a lmpada velha;- colocar a lmpada nova;- se a lmpada no acender, ento:- retirar a lmpada;- colocar outra lmpada;- se a lmpada no acender, ento: ...Observamos que o teste da lmpada nova efetuado por um conjunto de aes: -se a lmpada no acender ento:- retire a lmpada- coloque outra lmpadaEm vez de escrevermos vrias vezes este conjunto de aes, podemos alterar o fluxo sequencial de execuo doprograma, de forma que, aps executar a ao coloque outra lmpada, voltemos a executar a ao se almpada no acender.Precisa-se ento determinar um limite para tal repetio, para garantir que ela cesse quando a lmpadafinalmente acender:- enquanto a lmpada no acender, faa: - retire a lmpada - coloque outra lmpadaUma verso final do algoritmo, que repete aes at alcanar o seu objetivo: trocar a lmpada queimada por umaque funcione, apresentada abaixo.- ligar o interruptor;- se a lmpada no acender, ento:- pegar uma escada;- posicionar a escada embaixo da lmpada;- buscar uma lmpada nova;- subir na escada;- retirar a lmpada velha;- colocar a lmpada nova;- enquanto a lmpada no acender, faa:- retirar a lmpada;- colocar outra lmpada.At agora, estamos efetuando a troca de uma nica lmpada. Todo o procedimento poderia ser repetido 10vezes, por exemplo, no caso de querermos trocar 10 lmpadas.Inicialmente, tnhamos um pequeno conjunto de aes que deveriam ser executadas (estruturaseqencial). Atravs de uma condio, inclumos posteriormente uma estrutura de seleo. Nanecessidade de repetir um determinado trecho do algoritmo, construiu-se no final uma estrutura derepetio. Fatores a serem levados em considerao na construo de um algoritmo1. ComplexidadePercebeu-se, na medida em que colocvamos situaes novas no problema a ser resolvido, que ia6 7. Algoritmoaumentando a complexidade do algoritmo. Esse certamente o maior problema envolvido na construo dealgoritmos. A complexidade pode ser vista como um sinnimo de variedade (quantidade de situaesdiferentes que um problema pode apresentar), as quais devem ser previstas na sua soluo.J que conviver com a complexidade um mal necessrio, saudvel fazer o possvel para diminu-la aomximo, a fim de controlar o problema e encontrar sua soluo.Deve-se diferenciar O que de Como. Muitos programadores aumentam a complexidade de um devidoproblema desnecessariamente. A forma errada de interpretao de um problema pode levar a respostasirrelevantes soluo almejada ou at mesmo a nenhuma soluo, gerando algoritmos mais complexos doque o necessrio.Exemplo: digamos que se pergunte a um leigo a respeito de um relgio: -Como um relgio?= um instrumento com trs ponteiros concntricos.Como a descrio no relevante, poderamos indagar: -Um relgio com 2 ponteiros possvel?= ... pode ser!Poderamos ainda indagar:- E um relgio com apenas 1 ponteiro no poderia ser uma possibilidade? =Bem... Pode ser com 3, 2 ou 1 ponteiro.- E sem ponteiro pode?= Ah!, Sim! Pode ser digitalJ a pergunta: O que um relgio?, poderia resultar na resposta: - um instrumento cuja finalidade marcar o decorrer do tempo.Ou seja, algumas variveis podem aumentar ou diminuir a complexidade de um sistema quando forembem ou mal utilizadas.2. LegibilidadeMede a capacidade de compreenso de um algoritmo por qualquer observador (que no o construiu); aclareza com que sua lgica est exposta. Quanto mais legvel for um algoritmo, menor ser suacomplexidade.3. PortabilidadeDevido a quantidade enorme de linguagens de programao existentes, no ser adotada nenhumalinguagem especfica para trabalhar os algoritmos (ex: C, pascal, Java, etc.). Isso porque a soluo doproblema fica ligada a caractersticas e recursos da linguagem na qual ela foi concebida.Utilizaremos uma pseudo-linguagem (linguagem fictcia) que visa a permitir a representao dos algoritmosatravs da lngua portuguesa (portugus estruturado). Esses algoritmos podero ser convertidos facilmentepara qualquer linguagem de programao usual (Basic estruturado, C, pascal, Java).4. Tcnica de resoluo por mtodo cartesianoA famosa frase de Descartes Dividir para conquistar muito importante dentro da programao. ummtodo que ataca um problema grande, de difcil soluo, dividindo-o em problemas menores, de soluo 7 8. Algoritmomais fcil. Se necessrio, pode-se dividir novamente as partes no compreendidas. Esse mtodo pode seresquematizado em passos:1. Dividir o problema em partes2. Analisar a diviso e garantir a coerncia entre as partes.3. Reaplicar o mtodo, se necessrio5. Planejamento reversoConsiste em, a partir do resultado final, determinar quais so os componentes bsicos. Ou seja, a partir dasada desejada, devemos poder determinar, reversamente, quais so os componentes da entrada de dadosnecessrios. Mtodo para construir um algoritmoUtilizando os conceitos j desenvolvidos, esquematizaremos um mtodo para construir um algoritmologicamente correto:1. Ler atentamente o enunciadoDeve-se reler o enunciado de um exerccio quantas vezes for necessrio, at compreend-lo completamente. Amaior parte da resoluo de um exerccio consiste na compreenso completa do enunciado.2. Retirar a relao das entradas de dados do enunciadoAtravs do enunciado, descobrimos quais so os dados que devem ser fornecidos ao programa, via teclado, apartir dos quais so desenvolvidos os clculos. Obs. Pode haver algum algoritmo que no necessite daentrada de dados (pouco comum).3. Retirar do enunciado, a relao das sadas das informaesAtravs do enunciado podemos descobrir quais so as informaes que devem ser mostradas para compor oresultado final, objetivo do algoritmo.4. Determinar o que deve ser feito para transformar as entradas nas sadas especificadasNessa fase que teremos a construo do Algoritmo propriamente dito. Devemos determinar qual sequncia depassos ou aes capaz de transformar um conjunto de dados nas informaes de resultado. Para isso,utilizamos os fatores descritos anteriormente, tais como legibilidade, portabilidade, mtodo cartesiano eplanejamento reverso, e finalmente podemos construir o algoritmo.Exerccios de Fixao1. Um homem quer atravessar um rio com um barco que pode carregar ele mesmo e apenas mais uma de suastrs cargas: um lobo, um carneiro e um mao de alfafa. O que o homem deve fazer para atravessar o rio semperder nenhuma de suas cargas?2. Elabore um algoritmo que mova 3 discos de uma torre de Hani, que consiste em 3 hastes (a-b-c), uma dasquais serve de suporte para os trs discos de tamanhos diferentes (1-2-3), os menores sobre os maiores. Pode-se 8 9. Algoritmomover um disco de cada vez para qualquer haste, sendo que nunca deve ser colocado um disco maior sobreum menor. O objetivo transferir os trs discos da haste A para haste C.Mova da haste para haste -------9 10. AlgoritmoTipos de InformaesPodemos classificar os tipos de informaes a serem processadas, a grosso modo, em dados e instrues. DadosSo as informaes a serem processadas por um computador. Consideremos 3 tipos de dados: numricos(inteiros e reais), caracteres e lgicos.Tipos primitivos de dados:1.a) Inteiro: toda e qualquer informao numrica que pertena ao conjunto dos nmeros inteiros(negativa, nula ou positiva). Exemplos: 39, 0, -56 entre outros.a) Ele tem 15 irmos. b) A temperatura desta noite ser de -2 graus.1.b) Real: toda e qualquer informao numrica que pertena ao conjunto dos nmeros reais (negativa, nula oupositiva, inteiro ou fracionrio). Exemplos:- 4, 3, 0, 35, 1,23a) Ela tem 1,73 metro de altura. b) Meu saldo bancrio de - R$ 121,07.2) Caractere: So caracterizadas como tipos caracteres, as seqncias contendo letras, nmeros esmbolos especiais. Uma seqncia de caracteres deve ser indicada entre aspas (). Este tipo de dado tambm conheci...</p>