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 1 Capítulo I - INTRODUÇÃO É comum seguirmos roteiros para solucionar problemas no dia a dia. Esses roteiros descrevem ações que devem ser seguidas uma a após a outra com o objetivo de produzir o resultado desejado. Os roteiros podem ser textuais ou gráficos. Exemplo 1: Como fazer um pato no tucupi? Tempere o pato com o alho, a cebola, sal e pimenta-do-reino. Aqueça o forno em temperatura 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 RJ 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 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. Buscar uma lâmpada nova; 2. Pegar uma escada 3. Posicionar a escada debaixo da lâmpada; 4. Subir na escada até que a lâmpada possa ser alcançada; 5. Girar a lâmpada queimada no sentido anti-horário até que se solte; 6. Colocar a lâmpada nova girando-a no sentido horário; 7. Descer da escada; E se a lâmpada não 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; 9. Descer da escada; 3 Nessa versão algumas ações estão vinculadas à condição lâmpada não acender, ou seja, somente efetua-se a troca da lâ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 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.4 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.7 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. I.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é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 seqüê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). 4 Um algoritmo pode ser definido também como: “uma seqüência ordenada, sem ambigüidade, de passos que levam à solução de um 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 seqüê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 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. I.2 REPRESENTAÇÃO 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 em 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 5 edificação para diferentes fins. A edificação é a solução projetada e cada planta, embora diferente, é a representação da mesma edificação. 1) A primeira representação: usadas pelas pessoas A linguagem natural (português, inglês): utilizada nas receitas, instruções, etc.. Para solução de problemas em computação apresenta um inconveniente: a ambigüidade de alguns termos. Assim, restrições são impostas à linguagem natural, objetivando a redução de 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. a) 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, C# etc.), para representar algoritmos, transformando-os em programas. 6 Capítulo II - CONSTRUÇÃO DE ALGORITMOS Como vimos anteriormente quando queremos resolver um problema 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ção. OS PASSOS DE UM ALGORITMO Um algoritmo é uma seqüê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 uma seqüência de passos; A) OPERAÇÕES 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 de 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ônio" 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: 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ÇÃO 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 usuário. 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: Tabela de Símbolos NOME TIPO VALOR SOMA Inteiro 1 RESULTADO Inteiro 15 Quando necessitarmos de manipular o valor 15 devemos utilizar 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. 8 A criação de nomes é livre? Não, o programador deve seguir uma regra para construir os identificador, ou em outras palavras os nomes utilizados no algoritmo. Regra para Construção de Identificadores Onde: LETRA = A ... Z DÌGITO = 0 ... 9 Observações: 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 especiais, tais como: ( ) # $ % & * ‘ “ = + [ ^ ´ ` ; 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 reservada a uma instrução. Isto é, os nomes devem ser diferentes de: inteiro, real, caractere, lógico, enquanto, faça, fim- enquanto, declare, repetir, leia, escreva, etc.. 1. Assinale os identificadores válidos: a) (X), b) x c) ah! d) "aluno" e) #55 f)KM/L g)UYT h) AB*C i) CEP h) dia/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 compilação da declaração que produz uma TS correspondente a um programa). 9 Em pseudocódigo as declarações podem ser representadas como: DECLARE <identificador1, identificador2, ...> COMO <tipo> 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 INTEIRO Essa declaração produzirá a seguinte tabela: NOME TIPO VALOR SOMA Inteiro RESULTADO Inteiro Outros exemplos: DECLARE X, Y, Z, TOTAL COMO REAL NOME TIPO VALOR X Real Y Real Z Real DECLARE T COMO LOGICO NOME TIPO VALOR T LÓGICO DECLARE A, B, TOTALH, TOTALM COMO INTEIRO DECLARE X, K COMO REAL DECLARE S COMO CARATER NOME TIPO VALOR A INTEIRO B INTEIRO TOTALH INTEIRO TOTALM INTEIRO X REAL K REAL S CARATER 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