Apostila_1_Construcao_de_algoritmos

Prévia do material em texto

Apostila: Construção de Algoritmos 
Prof. Angelo Passaro página 1 
Construção de Algoritmos A – T7012A 
Engenharia da Computação 
 
 
1 Algoritmo 
 
Programar é criar Algoritmos. 
 
Algoritmos 
 
 Seqüência de ações necessárias para a obtenção da solução de um determinado 
tipo de problema (classe de problemas). Cada ação deve ocorrer num intervalo finito 
de tempo. 
 
 No desenvolvimento de Algoritmos devem ser considerados dois aspectos: 
1. Aspecto (ou visão) Estática 
 A seqüência de ações expressas em seqüência. 
2. Aspecto Dinâmico 
 Expressa a transformação de valores de variáveis conforme as ações são 
executadas no tempo. 
 A visão dinâmica expressa o fluxo de execução das ações para um conjunto de 
dados. 
 A capacidade de desenvolver algoritmos está intimamente relacionado com a 
compreensão e exploração desses 2 aspectos dos algoritmos (a relação entre os 2 
aspectos). 
 
Estrutura de Dados 
 É a forma na qual os dados relevantes de um problema estão organizados. 
 
Programação 
 Corresponde, essencialmente, a estruturar dados e construir algoritmos que irão 
manipular e modificar esses dados. 
 
 Análise 
Problema ���� Algoritmos ���� Solução 
 
Memória ���� Variável ���� Identificador 
 
Os seguintes operadores e funções básicas (ou primitivas) serão considerados no 
desenvolvimento dos algoritmos no escopo desta disciplina. 
 
Operadores 
 - Lógicos (E, OU, XOU, NÃO) 
 - Aritméticos (+, -, *, /, ^, MOD, DIV) 
 - Relacionais (=, <>, >=, >, <=, <) 
Apostila: Construção de Algoritmos 
Prof. Angelo Passaro página 2 
 
Funções Primitivas 
 - Matemáticas (SEN(X), COS(X), TAN(X), SQRT(X), ABS(X),...) 
 - Entrada e Saída (leia, armazene, imprima, ...) 
 - Outras. 
 
Tipos Primitivos de Dados 
INTEIRO, REAL, CARACTERE, LÓGICA 
 
Relação: Tipo � Operadores 
 
Constantes 
É um valor fixo que não pode ser modificado ao longo do tempo de execução 
do algrotimo. 
 
Modelo para declaração de variáveis e constantes(Exemplo) 
 Declaração de Constantes 
A = 4; 
 PI = 3.1415 
 
 Declaração de Variáveis 
 var1 , var2 : INTEIRO 
 var3 : REAL 
 
Estrutura de Controle 
- Seqüencial 
- Condicional 
 Simples 
 Se (condição) então 
 Inicio 
 BLOCO de instrução 
 Fim_se 
 
 Composta 
 Se (condição) então 
 Inicio 
 BLOCO executado se a condição é VERDADEIRA 
 Fim 
 Senão 
 Inicio 
 BLOCO executado se a condição é FALSA 
 Fim_se 
 
 Aninhada 
 Se (condição 1) então 
 Inicio 
Apostila: Construção de Algoritmos 
Prof. Angelo Passaro página 3 
 Se (condição 2) então 
 Inicio 
 BLOCO A 
 Fim 
 Senão 
 Inicio 
 BLOCO B 
 Fim_se 
 Fim 
 Senão 
 Inicio 
 Se (condição 3) então 
 Inicio 
 BLOCO C 
 Fim_se 
 Fim_se 
 
 Repetição 
 Enquanto (condição) faça 
 Inicio 
 BLOCO executado enquanto a condição é verdadeira 
 Fim_enquanto 
 
 Para i� valor_inicial até valor_final, INCR(j), Faça 
 Inicio 
 BLOCO executado enquanto a variável de controle 
encontra-se no intervalo Valor_inicial <= i <= valor_final 
 Fim_para 
 
OBS.: INCR(j) indica que i (variável de controle) varia com incrementos de j: 
 i � i + j; 
Quando j = 1 o trecho entre virgulas é opcional 
Para “incrementos” negativos utilizaremos DECR ao invés de INCR, j será sempre 
positivo. 
 
 Faça 
 BLOCO de instruções executado enquanto a condição é 
verdadeira 
 Enquanto (condição); 
 
 
Estruturas de dados homogêneas. 
Arrays - Permite a manipulação de um conjunto finito de dados do mesmo tipo. 
 Em termos de memória, esse conjunto de dados é armazenado de forma 
contínua (armazenamento contíguo). 
 O acesso aos dados é feito por meio de índices (variável indexada). 
Apostila: Construção de Algoritmos 
Prof. Angelo Passaro página 4 
 
Vetor - (Arrays unidimensionais) 
 O acesso aos dados armazenados em um vetor é feito com o uso de apenas um 
índice.A Figura 1 ilustra o índice e o posicionamento dos elementos de um vetor na 
memória. 
 
início . 
. 
. 
 
 1 � Vetor [1] 
 5 � Vetor [2] 
 10 � Vetor [3] 
 15 � Vetor [4] 
 
 
fim 
. 
. 
. 
 
Figura 1. Representação de um vetor na memória. 
 
 
 Usaremos o símbolo [] (colchetes) para indicar que estamos tratando com um 
“Array” e o índice do elemento do vetor é posicionado no interior dos colchetes. 
 
A declaração de um vetor será feita com o uso da seguinte sintaxe na declaração 
de variáveis: 
 id_vetor: vetor [Ii .. If] tipo 
 
Exemplos: Declarar um vetor com o nome A, Inteiro, de 30 elementos e um vetor B de 
10 elementos do tipo Real : 
 A: vetor [1..30] Inteiro 
 B: vetor [1..10] Real 
 
Matrizes - (Arrays bidimensional) 
 São necessários 2 índices para se ter acesso a um elemento do array. 
 
 Os elementos da matriz são armazenados em seqüência na memória, em ordem 
de linha ou de colunas, dependendo da linguagem de programação adotada. 
 
 
Estruturas de dados heterogêneas 
 
Registro: Estrutura de dados composta por um conjunto de variáveis de tipos 
diferentes, primitivos e/ou estruturados (homogêneos ou heterogêneos), que estão 
relacionadas logicamente e podem ser referenciadas por um mesmo nome (um 
identificador de registro) ou individualmente. 
 
A sintaxe de declaração de um registro utilizada é: 
Vetor 
1 
5 
10 
15 
(4 valores 
inteiros) 
Apostila: Construção de Algoritmos 
Prof. Angelo Passaro página 5 
 
Declaração de tipos 
 id_tipo_reg : Registro 
inicio 
 campo_1 : tipo_campo_1; 
 campo_2 : tipo_campo_2; 
........ 
 campo_N: tipo_campo_N; 
fim_registro 
 
onde: 
 id_tipo_reg é o identificador do novo tipo registro. 
 campo_i corresponde ao identificador dos componentes do registro. 
 
Se vários campos (ou componentes) apresentam o mesmo tipo, sua declaração 
pode ser efetuada na mesma linha de declaração. 
 
A declaração de uma variável do tipo id_tipo_reg é feita na seção de declaração 
de variáveis: 
 
 registro1 : id_tipo_reg 
 
Exemplo 
 
Declaração de tipos 
 Data : Registro 
 inicio 
 dia, mes, ano: inteiro; 
 fim_registro 
 
Declaração de variáveis 
 i, j : inteiro 
 inicio_aulas : Data 
 
 
2 Técnicas de desenvolvimento de algoritmos 
 
Existem várias técnicas para o desenvolvimento de algoritmos. Dentre elas, 
destaca-se a programação estrutura. A Programação Estruturada é um conjunto de 
metodologias para o desenvolvimento organizado de software, buscando obter 
produtos confiáveis, legíveis, portáveis e flexíveis, de forma a garantir fácil 
manutenção. A programação estruturada não elimina a necessidade de reflexão e 
entendimento do problema. 
 
Apostila: Construção de Algoritmos 
Prof. Angelo Passaro página 6 
As idéias básicas associadas ao desenvolvimento estruturado podem ser 
resumidas como segue: 
1. utilização de um número limitado de estruturas de controle 
(seqüencial, condicional e de repetição), e 
2. desenvolvimento de algoritmos utilizando a técnica de refinamentos 
sucessivos; 
3. transformação de alguns refinamentos em módulos. 
 
O primeiro item corresponde ao uso das estruturas de controle já discutidas 
anteriormente. Pode ser provado que qualquer problema pode ser resolvido com a 
aplicação das estruturas seqüencial, condicional e de repetição. 
Os demais itens são discutidos nas duas subseções a seguir. 
 
2.1 TÉCNICA DE REFINAMENTOS SUCESSIVOS (REFINAMENTO “TOP-DOWN”) 
O segundo item está relacionado ao processo criativo de desenvolvimento da 
solução de um problema a partir da decomposição de um problema em problemas 
menores e mais simples de serem resolvidos do que o inicial. A decomposição dos sub-
problemas deve ser feita até que as soluções estejam expressas por um conjunto de 
ações (instruções, operações e funções) elementares, como as citadas anteriormente. 
Os refinamentos sucessivos possibilitam ao desenvolvedor a preocupação com detalhes 
conforme o nível do processo de refinamento. Com este procedimento, o volume de 
noções a serem manipuladas e entendidas acada instante é mantido sob controle, o que 
facilita o entendimento necessário para se formular, completa e corretamente, a 
solução do problema a ser resolvido. O processo de refinamento sucessivo leva à 
modularização da solução. 
 
2.2 MODULARIZAÇÃO 
O último item está associado à construção de módulos isolados com funções 
bem definidas. Um módulo é um grupo de instruções (comandos) que se constitui em 
uma função bem definida e o mais independente possível em relação ao restante do 
algoritmo. Este método permite que a solução do problema possa ser desenvolvida por 
vários programadores de uma equipe, já que um módulo é “independente” dos demais. 
Este procedimento também concorre para o desenvolvimento de um conjunto de 
módulos que podem ser reutilizados, já que sua função é independente do problema 
original mas contribui para a solução. 
 
A geração de módulos tem por objetivos: 
1. evitar a duplicação de código, ou seja, que uma determinada seqüência 
de comandos necessária em vários locais do algoritmo seja repetida 
em cada um desses locais; 
2. dividir e estruturar um algoritmo em partes fechadas e logicamente 
coerentes 
3. aumentar a legibilidade do código, 
4. facilitar a documentação do algoritmo. 
 
Apostila: Construção de Algoritmos 
Prof. Angelo Passaro página 7 
Em geral, os módulos devem ter um tamanho limitado. Além disso, uma das 
características interessantes de módulos é a possibilidade de se definir estruturas de 
dados próprias do módulo, necessárias e suficientes para que estes executem suas 
tarefas. O uso de dados locais (definidos no escopo do módulo) que não têm nenhum 
significado fora do módulo é fator importante para a reutilização de um módulo criado 
para resolver um determinado problema na solução de outros problemas, além de 
simplificar a manutenção de softwares. 
Sem o uso de dados globais é necessário um mecanismo para o 
compartilhamento de informações entre módulos. Esses mecanismos são descritos na 
seção 2.2.2. 
 
A descrição estrutural da modularização pode ser feita por meio de diagramas 
hierárquicos. Na Figura 2 são representados seis módulos. O módulo A aciona os 
módulos B e C. O módulo B aciona os módulos D, E e F e o módulo C também aciona 
o módulo F. 
 
 módulo A 
módulo F módulo D módulo E 
módulo B módulo C 
 
Figura 2 – Módulos hierarquicamente organizados. 
 
2.2.1 FERRAMENTAS PARA MODULARIZAÇÃO 
 Praticamente todas as linguagens modernas de programação dispõem de 
ferramentas básicas de modularização, ou seja, permitem criar e manipular módulos. 
Dentre as principais ferramentas pode-se citar as sub-rotinas e as funções. 
 
 
2.2.2 VINCULAÇÃO ENTRE MÓDULOS (PASSAGEM DE PARÂMETROS) 
 
Visto que os módulos correpondem a um conjunto de comandos com um 
significado lógico e o mais independente possível dos detalhes do problema que se 
deseja resolver é necessário informar a ele com base em que dados a computação deve 
ser realizada. Isso pode ser feito transferindo os dados necessários por meio de 
passagem de parâmetros, os quais acabam por vincular os módulos que concorrem 
para resolver o problema. 
Os principais modos de transferência de dados são: 
 
Passagem de parâmetros por valor (parâmetros de entrada): As alterações 
efetuadas nos parâmetros formais (veja seção 2.2.3) no módulo chamado não são 
propagados para os parâmetros atuais no módulo que faz a chamada. 
Apostila: Construção de Algoritmos 
Prof. Angelo Passaro página 8 
 
Passagem de parâmetros por resultado (parâmetros de saida): Permite retornar um 
valor calculado num módulo para o módulo que fez a chamada. 
 
Passagem de parâmetros por referência (parâmetros de entrada e saída): Toda 
alteração dos parâmetros formais passados por referência para o módulo chamado se 
reflete nos parâmetros atuais do módulo que fez a chamada. 
 
 
2.2.3 SINTAXE A SER UTILIZADA NA DESCRIÇÃO DE MÓDULOS 
A sintaxe de definição de módulos utilizada nesta disciplina é apresentada a 
seguir: 
 
Identificador_módulo(lista de parâmetros formais) : tipo_retorno 
inicio 
 bloco de instruções do módulo 
fim_módulo 
 
onde: 
Identificador_módulo: nome (identificação) do módulo 
tipo_retorno: indica o tipo do parâmetro de resultado. Se nenhum tipo de retorno é 
indicado significa que o módulo não apresenta parâmetro de resultado. 
Lista de parâmetros formais: parâmetros que permitem a vinculação de módulos. 
 
Algoritmo 1: 
Módulo para o cálculo da média dos elementos de um vetor 
 
Media (A:vetor de real, N: inteiro) : real 
Declaração de variáveis (locais) 
soma,med : real; 
inicio 
 soma ← 0 
 Para i ← 1 até N faça 
 soma ← soma + A[i] 
 med ← soma/N 
 retorna med 
fim_módulo 
 
Neste exemplo, A e N são parâmetros (N é passado por valor e o vetor é passado por 
referência). O módulo calcula e retorna um valor por meio da instrução retorna. 
 
 
2.3 RECURSIVIDADE 
 
É uma das principais técnicas de projeto de algoritmos. Um procedimento é 
recursivo se chama a si mesmo, direta ou indiretamente. 
Apostila: Construção de Algoritmos 
Prof. Angelo Passaro página 9 
Em geral, o uso da recursividade permite uma descrição mais clara e concisa de 
algoritmos, principalmente quando o problema a ser resolvido é recursivo por natureza 
ou permite a utilização de estruturas recursivas, tais como árvores. 
Todo processo recursivo deve implementar uma condição de TERMINAÇÃO. A 
chamada recursiva a um procedimento P deve estar sujeita a uma condição B, a qual se 
torna não satisfeita em algum momento da computação. Conforme definido por Wirth 
(1976): 
 
[ ]PSCentãoBseP i ,≡ 
 
onde C é uma composição de comandos Si (outras instruções) e P(chamada ao 
procedimento recursivo). 
 
Técnica Básica: Definir f(x) tal que: 
 
f(x) <= 0 corresponde à condição de terminação; 
f(x) é decrementada a cada iteração, 
 
onde x é um conjunto de variáveis do programa. 
 
Simplificação: Associar um parâmetro n para P (por valor) e chamar P recursivamente 
com (n-1). Nestas condições a B é substituída por N > 0 : 
 
( )[ ]1,0 −>≡ nPSCentãonseP i 
 
Algoritmo 2 : 
Cálculo do Fatorial 
 
 
Por definição o fatorial de N>= 0 (N inteiro) é dado por 
 
�
�
�
==
>
=
10,1 NeNpara
1 N para ,1* 2* 3* ...* 2)-(N* 1)-(N* N
 N! 
 
Observe que N! = N * (N-1)! Com base nisso, podemos escrever uma versão 
recursiva do cálculo do fatorial: 
 
Fatorial (N : inteiro): inteiro 
inicio 
 Se N <= 1 retorna 1 
 senão 
retorna (N * Fatorial (N-1)) 
fim_módulo 
 
 
Apostila: Construção de Algoritmos 
Prof. Angelo Passaro página 10 
Algoritmo 3 : 
Árvore binária de pesquisa 
 
Seja a árvore apresentada na Figura 3. A estrutura de dados pode ser 
representada por: 
 
Tipo Reg : Registro 
inicio 
 chave : inteiro 
fim 
 
Tipo Apontador: ponteiro para NO. 
 
Tipo NO : Registro 
inicio 
 R : Reg 
 Esq, Dir : Apontador 
fim 
 
 5 
 1 
4 2 
3 7 
6 8 
 
 
 
 
folha 
 
Figura 3 – Uma árvore binária de pesquisa. 
 
 O seguinte algoritmo permite a realização de pesquisa central na árvore 
utilizando um procedimento recursivo. A não indicação do tipo de retorno indica que 
este módulo nada retorna. 
 
Busca_Central(p: Apontador) 
inicio 
Se p <> folha então 
 Busca_Central(p->Esq) 
 Escreve(p->R.chave) 
 Busca_Central(p->Dir) 
fim_se 
fim_módulo 
Apostila: Construção de Algoritmos 
Prof. Angelo Passaro página 11 
 
Para a implementação de um procedimento recursivo o nível mais profundo 
deve ser finito e pequeno, pois cada ativação recursiva utiliza uma parcela de memória 
para aculumar variáveis a cada chamada. Por outro lado, para que um procedimento 
recursivo seja eficiente é importante que se considere um algoritmo balanceado (o 
balanceamento também é uma técnica básica para um bom projeto de algoritmos). 
 
Há situações nas quais, mesmo que o algoritmo seja naturalmente recursivo, 
não vale a pena utilizar recursividade. Estas situações ocorrem por exemplo no caso de 
recursividade de cauda (procedimentos recursivos comchamadas ao final do 
algoritmo), representada como: 
 
 
[ ]PSCentãoBseP ,≡ 
 
Problemas com essa característica podem ser transformados facilmente em 
versões não recursivas: 
 
);( 0 SfaçaBEnquantoxxP ←≡ 
 
O caso do cálculo do fatorial é um exemplo de recursividade de cauda. A versão 
não –recursiva é mais eficiente do que a apresentada anteriormente. O mesmo vale 
para o algoritmo para o cálculo da seqüência de Fibonacci. 
 
Algoritmos 4 e 5: 
Números de Fibonacci 
 
Os números de Fibonacci têm grande aplicação em Matemática, Teoria dos 
Jogos e Ciência da Computação. Sua primeira apresentação se deu por volta do século 
XII em um estudo da velocidade de reprodução de coelhos realizado pelo matemático 
Fibonacci (Itália). 
Os números de Fibonacci são dados pela série: 
 
{ 0,1,1,2,3,5,8,13,21,34,55,89, ....} 
 
a qual é representada pela relação de recorrência: 
 
f0 = 0, 
f1 = 1 
fn = fn-1 + fn-2 para n ≥ 2 
O algoritmo recursivo (Algoritmo 4) é apresentado a seguir. 
 
 
Fibrec (n:inteiro ): inteiro 
Declaração de variáveis: 
 fib : inteiro; 
Apostila: Construção de Algoritmos 
Prof. Angelo Passaro página 12 
inicio 
se n < 2 então fib ← n 
senão fib ← FibRec(n-1) + FibRec(n-2) 
retorna fib 
fim_módulo 
 
 
Este algoritmo é ineficiente devido à repetição de cálculos. Isto pode ser 
avaliado realizando um acompanhamento do comportamento dinâmico das chamadas 
recursivas, por exemplo, para N = 5. 
 
Uma implementação não recursiva é apresentada a seguir (Algoritmo 5). Note 
que a legibilidade é menor, mas o algoritmo é muito mais eficiente. 
 
FibIter (n:inteiro ): inteiro 
Declaração de variáveis: 
 fib : inteiro; 
 i,k,F : inteiro 
inicio 
i ← 1; F ← 0 
Para k ←1 até n faça 
inicio 
F ← i + F 
i ← F – i 
fim_para 
fib ← F 
retorna fib 
fim_módulo 
 
 
 Em geral, evita-se o uso de recursividade quando existe uma solução óbvia por 
iteração. 
 
3 Diretrizes para o desenvolvimento de algoritmos 
 
As diretrizes apresentadas abaixo são genéricas e podem ser usadas ou 
adaptadas na organização dos passos que comporão a solução de um determinado 
problema (ou seja, na criação de um algoritmo para atingir um objetivo determinado). 
 
1. Identificação do problema: determinar o que se quer resolver ou qual objetivo a ser 
atingido. 
2. Identificação das “entradas de dados”: informações fornecidas, a partir das quais se 
desenvolverão os cálculos. 
3. Identificação das “saídas de dados”: as informações a serem geradas como 
resultado. 
Apostila: Construção de Algoritmos 
Prof. Angelo Passaro página 13 
4. Identificação das regras e limitações do problema ou das limitações impostas ao 
problema (recursos de hardware, por exemplo). 
5. Determinação dos procedimentos para transformar as “entradas” em “saídas”. Neste 
ponto deve ser determinada a seqüência de ações que leve à solução do problema. 
Para isto é preciso: 
5.1. observar as regras e limitações já identificadas; 
5.2. determinar ações possíveis de serem realizadas. 
6. Construção do Algoritmo, utilizando uma forma adequada para a representação de 
algoritmos (em nosso caso, utilizaremos o português estruturado, com regras de 
sintaxe definidas anteriormente neste texto);. 
7. Teste da solução - execução de todas as ações do algoritmo, seguindo o fluxo 
estabelecido para verificar se ele está realmente gerando os resultados esperados ou 
detectar possíveis erros em sua descrição. Trata-se da verificação do 
comportamento dinâmico do algoritmo, apresentado anteriormente. 
 
Algoritmo 6: 
 
Identificar o maior divisor comum (mdc) de dois inteiros. 
 
objetivo a ser atingido: encontrar o maior inteiro que divide dois inteiros 
 
dados de entrada: dois inteiros denominados u e v 
dados de saída : o mdc 
restrições: inteiros maiores que zero. 
Descrição da solução: Para resolver este problema utilizaremos o algoritmo de 
Euclides, o qual é conhecido a mais de dois mil anos. A idéia básica é : se u > v, então 
o mdc de u e v é o mesmo de v e (u-v) 
 
Algoritmo: 
u e v são inteiros fornecidos a partir de algum procedimento externo e passados por 
valor. 
 
mdc (u, v: inteiro) : inteiro 
Declaração de variáveis 
 t: inteiro 
Inicio 
Enquanto (u > 0) 
inicio 
se (u <v) então 
inicio 
 t ← u; u ← v; v ← t; 
fim_se 
u ←u – v 
fim_enquanto 
retorna v 
fim_módulo 
 
Apostila: Construção de Algoritmos 
Prof. Angelo Passaro página 14 
4 Exercícios 
 
1. Escrever um algoritmo que calcule e imprima a média das notas da classe. 
(escrever a parte do algoritmo que calcula a média em separado, reservando-o 
para o próximo exercício) 
 
2. Escrever um algoritmo que calcule e escreva o número de alunos em uma sala 
com nota superior à média (utilizar o cálculo da média obtido no exercício 
anterior, e aproveitar para incluir a noção de função (modularização). Lembrar 
que dependendo da linguagem certas adaptações podem ser necessárias). 
 
3. Faça um teste de comportamento dinâmico do algoritmo 6 utilizando como 
dados de entrada: 
a. u = 4 e v = 8 
b. u = 3 e v = 13 
c. u = 3 e v = 0 
d. u = 0 e v = 7 
 
4. O algoritmo 6 funciona sempre? Se não, sugira uma correção no algoritmo 
apresentado. 
 
5. Desenvolva um algoritmo que reduza uma fração a seus termos básicos. Utilize 
no algoritmo um registro para a representação da fração: 
 
Declaração de tipo 
 Frac: registro 
 inicio 
 n, d : inteiro 
 fim 
 
Declaração de variáveis 
 f: Frac 
 
6. Uma universidade está interessada em identificar se existem alunos cursando as 
disciplinas de “construção de algoritmos” e de “cálculo numérico” 
simultaneamente. As listas com o número de registro dos alunos de “construção 
de algoritmos” (no máximo 100 alunos) e de “cálculo numérico”(no máximo 
75 alunos) é fornecida, e cada conjunto de número de registro em uma 
disciplina tem um número de registro fictício igual a –1 no final. Desenvolva 
um algoritmo para resolver o problema.