Baixe Sebenta - ALG - EST e outras Notas de estudo em PDF para Informática, somente na Docsity! Algoritmia e Estruturas de Dados Jorge Santos Instituto Superior de Engenharia do Porto Departamento de Engenharia Informática Fevereiro de 2006 Aviso de licença de utilização: Este documento pode ser utilizado livremente para fins não comerciais, é permitido aos seus utilizadores, copiar, distribuir e exibir publicamente os seus conteúdos, desde que sejam ressalvados os direitos de autor do mesmo, nomeadamente, de- verá ser sempre incluída esta página em todas as cópias. Jorge Santos, 2006 2 Estruturas de dados 45 2.1 Vectores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.1.1 Exercícios resolvidos . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.1.1.1 Funções manipulando vectores . . . . . . . . . . . . . 48 2.1.2 Exercícios propostos . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.1.2.1 Determinar desvio padrão de uma série . . . . . . . . 50 2.1.2.2 Prova de atletismo . . . . . . . . . . . . . . . . . . . . . 50 2.2 Ordenação e pesquisa de vectores . . . . . . . . . . . . . . . . . . . . . . 51 2.2.1 Ordenação por selecção . . . . . . . . . . . . . . . . . . . . . . . 51 2.2.2 Pesquisa Sequencial . . . . . . . . . . . . . . . . . . . . . . . . . 52 2.2.3 Exercicios resolvidos . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.2.3.1 Inverter um vector . . . . . . . . . . . . . . . . . . . . . 53 2.2.4 Exercícios propostos . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.2.4.1 Junção ordenada de vectores . . . . . . . . . . . . . . . 54 2.2.4.2 Método de ordenação por troca directa . . . . . . . . . 54 2.2.4.3 Filtro gráfico . . . . . . . . . . . . . . . . . . . . . . . . 54 v vi Lista de Figuras 1.1 Estrutura de um computador . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Notação dos Fluxogramas . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Fluxograma e sintaxe - Instruções sequenciais . . . . . . . . . . . . . . . 8 1.4 Fluxograma e sintaxe - Saída de dados . . . . . . . . . . . . . . . . . . . 8 1.5 Fluxograma e sintaxe - Entrada de dados . . . . . . . . . . . . . . . . . 9 1.6 Fluxograma e sintaxe - Atribuição . . . . . . . . . . . . . . . . . . . . . 9 1.7 Fluxograma e sintaxe - Instrução decisão se-então . . . . . . . . . . . . 13 1.8 Fluxograma e sintaxe - Instrução decisão se-então-senão . . . . . . . . 14 1.9 Fluxograma e sintaxe - Instrução decisão múltipla seleccione-caso . 15 1.10 Fluxograma da determinação do máximo de 3 valores . . . . . . . . . . 19 1.11 Fluxograma e sintaxe - Instrução ciclo repetir-até . . . . . . . . . . . 24 1.12 Fluxograma e sintaxe - Instrução ciclo enquanto-fazer . . . . . . . . . 25 1.13 Fluxograma e sintaxe - Instrução ciclo para-fazer . . . . . . . . . . . . 26 1.14 Divisão inteira através de subtracções sucessivas . . . . . . . . . . . . . 35 1.15 Fluxograma e sintaxe - Função . . . . . . . . . . . . . . . . . . . . . . . 38 1.16 Fluxograma e sintaxe - Procedimento . . . . . . . . . . . . . . . . . . . . 39 1.17 Ilustração da lei de Ohm . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.1 Vector unidimensional: notas . . . . . . . . . . . . . . . . . . . . . . . . 47 2.2 Vector bidimensional (matriz): imagem . . . . . . . . . . . . . . . . . . 47 2.3 Imagem vídeo - original . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.4 Imagem vídeo - em tratamento . . . . . . . . . . . . . . . . . . . . . . . 55 vii x Resumo Estes apontamentos têm como objectivo principal apoiar os leitores que pretendam aprender programação de computadores Os conteúdos propostos têm como objectivo fornecer bases sólidas de metodo- logias de programação que auxiliem a compreensão de programas computacionais simples, a sua adaptação e desenvolvimento de novas aplicações, e estimular a capa- cidade dos leitores para: analisar e resolver problemas de programação. A estrutura destes apontamentos foi definida de acordo com a abordagem de aprender-por-exemplo, pelo que, os conceitos são apenas introduzidos de acordo com a necessidade de explicar a resolução de um determinado algoritmo. Neste manual introduzem-se as bases da algoritmia de acordo com o paradigma da programação estruturada. Em cada secção é apresentada um pequena introdu- ção teórica sobre o tópico em destaque, apresentados problemas e propostas soluções para os mesmos, adicionalmente são propostos exercícios para resolução. Na codifi- cação/apresentação das soluções é geralmente Pseudo-Código e/ou Fluxogramas. Este documento compila exercícios de vários anos de ensino de muitos docentes do departamento nos quais me incluo. Ao longo do manual poderão ser encontrados exemplos e exercícios propostos pelos docentes nas disciplinas de Algoritmia e Progra- mação, Linguagens de Programação I do curso de Engenharia Informática do Departa- mento de Engenharia Informática (DEI), bem como de Programação I e Programação II do curso Engenharia Electrotécnica do Departamento de Engenharia Electrotécnica (DEE), ambos do ISEP. xi xii ISEP/DEI - Jorge Santos Mémoria CPU Periféricos Hardware Ferramentas de desenvolvimento Sistema Operativo Software Aplicações COMPUTADOR Figura 1.1: Estrutura de um computador – executar um determinado tipo de instruções a uma determinada veloci- dade; – armazenar um conjunto de bytes; – comunicar com um conjunto de periféricos. Estas componentes físicas têm que receber ordens do que fazer e como se arti- cular. Esta é a função do software. • Software - esta é a componente lógica do computador, que consiste num con- junto de programas que dirigem o funcionamento do computador. Para uma melhor sistematização do software e as respectivas funções, este pode ser organizado nas seguintes categorias: – Software de Sistema Operativo - conjunto de programas que comunica di- rectamente com o hardware e é responsável pela gestão de recursos e peri- féricos. Neste conjunto incluem-se o sistema operativo e os programas de controle do funcionamento do hardware, tais como programas de parame- trização, drivers e afins. – Ferramentas de desenvolvimento - conjunto de aplicações utilizadas no de- senvolvimento de aplicações. Neste conjunto incluem-se as linguagens de programação (compiladores e interpretadores) e os sistemas de gestão de bases de dados. 2 Capítulo 1. Algoritmia e Programação – Aplicações - conjunto de aplicações que se destinam à utilização pelo utili- zador final do sistema de computação. Regra geral o nível de abstracção é mais elevado do que nas categorias anteriores. Neste conjunto incluem-se as aplicações por medida, ferramentas de gestão, folhas de cálculo, editores de texto, etc. 1.1.2 Programação estruturada Numa primeira fase, nas décadas de 50 e 60, o desenvolvimento do hardware era o responsável pela expansão dos computadores. A maioria do investimento era feito a este nível, sendo a programação vista como uma arte. Na década de 70, incentivados pela melhoria das características de hardware (mi- niaturização e baixo custo) os informáticos foram confrontados com projectos cada vez mais sofisticados. Constata-se nessa altura a inversão dos custos dispendidos com hardware e software, para além do problema da fiabilidade do software passar a ser uma preocupação. Surge então a necessidade de transformar a tarefa de construir software numa actividade com rigor comparável a uma disciplina de engenharia nascendo assim uma nova disciplina – a Engenharia de Software – cujo objectivo é a produção de Software de modo eficiente em custos controlados e segurança. A produção de software, como de qualquer outro produto de engenharia passa por diferentes fases como sejam: planeamento, análise, projecto, programação, im- plementação e manutenção. Para cada uma das fases do desenvolvimento do soft- ware foram estudadas métodos e técnicas específicas. A programação estruturada enquadra-se num desses métodos e permite fasear o processo de construção de um programa descrevendo o processo computacional de um modo não ambíguo - Algo- ritmo. A programação estruturada define um conjunto de regras para elaboração de pro- gramas. A programação estruturada baseia-se no desenho modular dos programas e no refinamento gradual do topo para a base. De acordo com este paradigma um programa pode ser definido pela forma se- guinte: Programa = Estrutura de Dados + Algoritmo Um algoritmo manipula dados que podem ser de diversos tipos, designadamente: números (inteiros ou reais), caracteres, cadeias de caracteres, endereços (apontado- res), lógicos (verdadeiro e falso). As estrutura de dados são o modo como os dados estão organizados, acedidos e alterados. De entre as mais relevantes destacam-se: variáveis simples, vectores mono e multi-dimensionais, listas, filas, árvores, grafos e ficheiros. Um algoritmo consiste num conjunto finito e bem-definido de instruções que des- crevem os passos lógicos necessários à realização de uma tarefa ou resolução de um 3 ISEP/DEI - Jorge Santos problema, dado o estado inicial (único), a execução do algoritmo conduz ao estado final (único). Considere-se por exemplo a seguinte receita para a confecção de uma omeleta de queijo. OMELETA DE QUEIJO FRESCO Ingredientes: • 170 gr de queijo fresco • 6 ovos grandes • 30 gr de manteiga ou margarina • Sal q.b. Modo de Preparação: Ponha o queijo fresco numa tigela e esmague-o com uma colher de pau, até formar um puré espesso e cremoso. Bata os ovos e misture-os com o queijo, adicionando um pouco de água fria. Tempere a gosto. Derreta um pouco de gordura numa frigideira de base larga e adicione a mistura de ovos e queijo. Cozinhe em lume brando até que a omeleta fique pronta mas não demasiado cozida. Estabelecendo um paralelo entre esta receita culinária e um programa, os ingredi- entes são as estruturas de dados e o modo de preparação é o algoritmo. Naturalmente que uma receita culinária usa a linguagem natural e como tal é muito difícil a sua in- terpretação por parte de um computador. De acordo com o paradigma da programação estruturada qualquer programa pode ser descrito utilizando exclusivamente as três estruturas básicas de controlo: • Instruções de Sequência - as instruções de sequência são instruções atómicas (simples) permitem a leitura/escrita de dados, bem como o cálculo e atribuição de valores; • Instruções de Decisão - as instruções de decisão, ou selecção, permitem a selec- ção em alternância de um ou outro conjunto de acções após a avaliação lógica de uma condição; • Instruções de Repetição - as instruções de repetição, ou ciclos, permitem a exe- cução, de forma repetitiva, de um conjunto de instruções. Esta execução de- pende do valor lógico de uma condição que é testada em cada iteração para decidir se a execução do ciclo continua ou termina. Na descrição de algoritmos são utilizados diferentes formalismos conforme o ob- jectivo ou audiência. Entre os mais comuns encontram-se o pseudo-código e fluxo- gramas. 4 Capítulo 1. Algoritmia e Programação Tabela 1.3: Operadores lógicos Símbolo Nome e , ∧ conjunção ou , ∨ disjunção não, ¬ negação Tabela 1.4: Tabela de verdade - conjunção a b a ∧ b falso falso falso falso verdadeiro falso verdadeiro falso falso verdadeiro verdadeiro verdadeiro Tabela 1.5: Tabela de verdade - disjunção a b a ∨ b falso falso falso falso verdadeiro verdadeiro verdadeiro falso verdadeiro verdadeiro verdadeiro verdadeiro Tabela 1.6: Tabela de verdade - negação a ¬a falso verdadeiro verdadeiro falso 1.2 Instruções sequenciais As instruções do tipo sequencial são as mais simples de todas apresentando uma uma estrutura atómica. São responsáveis por permitirem fazer a entrada/saída de dados, execução de cálculos e atribuição de valores a variáveis. A noção de ordem/sequência é representada através da seta de fluxo (ver figura 1.3). 1.2.1 Saída de dados As instruções de escrita permitem fazer a saída de dados (tipicamente para o écran) sejam estes variáveis e/ou textos e/ou resultado de cálculos. Na figura 1.4 é apresen- tada sintaxe proposta para a escrita de uma ou várias variáveis. Conforme os exemplos seguintes: 7 ISEP/DEI - Jorge Santos instrução1 instrução2 instrução3 inicio . . . <instrução1>; <instrução2>; <instrução3>; . . . fim Figura 1.3: Fluxograma e sintaxe - Instruções sequenciais escrever inicio . . . escrever <lista-de-variaveis/textos>; . . . fim Figura 1.4: Fluxograma e sintaxe - Saída de dados início # Escrever o conteúdo da variável x; escrever x; # Escrever o conteúdo das variáveis nome e idade; escrever nome, idade; # Escrever um texto seguido do valor da variável x; escrever "O valor de x é:", x; # Escrever o resultado da operação 4*4, 16; escrever 4*4; # Escrever 4*4; escrever "4*4"; fim 1.2.2 Entrada de dados As instruções de leitura permitem fazer a entrada de dados, tipicamente a partir de um teclado, colocando-os em variáveis. Na figura 1.5 é apresentada a sintaxe pro- posta para a leitura de uma ou várias variáveis. No caso de se pretender ler mais do que uma variável, os nomes das variáveis separam- se por vírgulas. Considerem-se os seguintes exemplos: 8 Capítulo 1. Algoritmia e Programação ler inicio . . . ler <lista-de-variaveis>; . . . fim Figura 1.5: Fluxograma e sintaxe - Entrada de dados início # ler a variável x; ler x; # ler as variáveis nome e idade; ler nome,idade; fim 1.2.3 Atribuição A instrução designada por atribuição permite atribuir o valor de uma expressão a uma variável. A variável que aparece no lado esquerdo da instrução vai assim rece- ber o valor da expressão que aparece no lado direito da mesma instrução. Do lado direito da atribuição podemos ter: um número, um texto, o resultado de um cálculo ou o conteúdo de uma outra qualquer variável. Na figura 1.6 é apresentada a sintaxe proposta para a atribuição. var ß expr inicio . . . <variável> ← <expressão>; . . . fim Figura 1.6: Fluxograma e sintaxe - Atribuição Considerem-se os seguintes exemplos: 9 ISEP/DEI - Jorge Santos 1.2.4.3 Determinar perímetro e área de circunferência O algoritmo 1.3 permite determinar o perímetro e área de uma circunferência, a partir do valor do raio. Entrada: raio Saída: perimetro, area início pi← 3,1415; # Ler o valor do raio; escrever "Introduza valor do raio:"; ler raio; # Calcular perímetro e área; area← pi ∗ raio2; perimetro← 2 ∗ pi ∗ raio; # Apresentar resultados; escrever "Área=", area; escrever "Perímetro=", perimetro; fim Algoritmo 1.3: Determinar perímetro e área de circunferência 1.2.5 Exercícios Propostos Nesta secção são propostos alguns problemas com vista à aplicação conjugada de instruções sequenciais. 1.2.5.1 Calcular índice de massa corpórea (IMC) O índice de massa corpórea (IMC) de um indivíduo é obtido dividindo-se o seu peso (em Kg) por sua altura (em m) ao quadrado. Assim, por exemplo, uma pessoa de 1,67m e pesando 55kg tem IMC igual a 20,14, já que: IMC = peso altura2 = 55kg 1, 67m ∗ 1, 67m = 20, 14 Escreva um programa que solicite ao utilizador o fornecimento do seu peso em kg e de sua altura em m e a partir deles calcule o índice de massa corpórea do utilizador. 1.2.5.2 Converter horas, minutos e segundos Descreva um algoritmo que a partir de um determinado número de segundos cal- cula o número de horas, minutos e segundos correspondentes. Conforme o seguinte exemplo: 8053s = 2h + 14m + 13s 12 Capítulo 1. Algoritmia e Programação 1.2.5.3 Teorema de Pitágoras Descreva um algoritmo para determinar a hipotenusa de um triângulo rectângulo, dados os catetos. 1.2.5.4 Converter temperaturas Descreva um algoritmo que a partir de uma temperatura expressa em graus Fahre- nheit (tempF), calcule a temperatura expressa em graus Celsius (tempC). A conversão pode ser realizada de acordo com a fórmula 1.2.2. tempF = 32 + 9 ∗ tempC 5 (1.2.2) 1.3 Instruções de Decisão As instruções de decisão, ou selecção, permitem a selecção em alternância de um ou outro conjunto de acções após a avaliação lógica de uma condição. 1.3.1 Decisão binária A decisão binária permite bifurcar a execução de um algoritmo em dois fluxos dis- tintos, para tal é utilizada instrução se. Esta instrução pode ser utilizada de duas formas: se-então e se-então-senão. Na figura 1.7 é apresentada a sintaxe para o primeiro caso. se a condição for verdadeira é executado o bloco-instruções caso contrário nada acontece. se bloco de instruções então inicio . . . se <condição> então <bloco-instruções> fim-se . . . fim Figura 1.7: Fluxograma e sintaxe - Instrução decisão se-então Considere-se o seguinte exemplo utilizando a forma se-então, no qual um aluno é aprovado se tem nota maior ou igual a 9,5: 13 ISEP/DEI - Jorge Santos Entrada: nota início escrever "Introduza nota:"; ler nota; se nota ≥ 9,5 então escrever "O aluno foi aprovado"; fim-se fim Note-se que um bloco de instruções é delimitado pelas instruções então e fim-se. No segundo caso (ver figura 1.8), em que a instrução tem a estrutura se-então-senão, se a condição for verdadeira é executado o bloco-instruções1 senão é executado o bloco-instruções2. se bloco de instruções 2 senão bloco de instruções 1 então inicio . . . se <condição> então <bloco-instruções1> senão <bloco-instruções2> fim-se . . . fim Figura 1.8: Fluxograma e sintaxe - Instrução decisão se-então-senão Considere-se o seguinte exemplo utilizando a forma se-então-senão. Entrada: lado1, lado2 Saída: area início # Ler as medidas dos lados; escrever "Introduza medidas dos lados:"; ler lado1, lado2; # Calcular área; area← lado1*lado2; se lado1 = lado2 então escrever "Área do quadrado=", area; senão escrever "Área do rectângulo=", area; fim-se fim 14 Capítulo 1. Algoritmia e Programação 1.3.3 Exercícios Resolvidos Nesta secção são apresentados alguns problemas e respectivas soluções com o objec- tivo de ilustrar a utilização de instruções de decisão. 1.3.3.1 Distância euclidiana entre dois pontos O algoritmo 1.6 permite realizar o cálculo da distância euclidiana entre dois pontos, sendo que cada ponto é definido pelas coordenadas (x,y). no cálculo da distância pode ser utilizada a fórmula 1.3.1. distância = √ (x2 − x1)2 + (y2 − y1)2 (1.3.1) Caso os pontos sejam coincidentes mostra mensagem "Pontos Coincidentes". Entrada: x1, y1, x2, y2 Saída: distancia início # Ler coordenadas do ponto 1; escrever "Coordenadas ponto1 (x/y):"; ler x1, y1; # Ler coordenadas do ponto 2; escrever "Coordenadas ponto2 (x/y):"; ler x2, y2; # Calcular distância e mostrar resultado; distancia← √(x2− x1)2 + (y2− y1)2; se distancia=0 então escrever "Os pontos são coincidentes"; senão escrever "Distância=", distancia; fim-se fim Algoritmo 1.6: Calcular distância euclidiana entre pontos 1.3.3.2 Classificar em função da média O algoritmo 1.7 permite ler as notas de um aluno às disciplinas de Matemática, Por- tuguês, Inglês e Geografia e calcular a média. Em função da média mostra uma men- sagem com o conteúdo "Aprovado" ou "Reprovado". Consideram-se notas positivas as notas iguais ou superiores a 9,5. 17 ISEP/DEI - Jorge Santos Entrada: mat, por, ing, geo início # Ler as notas do aluno; escrever "Introduza notas (mat, por, ing, geo):"; ler mat, por, ing, geo; # Calcular média; media← mat+por+ing+geo4 ; se media ≥ 9,5 então escrever "Aprovado"; senão escrever "Reprovado"; fim-se fim Algoritmo 1.7: Classificar em função da média 1.3.3.3 Determinar o máximo de 3 valores Considere-se o problema de ler três números e calcular o maior deles. O fluxograma 1.10 permite capturar com grande facilidade a noção de fluxo e passos alternativos. Na resolução do problema foi adoptada uma estratégia de isolamento dos vários ca- sos, primeiro é testado o número A, depois o número B e caso nenhum dos dois seja o máximo, por exclusão de partes, se concluí que o número C é o maior de todos. Note-se que a utilização de fluxogramas está regra geral limitada à representação de pequenos programas ou processos com elevado grau de abstracção porque caso contrário o fluxograma estender-se-ia por inúmeras páginas tornando a sua interpre- tação muito difícil. No algoritmo 1.8 foi codificado em pseudo-código a solução anteriormente deli- neada no fluxograma da figura 1.10. 18 Capítulo 1. Algoritmia e Programação Início ler A,B,C “Introduza três números” A>B Fim escrever Maior B>C Maior ß B Maior ß CMaior ß A A>C então senão então então senão Figura 1.10: Fluxograma da determinação do máximo de 3 valores Entrada: A, B, C Saída: maximo início # Ler números; escrever "Introduza número1, número2 e número3:"; ler A, B, C; se A ≥ B então se A ≥ C então maximo← A; fim-se senão se B ≥ C então maximo← B; senão maximo← C; fim-se fim-se escrever "O número maior é:", maximo; fim Algoritmo 1.8: Calcular máximo de 3 números 19 ISEP/DEI - Jorge Santos 1.3.4.3 Resolver equação da forma ax2 + bx + c = 0 Calcular as raízes de uma equação na forma ax2 + bx + c = 0. Note que os valores a, b e c podem ser zero, podendo dar origem a equações sem solução ou equações de primeiro grau. Considere as fórmulas 1.3.2 e 1.3.3 na resolução do problema. binómio = b2 − 4ac (1.3.2) x = −b∓ √ binómio 2a (1.3.3) 1.3.4.4 Converter entre escalas de temperaturas Escrever um programa que faça conversões entre as três escalas de temperaturas, Kelvin, Celsius e Fahrenheit, com base em três valores de entrada: a temperatura e escala actual e escala pretendida. Conforme o seguinte exemplo: As entradas 38, ’C’ e ’K’, significam que o utilizador pretende converter a tem- peratura 38 Celsius para Kelvin. Considere as fórmulas 1.3.4 e 1.3.5 na resolução do programa. tempF = 32 + 9 ∗ tempC 5 (1.3.4) tempC = tempK+ 273 (1.3.5) Sugestão: Tentar a resolução com as estruturas se-então-senão e alternativamente utilizar a estrutura de múltipla decisão. 1.3.4.5 Calcular índice de massa corpórea (IMC) O índice de massa corpórea (IMC) de um indivíduo é obtido dividindo-se o seu peso (em Kg) por sua altura (em m) ao quadrado. Assim, por exemplo, uma pessoa de 1,67 m e pesando 55 Kg tem IMC igual a 20,14, já que: IMC = peso altura2 = 55kg 1, 67m ∗ 1, 67m = 20, 14 IMC Interpretação Até 18,5 (inclusive) Abaixo do peso normal De 18,5 a 25 (inclusive) Peso normal De 25 a 30 (inclusive) Acima do peso normal Acima de 30 Obesidade Tabela 1.7: Índice de massa corpórea 22 Capítulo 1. Algoritmia e Programação Considerando a tabela 1.7, escreva um programa que leia o peso em kg e a altura em m de uma determinada pessoa de forma a calcular o índice de massa corpórea do mesmo e de seguida, estabeleça as comparações necessárias entre o IMC calculado e os valores da tabela 1.7 e escreva uma das frases, conforme for o caso: • Você está abaixo do peso normal. • O seu peso está na faixa de normalidade. • Você está acima do peso normal. • Você precisa de perder algum peso. 1.3.4.6 Determinar ano bissexto Um ano é bissexto se é divisível por 4, excepto se, além de ser divisível por 4, for também divisível por 100. Então ele só é bissexto se também for divisível por 400. Escrever um algoritmo que leia o valor de um ano e escreva se o ano é ou não bissexto. 1.3.4.7 Parque de estacionamento Considere um parque de estacionamento que pratica os preços seguintes: • 1a hora: 2e • 2a hora: 1,5e • a partir da 2a hora: 1e/hora O tempo de permanência no parque é contabilizado em horas e minutos. Por exemplo, se uma viatura permanecer 2 horas e 30 minutos no parque, pagará 2e (1a hora) + 1,5e (2a hora) + 0,5e (30 minutos a 1e/hora) = 4e. Elabore um algoritmo que, lido o tempo que determinada viatura permaneceu estacionada no parque, diga a quantia que deve ser paga. 1.4 Instruções de Repetição (Ciclos) As instruções de repetição, ou ciclos, permitem a execução de forma repetitiva de um conjunto de instruções. Esta execução depende do valor lógico de uma condição que é testada em cada iteração para decidir se a execução do ciclo continua ou termina. Note-se que as diferentes instruções de ciclos a seguir apresentadas consistem em variações da mesma estrutura. 23 ISEP/DEI - Jorge Santos 1.4.1 Ciclo condicional: repetir-até O ciclo repetir-até executa um bloco de instruções até que uma determinada condi- ção lógica seja verdadeira. Este ciclo testa a condição lógica após a primeira iteração, ou seja, o teste é realizado à saída. Este ciclo deve ser utilizado sempre que se desejar que o código seja executado pelo menos uma vez. Na figura 1.11 é apresentada a sintaxe proposta para o ciclo repetir-até. até condição bloco de instruções falso verdade repita inicio . . . repetir <bloco-instruções> até <condição>; . . . fim Figura 1.11: Fluxograma e sintaxe - Instrução ciclo repetir-até Considere-se o seguinte exemplo em que a utilização da estrutura repetir-até permite garantir que o valor da nota introduzida está situado entre 0 e 20. Entrada: nota início repetir escrever "Introduzir nota entre 0-20:"; ler nota; até nota ≥ 0 e nota ≤ 20; fim 1.4.2 Ciclo condicional: enquanto-fazer O ciclo enquanto executa um bloco de instruções enquanto uma determinada condi- ção lógica for verdadeira. Este ciclo testa a condição lógica à entrada. Na figura 1.12 é apresentada a sintaxe proposta para o ciclo enquanto-fazer. Considere-se o seguinte exemplo em que a utilização da estrutura enquanto-fazer permite calcular e escrever a tabuada de um número. 24 Capítulo 1. Algoritmia e Programação Saída: soma início soma← 0; # A iniciação da variável de iteração tem de ser realizada antes do início do ciclo i← 1; enquanto i ≤ 100 fazer soma← soma + i; # Incremento da variável de iteração i← i+1; fim-enquanto escrever soma; fim 1.4.4 Exercícios Resolvidos Nesta secção são apresentados alguns problemas e respectivas soluções com o ob- jectivo de ilustrar a utilização de instruções cíclicas. Nas soluções são exploradas situações com utilização simples dos ciclos e/ou imbricados. 1.4.4.1 Calcular somatório entre dois limites O algoritmo 1.11 permite calcular a somatório dos números existentes num intervalo definido por limites inferior e superior. Note que o utilizador pode introduzir os li- mites na ordem que entender, desta forma os intervalos [5-10] e [10-5] são igualmente válidos. 27 ISEP/DEI - Jorge Santos Entrada: limite1, limite2 Saída: soma início # Ler intervalo; escrever "Introduza número1:"; ler limite1; escrever "Introduza número2:"; ler limite2; # Determinar o limite inferior e superior; se limite1>limite2 então maximo← limite1; minimo← limite2; senão maximo← limite2; minimo← limite1; fim-se # Calcular soma propriamente dita; soma← 0; para i← minimo; i≤maximo; i← i+1 fazer soma← soma + i; fim-para # Mostrar resultado; escrever soma; fim Algoritmo 1.11: Calcular somatório entre dois limites 1.4.4.2 Calcular factorial de um número O algoritmo 1.12 permite calcular o factorial de um número sabendo que: factorial(n) = { n = 0 → 1 n ≥ 1 → n ∗ factorial(n− 1) Exemplo: factorial(5)=5*4*3*2*1=120 28 Capítulo 1. Algoritmia e Programação Entrada: numero Saída: factorial início # Ler o número para o qual se pretende calcular o factorial; escrever "Introduza número:"; ler numero; # Efectuar o cálculo; factorial← 1; para i← 1; i≤numero; i← i+1 fazer factorial← factorial * i; fim-para # Apresentar resultado; escrever factorial; fim Algoritmo 1.12: Calcular factorial de um número 1.4.4.3 Determinar se um número é primo Um número é primo se for apenas divisível por si próprio e pela unidade, por exem- plo: 11 é número primo (visto que é apenas divisível por 11 e por 1), enquanto que 21 não é primo, pois tem os seguintes divisores: 1,3,7 e 21. Entrada: numero início escrever "Introduza número:"; ler numero; # A variável ndiv será utilizada na contagem do número de divisores de um número; ndiv← 0; para i← 2; i<numero; i← i+1 fazer # Determinar se i é divisor do número; se numero%i=0 então ndiv← ndiv+1; fim-se fim-para # Testar se existem divisores diferentes de 1 e do próprio número; se ndiv>0 então escrever "O número ", numero, "não é primo"; senão escrever "O número ", numero, "é primo"; fim-se fim Algoritmo 1.13: Determinar se um número é primo O algoritmo 1.13 permite determinar se um número é primo através da contagem de divisores diferentes da unidade e do próprio número. Esta solução necessita de 29 ISEP/DEI - Jorge Santos Saída: nomeMax, notaMax, media início soma← 0; nAlunos← 0; repetir escrever "Introduza nome:"; ler nome; se nome 6= "STOP" então repetir escrever "Introduza nota de português do aluno", nome; até nota≥0 e nota≤100; soma← soma+nota; nAlunos← nAlunos+1; se nota > notaMax então notaMax← nota; nomeMax← nome; fim-se fim-se até nome="STOP"; se nAlunos > 0 então # Calcular média; media← soma/nAlunos; escrever "Nome do aluno melhor classificado:", nomeMax; escrever "Média obtida pela turma:", media; senão # Não pode calcular média; escrever "Não foram inseridos dados."; fim-se fim Algoritmo 1.16: Determinar o aluno melhor classificado e a média das notas de uma turma Sugestão: Resolver o último exercício utilizando ciclos do tipo enquanto-fazer. 1.4.5 Exercícios Propostos Nesta secção são propostos alguns problemas com vista à aplicação dos diferentes tipos de instruções anteriormente introduzidas com particular ênfase na instruções cíclicas. 1.4.5.1 Divisão através de subtracções sucessivas O resultado da divisão inteira de um número inteiro por outro número inteiro pode sempre ser obtido utilizando-se apenas o operador de subtracção. Assim, se quiser- mos calcular 7/2, basta subtrair o dividendo (2) ao divisor (7), sucessivamente, até 32 Capítulo 1. Algoritmia e Programação que o resultado seja menor do que o dividendo. O número de subtracções realizadas corresponde ao quociente inteiro, conforme o exemplo seguinte: 7− 2 = 5 5− 2 = 3 3− 2 = 1 Descrever um algoritmo para o cálculo da divisão de um inteiro pelo outro. Note que se o dividendo for zero, esta é uma operação matematicamente indefinida. 1.4.5.2 Determinar o máximo e mínimo de uma série Ler 100 valores e determinar os valores máximo e mínimo da série. 1.4.5.3 Determinar quantidade de números primos Determinar quantos são os números primos existentes entre os valores 1 e 1000 (ex- cluindo os limites do intervalo). 1.4.5.4 Determinar se um número é perfeito Um número n é perfeito se a soma dos divisores inteiros de n (excepto o próprio n) é igual ao valor de n. Por exemplo, o número 28 tem os seguintes divisores: 1, 2, 4, 7, 14, cuja soma é exactamente 28. (Os seguintes números são perfeitos: 6, 28, 496, 8128.) Escreva um algoritmo que verifique se um número é perfeito. 1.4.5.5 Calcular potência por multiplicações sucessivas Escrever um programa que permita calcular uma potência do tipo baseexpoente atra- vés de multiplicações sucessivas. Por exemplo: 24 = 2 ∗ 2 ∗ 2 ∗ 2. Considere as dife- rentes situações relacionadas com os valores da base e/ou expoente iguais a zero. 1.4.5.6 Maior número ímpar de uma sequência de valores Descreva um algoritmo que lê uma sequência de números inteiros terminada pelo número zero e calcule o maior ímpar e a sua posição na sequência de valores. 1.4.5.7 Algarismos de um número Escreva um programa para extrair os algarismos que compõem um número e os vi- sualize individualmente. 33 ISEP/DEI - Jorge Santos 1.4.5.8 Apresentação gráfica de temperaturas Escreva um algoritmo que lê a temperatura de N cidades portuguesas e que repre- sente a temperatura de cada uma delas com uma barra de asteriscos (*), em que cada asterisco representa um intervalo de 2◦C. De acordo com os exemplos seguintes: Porto 11 ***** Lisboa 16 ******** Faro 20 ********** Chaves 8 **** 1.4.5.9 Soma dos algarismo de um número Escreva um programa que calcule a soma dos algarismos que compõem um número. Por exemplo: 7258 = 7+2+5+8 = 22 1.4.5.10 Jogo de adivinhar o número Escrever um programa para o o jogo de adivinhar um número. Este jogo consiste no seguinte: o programa sorteia um número e o jogador deve tentar adivinhar o número sorteado. Para isso o programa deve indicar se o palpite do jogador foi maior, menor ou se acertou no número sorteado. Caso o jogador acerte deve visualizado no écran o número de tentativas utilizadas. 1.4.5.11 Capicua de um número Escreva um programa que leia um número inteiro positivo e verifique se se trata de uma capicua, isto é, uma sequência de dígitos cuja leitura é a mesma nos dois senti- dos (exemplo:32523). Sugestão: Inverter a ordem dos dígitos e verificar se o número obtido coincide com o original. Por exemplo, 327 invertido é ((7*10)+2)*10+3=723. 1.4.5.12 Conversão de base numérica Elaborar um programa para converter um número escrito em binário para o corres- pondente na base decimal. A conversão faz-se de acordo com o exemplo seguinte: 10110011(2) = = 1 ∗ 27 + 0 ∗ 26 + 1 ∗ 25 + 1 ∗ 24 + 0 ∗ 23 + 0 ∗ 22 + 1 ∗ 21 + 1 ∗ 20 = 128 + 0 + 32 + 0 + 16 + 0 + 0 + 2 + 1 = 179(10) Note que os expoentes das potências na fórmula de conversão correspondem, res- pectivamente, à posição ocupada por cada algarismo no número em binário. Sendo que o algarismo mais à direita corresponde à posição zero. 34 Capítulo 1. Algoritmia e Programação de sub-rotinas permite modularizar os programas e encapsular processamento o que resulta em programas mais simples de desenvolver e ler. Quanto mais independentes os módulos (sub-rotinas) mais atentamente o progra- mador se pode concentrar sobre cada uma ignorando os restantes. Com a chamada de uma sub-rotina num qualquer ponto de um programa é transferido o controlo para essa sub-rotina. isto é, passam a ser executadas do início ao fim as instruções presentes nessa sub-rotina, retornado-se depois ao programa principal, exactamente à instrução seguinte à da chamada da sub-rotina. 1.6.1 Sub-rotinas, parâmetros e variáveis locais Na programação estruturada são normalmente referidos dois tipos de sub-rotinas: as funções e os procedimentos. A diferença entre funções e procedimentos consiste no facto de as primeiras retornarem um valor, e os segundos não. No contexto da programação uma função tem um funcionamento similar a fun- ção matemática, isto é, funciona como uma caixa preta que recebe valores (designada por parâmetros) e devolve um resultado. Por exemplo a função potencia (ver fór- mula 1.6.1) recebe a base e expoente, e devolve o resultado. Note-se que a lista de parâmetros passados para uma função pode ser vazia. resultado = potencia(base, expoente) (1.6.1) As variáveis definidas no âmbito das sub-rotinas são criadas no momento em que se inicia a execução da sub-rotina e destruídas no momento em que a sub-rotina ter- mina a sua execução, isto é, são variáveis locais (dentro do contexto da sub-rotina) por oposição às variáveis do programa que se designam por variáveis globais. Este conceito é muito importante e implica que: • a forma correcta de se passar valores para dentro de uma sub-rotina é através dos parâmetros (e não recorrendo a uma variável com o mesmo nome fora e dentro da sub-rotina); • a forma correcta de se obter valores de uma sub-rotina é recorrer a uma função (e não a um procedimento) que tem a possibilidade de devolver valores. 1.6.1.1 Funções A sintaxe e o fluxograma propostos para a definição de uma função são apresentados na figura 1.15. A função é identificada por um nome (nomeFuncao), sendo a listaParâmetros constituída por zero ou mais variáveis passadas à função. A expressão representa o valor a retornar pela função. 37 ISEP/DEI - Jorge Santos Execução função Função nomeFuncao(listaParametros) inicio . . . nome ← <expressão> . . . fim-função Figura 1.15: Fluxograma e sintaxe - Função Considere-se no seguinte exemplo a definição e utilização da função potencia1 na construção de um programa modular. Função potencia(base,expoente) início # A variável resultado é local; resultado← 1; # Calcular a potência através de multiplicações sucessivas; para i← 1; i ≤ expoente; i← i+1 fazer resultado← resultado*base; fim-para # O valor calculado é retornado através do nome da função; potencia← resultado; fim-função A potencia é utilizada no programa seguinte: início # Ler base e expoente; escrever "Introduza base="; ler base; escrever "Introduza expoente="; ler expoente; # Apresentar resultado; escrever base," ˆ ",expoente,"=",potencia(base,expoente); fim Executando o programa por exemplo para os valor 3 e 2, seria visualizado num monitor o seguinte texto: Introduza base=3 Introduza expoente=2 3^2=8 1Por uma questão de simplicidade são considerados apenas expoentes inteiros e positivos no cál- culo da potência. 38 Capítulo 1. Algoritmia e Programação 1.6.1.2 Procedimentos A sintaxe e o fluxograma propostos para a definição de um procedimento são apre- sentados na figura 1.16: Execução procedimento Procedimento nomeProcedimento(listaParametros) . . . blocos-de-instruções . . . Fim-procedimento Figura 1.16: Fluxograma e sintaxe - Procedimento Considere-se no seguinte exemplo a definição e utilização do procedimento prtNumeroInvertido que permite imprimir um número inteiro invertido. Comentário: Explicar a razão de subtrair algarismo!! Procedimento prtNumeroInvertido(numero) início enquanto numero>0 fazer # O algarismo mais à direita do número é calculado através; # da divisão inteira do número por 10; algarismo← numero % 10; escrever algarismo; # Truncar o algarismo à direita; numero← (numero-algarismo)/10; fim-enquanto fim-procedimento 1.6.2 Exercícios resolvidos Nesta secção são apresentados alguns problemas e respectivas soluções com o objec- tivo de ilustrar a utilização de procedimentos e funções na produção de programas modulares. 1.6.2.1 Função que devolve o maior algarismo de um número Considere uma função que receba um número inteiro e devolva o maior algarismo contido nesse número. 39 ISEP/DEI - Jorge Santos a) Escreva uma função que receba um inteiro decimal de 4 dígitos e o devolva cifrado. b) Escreva uma função que receba um inteiro cifrado e o decifre para o valor ori- ginal. c) Escreva uma função que apresente um «menu» com 2 opções, cifrar e decifrar número, peça ao utilizador para escolher uma das opções, e retorne a opção escolhida. d) Faça um programa que permita testar as funções anteriores. 1.6.3.5 Números primos Escreva um procedimento que imprima os números primos existentes entre dois nú- meros. Na resolução deste problema deve ser utilizada uma função que determina se um número é primo. 1.7 Recursividade Recursividade é uma característica comum a todas definições que necessitam de re- correr a si próprias para se definirem. A recursividade é largamente utilizada na ma- temática e nas ciências de computação. No contexto da computação a recursividade é muito utilizada na resolução de uma gama variada de problemas e muito particu- larmente na manipulação de estruturas de dados recursivas (e.g., e listas, árvores e grafos). Considerem-se o exemplo da função factorial definido através da formula 1.7.1. Normalmente uma definição recursiva compreende casos particulares e casos gerais, neste caso, n = 1 é o caso particular e n > 1 o caso geral. Note-se que no caso geral, a definição da função factorial é conseguida através da própria função factorial. factorial(n) = { n = 0 → 1 n > 1 → factorial(n− 1) ∗ n (1.7.1) No dia-a-dia também se encontram inúmeras definições recursivas, por exemplo, o caso dos ascendentes familiares. • Caso particular – os ascendentes de determinada pessoa são os seus pais; • Caso geral – os ascendentes de uma pessoa são os ascendentes dos seus ascen- dentes; 1.7.1 Exercícios Resolvidos Nesta secção são apresentados alguns problemas e respectivas soluções com o objec- tivo de ilustrar a utilização de algoritmos recursivos. 42 Capítulo 1. Algoritmia e Programação 1.7.2 Exercícios Propostos Nesta secção são propostos alguns problemas com vista a ilustrar a utilização de al- goritmos recursivos. 43 ISEP/DEI - Jorge Santos 44 Capítulo 2. Estruturas de dados permite definir um vector unidimensional chamado notas com 20 posições nume- radas de 1 a 20. Na figura 2.1 é apresentada uma representação gráfica possível deste vector. ... 1112 8 9 17 15Valor 201 2 3 4 5Índice ... Figura 2.1: Vector unidimensional: notas A sintaxe utilizada no acesso a cada posição do vector é a seguinte forma: nome-do-vector[índice] Como por exemplo: início # Declaração do vector; DIM notas(1 até 20); # Atribuir o valor 5 à posição 3 do vector; notas[3]← 5; # Escrever no écran o valor da posição 1 do vector ; escrever notas[1]; fim Um vector pode ter as dimensões que se pretenderem1, fazendo-se a sua separação por vírgulas. Considere-se ainda um outro exemplo, um vector bidimensional que permite re- presentar uma imagem, as duas dimensões da matriz definem o tamanho da imagem (largura e altura) e o valor guardado em cada posição, a cor do pixel. Na figura 2.2 é apresentada uma representação gráfica possível para esta matriz. ...... ......... 8001 2 3 ... ... 512 8 1 ... 64 56 11 ... 45 83 9640 1 2 ... Figura 2.2: Vector bidimensional (matriz): imagem 1Um vector também é designado matriz quando apresenta mais do que uma dimensão. 47 ISEP/DEI - Jorge Santos No seguinte exemplo é procedesse à declaração e consequente utilização deste vector bidimensional : início # Declaração da matriz; DIM imagem(1 até 800, 1 até 640); # Atribuir o valor 5 à posição definida pela coluna 2 e linha 3 da matriz; imagem[2][3]← 5; # Escrever no écran o valor da posição definida pela coluna 1 e linha 4 da matriz; escrever notas[1][4]; fim Para além da utilização descrita nesta secção, os vectores são muito utilizados de forma combinada com outras estruturas de dados (e.g., registos) por forma a definir estruturas mais complexas como por exemplo: filas, pilhas e árvores. Existem alguns aspectos a que é necessário prestar atenção quando se manipula vectores em programação, nomeadamente: • Os vectores têm dimensão fixa. O número de elementos é indicado na declara- ção e não pode ser alterado durante a execução do programa. • Os vectores não se podem manipular como um todo, mas sim elemento a ele- mento. Isto significa que não se podem somar dois vectores directamente, mas sim os elementos de cada vector individualizados. • Muitas linguagens de programação não avisam (isto é não dá erro) se o limite da dimensão de um vector for excedido. Neste caso os resultados da execução do programa podem ser imprevisíveis. 2.1.1 Exercícios resolvidos 2.1.1.1 Funções manipulando vectores Faça um algoritmo que permita: a) Uma função que faça a leitura de 10 valores (inteiros), guardando-os num vec- tor; b) Uma função que retorne a diferença entre o maior e o menor valor do vector; c) Uma função que devolva o número de valores pares e ímpares do vector; No procedimento leituraVector apresentada de seguida é realizada a leitura do vector. Note-se que tanto o próprio vector como a respectiva dimensão são passados para o procedimento como argumentos. 48 Capítulo 2. Estruturas de dados Procedimento leituraVector(vector,dim) início para i← 1; i≤ dim; i← i+1 fazer escrever "Introduza o elemento", i; ler vector[i]; fim-para fim-procedimento A função contarPares apresentada de seguida contabiliza a quantidade de nú- meros existentes no vector. A função recebe próprio vector e a respectiva dimensão como parâmetros e retorna a quantidade de pares. Função contarPares(vector,dim) início soma← 0; para i← 1; i≤ dim; i← i+1 fazer se vector[i] % 2 então soma← soma+1; fim-se fim-para # Retornar resultado; contarPares← soma; fim-função A função maiorDiferenca apresentada de seguida, recebe o próprio vector e a respectiva dimensão como parâmetros e retorna a diferença entre os valores máximo e mínimo existentes no vector. Função maiorDiferenca(vector,dim) início # Os valores máximo e mínimo são iniciados com o primeiro elemento do vector; máximo← vector[1]; mínimo← vector[1]; para i← 1; i≤ dim; i← i+1 fazer se vector[i] > máximo então máximo← vector[i]; senão se vector[i] < mínimo então mínimo← vector[i]; fim-se fim-se fim-para # Retornar resultado; maiorDiferenca← máximo-mínimo; fim-função 49 ISEP/DEI - Jorge Santos O problema de trocar os conteúdos de duas variáveis é similar e como tal o ex- tracto de código seguinte está errado, pois no final ambas as variáveis A e B conterão o mesmo valor, 5. início A← 10; B← 5; # Fazer a troca dos conteúdos - ERRADO!!!; A← B; B← A; fim No extracto seguinte é adoptado o procedimento adequado, conforme descrito anteriormente, a utilização de uma variável auxiliar. No final, as variáveis A e B conterão os valores 5 e 10, respectivamente. início A← 10; B← 5; # Fazer a troca dos conteúdos - CORRECTO!!!; temp← A; A← B; B← temp; fim 2.2.2 Pesquisa Sequencial A pesquisa sequencial é o método mais simples de implementar na procura de um elemento num vector. Este método consiste em pesquisar sequencial e exaustiva- mente um vector na procura de um dado valor. A pesquisa termina quando for en- contrado o valor a procurar ou quando tenha chegado ao fim do vector. Este método funciona em vectores ordenados e/ou desordenados. No exemplo seguinte é considerado um vector notas com 100 elementos em que se pretende procurar um valor usando o método de pesquisa sequencial descrita. 52 Capítulo 2. Estruturas de dados início DIM notas (1 até 100); escrever "Introduza o valor a pesquisar="; ler valor; # Evocar a função de pesquisa; posicao← pequisarValor(notas, 100, valor); se posicao= -1 então escrever "O valor desejado não existe no vector"; fim-se escrever "O valor desejado existe na posição=",posicao; fim Algoritmo 2.2: Utilizar a pesquisa sequencial) A pesquisa propriamente dita é realizada pela seguinte função: Função pequisarValor(vector,dim,valor) início encontrou← falso; i← 0; # Percorrer o vector até encontrar o elemento ou chegar ao fim do vector; enquanto encontrou=falso e i≤dim fazer se valor = vector[i] então encontrou← verdade; senão i← i+1; fim-se fim-enquanto se encontrou = verdade então # Caso encontre o valor retorna a posição; pequisarValor← i; senão # Caso não encontre o valor retorna -1; pequisarValor← -1; fim-se fim-função 2.2.3 Exercicios resolvidos 2.2.3.1 Inverter um vector Considere o problema de inverter um vector para o qual é apresentada de seguida uma solução possível. Esta solução troca o primeiro elemento com o último, o se- gundo com o penúltimo, o terceiro com o antepenúltimo e assim sucessivamente até inverter a totalidade do vector. Note-se que o iterador do vector vai variar desde a primeira posição até metade da dimensão. 53 ISEP/DEI - Jorge Santos Procedimento invertervector(vector,dim) início para i← 1; i ≤ dim/2; i← i+1 fazer # Fazer a troca dos dois elementos; temp← vector[i]; vector[i]← vector[dim-i+1]; vector[dim-i+1]← temp; fim-para fim-procedimento 2.2.4 Exercícios propostos 2.2.4.1 Junção ordenada de vectores Suponha que as notas dos alunos de duas turmas são lidas para dois vectores, um para cada turma. Considere que as notas foram inseridas em ambos os vectores or- denadamente, da menor para a maior. Escreva um programa que faça a junção ordenada dos dois vectores de notas num terceiro vector. 2.2.4.2 Método de ordenação por troca directa Neste método compara-se cada posição do vector com todas as outras sucessiva- mente e troca sempre que encontrar um valor menor numa posição à frente. Escreva um algoritmo que implemente este método. 2.2.4.3 Filtro gráfico Uma unidade industrial na área da metalomecânica utiliza sistemas de vídeo para o reconhecimento automático de componentes que passam num tapete rolante. Após a captura de cada imagem, esta tem que ser tratada com filtros de software que permi- tem eliminar erros menores e suavizar a imagem. Construa um programa que implementa um filtro que substitui cada pixel pela média dos valores das oito células que o rodeiam. Na imagem 2.3 está representada a imagem conforme foi capturada em que cada célula representa o tom de cinzento de um pixel. Exemplo de cálculo das células: célula B2 = A1 + A2 + A3 + B1 + B3 + C1 + C2 + C3 = 108 célula C2 = B1 + B2 + B3 + C1 + C3 + D1 + D2 + D3 = 114 Note-se que as células dos limites da imagem (assinalados a cinzento) não podem ser calculados pois não têm o número suficiente de vizinhos. 54