Blog

Universidade Federal Fluminense Centro Tecnológico Instituto de Computação Departamento de Ciência da Computação Construção de Algoritmos Versão 2005 Prof. Leonardo Cruz da Costa capítulo I – INTRODUÇÃO É comum seguirmos roteiros para solucionar problemas no dia a dia. Esses roteiros de a apos a outra com o Os roteiros podem s fazer um pato no tuc sal e pimenta-do-rein or75 m ser seguidas uma esultado desejado. xemplo 1: Como o alho, a cebola, mperatura média. Coloque o pato numa assadeira com um pouco de óleo e leve ao forno até dourar.

Numa panela, coloque o tucupi e os pedaços de pato assado. Leve ao fogo alto até ferver. Abaixe o fogo e cozinhe até ficar macio. Acrescente mais tucupi, se necessário. Junte as folhas de jambu e cozinhe até que os talos fiquem macios. Sirva com farinha de mandioca. Exemplo 2: Como chegar no sítio do amigo para churrasco de final de semana? Siga pela rodovia R] 104 No quilometro 98 virar a esquerda na primeira entrada de terra Siga até a primeira ponte. Atravesse a ponte e dobre ? esquerda. Procure a placa sítio Animação.

Exemplo 3: Como deve ser a instalação do sistema de aquecimento de água solar para piscinas. 1. Moto Bomba 2. Filtro 3. Registro de Esfera ou Gaveta 4. Válvula de Rete Retenção 5. Saída de água fria para as placas 6. Retorno de água quente das placas 7. Tubulação de retorno para piscina. 2 Exemplo 4: Roteiro para trocar uma lâmpada queimada. a) Primeira versão 1 . Remover a lâmpada queimada; 2. Colocar a nova lâmpada; Mas isto está muito abstrato. O que é remover uma lâmpada? b) Segunda versão (um pouco mais detalhada) 1. 2. 3. 4. 5. 6. 7.

Buscar uma lâmpada nova; Pegar uma escada Posicionar a escada debaixo da lâmpada; Subir na escada até que a lâmpada possa ser alcançada; Girar a lâmpada queimada no sentido anti-horário até que se solte; Colocar a lâmpada nova irando-a no sentido horário; Descer da escada; E se a lâmpada nao estiver queimada? c) Terceira versão (um pouco mais detalhada) 1 . Buscar uma lâmpada nova; 2. Pegar uma escada 3. Posicionar a escada debaixo da lâmpada; 4. Acionar o interruptor; 5. Se a lâmpada não acender, então 6. Subir na escada até que a lâmpada possa ser alcançada; 7.

Girar a lâmpada queimada no sentido anti-horário até que se solte; 8. Colocar a lâmpada nova girando-a no sentido horário; g. Descer da escada; Nessa versão algumas ações estão vinculadas à condição lâmpada não acender, ou seja, somente efetua-se a troca da âmpada caso a condição lâmpada queimada (lâmpada não acender) for verdadeira. Se a condição lâmpada não acender for falsa, nada mais será realizado. Apesar do algoritmo estar correto, ele pode ser melhorado uma vez que somente seria ne PAGF realizado.

Apesar do algoritmo estar correto, ele pode ser melhorado uma vez que somente seria necessário pegar a escada, caso a condição lâmpada não acender seja verdadeira: d) Quarta versão (um pouco mais detalhada) 1 . Acionar o interruptor; 2. Se a lâmpada não acender, então 2. 1 Buscar uma lâmpada nova; 2. 2 pegar uma escada 2. 3 Posicionar a escada debaixo da lâmpada; 2. Subir na escada até que a lâmpada possa ser alcançada; 2. 5 Girar a lâmpada queimada no sentido anti-horário até que se solte; 2. 6 Colocar a lâmpada nova girando- a no sentido horário; 2. Descer da escada; Exercícios 1. Elaborar um algoritmo que mostre os passos necessários para trocar um pneu furado. 2. Um homem precisa atravessar um rio com um barco que possui capacidade apenas para carregar ele mesmo e mais uma de suas três cargas, que são: um lobo, um bode e um maço de alfafa. O que o homem deve fazer para conseguir atravessar o rio sem permite que fiquem em uma margem, o lobo e a cabra, a cabra e a alfafa? Escreva um algoritmo mostrando a resposta, ou seja, indicando todas as ações necessárias para efetuar a travessia segura. . 1 – ALGORITMOS Computadores muitas vezes chamados erroneamente de cérebro eletrônico, não têm, pelo menos até agora, a capacidade de resolver por conta própria problemas. Assim, como outras máquinas, eles precisam ser instruídos, para que através de um conjunto de ações possam solucionar o problema. Para resolvermos problemas, atrav resolvermos problemas, através de computador, é necessário que uma seqüência de operações seja criada, semelhante aos roteiros apresentados anteriormente.

A solução é obtida através de duas etapas: • • A criação de uma seqüência de operações que, quando executada, produz o resultado do problema (a esta sequência se dá o nome de algoritmo). A execução, propriamente dita, da seqüência de operações. “Um algoritmo é a descrição de um padrão de comportamento, expressado em termos de um repertório bem definido e finito de ações primitivas, as quais damos por certo que podem ser executadas” (Guimarães e Lages). Um algoritmo pode ser definido também como: “uma seqüência ordenada, sem ambigüidade, de passos que levam à solução de m dado problema” (Tremblay e Bunt [5]). As definições acima mostram que um algoritmo precisa: • • • Ter inicio e fim; Ser descritas em termos de ações não ambíguas e bem definida; Que as ações sigam uma sequência ordenada. Essas três características são entendidas de maneira fáceis, pois: 1 . Ter inicio e fim: um computador não pode ficar infinitamente buscando uma solução para o problema; 2.

Ações não ambíguas e bem definidas: não poder haver dúvidas da ação a ser tomada. Observe o passo no exemplo 1 – Coloque o pato numa assadeira com um pouco de óleo e leve ao forno até dourar. O que significa um pouco de óleo: 1 ml. , 2 ml, 10 litros, etc. 3. Seqüência leve ao forno até dourar. O que significa um pouco de óleo: 1 ml. , 2 ml, 10 litros, etc. 3. Sequência ordenada: as ações devem seguir sempre a mesma ordem de execução, pois se A ordem fosse aleatória não se pode garantir a solução adequada para o problema. 1. REPRESENTAÇAO DE ALGORITMOS O processo de resolução de um problema através de computador começa no entendimento de forma clara do problema, para qual é projetado um algoritmo, que futuramente será codificado em uma linguagem de programação, transformando-se dessa forma m um programa. Fase de resolução do Problema Fase de Implementação (utilização de uma linguagem de Programação) Assim, um algoritmo é representado de duas maneiras diferentes (mas equivalentes): A primeira representação deve ser fácil para as pessoas, construir, modificar e testar as ações (usada na construção em si).

A segunda deve ser entendida por computadores – é usada na fase de execução, quando da transformação (codificação) em programa (tradução de um algoritmo em linguagem de programação). Situações semelhantes ocorrem em outras áreas do conhecimento. Na Arquitetura e na Engenharia, os profissionais elaboram várias plantas (baixa, corte, situação, etc. ) da mesma edificação para diferentes fins. A edificação é a solução projetada e cada planta, embora diferente, é a representação da mesma edificação. ) A primeira representaç PAGF s OF as pessoas A linguagem 1) A primeira representação: usadas pelas pessoas A linguagem natural (português, inglês): utillzada nas receitas, instruções, etc.. Para solução de problemas em computação apresenta um inconveniente: a ambiguidade de alguns termos. Assim, restrições são impostas à linguagem natural, objetivando a redução e ambigüidade, criando uma pseudolinguagem (ou, ainda, pseudocódigo, Portugol). Representações gráficas: são bastante recomendáveis já que um desenho muitas vezes substitui, com vantagem, mil palavras. ) fluxograma b) diagramas de Nassi- Shneidermam c) método de Jackson d) diagramas de Warnier-Or 2) A segunda representação: usada pelo computador Utiliza-se uma linguagem de programação (Pascal, Cobol, C, Java, etc. ), para representar algoritmos, transformando-os em programas. 6 capítulo II – CONSTRUÇÃO DE ALGORITMOS Como vimos anteriormente quando queremos resolver um roblema utilizando um computador, devemos construir uma seqüência de passos (algoritmo) que conduz à solução do problema. uma das vantagens de utilizar algoritmos é que a partir dele o programador pode codificá-lo em qualquer linguagem de programaçao.

OS PASSOS DE UM ALGORITMO Um algoritmo é uma sequência de passos, onde cada passo é de uma das três naturezas seguintes: a) uma operação elementar; b) uma operação de controle especificando uma seleção entre seqüências de passos; c) uma operação de controle especificando a repetição de um entre seqüências de passos; c) uma operação de controle specificando a repetição de uma sequência de passos; A) OPERAÇOES ELEMENTARES A principal motivação para o desenvolvimento e uso dos computadores foi a necessidade de manipular com eficiência grandes quantidade de dados.

Os dados podem ser de diversos tipos: primitivos, agregados homogêneos, agregados heterogêneos, registros, arquivos de registros, etc.. O conjunto dos tipos primitivos que compõe uma linguagem de programação pode mudar dependendo da linguagem de programação. A seguir apresentamos os tipos primitivos que normalmente são usados na construção de algoritmos.

Inteiro: denota todo o conjunto e valores numéricos que pertencem ao conjunto dos números inteiros (negativos, positivos ou nulos) Ex: Quantidade de alunos: 50 Quantidade de professores de um curso: 35 Real: denota todo o conjunto de valores numéricos que pertença ao conjunto dos números reais (negativos, positivos ou nulos) Ex: Média de um aluno: 8. 5 Salário de uma pessoa: R$ 300. 00 Caractere: denota todo o conjunto de valores que pertença ao conjunto dos caracteres (Alfabéticos: A-Z, a-z; numéricos: 0-9; e especiais: ? , etc. Ex: Nome do aluno: ‘João Antônioi Orientação: “usar somente caneta preta no preenchimento” 7 Lógico: denota duas situações (biestável: verdadeiro – falso, 0-1 ) Ex: Questão: Certa Situação: Reprovado 1 . Determinar qual o tipo de dado presente nas sentenças abaixo: PAGF 7 Certa Situação: Reprovado a) Há na porta do banheiro uma placa ‘HOMENS’. b) O salário de Maria é de R$ 1030,98. c) Uma maneira econômica de representar o sexo de uma pessoa é através de ‘F’ ou ‘M’. d) A sala de aula fica no segundo andar. e) O planeta Terra tem a forma quadrada.

Entende-se por operações elementares todos os cálculos com um resultado produzido, entrada e saída de dados; movimentação de dados. A. 1) ATRIBUIÇAO A memória permite o armazenamento de dados (valores), que podem ser obtidos pelos dispositivos de entrada e saída, ou calculados em operações no programa e posteriormente colocados à disposição do usuario. Para que a memória possa armazenar os dados, uma área é reservada na memória e associada a identificadores (nomes) usados no programa. A esta área se dá o nome de Tabela de Símbolos (TS).

Exemplo: Suponha que desejamos utilizar os valores numéricos 1 e 15. Para que esses possam permanecer na memória e posteriormente serem utilizados para algum tipo de processamento, são criados dois nomes SOMA e RESULTADO. Cada linha na Tabela de Símbolo (TS), representa uma área na memória que guardará os valores e será manipulada (referenciada, identificada) pelo nome dado (SOMA e RESULTADO), como representado a seguir: -rabela de Símbolos NOME TIPO SOMA Inteiro RESULTADO Inteiro VALOR 1 15 Quando necessitarmos de manipular o valor 15 devemos utilizar RESULTADO Inteiro o nome Resultado e para o valor 1, Soma.

A esses nomes criados pelo programador, são chamados de identificadores. Pois, identificam o local (área de memória) onde o valor está armazenado. A criação de nomes é livre? Não, o programador deve seguir ma regra para construir os identificador, ou em outras palavras os nomes utilizados no algoritmo.

Regra para Const ução de Identificadores onde: LETRA = A Z DIGITO = O 9 Observaçoes: a) O primeiro caractere do nome sempre será uma letra; b) Não existe uma restrição a quantidade de letras ou dígitos que formam o nome; d) O nome não pode possuir espaço em branco ou símbolos especials, tais como: ( ) # S % ‘ • ; e) Não poderão ser usados outros caracteres a não ser letras e números; f) As letras sempre serão maiúsculas; g) Não há acentuação dos nomes; h) Não poderá ser um nome uma palavra resem•ada a uma nstrução.

Isto é, os nomes devem ser diferentes de: inteiro, real, caractere, lógico, enquanto, faça, fimenquanto, declare, repetir, leia, escreva, etc.. 1 . Assinale os identificadores válidos: a) (X), f)KM/L b) x g)UYT c) ah! h) AB*C d) “aluno” i) CEP e) 455 h) dla/mes/ano Como especificamos cada linha da tabela de símbolos?

A associação do identificador ao local que receberá o dado na tabela de símbolo (definição de cada linha da tabela) é chamada de declaração (é a dado na tabela de símbolo (definição de cada linha da tabela) é chamada de declaração (é a compilação da declaração que produz ma TS correspondente a um programa). Em pseudocódigo as declarações podem ser representadas como: DECLARE COMO Onde tipo define as características dos dados a serem manipulados, pode ser: inteiro, real, caracter, lógico, entre outros.

Assim, para definirmos que SOMA e RESULTADO, são os nomes utilizados no algoritmo e que ambos representarão números inteiros, é necessário utilizarmos a declaração: DECLARE SOMA, RESULTADO COMO INTE-IRO Essa declaração produzirá a seguinte tabela: NOME SOMA RESULTADO outros exemplos: DECLARE X, Y, Z, TOTAL COMO REAL NOME X Y Z TIPO Real Real Real VALOR

TIPO Inteiro Inteiro VALOR DECLARE T COMO LOGICO NOME T TIPO LOGICO VALOR DECLARE A, B, TOTALH, TOTALM COMO INTEIRO DECLARE X, K COMO REAL DECLARE S COMO CARATER NOME A B TOTALH TOTALM X KS TIPO INTEIRO INTEIRO INTEIRO INTEIRO REAL REAL CARATER VALOR Observe que a declaração irá produzir uma tabela com os nomes definidos, porém os valores não aparecem, não estão especificados. 10 Como os valores serão colocados na tabela? A associação de um valor a um nome (declarado) se dá através da atribuição. ATRIBUIÇÃO: associa um identificador a uma expressão (valor). forma geral: Identificador 10 deve ser lido como