Embed Size (px)
DESCRIPTION
Curso de 1 semestre de algoritmos e programação
Citation preview
Algoritmos
Carlos A. P. Campani
6 de setembro de 2006
Sumario
1 Introducao 2
2 Conceitos Basicos 32.1 Comando de Escrita . . . . . . . . . . . . . . . . . . . . . . . 42.2 Constantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.3 Variaveis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.4 Atribuicao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.5 Comando de Leitura . . . . . . . . . . . . . . . . . . . . . . . 82.6 Expressoes Aritmeticas . . . . . . . . . . . . . . . . . . . . . . 102.7 Expressoes Logicas . . . . . . . . . . . . . . . . . . . . . . . . 13
3 Estrutura Condicional 14
4 Estrutura de Repeticao 16
5 Algoritmos com Acumulador 19
6 Refinamentos Sucessivos 21
7 Usando Matrizes 247.1 Declaracao de Matrizes . . . . . . . . . . . . . . . . . . . . . . 257.2 Tratando com Matrizes . . . . . . . . . . . . . . . . . . . . . . 26
1
8 Usando Listas 298.1 Constantes Lista . . . . . . . . . . . . . . . . . . . . . . . . . 308.2 Operacoes com Listas . . . . . . . . . . . . . . . . . . . . . . . 308.3 Declaracao de Variavel Lista . . . . . . . . . . . . . . . . . . . 308.4 Tratando Listas . . . . . . . . . . . . . . . . . . . . . . . . . . 32
9 Sub-algoritmos 359.1 Sub-rotinas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379.2 Funcoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
10 Recursividade 44
11 Algoritmos de Ordenacao 5011.1 BUBLE SORT . . . . . . . . . . . . . . . . . . . . . . . . . . 5011.2 SELECAO DIRETA . . . . . . . . . . . . . . . . . . . . . . . 5011.3 QUICK SORT . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
12 Programacao Funcional 5512.1 Declaracao de Funcoes Lambda . . . . . . . . . . . . . . . . . 5512.2 Estruturas de Programacao Funcional . . . . . . . . . . . . . . 5512.3 Escrevendo Funcoes . . . . . . . . . . . . . . . . . . . . . . . . 56
Bibliografia
• FARRER, H. et alii. Algoritmos Estruturados. Rio de Janeiro, EditoraGuanabara, 1989;
• WIRTH, N. Programacao Sistematica. Rio de Janeiro, Ed. Campus,1978.
1 Introducao
Algoritmos sao ferramentas importantes no estudo de ciencia da computacao.A compreensao das tecnicas de desenvolvimento e construcao de algoritmose uma ferramenta valiosa, nao so para o aprendizado de linguagens de pro-gramacao, mas para o estudo das mais variadas disciplinas da area. Umexemplo poderia ser dado se lembrarmos que boa parte da teoria matematica
2
da computacao baseia-se no conceito de “algoritmo”, como uma ideia primi-tiva.
Nesta disciplina, desenvolveremos os algoritmos usando uma linguagemhipotetica, cuja estrutura e funcionamento serao descritos ao longo do desen-volvimento da disciplina. A linguagem adotada aqui foi projetada para quefosse facil a implementacao dos exemplos apresentados em uma linguagem deprogramacao usual, particularmente visando Python como linguagem alvo.
2 Conceitos Basicos
Algoritmo e a descricao de um conjunto de comandos que, efetuados, resul-tam numa sucessao finita de acoes. Uma outra forma: Algoritmo e umalista de instrucoes (comandos) ordenadas que tem por finalidade resolverum determinado problema. Exemplos de algoritmos: Uma receita culinaria;Instrucoes para montar algo.
Ex. Algoritmo para fritar um ovo:
1. Colocar um ovo na frigideira;
2. Esperar o ovo ficar frito;
3. Tirar o ovo.
O algoritmo acima nao esta detalhado. Uma versao mais aceitavel e:
1. Retirar um ovo da geladeira;
2. Colocar a frigideira no fogo;
3. Colocar oleo;
4. Esperar ate o oleo ficar quente;
5. Quebrar o ovo separando a casca;
6. Colocar o conteudo na frigideira;
7. Esperar um minuto;
8. Retirar o ovo da frigideira;
9. Apagar o fogo.
3
Esta versao e mais completa e detalhada que a anterior. Para que umalgoritmo possa ser executado e necessario que seu usuario conheca a termi-nologia nele utilizada. No exemplo anterior, para que o algoritmo seja util,e necessario que o usuario conheca o significado dos verbos Retirar, Colocar,Esperar assim como dos substantivos utilizados.
Os algoritmos estudados em aula serao algoritmos computacionais, listasde comandos a serem executados por um computador. Para que o computa-dor consiga executa-los ele tambem deve conhecer a terminologia utilizada.Ao conjunto de comandos que fazem parte de uma linguagem de programacaochama-se sintaxe da linguagem de programacao.
Os algoritmos estudados na disciplina de Algoritmos serao desenvolvidosutilizando uma sintaxe que sera apresentada progressivamente ao longo dosemestre. Esta sintaxe pode ser chamada de portugues estruturado e osalgoritmos nela desenvolvidos podem ser facilmente adaptaveis as diversaslinguagens de programacao existentes.
A forma geral dos algoritmos a ser adotada em aula e:
Algoritmo
{ lista-de-comandos }
fim_algoritmo
onde { lista-de-comandos } e uma lista com um ou mais comandos. Notea endentacao dos comandos dentro do ambiente Algoritmo-fim_algoritmo.
Vamos imaginar uma maquina virtual que executa os comandos de nossosalgoritmos, lendo os dados de uma entrada fictıcia, e imprimindo os resulta-dos em uma tela virtual. Embora esta maquina nao exista no mundo real,com ela poderemos mentalmente executar os nossos algoritmos. Com relati-vamente pouca dificuldade e possıvel traduzir os algoritmos de sala de aulapara uma linguagem de programacao real.
2.1 Comando de Escrita
O comando de escrita e utilizado quando se deseja que o algoritmo escrevaalgo. Esta “escrita” pode ser em uma impressora, um terminal de vıdeo ououtra saıda qualquer. O formato do comando e:
Escreva { lista-de-express~oes }
4
onde { lista-de-express~oes } e uma lista de uma ou mais expressoes euma expressao pode ser uma constante, uma expressao aritmetica, variavelou chamada de funcao.
Ex: (dica: use endentacao)
Algoritmo
Escreva ’Jo~ao Vitor’,’ ’,’Luana’ Escreva ’1’
Escreva 1 + 2
fim_algoritmo
Ao ser executado este algoritmo o resultado sera:
Jo~ao Vitor Luana
1
3
O exemplo e composto de tres comandos de escrita. Observe que podemoscolocar mais de um comando por linha (opcao nao muito interessante poisesconde a estrutura do algoritmo e confunde a sua leitura).
O primeiro comando manda escrever uma lista de tres constantes, nosegundo deve escrever uma constante e no terceiro deve escrever o resultadode uma expressao aritmetica. Quando um comando de escrita tiver mais deum valor a ser escrito como no primeiro, os diversos valores sao separadospor vırgula.
Observe que ’Jo~ao Vitor’ e um literal, ou seja, tudo que estiver entredois ’ sera impresso exatamente da forma com que esta escrito. A utilidadedo ’ ’ e efetuar a separacao entre os diversos termos a serem impressos jaque o comando Escreva imprime os termos sem espacos entre eles.
Ex2:
Algoritmo
Escreva ’Jo~ao Vitor’,’Luana’
Escreva 1+2
Escreva ’1+2’
fim_algoritmo
Produzindo:
Jo~ao VitorLuana
3
1+2
5
Observe o efeito da ausencia de ’ ’ entre ’Jo~ao Vitor’ e ’Luana’.Os comandos como Algoritmo e fim_algoritmo sao chamados palavras
reservadas da linguagem. A linguagem trata maiusculas e minusculas comoiguais.
2.2 Constantes
Uma constante e um valor que nao se modifica com o tempo. As constan-tes com que trabalharemos podem ser de tres tipos diferentes, numericas,logicas ou literais. Constantes numericas podem conter quaisquer valoresnumericos, reais ou inteiros, positivos ou negativos, etc. Exemplos de cons-tantes numericas sao:
25
3.14
-2.57
-0.0003
-10
Constantes literais podem conter um ou mais caracteres alfabeticos ounumericos. Sao delimitados por aspas. Exemplos de constantes literais sao:
’Jose da Silva’
’1245’
’1 2 3 de oliveira’
Constantes logicas podem conter somente dois valores, verdadeiro efalso. Normalmente sao utilizadas em testes em algoritmos.
2.3 Variaveis
Uma variavel e um valor que pode ser alterado em um algoritmo. Cadavariavel tem um nome associado a ela que a identifica. O identificador deuma variavel deve comecar por uma letra e pode conter letras ou dıgitos. Ex:
A
X5
Joao
6
Assim como as constantes as variaveis tambem podem ser de tres tipos:numericas, logicas ou literais.
Para utilizar uma variavel em um algoritmo e necessario que ela sejadeclarada no inıcio do algoritmo, ou seja, defina-se no inıcio do algoritmoqual o tipo de valor com que a variavel ira trabalhar ( numerico, logico ouliteral ). O formato do comando de declaracao e:
Declare <lista de identificadores> <tipo das variaveis>
Ex:
Declare Nota,Codigo,X5 Numerico
Declare Teste,Sim Logico
Declare Nome,End1,End2 Literal
Assim, a forma geral de um algoritmo passa a ser:
Algoritmo
{ declarac~oes }
{ corpo do algoritmo }
fim_algoritmo
2.4 Atribuicao
Uma variavel pode armazenar qualquer valor e seu valor pode ser alterado aqualquer momento no algoritmo. O comando utilizado para alterar o valorde uma variavel e o comando de atribuicao. Sua forma geral e a seguinte:
<identificador de variavel> := <express~ao>
onde <express~ao> pode ser uma constante, expressao aritmetica, variavelou chamada de funcao. Por exemplo:
A := 5
O comando acima (le-se “A recebe cinco”) faz com que a variavel A passea valer 5. O valor anterior da variavel A e perdido e seu novo valor passa aser 5.
Assim, por exemplo:
{A=10}
A := 5
{A=5}
7
E fica perdido o valor anterior da variavel (10).Entao, como trocar dois valores? Resposta: Usando uma variavel auxiliar.
Ex: trocar os valores de a e b.
aux := a
a := b
b:= aux
Outros exemplos de atribuicao sao:
A := 3 + 2
A := B
X5 := A + 1
No primeiro exemplo a variavel A recebe o resultado da expressao aritmetica3 + 2, expressao esta que contem somente constantes. No segundo exemplo avariavel A recebe o conteudo da variavel B e no terceiro exemplo a variavel X5recebe o resultado da expressao aritmetica A + 1, expressao esta que contema variavel A e a constante 1.
Um exemplo interessante:
{A=10}
A := A+1
{A=11}
Ou seja, a expressao A+1 e avaliada, tendo como resultado 10 + 1 = 11 e ovalor e atribuido a variavel A.
2.5 Comando de Leitura
O comando de leitura e utilizado quando o algoritmo deve receber um valorexterno, por exemplo, de um teclado. Seu formato geral e:
Leia <lista-de-variaveis>
Este comando faz com que a primeira variavel da lista receba o primeirovalor digitado no teclado, a segunda variavel receba o segundo valor e assimpor diante.
Ex:
Leia A,B
8
Ao executar este comando o computador espera que sejam fornecidos doisvalores na entrada virtual ( p.ex: 10 e 20 ). A variavel A recebera entao oprimeiro valor (10) e a variavel B recebera o segundo valor (20).
Ex 2.8 - Escrever um algoritmo que le tres numeros, calcula as mediasaritmetica, harmonica e geometrica e escreve os numeros lidos e as mediascalculadas.
MA =A + B + C
3MG = 3
√A×B × C MH =
31A
+ 1B
+ 1C
Ex 2.9 - Escrever um algoritmo que le o nome de um funcionario, onumero do funcionario, seu numero de horas trabalhadas, o valor que recebepor hora, o numero de filhos com idade menor que 14 anos e calcula o salariodeste funcionario.
Ex 2.10 - Escrever um algoritmo que calcula o fatorial de 5.Ex 2.11 - Escrever um algoritmo que le tres valores, a, b e c e calcula:
1. A area do triangulo que tem a por base e b por altura;
2. A area do cırculo de raio c;
3. A area do trapezio que tem a e b por bases e c por altura;
4. A area do quadrado de lado b;
5. A area do retangulo de lados a e b;
6. A area da superfıcie de um cubo que tem c por aresta.
Ex 2.12 - Escrever um algoritmo que escreve os numeros ımpares entre10 e 20.
Ex 2.13 - Escrever um algoritmo que le p, u e r, respectivamente o primeirotermo de uma progressao aritmetica, o ultimo termo da progressao e a razaodesta progressao. Determinar a soma dos termos desta progressao aritmetica.
soma =an + a1
2× n n =
an − a1
r+ 1
Ex 2.14 - Escrever um algoritmo que le o codigo da peca 1, o numero depecas 1, o valor unitario da peca 1, o codigo da peca 2, o numero de pecas2, o valor unitario da peca 2 e a percentagem do IPI a ser acrescentado ecalcula o valor total a ser pago.
9
Operacao Sımbolo Precedencia
Adicao + 3Subtracao - 3
Multiplicacao * 2Divisao / 2
Potenciacao ** 1
Tabela 1: Operacoes Aritmeticas
2.6 Expressoes Aritmeticas
Para que uma expressao possa ser avaliada em um algoritmo ela deve seguiruma sintaxe bem definida. As operacoes utilizadas nas expressoes aritmeticasem nossa linguagem sao as mostradas na Tabela 1 junto com as suas pre-cedencias. A precedencia dos operadores indica a ordem que eles serao ava-liados em uma expressao.
A precedencia dos operadores e relevante para o resultado da avaliacaode uma expressao. Por exemplo, a avaliacao da expressao 3 + 4 * 2 poderesultar 14 se a soma for efetuada em primeiro lugar ou 11 se a multiplicacaofor efetuada em primeiro lugar. Para isto se define a prioridade das operacoes.Ao avaliar uma expressao primeiro sao efetuada as potenciacoes, apos sao efe-tuadas as multiplicacoes e divisoes e por fim as adicoes e subtracoes. Quandohouverem duas operacoes de mesma prioridade para serem efetuadas, a or-dem de execucao e da esquerda para a direita.
E possıvel alterar a ordem de execucao das operacoes em uma expressaocom o uso de parenteses. Em uma expressao com parenteses em primeirolugar sao efetuadas as operacoes entre parenteses.
Ex: Expressao para o calculo das raızes de uma equacao de segundo grausegundo a formula de Bascara (usar o - unario).
X1 := (-B+(B**2-4*A*C)**(1/2))/(2*A)
X2 := (-B-(B**2-4*A*C)**(1/2))/(2*A)
Alem das operacoes acima descritas a nossa ’linguagem’ oferece as funcoespre-definidas da Tabela 2.
Ex: ABS(-2)= 2, QUOCIENTE(7,2)= 3, RESTO(5,2)= 1, TRUNCA(3.9)=3, ARREDONDA(3.4)= 3 e ARREDONDA(3.5)= 4.
10
Funcao Especificacao
LOG(x) logaritmo de x na base 10LN(x) logaritmo natural de xEXP(x) e elevado na x-esima potenciaABS(x) modulo ( valor absoluto ) de x
TRUNCA(x) valor inteiro de xARREDONDA(x) inteiro mais proximo a x
SINAL(x) −1 se x < 00 se x = 01 se x > 0
QUOCIENTE(x,y) quociente inteiro da divisao de x por yRESTO(x,y) resto da divisao inteira de x por y
Tabela 2: Funcoes Pre-definidas
Ex 2.16 - Escrever um algoritmo para calcular os sucessivos valores deE usando a serie abaixo considerando primeiro 3 termos, depois 4 termos efinalmente 5 termos:
E =1
1!+
1
2!+
1
3!+
1
4!
Ex 2.17 - Escrever um algoritmo que le o valor de um emprestimo ecalcula o valor de cada amortizacao considerando 24 amortizacoes a umataxa de 48%. Depois fazer o mesmo algoritmo lendo os valores da taxa e donumero de amortizacoes.
VAMORT = VEMPREST× TAXA/NAMORT
onde VAMORT e o valor da amortizacao, VEMPREST e o valor do empres-timo, TAXA e a taxa, e NAMORT e o numero de amortizacoes.
Ex 2.18 - Escrever um algoritmo que le um valor em cruzeiros e calculaqual o menor numero possıvel de notas de 5000, 1000, 500, 200, 100, 50, 10,5 e 1 em que o valor lido pode ser decomposto. Escrever o valor lido e arelacao de notas necessarias.
Ex 2.19 - Escrever um algoritmo que le o numero do vendedor, o seusalario fixo, o total de vendas por ele efetuadas e o percentual que ganhasobre o total de vendas. Calcular o salario total do vendedor. Escrever onumero do vendedor e o salario total.
11
Ex 2.20 - Escrever um algoritmo que le 3 valores a, b e c que sao lados deum triangulo e calcule a area deste triangulo.
area =√
s(s− a)(s− b)(s− c)
onde s = (a + b + c)/2 (semi-perımetro).Ex 2.21 - Um sistema de equacoes lineares do tipo:
{ax + by = cdx + ey = f
pode ser resolvido segundo mostrado abaixo:
x =ce− bf
ae− bdy =
af − cd
ae− bd
Escrever um algoritmo que le os coeficientes a, b, c, d, e, e f , e calcula eescreve os valores de x e y.
Ex 2.22 - O custo ao consumidor, de um carro novo, e a soma do custode fabrica com a porcentagem do distribuidor e dos impostos ( aplicados aocusto de fabrica ). Supondo que a percentagem do distribuidor seja de 28%e os impostos de 45%, escrever um algoritmo para ler o custo de fabrica deum carro e escrever o custo ao consumidor. Depois fazer o mesmo algoritmolendo os valores da porcentagem do distribuidor e dos impostos.
Ex 2.23 - Uma revendedora de carros usados paga a seus funcionariosvendedores, um salario fixo por mes, mais uma comissao tambem fixa paracada carro vendido e mais 5% do valor das vendas por ele efetuadas. Escreverum algoritmo que le o nome do vendedor, o numero do vendedor, o numerode carros por ele vendidos, o valor total de suas vendas, o salario fixo e ovalor que recebe por carro vendido e calcula o salario mensal do vendedor,escrevendo-o juntamente com o seu nome e seu numero de identificacao.
Ex 2.24 - Considerando que o aumento dos funcionarios e de 80% do INPCe mais um percentual de produtividade discutido com a empresa. Escreverum algoritmo que le o nome do funcionario, o numero do funcionario, seusalario atual, o valor do INPC e o ındice de produtividade conquistado eescreve o nome do funcionario, seu aumento e o valor do novo salario.
Ex 2.25 - Escrever um algoritmo que le 3 valores a, b e c e os escreve.Encontre a seguir o maior dos tres valores e o escreva com a mensagem: ”Eo maior”.
maior =a + b + |a− b|
2
12
Relacional Significado
= Igual a<> ou 6= Diferente de
> Maior que< Menor que>= Maior ou igual a<= Menor ou igual a
Tabela 3: Relacionais
Operador Significado
N~ao Inverte o valor logico do operandoE Verdadeiro se e somente se os
dois opeandos sao verdadeirosOu Verdadeiro se pelo menos um dos
dois operandos e verdadeiro
Tabela 4: Operadores Logicos
2.7 Expressoes Logicas
Expressoes logicas sao expressoes que avaliadas resultam em um valor logico( verdadeiro ou falso ). Assim como as expressoes aritmeticas elas tambemdispoem de um conjunto de operadores, sımbolos e prioridades. Os operado-res sao divididos em operadores relacionais e operadores logicos.
Operadores relacionais atuam sobre operandos numericos mas resultamem valores logicos. Sao operadores de comparacao entre dois operandos. ATabela 3
Operadores logicos atuam sobre valores logicos e resultam em valoreslogicos (veja Tabela 4).
Exemplos de expressoes logicas:
A > 0 E B > 3
Teste OU A * B > C
A precedencia de operadores da nossa linguagem e apresentada na Ta-bela 5.
13
Operador Precedencia
Operadores Aritmeticos 1Operadores Relacionais 2
Nao 3E 4
OU 5
Tabela 5: Operadores e suas Precedencias
Ex: Se A = 1, B = 2 e C = 2 qual o resultado da avaliacao da expressaoseguinte?
A + B = 0 E C <> 0
3 = 0 E C <> 0
Falso E Verdadeiro
Falso
3 Estrutura Condicional
Utilizada quando um trecho de algoritmo so deve ser executado em determi-nadas condicoes. Formas Gerais:
1. Se <condic~ao>
ent~ao <lista-de-comandos>
fim_se
2. Se <condic~ao>
ent~ao <lista-de-comandos>
sen~ao <lista-de-comandos>
fim_se
onde <condic~ao> e uma expressao logica qualquer.Ex:
Se a>b
ent~ao Escreva a
sen~ao Escreva b
fim_se
14
Ao ser executado este comando a expressao a > b e avaliada e depen-dendo do resultado da avaliacao e executado o primeiro comando (escrevaa) ou o segundo comando (escreva b). Observe que as estruturas podem ser“aninhadas”.
Ex2:
Se a<>b
ent~ao Se a>b
ent~ao Escreva ’a maior que b’
sen~ao Escreva ’a menor que b’
fim_se
sen~ao Escreva ’a igual a b’
fim_se
Ex3: Algoritmo que calcula a raiz da equacao y = ax + b.
Algoritmo
Declare A,B,X numerico
Leia A,B
Se A = 0
ent~ao Escreva ’N~ao ha raizes’
sen~ao X := -B/A
Escreva ’Raiz=’,X
fim_se
fim_algoritmo
15
Ex4: Algoritmo que calcula as raizes da equacao y = ax2 + bx + c.
Algoritmo
Declare A,B,C,Delta numerico
Leia A,B,C
Delta := B**2-4*A*C
Se Delta = 0
ent~ao Escreva ’So ha uma raiz’,-B/(2*A)
fim_se
Se Delta < 0
ent~ao Escreva ’ha duas raizes complexas’
Escreva -B/(2*A),’+-’,ABS((-Delta)**0.5/(2*A)),’J’
fim_se
Se Delta > 0
ent~ao Escreva ’Ha duas raizes reais’
Escreva (-B+Delta**0.5)/(2*A),’ E ’,\
(-B-(Delta**0.5))/(2*A)
fim_se
fim_algoritmo
Observe o \ no algoritmo. Ele serve para indicar que a linha continua naseguinte. Isto e util quando a linha de um algoritmo e muito grande.
4 Estrutura de Repeticao
Utilizada quando um trecho de um algoritmo deve ser repetido um deter-minado numero de vezes. Esta estrutura tambem e chamada de laco derepeticao. Forma geral:
1. Enquanto <condic~ao>
faca { lista-de-comandos }
fim_enquanto
2. Repita
{ lista de comandos }
ate <condic~ao>
16
Na primeira forma os comandos sao executados repetitivamente enquantoa condicao e verdadeira, e a condicao e testada antes (pode nao executar ne-nhuma vez). Na segunda forma os comandos sao executados repetitivamenteate a condicao tornar-se verdadeira (testa depois de executar, assim sempree executado pelo menos uma vez).
Ex: Escrever os numeros de 1 a 10.
Algoritmo
Declare I numerico
I := 1
Repita
Escreva I
I := I + 1
ate I > 10
fim_algoritmo
A variavel I e quem controla o numero de repeticoes do laco. E chamadavariavel contadora. Uma variavel contadora e uma variavel que recebe umvalor inicial, e incrementada de um valor constante no laco e tem seu valortestado em algum ponto do laco. Ao chegar a um determinado valor o laco einterrompido. A inicializacao da variavel contadora deve ir, necessariamente,fora do laco.
Existem diversas maneiras de implementar o mesmo laco, mas todo lacocom variavel de controle deve conter:
• inicializacao;
• incremento (ou decremento);
• teste de valor final.
Abaixo sao mostradas outras tres maneiras de implementar o algoritmoanterior:
17
1. Algoritmo
Declare I numerico
I := 0
Repita
I := I + 1
Escreva I
ate I = 10
fim_algoritmo
2. Algoritmo
Declare I numerico
I := 0
Enquanto I < 10
faca
I := I + 1
Escreva I
fim_enquanto
fim_algoritmo
3. Algoritmo
Declare I numerico
I := 1
Enquanto I < 11
faca
Escreva I
I := I + 1
fim_enquanto
fim_algoritmo
Ainda existe uma possibilidade adicional de abandonar um laco de re-peticao (tanto o Repita quanto o Enquanto) em qualquer lugar por meio deum comando Interrompa:
18
Enquanto verdadeiro
faca
Leia x
Se x>0 ent~ao Interrompa fim_se
Escreva ’Valor invalido’
Escreva ’Digite novamente’
fim_enquanto
significando que o laco (condicao de parada do laco e verdadeiro) sera in-terrompido (pelo comando Interrompa) apenas quando o usuario fornecerum numero maior que zero.
Ex. 4.7 Escrever um algoritmo que gera e escreve os numeros imparesentre 100 e 200.
Exerc. Escrever um algoritmo para calcular o fatorial de um numero.
5 Algoritmos com Acumulador
Quando o algoritmo necessitar efetuar alguma totalizacao usa-se uma variavelchamada acumulador. A variavel acumuladora tambem deve ser inicializada(normalmente com zero) e pode ser incrementada ou nao de um valor variavelno laco.
Ex: Somar os numeros de 1 a 10.
S := 0
I := 0
Enquanto I<10
faca
I := I + 1
S := S + I
fim_enquanto
Assim, os valores de S e I ao longo da execucao do algoritmo sao mostra-dos na Tabela 6.
Ex. 4.6 - Escrever um algoritmo que le 5 valores para a, um de cada vez,e conta quantos destes valores sao negativos, escrevendo esta informacao.
Ex. 4.8 - Escrever um algoritmo que le 10 valores, um de cada vez,e conta quantos deles estao no intervalo [10,20] e quantos deles estao foradeste intervalo, escrevendo estas informacoes.
19
Volta do laco Valor de I (ao final) Valor de S (ao final)
1 1 12 2 33 3 64 4 10...
......
10 10 55
Tabela 6: Execucao Programa de Soma
Ex. 4.9 - Escrever um algoritmo que le um numero nao conhecido de va-lores, um de cada vez, e conta quantos deles estao em cada um dos intervalos[0,25], (25,50], (50,75], (75,100].
Ex. 4.10 - Escrever um algoritmo semelhante ao anterior que calcula asmedias aritmeticas de cada intervalo e as escreve, juntamente com o numerode valores de cada intervalo.
Exercıcio: A serie de Fibonacci e uma sequencia de numeros em que osdois primeiros sao 0 e 1 e a partir daı cada numero e a soma dos anteriores,ou seja
tn = tn−1 + tn−2
Escrever um algoritmo que escreve os 10 primeiros termos da serie.Ex. 4.11 - Escrever um algoritmo que gera os 10 primeiros termos da
Serie de Fibonacci e calcula e escreve a soma destes termos.Exercıcio: Escrever um algoritmo que leia um numero N e escreva o
numero de divisores de N.
20
Algoritmo
Declare N,acum,I numerico
Leia N
acum := 0
I := 1
Repita
Se Resto(N,I)=0
entao acum := acum+1
fim_se
I := I+1
ate I>N
escreva acum
fim_algoritmo
Escrever um algoritmo que leia um numero e escreva uma mensagemdizendo: “O numero e primo” ou “O numero nao e primo” conforme o caso.
Ex. 4.12 - Escrever um algoritmo que gera os 30 primeiros termos daserie de Fibonacci e escreve os termos gerados com a mensagem: “E primo”ou “Nao e primo” conforme o caso.
6 Refinamentos Sucessivos
E uma tecnica para desenvolver um algoritmo em diversos passos aumentandoo nıvel de detalhamento a cada passo. A partir do problema gerar umapossıvel solucao e detalha-la ate um nıvel aceitavel.
Ex: Escrever um algoritmo que leia um numero e escreva a mensagem “Eprimo” ou “Nao e primo”. Primeira Versao:
Algoritmo
Declare numero
Leia numero
{Verifica se numero e primo}
Se {numero e primo}
ent~ao escreva ’numero e primo’
sen~ao escreva ’numero n~ao e primo’
fim_se
fim_algoritmo
21
Detalhamentos:
{ Verifica se numero e primo }
Um numero e primo se e divisıvel somente por si e pela unidade (1). Umamaneira de descobrir isto e contando o numero de divisores do numero. Sepossuir apenas dois divisores (1 e o proprio numero ) ele e primo.
{ Verifica se numero e primo } ⇒ { Conta numero de divisores }{ Conta numero de divisores }
acum := 0
i := 1
Repita
Se Resto(Numero,i)=0
ent~ao acum:=acum+1
fim_se
i:=i+1
ate i>numero
{ Numero e primo }
Se acum=2
ent~ao...
O refinamento para { Conta numero de divisores } nao e bom, por-que basta verificar que existem mais de dois divisores do numero para elenao ser primo. Assim, rebatizando { Conta numero de divisores } para{ Verifica se ha mais de dois divisores }, obtemos, usando o coman-do Interrompa:
{ Verifica se ha mais de dois divisores }
acum := 1
i := 1
Enquanto i <= TRUNCA(numero/2)
Faca
Se Resto(Numero,i)=0
ent~ao acum:=acum+1
fim_se
Se acum>2 ent~ao Interrompa fim_se
i:=i+1
fim_enquanto
22
Principal
rrffffffffffffffffffffffffff
²²{ numero e primo } { Verifica de numero e primo }
²²{ Verifica se ha mais de dois divisores }
Figura 1: Diagrama de Refinamentos para o Exemplo
Isto melhora a performance do algoritmo, pois ele abandona o laco assimque percebe que ja existem mais de dois divisores e faz divisoes apenas ateTRUNCA(numero/2).
A Figura 1 apresenta o diagrama de refinamentos para este exemplo.Montando as partes obtemos a versao final:
Algoritmo
Declare numero,i,acum numerico
Leia numero
acum := 1
i := 1
Enquanto i <= TRUNCA(numero/2)
Faca
Se Resto(Numero,i)=0
ent~ao acum:=acum+1
fim_se
Se acum>2 ent~ao Interrompa fim_se
i:=i+1
fim_enquanto
Se acum=2
ent~ao escreva ’numero e primo’
sen~ao escreva ’numero n~ao e primo’
fim_se
fim_algoritmo
23
Usar refinamentos sucessivos:Ex 1.12.30. Escrever um algoritmo para gerar e escrever uma tabela
com os valores do seno de um angulo A em radianos, utilizando a serie deMac-Laurin truncada com 20 termos:
sin(A) =A1
1!− A3
3!+
A5
5!− A7
7!· · ·
Os valores dos angulos A devem variar de 0.0 a 6.3 de 0.1 em 0.1.Exerc.: Repetir o exercıcio anterior, truncando a serie considerando uma
precisao de 0,0001 na aproximacao obtida (dica: considere o valor absolutodo ultimo termo).
Ex. 1.12.40. Fazer um algoritmo que calcule e escreva o cosseno de Ausando a serie truncada com 20 termos:
cos(A) = 1− A2
2!+
A4
4!− A6
6!+
A8
8!· · ·
Ex. 1.12.32. O valor aproximado de ? pode ser calculado usando-se aserie:
S =1
13− 1
33+
1
53− 1
73+
1
93· · ·
sendo π ≈ 3√
S × 32. Fazer um algoritmo para calcular e escrever o valor deπ com 51 termos.
7 Usando Matrizes
Matriz e um conjunto de variaveis, cada uma podendo representar o valorde uma constante, como se fossem variaveis simples, mas todas elas com-partilhando um nome comum. Indices sao associados a este nome comumpermitindo individualizar os elementos do conjunto.
Ex: conjunto de 5 elementos e nome a
a1 a2 a3 a4 a5
Qual e a utilidade dos matrizes? Resposta: Tratar com dados em seriedo mesmo tipo.
Ex: Deseja-se calcular a media de notas de 10 alunos e determinar quantosficaram acima da media. Portanto, deve-se calcular a media de 10 numeroslidos e determinar quantos destes numeros estao acima da media.
Para calcular a media podemos usar o seguinte algoritmo:
24
Algoritmo
Declare cont,soma,num numerico
cont := 10
soma := 0
Repita
Leia num
soma := soma+num
cont := cont-1
Ate cont=0
Escreva soma/10
fim_algoritmo
Problema: Quando os numeros sao lidos nao conhecemos ainda o valorda media. Ao final do programa anterior nao temos mais acesso aos numeroslidos (pois ja foram lidos). Le-los novamente seria perda de tempo.
Como fazer este algoritmo sem matrizes?Resposta: Ler os 10 numeros e guarda-los em 10 variaveis para testar
uma a uma apos obter a media.Problema: E se fossem 1000 alunos? Teriamos dificuldades de manipular
1000 variaveis diferentes.Solucao: uso de uma matriz para armazenar os valores das notas para
posteriormente processa-los.
7.1 Declaracao de Matrizes
Deve-se definir nas declaracoes:
1. Quais variaveis do algoritmo sao do tipo matriz;
2. Quantas dimensoes possui cada uma delas;
3. Qual o tamanho de cada dimensao;
4. O tipo dos componentes individuais da matriz.
Notacao:
Declare <Nome> ’(’ <tamanho> ’)’ <tipo>
Declare <Nome> ’(’ <tamanho> ’,’ <tamanho> ... ’)’ <tipo>
25
Ex: Declare a(5),m(6,8) numerico.Convencao: O primeiro ındice representa a linha e o segundo a coluna.
O menor ındice e o 1.
7.2 Tratando com Matrizes
Para ler uma matriz e necessario ler cada um dos seus componentes indivi-duais.
Ex: Ler 5 elementos da matriz a.
Algoritmo
Declare i,a(5) numerico
i := 1
Enquanto i<6
faca
Leia a(i)
i:=i+1
fim_enquanto
fim_algoritmo
Observacao: a variavel i e chamada de ındice.Ex: Ler os 48 elementos da matriz m(6, 8). Devemos usar duas variaveis
de ındice.
Algoritmo
Declare i,j,m(6,8) numerico
i:=1
Enquanto i<7
faca
j:=1
Enquanto j<9
faca
Leia m(i,j)
j:=j+1
fim_enquanto
i:=i+1
fim_enquanto
fim_algoritmo
26
Observe que este algoritmo usa dois lacos aninhados.Ex: Somar os elementos da diagonal principal de m(10, 10), lendo a matriz
antes e escrevendo a soma ao final.
Algoritmo
Declare soma,i,j,m(10,10) numerico
i:=1
Repita
j:=1
Repita
Leia m(i,j)
j:=j+1
ate j>10
i:=i+1
ate i>10
soma:=0
i:=1
Repita
soma:=soma+m(i,i)
i:=i+1
ate i>10
Escreva soma
fim_algoritmo
Exerc.: Calcular a media de 10 alunos de uma disciplina, entrando anota e o nome do aluno. Determinar o numero de alunos que tiveram notasuperior a media e imprimir o nome dos alunos que tiveram este feito.
Ex. 2.5.1.4. Dado um conjunto de 100 valores numericos disponıveis naentrada, fazer um algoritmo para armazena-los em uma matriz e calcular eimprimir o valor do somatorio dado a seguir:
S = (v1 − v100)3 + (v2 − v99)
3 + (v3 − v98)3 + · · ·+ (v50 − v51)
3
Determinar a posicao, dentro de uma matriz quadrada, de um elementopode ser muito util em alguns tipos de algoritmos. Por exemplo, determi-nar se determinado elemento esta acima ou abaixo da diagonal principal damatriz.
27
Figura 2: Posicoes em uma Matriz
Algumas relacoes sao importantes para determinar a posicao dos elemen-tos de uma matriz quadrada (veja Figura 2).
a11 a12 a13 · · · a1n
a21 a22 a23 · · · a2n
a31 a32 a33 · · · a3n...
......
. . ....
an1 an2 an3 · · · ann
Sendo i e j os ındices dos elementos da matriz:
• Diagonal principal – i = j;
• Diagonal secundaria – i + j = n + 1;
• Abaixo da diagonal principal – i > j;
• Acima da diagonal principal – i < j;
• Acima da diagonal secundaria – i + j < n + 1;
• Abaixo da diagonal secundaria – i + j > n + 1.
Exerc. Escrever um algoritmo para ler um valor n e a seguir ler umamatriz n × n. Entao, determinar a soma de todos os elementos acima dadiagonal principal e imprimi-lo.
Exerc. Escrever um algoritmo para ler uma matriz a de tamanho n×me outra matriz b de tamanho m× p. Entao, determinar e imprimir a matrizproduto c de tamanho n× p.
cij =m∑
k=1
aikbkj
28
CAR CDR
3 nil
nila
1 2 c
b
Figura 3: Representacao Grafica da Lista
8 Usando Listas
Uma estrutura formada por uma sequencia de elementos de tipos diversos echamada de lista. Importante observar que um elemento de uma lista podeser outra lista.
Por exemplo:
[1,2,3,[’a’,’b’],’c’]
que e uma lista com cinco elementos e o quarto elemento da lista e uma outralista de dois elementos.
Na representacao interna de lista, cada elemento de uma lista e formadopor um nodo com dois elementos (CAR e CDR – pronuncia-se “cuder”) quepodem ser preenchidos com valores constantes (numericos, literais ou logicos)ou elos. Um elo e um indicador da posicao de um outro nodo na memoria damaquina. Existe um elo especial (nil) que nao aponta para nenhum lugar ee usado para indicar o fim de uma lista. nil pode indicar tambem uma listavazia. Observe que uma matriz nao pode ser um elemento de uma lista.
Exemplo:
[1,2,3,[’a’,’b’],’c’]
seria armazenado internamente na memoria da maquina como ilustrado naFigura 3.
Comumente se chama a parte CAR de cabeca da lista e a parte CDR deresto ou rabo da lista.
29
8.1 Constantes Lista
As constantes listas sao qualquer sequencia de numericos, literais ou logicos,separados por vırgulas e delimitados por [ e ]. Uma constante lista pode terem um ou mais de seus termos outras listas e assim por diante. Ex:
[1,2,[’a’,’b’,[1,’b’]],3]
8.2 Operacoes com Listas
Estao definidas em nossa linguagem de algoritmos as funcoes e operacoessobre listas da Tabela 7. Ex:
CAR(CDR([1,2,3]))=2
CDR(CDR([’a’,’b’,’c’,’d’]))=[’c’,’d’]
CDR(CAR(CDR([1,[2,3],4])))=[3]
CONS(’a’,[’b’,’c’])=[’a’,’b’,’c’]
CONS(’a’,nil)=[’a’]
CONS([1,2],[’a’,’b’])=[[1,2],’a’,’b’]
NIL([1,2])=falso
[1,2,3,4,5](2)=3
A Figura 4 apresenta a interpretacao grafica das operacoes CAR e CDR paraa avaliacao CDR(CAR(CDR([a,[b,[c]],d]))).
8.3 Declaracao de Variavel Lista
Uma variavel lista e declarada da seguinte forma:
Declare x lista
Podemos agora manipular a variavel lista em uma atribuicao.Ex:
x := [2,3,4]
x := CONS(1,x)
que resulta em x igual a [1,2,3,4].Observacao: Nao podemos atribuir um valor a uma posicao qualquer da
lista. So podemos trocar sua cabeca:
x := [1,2,3,4]
x := CONS(10,CDR(x))
que resulta em x igual a [10,2,3,4].
30
a
b d nil
nil
nilc
primeiro CDR
CAR
segundo CDR
Figura 4: Interpretacao Grafica de CAR e CDR
31
Operacao Significado
CAR(x) Obtem a cabeca de uma lista(devolve o CAR de x)
CDR(x) Obtem o resto de uma lista(devolve a lista CDR de x)
CONS(x,y) Constroi um nodo tendo comoCAR x, e como CDR y
(segundo argumento deve ser uma lista)x(i) Devolve a i-esima posicao da lista x
(o ındice da primeira posicao e zero)TAM(x) Tamanho da lista x
NIL(x) Verifica se a lista e vazia(testa se x e igual a nil,
retornando verdadeiro ou falso)
Tabela 7: Funcoes e Operacoes sobre Listas
8.4 Tratando Listas
Listas sao uma estrutura dinamica muito poderosa e flexıvel para construiralgoritmos que tratem com situacoes em que os dados estao constantementesendo inseridos e retirados (pilhas e filas sao exemplos).
Tambem sao uma boa alternativa as matrizes, em casos em que o tama-nho dos dados e conhecido apenas em tempo de execucao. Por exemplo, sedesejamos encontrar o numero de elementos que sao menores que a media deum conjunto de numericos:
32
Algoritmo
Declare x,n,i,acum,m numerico
Declare a lista
Escreva ’Entre a quantidade de valores’
Leia n
i := 1
a := nil
acum := 0
Enquanto i<n+1
faca
Escreva ’Entre com valor ’,i
Leia x
a := CONS(x,a)
i := i+1
acum:=acum+x
fim_enquanto
m := acum/n
acum := 0
Enquanto N~ao NIL(a)
faca
Se a(0)<m ent~ao acum := acum+1 fim_se
a := CDR(a)
fim_enquanto
Escreva acum
fim_algoritmo
Exercıcio: Escreva um trecho de algoritmo que apague o ultimo elementode uma lista qualquer.
Exercıcio: Escrever um algoritmo que leia uma lista de 10 elementos edepois apague da lista todos os elementos que forem menores que 100.
33
Solucao:
Algoritmo
Declare x,i numerico
Declare a,b lista
i := 1
a := nil
Enquanto i<11
faca
Leia x
a := CONS(x,a)
i := i+1
fim_enquanto
i := 1
b := nil
Enquanto N~ao NIL(a)
faca
Se CAR(a)>=100
ent~ao b:=CONS(CAR(a),b)
fim_se
a := CDR(a)
fim_enquanto
Escreva b
fim_algoritmo
Exercıcio: Escreva um trecho de algoritmo que encontre o maior valor deuma lista de numericos.
Exercıcio: Escrever um trecho de algoritmo que inverta uma lista.E se precisassemos fazer a concatenacao de duas listas? Assim, se a=[1,2,3]
e b=[4,5] sua concatenacao sera [1,2,3,4,5].Atencao: CONS(a,b) nao vai funcionar. Por que?Exercıcio: Escrever um trecho de algoritmo para concatenar duas listas.
34
9 Sub-algoritmos
Sub-algoritmos sao trechos de algoritmos que efetuam um ou mais calculosdeterminados em sua declaracao ou definicao. Ao inves de escrever-se umalgoritmo grande, escrevem-se varios algoritmos menores, os quais, nao iso-ladamente, mas em conjunto, resolvem o problema proposto. E convenienteusa-los quando uma determinada tarefa e efetuada em diversos lugares nomesmo algoritmo. Ao inves de escrever-se o mesmo trecho diversas vezes,escreve-se o sub-algoritmo e o mesmo e chamado diversas vezes.
As vantagens sao:
• Eles reduzem o tamanho do algoritmo;
• Facilitam a compreensao e visualizacao do algoritmo;
• Isolam determinadas partes do algoritmo para que possam ser desen-volvidas e testadas em separado.
O sub-algoritmo e definido apos as declaracoes de variaveis e antes docorpo principal do algoritmo. Assim, a estrutura dos nossos algoritmos pas-sara a ser:
Algoritmo
{ Declarac~oes de variaveis }
{ Definic~oes de sub-algoritmos }
{ corpo do algoritmo }
fim_algoritmo
Argumentos (ou parametros) sao valores enviados ao sub-algoritmo paraserem processados, e/ou recebidos do sub-algoritmo como resultados do pro-cessamento.
Um sub-algoritmo pode conter declaracoes de variaveis, mas as variaveisdeclaradas nele (chamadas variaveis locais do sub-algoritmo) so podem seracessadas dentro dele. Alem de suas variaveis locais, um sub-algoritmopode acessar variaveis declaradas fora dele, no algoritmo principal (chama-das variaveis globais). Os parametros usados na definicao do sub-algoritmosao chamados parametros formais, e os parametros usados na chamada dosub-algoritmo sao chamados de parametros reais.
Ex:
35
Algoritmo
Declare a,b numerico
Sub-rotina y(c,d numericos)
Declare e,f numerico
{ comandos de y }
fim_sub-rotina
Sub-rotina z(e numerico)
Declare f numerico
{ comandos de z }
fim_sub-rotina
y(1,2)
z(10)
fim_algoritmo
Onde: a, b – variaveis globais (acessadas pelo algoritmo e pelos dois sub-algoritmos);
e, f – variaveis locais a y (acessadas apenas pelo sub-algoritmo y);c, d – parametros formais de y (usados na hora da chamada de y)
declarados como numericos;f – variavel local a z (acessada somente pelo sub-algoritmo z, nao
possuindo qualquer relacao com a outra variavel f (local a y);e – parametro formal de z, declarado como numerico;y(1, 2) – chamada de y com parametros reais 1 e 2 (1 sera atribuido a
c e 2 sera atribuido a d);z(10) – chamada de z.
Existem varios tipos de passagem de parametros para sub-algoritmo:
Passagem por valor Envia um valor para o sub-algoritmo e nao retornavalores pelo parametro formal (so entrada). No momento da chamadaos valores dos parametros reais sao copiados para os parametros formaispara serem usados dentro do sub-algoritmo sem que se modifiquem osvalores armazenados nos parametros reais. Ex: PASCAL (padrao);
Passagem Copia-restaura Envia e recebe valores do sub-algoritmo (en-trada e saıda). Na chamada os valores passados sao copiados para osparametros formais e usados. Ao final (no retorno do sub-algoritmo)
36
os valores finais dos parametros formais sao copiados de volta nosparametros reais (e obvio que os parametros reais, neste caso, deveraoser variaveis);
Passagem por referencia Envia e recebe valores do sub-algoritmo (en-trada e saıda) usando uma referencia a variavel (nao faz copia; usa oproprio parametro real dentro do sub-algoritmo). Ex: PASCAL (VAR).
Nos nossos algoritmos usaremos passagem Copia-restaura e por valor.Indicaremos o tipo copia-restaura antecedendo a palavra reservada CR aosparametros deste tipo.
Existem dois tipos de sub-algoritmos: sub-rotinas (ou procedures) e fun-coes.
9.1 Sub-rotinas
Retornam valores apenas pelos argumentos (caso sejam passados como copia-restaura).
Declaracao:
sub-rotina <nome>[’(’<lista de parametros formais>’)’]
{ declarac~oes locais a sub-rotina }
{ comandos }
fim_sub-rotina
Observe que podemos definir uma sub-rotina sem parametros formais(para qual nao precisamos passar nenhum parametro na chamada). Observetambem que e possıvel definir um sub-algoritmo dentro de outro (aninha-mento), pois nao faremos nenhuma restricao ao que pode ser declarado den-tro de um sub-algoritmo. Sub-algoritmos declarados dentro de outros saolocais a estes (desconhecidos fora).
Ex.: Sub-rotina troca
sub-rotina troca(x,y numerico)
Declare aux numerico
aux:=x
x:=y
y:=aux
fim_sub-rotina
37
Esta sub-rotina nao funciona. Porque? Resposta: falta definir a passagemde parametros Copia-restaura).
sub-rotina troca(CR x,y numerico)
Declare aux numerico
aux:=x
x:=y
y:=aux
fim_sub-rotina
Exemplo: Um algoritmo para ordenar 3 valores em ordem crescente.
Algoritmo
Declare a,b,c : numerico
sub-rotina troca(CR x,y numerico)
Declare aux numerico
aux:=x
x:=y
y:=aux
fim_sub-rotina
Leia a,b,c
Se a>b
ent~ao troca(a,b)
fim_se
Se a>c
ent~ao troca(a,c)
fim_se
Se b>c
ent~ao troca(b,c)
fim_se
Escreva a,b,c
fim_algoritmo
38
9.2 Funcoes
Retornam um valor pelo seu nome (alem de pelos parametros declaradoscomo copia-restaura).
Ex: ABS(x), TRUNCA(x) (funcoes pre-definidas)Declaracao:
func~ao <tipo> <nome>[’(’<lista de parametros formais’)’]
{ declarac~oes locais }
{ comandos }
fim_func~ao
Observe que devemos declarar o tipo que sera retornado pela funcao.Chamada:
a := TRUNCA(3.5)
ou
se SINAL(x)<=0 ...
Retorno do valor usando a palavra reservada Retorna.Ex: Funcao fatorial(n):
func~ao numerico fatorial(n numerico)
Declare fat numerico
fat:=1
Enquanto n>1
faca
fat:=fat*n
n:=n-1
fim_enquanto
Retorna fat
fim_func~ao
Usando sub-algoritmos:Ex 3.3: Escrever um algoritmo que leia as medidas dos tres lados a, b
e c de um paralelepıpedo, calcule e escreva o valor de sua diagonal (vejaFigura 5).
39
c
a
bd
dia
Figura 5: Paralelepıpedo
Ex 3.4: Escrever uma funcao logica que recebe uma variavel unidimen-sional M de numericos, o numero N de elementos de M , e um valor X eretorne verdadeiro se X pertence a M ou falso em caso contrario.
Como passar uma matriz como parametro real?Resposta: encontra(m(),n,x numerico) (nao indicar seu tamanho –
decidido na hora da chamada).Ex 3.5: Escrever uma funcao que calcule a distancia entre dois pontos de
um plano, sendo fornecidas as coordenadas (x1, y1) e (x2, y2).Exercıcio: Escrever um algoritmo que leia 10 conjuntos de valores x1,y1,
x2, y2, x3 e y3 coordenadas de 10 triangulos e calcule a area dos 10 triangulos,usando a funcao do exercıcio anterior. Usar duas funcoes:
1. A do exercıcio anterior;
2. Uma que chame a anterior tres vezes e use a formula do semi-perımetropara calcular a area.
Ex 3.6: escrever um algoritmo que:
• Leia varios pares de numeros inteiros positivos, M e P ;
40
• calcule e escreva o numero de arranjos e combinacoes de M elementosP a P , dado pelas formulas:
APM =
M !
(M − P )!CP
M =M !
P (M − P )!
Se M < P , por definicao:
APM = 0 CP
M = 0
Ao final de cada calculo de um par e perguntado se deseja continuar. Aresposta deve ser ’S’ ou ’N’.
Exerc. Utilizando as seguintes series, com 20 termos:
ex = 1 + x +x2
2!+
x3
3!+ · · ·
ln(x) =(
x− 1
x
)1
+ 1/2(
x− 1
x
)2
+ 1/3(
x− 1
x
)3
+ · · ·
Faca um algoritmo que gere uma tabela de x, ex, e ln(x), para x variandoentre 1 e 100 com intervalos de 0.5 (x = 1, x = 1.5, x = 2, . . . , x = 100).Defina sub-algoritmos onde for necessario.
Solucao (observe as funcoes aninhadas e seu escopo):
Algoritmo
Declare x numerico
{ declarac~oes das func~oes }
x := 1
Repita
Escreva x,’ ’,exp2(x),’ ’,ln2(x)
x := x+0.5
ate x>100
fim_algoritmo
41
Funcoes:
Func~ao numerico exp2(x numerico)
Declare soma,ind numerico
Func~ao numerico fatorial(n numerico)
Declare fat numerico
fat := 1
Enquanto n>1
faca
fat := fat*n
n := n-1
fim_enquanto
Retorna fat
fim_func~ao
soma := 1
ind := 1
Repita
soma := soma+(x**ind)/fatorial(ind)
ind := ind+1
ate ind>19
Retorna soma
fim_func~ao
Func~ao numerico ln2(x numerico)
Declare soma,ind numerico
soma := 0
ind := 1
Repita
soma := soma+(((x-1)/x)**ind)/ind
ind := ind+1
ate ind>20
Retorna soma
fim_func~ao
Observe que o laco da funcao exp2 tem como condicao de parada ind>19,pois serao somados 20 termos e o primeiro e 1 e ja foi somado (soma := 1).
42
Exerc. A partir das seguintes series do sin e cos, e usando funcoes, escrevaum algoritmo que gere uma tabela de x, sin(x), cos(x), tan(x), cot(x), sec(x),e csc(x) para x variando de 0.5 a 1.5 em intervalos de 0.1. Calcule os valoresdo sin e do cos com erro maximo de 0.0001 (≈ modulo do ultimo termo).
sin(x) = x− x3
3!+
x5
5!− x7
7!+ · · ·
cos(x) = 1− x2
2!+
x4
4!− x6
6!+ · · ·
Relacoes:
tan(x) =sin(x)
cos(x)cot(x) =
1
tan(x)sec(x) =
1
cos(x)csc(x) =
1
sin(x)
Solucao:
Algoritmo
Declare x numerico
{ declarac~oes de func~oes }
x := 0.5
Repita
Escreva x,’ ’,sen(x),’ ’,cos(x),’ ’,sen(x)/cos(x),’ ’,\
cos(x)/sen(x),’ ’,1/cos(x),’ ’,1/sen(x)
x := x+0.1
ate x>1.5
fim_algoritmo
Funcoes:
Func~ao numerico fatorial(n numerico)
Declare fat,cont numerico
cont := 1
fat := 1
Repita
fat := fat*cont
cont := cont+1
ate cont>n
Retorna fat
fim_func~ao
43
Func~ao numerico sen(x numerico)
Declare acum,soma,ind,termo,sinal numerico
acum := 0
ind := 1
sinal := 1
Enquanto abs(termo)>0.0001
faca
termo := sinal*(x**ind)/fatorial(ind)
acum := acum+termo
sinal := -sinal
ind := ind+2
fim_enquanto
Retorna acum
fim_func~ao
Func~ao numerico cos(x numerico)
Declare acum,ind,termo,sinal numerico
acum := 1
ind := 2
sinal := -1
Enquanto abs(termo)<0.0001
faca
termo := sinal*(x**ind)/fatorial(ind)
acum := acum+termo
ind := ind+2
sinal := -sinal
fim_enquanto
Retorna acum
fim_func~ao
10 Recursividade
Uma funcao e dita recursiva quando contem, em seu corpo, uma chamada a simesma (este tipo de recursividade e chamada recursividade direta). Sao uti-lizadas quando e possıvel decompor o problema a ser resolvido em problemasmenores, um dos quais e semelhante ao problema inicial.
44
Ex.: Fatorial.
n! = n× (n− 1)× (n− 2) · · · 3× 2× 1
Uma forma recursiva de definir o fatorial e:{
fat(n) = 1 n = 0 ∨ n = 1 (Base)fat(n) = n× fat(n− 1) n > 1 (Passo recursivo)
Outro ex.: A soma dos numeros de 1 a n pode ser definida de formarecursiva como:
{soma(1) = 1soma(n) = n + soma(n− 1) n > 1
A soma dos numeros ımpares de 1 a n pode ser definida de forma recursivapor:
somaimp(1) = 1somaimp(n) = somaimp(n− 1) n par ∧ n > 1somaimp(n) = n + somaimp(n− 2) n impar ∧ n > 2
Algoritmo da funcao fatorial definida recursivamente:
Func~ao numerico fatorial(n numerico)
Se n=0 OU n=1
ent~ao Retorna 1
sen~ao Retorna n*fatorial(n-1)
fim_se
fim_func~ao
A execucao desta funcao para uma chamada fatorial(3) e a mostradana Figura 6.
Exerc.: Definir recursivamente a funcao que devolve a soma dos numerosımpares de 1 a n.
Exerc.: Definir recursivamente a funcao que determina o n-esimo termoda serie de fibonacci (veja a Tabela 8).
45
fatorial(3)
²²3 ∗ fatorial(2)
²²
// 3× 2 = 6 // 6
2 ∗ fatorial(1)
²²
// 2× 1 = 2
88qqqqqqqqqqqq
fatorial(1) = 1
66mmmmmmmmmmmmm
Figura 6: Execucao de fatorial(3)
n fibonacci(n)
0 01 12 13 24 35 56 8...
...
Tabela 8: Tabela do Fibonacci
46
Solucao:
Func~ao numerico fibonacci(n numerico)
Se n=0 OU n=1
ent~ao Retorna n
sen~ao Retorna fibonacci(n-1)+fibonacci(n-2)
fim_se
fim_func~ao
Exerc.: Considere uma sequencia de numeros onde cada termo e dado pelacombinacao dos 4 termos anteriores An = An−4+2×An−3+3×An−2+4×An−1
e os 4 primeiros termos sao por definicao:
A1 = 1 A2 = 2 A3 = 3 A4 = 4
Escreva uma funcao recursiva SEQ que receba um numero n e retorne otermo An.
Solucao:
Func~ao numerico seq(n numerico)
Se n<=4
ent~ao Retorna n
sen~ao Retorna seq(n-4)+2*seq(n-3)+3*seq(n-2)+4*seq(n-1)
fim_se
fim_func~ao
Exerc.: Dois numeros sao amigos entre si, se a soma dos divisores de cadaum deles e igual ao outro. Exemplo, 220 e 284:
Divisores de 220 Divisores de 2841 12 24 45 7110 14211 Soma 22020224455110Soma 284
47
Faca um algoritmo que leia dois numeros e verifique se sao amigos.Solucao:
Algoritmo
Declare a,b numerico
{ declarac~ao de func~oes }
Leia a,b
Se a=soma(b) E b=soma(a)
entao Escreva ’S~ao amigos’
sen~ao Escreva ’N~ao s~ao amigos’
fim_se
fim_algoritmo
Funcoes com solucao nao recursiva:
Func~ao numerico soma(n numerico)
Declare aux,ind numerico
ind := 1
aux := 0
Repita
Se resto(n,ind)=0
ent~ao aux := aux+ind
fim_se
ind := ind+1
ate ind=n
Retorna aux
fim_func~ao
Solucao recursiva (chamar soma(n,n-1)):
Func~ao numerico soma(num,cont numerico)
Se cont=1
ent~ao Retorna 1
sen~ao
Se RESTO(num,cont)=0
ent~ao Retorna cont+soma(num,cont-1)
sen~ao Retorna soma(num,cont-1)
fim_se
fim_se
fim_func~ao
48
CBA
Figura 7: Torre de Hanoi
Exemplo: Torre de Hanoi (objetivo e mover os tres discos de A para C,movendo um por vez e sem nunca colocar um disco maior sobre um menor;veja Figura 7).
Mover 3 discos de A para C=
Mover 2 discos de A para B=
Mover 1 de A para C
Mover 1 de A para B
Mover 1 de C para B
Mover 1 disco de A para C=
Mover 1 de A para C
Mover 2 discos de B para C=
Mover 1 de B para A
Mover 1 de B para C
Mover 1 de A para C
Solucao (chamar move(3,1,3,2)):
Sub-rotina move(num,origem,destino,interm numerico)
Se num=1
ent~ao Escreva ’move de ’,origem,’ para ’,destino
sen~ao
move(num-1,origem,interm,destino)
move(1,origem,destino,interm)
move(num-1,interm,destino,origem)
49
fim_se
fim_sub-rotina
Outros problemas interessantes que podem ser resolvidos recursivamente:
O problema do cavalo Mover o cavalo por todas as casas do tabuleiro semocupar nunca duas vezes a mesma casa comecando em qualquer casa;
O problema das oito rainhas Colocar oito rainhas em um tabuleiro semque nenhuma ataque a outra.
11 Algoritmos de Ordenacao
Os algoritmos de ordenacao (ou classificacao) permitem ordenar os dados emalguma ordem (crescente ou decrescente). Podem ser aplicados sobre dadosnumericos ou alfabeticos (neste caso deve-se associar uma ordem entre ossimbolos alfabeticos).
11.1 BUBLE SORT
E um tipo de algoritmo de ordenacao por troca com tempo de ordenacaoproporcional a O(N2) trocas.
10 19 13 12 7 .10 13 12 7 . 1910 12 7 . 13 1910 7 . 12 13 197 . 10 12 13 19
11.2 SELECAO DIRETA
E um tipo de algoritmo de ordenacao por selecao com tempo de ordenacaoproporcional a O(N2) comparacoes.
. 10 19 13 12 77 . 19 13 12 107 10 . 13 12 197 10 12 . 13 197 10 12 13 . 19
50
Implementacao:
Sub-rotina selec(vet(),inic,fim numerico)
Declare elem,pos numerico
Se inic<>fim
ent~ao
pos := menor(vet,inic,fim)
elem := vet(pos)
vet(pos) := vet(inic)
vet(inic) := elem
selec(vet,inic+1,fim)
fim_se
fim_sub-rotina
e menor e uma funcao que encontra o menor elemento e devolve seu ındicena matriz.
Exercıcio: Reescrever esta sub-rotina usando listas. Escrever tambem afuncao menor para este caso.
Exercıcio: Implementar o Buble Sort.
11.3 QUICK SORT
E um tipo de algoritmo de ordenacao por troca e particao com tempo de or-denacao proporcional a O(n log2 n). Baseia-se no princıpio que e mais rapidoordenar dois vetores de n/2 elementos do que um vetor com n elementos.
Baseia-se em um algoritmo que particiona o vetor em dois, o primeirodos valores menores e um segundo dos valores maiores que um elemento decomparacao. O elemento de comparacao e, normalmente, o primeiro ele-mento do vetor. Depois o algoritmo e repetido para as duas partes, obtendoa ordenacao completa.
O particionador comeca em ambas as extremidades do vetor efetuandotrocas para colocar os elementos menores e maiores que o de comparacao emseus lugares.
Exemplo de particionamento:
51
60 83 25 98 94 36 99 73 45 15 22 1010 60
60 8322 60
60 9815 60
60 9445 60
60 9910 22 25 15 45 36 60 73 99 94 98 83
Algoritmo:
Sub-rotina quick(CR x lista)
Declare elem numerico
Declare x1,x2 lista
{ func~ao concat }
{ sub-rotina partic }
Se TAM(x)>1
partic(x,x1,elem,x2)
quick(x1)
quick(x2)
x := concat(x1,CONS(elem,x2))
fim_se
fim_sub-rotina
Funcao concat:
Func~ao concat(x1,x2 lista) lista
Se NIL(x1)
ent~ao
Retorna x2
sen~ao
Retorna CONS(CAR(x1),concat(CDR(x1),x2))
fim_se
fim_func~ao
52
Funcoes auxiliares de partic:
Func~ao adiciona_final(l lista, e numerico) lista
Se NIL(l)
ent~ao
Retorna CONS(e,nil)
sen~ao
Retorna CONS(CAR(l),adicional_final(CDR(l),e))
fim_func~ao
Func~ao retira_ultimo(l lista) lista
Se NIL(CDR(l))
ent~ao
Retorna nil
sen~ao
Retorna CONS(CAR(l),retira_ultimo(CDR(l)))
fim_se
fim_func~ao
Particionador:
53
sub-rotina partic(x lista, CR x1 lista, CR elem numerico,\
CR x2 lista)
Declare esq logico
{ func~oes auxiliares }
elem := x(0)
x := CDR(x)
esq := verdadeiro
x1 := nil
x2 := nil
Enquanto N~ao NIL(x)
faca
Se esq
ent~ao
Se elem>x(TAM(x)-1)
ent~ao
x1 := concat(x1,CONS(x(TAM(x)-1),nil))
x := retira_ultimo(x)
esq := falso
sen~ao
x2 := CONS(x(TAM(x)-1),x2)
x := retira_ultimo(x)
fim_se
sen~ao
Se elem<x(0)
ent~ao
x2 := CONS(x(0),x2)
x := CDR(x)
esq := verdadeiro
sen~ao
x1 := adiciona_final(x1,x(0))
x := CDR(x)
fim_se
fim_se
fim_enquanto
fim_sub-rotina
54
12 Programacao Funcional
Com os recursos de manipulacao de listas que ja temos em nossa linguagem ecom alguns outros recursos podemos implementar programacao funcional emnossa linguagem. Programacao funcional e um paradigma de programacaoem que as principais entidades sao funcoes e listas. Programacao funcio-nal se baseia na avaliacao de expressoes simbolicas. Este paradigma estaplenamente representado na linguagem de programacao LISP.
Algumas caracterısticas de programacao funcional pura:
• Nao existe declaracao de tipos. Todos os dados sao dinamicos e alinguagem efetua conversoes de tipo implıcitas;
• Homogeneidade das estruturas;
• Nao ha lacos de repeticao, apenas recursividade;
• Baseado em notacao-λ (funcoes-λ).
A estrutura basica de programacao funcional e o atomo que pode sernumerico ou literal (embora nao precise ser declarado como tal). Um parde elementos com lado esquerdo (CAR) e lado direito (CDR) e chamadoexpressao-S. A funcao CONS serve para construir expressoes-S.
12.1 Declaracao de Funcoes Lambda
Para declarar uma funcao lambda:
Func~ao lambda <nome>’(’<lista de parametros>’)’ ’(’ {definic~ao} ’)’
Ex:
Func~ao lambda cuder(x)(CDR(x))
Observe que nao e necessario declarar nenhum tipo de dado.
12.2 Estruturas de Programacao Funcional
Substituindo a estrutura “Se-entao-senao” tradicional, existe uma funcaoCOND, que recebe tres argumentos:
COND(<condic~ao>,<func~ao 1>,<func~ao 2>)
55
Caso a condicao seja verdadeira, e avaliada a funcao 1, caso contrario eavaliada a funcao 2.
Ex:
COND(NIL(x),nil,CAR(x))
que devolve nil se a lista x e vazia e o CAR de x caso contrario.O valor logico “falso” e representado por nil e o valor logico “verdadeiro”
por qualquer coisa diferente de nil. Assim, podemos testar a condicao listavazia, no exemplo anterior, sem usar a funcao NIL(x), embora por elegancianao seja recomendavel faze-lo:
COND(x,nil,CAR(x))
Alem da funcao NIL(x), estao definidas na linguagem as funcoes N~AO(x)que inverte o valor logico, IGUAL(x,y) que testa se x e y sao iguais, e ZERO(x)que testa se x = 0. Estao disponıveis tambem as operacoes aritmeticas jadefinidas na nossa linguagem de algoritmos.
A Tabela 9 sumariza as estruturas disponıveis em nossa linguagem dealgoritmos para programacao funcional.
12.3 Escrevendo Funcoes
A seguir sao apresentados exemplos de funcoes usando a notacao-λ apresen-tada.
Ex1: Calcula o fatorial.
Func~ao lambda fat(x)(
COND(ZERO(x),1,x*fat(x-1))
)
Ex2: Determina o tamanho de uma lista (implementa TAM(x)).
Func~ao lambda tamanho(x)(
COND(NIL(x),0,tamanho(CDR(x))+1)
)
Ex3: Concatena duas listas.
Func~ao lambda concat(x1,x2)(
COND(NIL(x1),x2,CONS(CAR(x1),concat(CDR(x1),x2)))
)
Com propositos de comparacao, apresentamos a solucao tradicional daconcatenacao de listas:
56
Estrutura Descricao
Func~ao lambda Define uma funcao nova<nome>’(’<list param>’)’
’(’{def func~ao}’)’
COND(<cond>,<f1>,<f2>) Condicional; Testa um valor;Se <cond> e diferente de nil
entao avalia <f1>, senao avalia <f2>
Funcao CAR(x) Devolve o CAR de uma lista x
Funcao CDR(x) Devolve o CDR de uma lista x
Funcao CONS(x,y) Devolve o CONS de x e y
Funcao TAM(x) Devolve o tamanho de uma lista x
Funcao NIL(x) Testa se a lista x e vaziaFuncao N~ao(x) Inverte o valor logico de x
Funcao ZERO(x) Testa se o argumento x e zeroFuncao IGUAL(x,y) Testa se x e y sao iguais
nil ou [] Lista vazia e/ou valor logico falsoOperador x(i) Devolve a i-esima posicao da lista x
Operador + Soma aritmeticaOperador - Subtracao aritmeticaOperador * Multiplicacao aritmeticaOperador / Divisao aritmeticaOperador ** Potenciacao aritmetica
Tabela 9: Resumo das Estruturas de Programacao Funcional
57
Func~ao concat(x1,x2 listas) lista
Declare ind numerico
Declare x lista
ind := TAM(x2)
x := nil
Enquanto ind>0
faca
x := CONS(x2(ind-1),x)
ind:=ind-1
x2 := retira_ultimo(x2)
fim_enquanto
ind := TAM(x1)
Enquanto ind>0
faca
x := CONS(x1(ind-1),x)
ind:=ind-1
x1 := retira_ultimo(x1)
fim_Enquanto
Retorna x
fim_func~ao
Ex4: Verifica se um elemento e pertence a uma lista l.
Func~ao lambda membro(e,l)(
COND(NIL(l),nil,
COND(IGUAL(e,CAR(l)),N~AO(nil),
membro(e,CDR(l))
)
)
)
Exercıcio: Escrever uma funcao lambda que inclua um elemento no finalde uma lista.
Exercıcio: Escrever uma funcao lambda que apaga o ultimo elemento deuma lista.
Exercıcio: Escrever uma funcao que obtem a derivada de um polinomioordem n. Ex:
d
dx
(3x5 + 2x3 − x + 1
)= 15x4 + 6x2 − 1
58
Representado como [[5,3],[3,2],[1,-1],[0,1]], que produzira[[4,15],[2,6],[0,-1]], que representa 15x4 + 6x2 − 1.
Exercıcio: Inverter uma lista. Ex: [1,2,3,4]⇒[4,3,2,1].Solucao:
Func~ao lambda inverte(x)(
COND(NIL(x),nil,concat(inverte(CDR(x)),CONS(CAR(x),nil)))
)
Exercıcio: Escrever uma funcao lambda que ordene uma lista por selecaodireta.
59
Copyright c©2005-2006 Carlos A. P. Campani.E garantida a permissao para copiar, distribuir e/ou modificar este do-
cumento sob os termos da Licenca de Documentacao Livre GNU (GNU FreeDocumentation License), Versao 1.2 ou qualquer versao posterior publicadapela Free Software Foundation; sem Secoes Invariantes, Textos de Capa Fron-tal, e sem Textos de Quarta Capa. Uma copia da licenca e incluıda na secaointitulada ”GNU Free Documentation License”.
veja: http://www.ic.unicamp.br/~norton/fdl.html.
60
