Algoritmos

Algoritmos Carlos A. P. Campani 6 de setembro de 2006

Sum´ ario 1 Introdu¸c˜ ao 2 Conceitos B´ asicos 2.1 Comando de Escrita . 2.2 Constantes . . . . . . . 2.3 Vari´aveis . . . . . . . . 2.4 Atribui¸c˜ao . . . . . . . 2.5 Comando de Leitura . 2.6 Express˜oes Aritm´eticas 2.7 Express˜oes L´ogicas . .

2 . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

3 4 6 6 7 8 10 13

3 Estrutura Condicional

14

4 Estrutura de Repeti¸c˜ ao

16

5 Algoritmos com Acumulador

19

6 Refinamentos Sucessivos

21

7 Usando Matrizes 24 7.1 Declara¸c˜ao de Matrizes . . . . . . . . . . . . . . . . . . . . . . 25 7.2 Tratando com Matrizes . . . . . . . . . . . . . . . . . . . . . . 26

1

8 Usando Listas 8.1 Constantes Lista . . . . . . 8.2 Opera¸c˜oes com Listas . . . . 8.3 Declara¸c˜ao de Vari´avel Lista 8.4 Tratando Listas . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

29 30 30 30 32

9 Sub-algoritmos 35 9.1 Sub-rotinas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 9.2 Fun¸c˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 10 Recursividade

44

11 Algoritmos de Ordena¸c˜ ao 11.1 BUBLE SORT . . . . . . . . . . . . . . . . . . . . . . . . . . ˜ DIRETA . . . . . . . . . . . . . . . . . . . . . . . 11.2 SELEC ¸ AO 11.3 QUICK SORT . . . . . . . . . . . . . . . . . . . . . . . . . . .

50 50 50 51

12 Programa¸c˜ ao Funcional 55 12.1 Declara¸c˜ao de Fun¸c˜oes Lambda . . . . . . . . . . . . . . . . . 55 12.2 Estruturas de Programa¸c˜ao Funcional . . . . . . . . . . . . . . 55 12.3 Escrevendo Fun¸c˜oes . . . . . . . . . . . . . . . . . . . . . . . . 56

Bibliografia • FARRER, H. et alii. Algoritmos Estruturados. Rio de Janeiro, Editora Guanabara, 1989; • WIRTH, N. Programa¸c˜ao Sistem´atica. Rio de Janeiro, Ed. Campus, 1978.

1

Introdu¸c˜ ao

Algoritmos s˜ao ferramentas importantes no estudo de ciˆencia da computa¸c˜ao. A compreens˜ao das t´ecnicas de desenvolvimento e constru¸c˜ao de algoritmos ´e uma ferramenta valiosa, n˜ao s´o para o aprendizado de linguagens de programa¸c˜ao, mas para o estudo das mais variadas disciplinas da ´area. Um exemplo poderia ser dado se lembrarmos que boa parte da teoria matem´atica

2

da computa¸c˜ao baseia-se no conceito de “algoritmo”, como uma id´eia primitiva. Nesta disciplina, desenvolveremos os algoritmos usando uma linguagem hipot´etica, cuja estrutura e funcionamento ser˜ao descritos ao longo do desenvolvimento da disciplina. A linguagem adotada aqui foi projetada para que fosse f´acil a implementa¸c˜ao dos exemplos apresentados em uma linguagem de programa¸c˜ao usual, particularmente visando Python como linguagem alvo.

2

Conceitos B´ asicos

Algoritmo ´e a descri¸c˜ao de um conjunto de comandos que, efetuados, resultam numa sucess˜ao finita de a¸c˜oes. Uma outra forma: Algoritmo ´e uma lista de instru¸c˜oes (comandos) ordenadas que tem por finalidade resolver um determinado problema. Exemplos de algoritmos: Uma receita culin´aria; Instru¸c˜oes 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 n˜ao est´a detalhado. Uma vers˜ao mais aceit´avel ´e: 1. Retirar um ovo da geladeira; 2. Colocar a frigideira no fogo; 3. Colocar ´oleo; 4. Esperar at´e o ´oleo ficar quente; 5. Quebrar o ovo separando a casca; 6. Colocar o conte´ udo na frigideira; 7. Esperar um minuto; 8. Retirar o ovo da frigideira; 9. Apagar o fogo. 3

Esta vers˜ao ´e mais completa e detalhada que a anterior. Para que um algoritmo possa ser executado ´e necess´ario que seu usu´ario conhe¸ca a terminologia nele utilizada. No exemplo anterior, para que o algoritmo seja u ´ til, ´e necess´ario que o usu´ario conhe¸ca o significado dos verbos Retirar, Colocar, Esperar assim como dos substantivos utilizados. Os algoritmos estudados em aula ser˜ao algoritmos computacionais, listas de comandos a serem executados por um computador. Para que o computador consiga executa-los ele tambem deve conhecer a terminologia utilizada. Ao conjunto de comandos que fazem parte de uma linguagem de programa¸c˜ao chama-se sintaxe da linguagem de programa¸c˜ao. Os algoritmos estudados na disciplina de Algoritmos ser˜ao desenvolvidos utilizando uma sintaxe que ser´a apresentada progressivamente ao longo do semestre. Esta sintaxe pode ser chamada de portuguˆes estruturado e os algoritmos nela desenvolvidos podem ser facilmente adapt´aveis as diversas linguagens de programa¸c˜ao 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. Note a endenta¸c˜ao dos comandos dentro do ambiente Algoritmo-fim_algoritmo. Vamos imaginar uma m´aquina virtual que executa os comandos de nossos algoritmos, lendo os dados de uma entrada fict´ıcia, e imprimindo os resultados em uma tela virtual. Embora esta m´aquina n˜ao exista no mundo real, com ela poderemos mentalmente executar os nossos algoritmos. Com relativamente pouca dificuldade ´e poss´ıvel traduzir os algoritmos de sala de aula para uma linguagem de programa¸c˜ao real.

2.1

Comando de Escrita

O comando de escrita ´e utilizado quando se deseja que o algoritmo escreva algo. Esta “escrita” pode ser em uma impressora, um terminal de v´ıdeo ou outra 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 express˜oes e uma express˜ao pode ser uma constante, uma express˜ao aritm´etica, vari´avel ou chamada de fun¸c˜ao. Ex: (dica: use endenta¸c˜ao) Algoritmo Escreva ’Jo~ ao Vitor’,’ ’,’Luana’ Escreva 1 + 2 fim_algoritmo

Escreva ’1’

Ao ser executado este algoritmo o resultado ser´a: Jo~ ao Vitor Luana 1 3 O exemplo ´e composto de trˆes comandos de escrita. Observe que podemos colocar mais de um comando por linha (op¸c˜ao n˜ao muito interessante pois esconde a estrutura do algoritmo e confunde a sua leitura). O primeiro comando manda escrever uma lista de trˆes constantes, no segundo deve escrever uma constante e no terceiro deve escrever o resultado de uma express˜ao aritm´etica. Quando um comando de escrita tiver mais de um valor a ser escrito como no primeiro, os diversos valores s˜ao separados por v´ırgula. Observe que ’Jo~ ao Vitor’ ´e um literal, ou seja, tudo que estiver entre dois ’ ser´a impresso exatamente da forma com que est´a escrito. A utilidade do ’ ’ ´e efetuar a separa¸c˜ao entre os diversos termos a serem impressos j´a que o comando Escreva imprime os termos sem espa¸cos 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 ausˆencia de ’ ’ entre ’Jo~ ao Vitor’ e ’Luana’. Os comandos como Algoritmo e fim_algoritmo s˜ao chamados palavras reservadas da linguagem. A linguagem trata mai´ usculas e min´ usculas como iguais.

2.2

Constantes

Uma constante ´e um valor que n˜ao se modifica com o tempo. As constantes com que trabalharemos podem ser de trˆes tipos diferentes, num´ericas, l´ogicas ou literais. Constantes num´ericas podem conter quaisquer valores num´ericos, reais ou inteiros, positivos ou negativos, etc. Exemplos de constantes num´ericas s˜ao: 25 3.14 -2.57 -0.0003 -10 Constantes literais podem conter um ou mais caracteres alfab´eticos ou num´ericos. S˜ao delimitados por aspas. Exemplos de constantes literais s˜ao: ’Jose da Silva’ ’1245’ ’1 2 3 de oliveira’ Constantes l´ogicas podem conter somente dois valores, verdadeiro e falso. Normalmente s˜ao utilizadas em testes em algoritmos.

2.3

Vari´ aveis

Uma vari´avel ´e um valor que pode ser alterado em um algoritmo. Cada vari´avel tem um nome associado a ela que a identifica. O identificador de uma vari´avel deve come¸car por uma letra e pode conter letras ou d´ıgitos. Ex: A X5 Joao

6

Assim como as constantes as vari´aveis tamb´em podem ser de trˆes tipos: num´ericas, l´ogicas ou literais. Para utilizar uma vari´avel em um algoritmo ´e necess´ario que ela seja declarada no in´ıcio do algoritmo, ou seja, defina-se no in´ıcio do algoritmo qual o tipo de valor com que a vari´avel ir´a trabalhar ( num´erico, l´ogico ou literal ). O formato do comando de declara¸c˜ao ´e: Declare Ex: Declare Nota,Codigo,X5 Num´ erico Declare Teste,Sim L´ ogico Declare Nome,End1,End2 Literal Assim, a forma geral de um algoritmo passa a ser: Algoritmo { declara¸ c~ oes } { corpo do algoritmo } fim_algoritmo

2.4

Atribui¸ c˜ ao

Uma vari´avel pode armazenar qualquer valor e seu valor pode ser alterado a qualquer momento no algoritmo. O comando utilizado para alterar o valor de uma vari´avel ´e o comando de atribui¸c˜ao. Sua forma geral ´e a seguinte: := onde pode ser uma constante, express˜ao aritm´etica, vari´avel ou chamada de fun¸c˜ao. Por exemplo: A := 5 O comando acima (lˆe-se “A recebe cinco”) faz com que a vari´avel A passe a valer 5. O valor anterior da vari´avel A ´e perdido e seu novo valor passa a ser 5. Assim, por exemplo: {A=10} A := 5 {A=5} 7

E fica perdido o valor anterior da vari´avel (10). Ent˜ao, como trocar dois valores? Resposta: Usando uma vari´avel auxiliar. Ex: trocar os valores de a e b. aux := a a := b b:= aux Outros exemplos de atribui¸c˜ao s˜ao: A := 3 + 2 A := B X5 := A + 1 No primeiro exemplo a vari´avel A recebe o resultado da express˜ao aritm´etica 3 + 2, express˜ao esta que cont´em somente constantes. No segundo exemplo a vari´avel A recebe o conte´ udo da vari´avel B e no terceiro exemplo a vari´avel X5 recebe o resultado da express˜ao aritm´etica A + 1, express˜ao esta que cont´em a vari´avel A e a constante 1. Um exemplo interessante: {A=10} A := A+1 {A=11} Ou seja, a express˜ao A+1 ´e avaliada, tendo como resultado 10 + 1 = 11 e o valor ´e atribuido `a vari´avel A.

2.5

Comando de Leitura

O comando de leitura ´e utilizado quando o algoritmo deve receber um valor externo, por exemplo, de um teclado. Seu formato geral ´e: Leia Este comando faz com que a primeira vari´avel da lista receba o primeiro valor digitado no teclado, a segunda vari´avel receba o segundo valor e assim por diante. Ex: Leia A,B 8

Ao executar este comando o computador espera que sejam fornecidos dois valores na entrada virtual ( p.ex: 10 e 20 ). A vari´avel A receber´a ent˜ao o primeiro valor (10) e a vari´avel B receber´a o segundo valor (20). Ex 2.8 - Escrever um algoritmo que lˆe trˆes n´ umeros, calcula as m´edias aritm´etica, harmˆonica e geom´etrica e escreve os n´ umeros lidos e as m´edias calculadas. MA =

A+B+C 3

MG =

√ 3

A×B×C

MH =

3 1 A

+

1 B

+

1 C

Ex 2.9 - Escrever um algoritmo que lˆe o nome de um funcion´ario, o n´ umero do funcion´ario, seu n´ umero de horas trabalhadas, o valor que recebe por hora, o n´ umero de filhos com idade menor que 14 anos e calcula o sal´ario deste funcion´ario. Ex 2.10 - Escrever um algoritmo que calcula o fatorial de 5. Ex 2.11 - Escrever um algoritmo que lˆe trˆes valores, a, b e c e calcula: 1. A ´area do triˆangulo que tem a por base e b por altura; 2. A ´area do c´ırculo de raio c; 3. A ´area do trap´ezio que tem a e b por bases e c por altura; 4. A ´area do quadrado de lado b; 5. A ´area do retˆangulo 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 n´ umeros ´ımpares entre 10 e 20. Ex 2.13 - Escrever um algoritmo que lˆe p, u e r, respectivamente o primeiro termo de uma progress˜ao aritm´etica, o u ´ ltimo termo da progress˜ao e a raz˜ao desta progress˜ao. Determinar a soma dos termos desta progress˜ao aritm´etica. soma =

an + a1 ×n 2

n=

an − a1 +1 r

Ex 2.14 - Escrever um algoritmo que lˆe o c´odigo da pe¸ca 1, o n´ umero de pe¸cas 1, o valor unit´ario da pe¸ca 1, o c´odigo da pe¸ca 2, o n´ umero de pe¸cas 2, o valor unit´ario da pe¸ca 2 e a percentagem do IPI a ser acrescentado e calcula o valor total a ser pago. 9

Opera¸c˜ao Adi¸c˜ao Subtra¸c˜ao Multiplica¸c˜ao Divis˜ao Potencia¸c˜ao

S´ımbolo + * / **

Precedˆencia 3 3 2 2 1

Tabela 1: Opera¸c˜oes Aritm´eticas

2.6

Express˜ oes Aritm´ eticas

Para que uma express˜ao possa ser avaliada em um algoritmo ela deve seguir uma sintaxe bem definida. As opera¸c˜oes utilizadas nas express˜oes aritm´eticas em nossa linguagem s˜ao as mostradas na Tabela 1 junto com as suas precedˆencias. A precedˆencia dos operadores indica a ordem que eles ser˜ao avaliados em uma express˜ao. A precedˆencia dos operadores ´e relevante para o resultado da avalia¸c˜ao de uma express˜ao. Por exemplo, a avalia¸c˜ao da express˜ao 3 + 4 * 2 pode resultar 14 se a soma for efetuada em primeiro lugar ou 11 se a multiplica¸c˜ao for efetuada em primeiro lugar. Para isto se define a prioridade das opera¸c˜oes. Ao avaliar uma express˜ao primeiro s˜ao efetuada as potencia¸c˜oes, ap´os s˜ao efetuadas as multiplica¸c˜oes e divis˜oes e por fim as adi¸c˜oes e subtra¸c˜oes. Quando houverem duas opera¸c˜oes de mesma prioridade para serem efetuadas, a ordem de execu¸c˜ao ´e da esquerda para a direita. ´ poss´ıvel alterar a ordem de execu¸c˜ao das opera¸c˜oes em uma express˜ao E com o uso de parˆenteses. Em uma express˜ao com parˆenteses em primeiro lugar s˜ao efetuadas as opera¸c˜oes entre parˆenteses. Ex: Express˜ao para o c´alculo das ra´ızes de uma equa¸c˜ao de segundo grau segundo a f´ormula de Bascara (usar o - un´ario). X1 := (-B+(B**2-4*A*C)**(1/2))/(2*A) X2 := (-B-(B**2-4*A*C)**(1/2))/(2*A) Al´em das opera¸c˜oes acima descritas a nossa ’linguagem’ oferece as fun¸c˜oes pr´e-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

Fun¸c˜ao LOG(x) LN(x) EXP(x) ABS(x) TRUNCA(x) ARREDONDA(x) SINAL(x)

QUOCIENTE(x,y) RESTO(x,y)

Especifica¸c˜ao logaritmo de x na base 10 logaritmo natural de x e elevado na x-´esima potˆencia m´odulo ( valor absoluto ) de x valor inteiro de x inteiro mais pr´oximo a x −1 se x < 0 0 se x = 0 1 se x > 0 quociente inteiro da divis˜ao de x por y resto da divis˜ao inteira de x por y

Tabela 2: Fun¸c˜oes Pr´e-definidas Ex 2.16 - Escrever um algoritmo para calcular os sucessivos valores de E usando a s´erie abaixo considerando primeiro 3 termos, depois 4 termos e finalmente 5 termos: 1 1 1 1 E= + + + 1! 2! 3! 4! Ex 2.17 - Escrever um algoritmo que lˆe o valor de um empr´estimo e calcula o valor de cada amortiza¸c˜ao considerando 24 amortiza¸c˜oes a uma taxa de 48%. Depois fazer o mesmo algoritmo lendo os valores da taxa e do n´ umero de amortiza¸c˜oes. VAMORT = VEMPREST × TAXA/NAMORT onde VAMORT ´e o valor da amortiza¸c˜ao, VEMPREST ´e o valor do empr´estimo, TAXA ´e a taxa, e NAMORT ´e o n´ umero de amortiza¸c˜oes. Ex 2.18 - Escrever um algoritmo que lˆe um valor em cruzeiros e calcula qual o menor n´ umero 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 a rela¸c˜ao de notas necess´arias. Ex 2.19 - Escrever um algoritmo que lˆe o n´ umero do vendedor, o seu sal´ario fixo, o total de vendas por ele efetuadas e o percentual que ganha sobre o total de vendas. Calcular o sal´ario total do vendedor. Escrever o n´ umero do vendedor e o sal´ario total. 11

Ex 2.20 - Escrever um algoritmo que lˆe 3 valores a, b e c que s˜ao lados de um triˆangulo e calcule a ´area deste triˆangulo. ´area =

q

s(s − a)(s − b)(s − c)

onde s = (a + b + c)/2 (semi-per´ımetro). Ex 2.21 - Um sistema de equa¸c˜oes lineares do tipo: (

ax + by = c dx + ey = f

pode ser resolvido segundo mostrado abaixo: x=

ce − bf ae − bd

y=

af − cd ae − bd

Escrever um algoritmo que lˆe os coeficientes a, b, c, d, e, e f , e calcula e escreve os valores de x e y. Ex 2.22 - O custo ao consumidor, de um carro novo, ´e a soma do custo de f´abrica com a porcentagem do distribuidor e dos impostos ( aplicados ao custo de f´abrica ). Supondo que a percentagem do distribuidor seja de 28% e os impostos de 45%, escrever um algoritmo para ler o custo de f´abrica de um carro e escrever o custo ao consumidor. Depois fazer o mesmo algoritmo lendo os valores da porcentagem do distribuidor e dos impostos. Ex 2.23 - Uma revendedora de carros usados paga a seus funcion´arios vendedores, um sal´ario fixo por mˆes, mais uma comiss˜ao tamb´em fixa para cada carro vendido e mais 5% do valor das vendas por ele efetuadas. Escrever um algoritmo que lˆe o nome do vendedor, o n´ umero do vendedor, o n´ umero de carros por ele vendidos, o valor total de suas vendas, o sal´ario fixo e o valor que recebe por carro vendido e calcula o sal´ario mensal do vendedor, escrevendo-o juntamente com o seu nome e seu n´ umero de identifica¸c˜ao. Ex 2.24 - Considerando que o aumento dos funcion´arios ´e de 80% do INPC e mais um percentual de produtividade discutido com a empresa. Escrever um algoritmo que lˆe o nome do funcion´ario, o n´ umero do funcion´ario, seu sal´ario atual, o valor do INPC e o ´ındice de produtividade conquistado e escreve o nome do funcion´ario, seu aumento e o valor do novo sal´ario. Ex 2.25 - Escrever um algoritmo que lˆe 3 valores a, b e c e os escreve. ´ Encontre a seguir o maior dos trˆes valores e o escreva com a mensagem: ”E o maior”. a + b + |a − b| maior = 2 12

Relacional = ou 6= > < >= 0 E B > 3 Teste OU A * B > C A precedˆencia de operadores da nossa linguagem ´e apresentada na Tabela 5. 13

Operador Operadores Aritm´eticos Operadores Relacionais Nao E OU

Precedˆencia 1 2 3 4 5

Tabela 5: Operadores e suas Precedˆencias Ex: Se A = 1, B = 2 e C = 2 qual o resultado da avalia¸c˜ao da express˜ao seguinte? A + B = 0 E C 0 3 = 0 E C 0 Falso E Verdadeiro Falso

3

Estrutura Condicional

Utilizada quando um trecho de algoritmo s´o deve ser executado em determinadas condi¸c˜oes. Formas Gerais: 1. Se ent~ ao fim_se 2. Se ent~ ao sen~ ao fim_se onde ´e uma express˜ao l´ogica qualquer. Ex: Se a>b ent~ ao Escreva a sen~ ao Escreva b fim_se 14

Ao ser executado este comando a express˜ao a > b ´e avaliada e dependendo do resultado da avalia¸c˜ao ´e executado o primeiro comando (escreva a) ou o segundo comando (escreva b). Observe que as estruturas podem ser “aninhadas”. Ex2: Se ab 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 equa¸c˜ao y = ax + b. Algoritmo Declare A,B,X num´ erico Leia A,B Se A = 0 ent~ ao Escreva ’N~ ao h´ a raizes’ sen~ ao X := -B/A Escreva ’Raiz=’,X fim_se fim_algoritmo

15

Ex4: Algoritmo que calcula as raizes da equa¸c˜ao y = ax2 + bx + c. Algoritmo Declare A,B,C,Delta num´ erico Leia A,B,C Delta := B**2-4*A*C Se Delta = 0 ent~ ao Escreva ’S´ o h´ a uma raiz’,-B/(2*A) fim_se Se Delta < 0 ent~ ao Escreva ’h´ a 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 na seguinte. Isto ´e u ´ til quando a linha de um algoritmo ´e muito grande.

4

Estrutura de Repeti¸ c˜ ao

Utilizada quando um trecho de um algoritmo deve ser repetido um determinado n´ umero de vezes. Esta estrutura tamb´em ´e chamada de la¸co de repeti¸c˜ao. Forma geral: 1. Enquanto fa¸ ca { lista-de-comandos } fim_enquanto 2. Repita { lista de comandos } at´ e

16

Na primeira forma os comandos s˜ao executados repetitivamente enquanto a condi¸c˜ao ´e verdadeira, e a condi¸c˜ao ´e testada antes (pode n˜ao executar nenhuma vez). Na segunda forma os comandos s˜ao executados repetitivamente at´e a condi¸c˜ao tornar-se verdadeira (testa depois de executar, assim sempre ´e executado pelo menos uma vez). Ex: Escrever os n´ umeros de 1 a 10. Algoritmo Declare I num´ erico I := 1 Repita Escreva I I := I + 1 at´ e I > 10 fim_algoritmo ´ chamada A vari´avel I ´e quem controla o n´ umero de repeti¸c˜oes do la¸co. E vari´avel contadora. Uma vari´avel contadora ´e uma vari´avel que recebe um valor inicial, ´e incrementada de um valor constante no la¸co e tem seu valor testado em algum ponto do la¸co. Ao chegar a um determinado valor o la¸co ´e interrompido. A inicializa¸c˜ao da vari´avel contadora deve ir, necessariamente, fora do la¸co. Existem diversas maneiras de implementar o mesmo la¸co, mas todo la¸co com vari´avel de controle deve conter: • inicializa¸c˜ao; • incremento (ou decremento); • teste de valor final. Abaixo s˜ao mostradas outras trˆes maneiras de implementar o algoritmo anterior:

17

1. Algoritmo Declare I num´ erico I := 0 Repita I := I + 1 Escreva I at´ e I = 10 fim_algoritmo 2. Algoritmo Declare I num´ erico I := 0 Enquanto I < 10 fa¸ ca I := I + 1 Escreva I fim_enquanto fim_algoritmo 3. Algoritmo Declare I num´ erico I := 1 Enquanto I < 11 fa¸ ca Escreva I I := I + 1 fim_enquanto fim_algoritmo Ainda existe uma possibilidade adicional de abandonar um la¸co de repeti¸c˜ao (tanto o Repita quanto o Enquanto) em qualquer lugar por meio de um comando Interrompa:

18

Enquanto verdadeiro fa¸ ca Leia x Se x>0 ent~ ao Interrompa fim_se Escreva ’Valor inv´ alido’ Escreva ’Digite novamente’ fim_enquanto significando que o la¸co (condi¸c˜ao de parada do la¸co ´e verdadeiro) ser´a interrompido (pelo comando Interrompa) apenas quando o usu´ario fornecer um n´ umero maior que zero. Ex. 4.7 Escrever um algoritmo que gera e escreve os n´ umeros impares entre 100 e 200. Exerc. Escrever um algoritmo para calcular o fatorial de um n´ umero.

5

Algoritmos com Acumulador

Quando o algoritmo necessitar efetuar alguma totaliza¸c˜ao usa-se uma vari´avel chamada acumulador. A vari´avel acumuladora tamb´em deve ser inicializada (normalmente com zero) e pode ser incrementada ou n˜ao de um valor vari´avel no la¸co. Ex: Somar os n´ umeros de 1 a 10. S := 0 I := 0 Enquanto IN escreva acum fim_algoritmo Escrever um algoritmo que leia um n´ umero e escreva uma mensagem dizendo: “O n´ umero ´e primo” ou “O n´ umero n˜ao ´e primo” conforme o caso. Ex. 4.12 - Escrever um algoritmo que gera os 30 primeiros termos da ´ primo” s´erie de Fibonacci e escreve os termos gerados com a mensagem: “E ou “N˜ao ´e primo” conforme o caso.

6

Refinamentos Sucessivos

´ uma t´ecnica para desenvolver um algoritmo em diversos passos aumentando E o n´ıvel de detalhamento a cada passo. A partir do problema gerar uma poss´ıvel solu¸c˜ao e detalh´a-la at´e um n´ıvel aceit´avel. ´ Ex: Escrever um algoritmo que leia um n´ umero e escreva a mensagem “E primo” ou “N˜ao ´e primo”. Primeira Vers˜ao: Algoritmo Declare n´ umero Leia n´ umero {Verifica se n´ umero ´ e primo} Se {n´ umero ´ e primo} ent~ ao escreva ’n´ umero ´ e primo’ sen~ ao escreva ’n´ umero n~ ao ´ e primo’ fim_se fim_algoritmo 21

Detalhamentos: { Verifica se n´ umero ´ e primo } Um n´ umero ´e primo se ´e divis´ıvel somente por si e pela unidade (1). Uma maneira de descobrir isto ´e contando o n´ umero de divisores do n´ umero. Se possuir apenas dois divisores (1 e o pr´oprio n´ umero ) ele ´e primo. { Verifica se n´ umero ´ e primo } ⇒ { Conta n´ umero de divisores } { Conta n´ umero de divisores } acum := 0 i := 1 Repita Se Resto(Numero,i)=0 ent~ ao acum:=acum+1 fim_se i:=i+1 at´ e i>n´ umero { N´ umero ´ e primo } Se acum=2 ent~ ao... O refinamento para { Conta n´ umero de divisores } n˜ao ´e bom, porque basta verificar que existem mais de dois divisores do n´ umero para ele n˜ao ser primo. Assim, rebatizando { Conta n´ umero de divisores } para { Verifica se h´ a mais de dois divisores }, obtemos, usando o comando Interrompa: { Verifica se h´ a mais de dois divisores } acum := 1 i := 1 Enquanto i 2 ent~ ao Interrompa fim_se i:=i+1 fim_enquanto 22

P rincipal fff fffff f f f f ffff fffff  rr ffff f

{ n´ umero ´ e primo }

{ Verifica de n´ umero ´ e primo } 

{ Verifica se h´ a mais de dois divisores } Figura 1: Diagrama de Refinamentos para o Exemplo Isto melhora a performance do algoritmo, pois ele abandona o la¸co assim que percebe que j´a existem mais de dois divisores e faz divis˜oes apenas at´e TRUNCA(n´ umero/2). A Figura 1 apresenta o diagrama de refinamentos para este exemplo. Montando as partes obtemos a vers˜ao final: Algoritmo Declare n´ umero,i,acum num´ erico Leia n´ umero acum := 1 i := 1 Enquanto i 2 ent~ ao Interrompa fim_se i:=i+1 fim_enquanto Se acum=2 ent~ ao escreva ’n´ umero ´ e primo’ sen~ ao escreva ’n´ umero 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 s´erie de Mac-Laurin truncada com 20 termos: A1 A3 A5 A7 sin(A) = − + − ··· 1! 3! 5! 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 s´erie considerando uma precis˜ao de 0,0001 na aproxima¸c˜ao obtida (dica: considere o valor absoluto do u ´ ltimo termo). Ex. 1.12.40. Fazer um algoritmo que calcule e escreva o cosseno de A usando a s´erie truncada com 20 termos: A2 A4 A6 A8 + − + ··· 2! 4! 6! 8! Ex. 1.12.32. O valor aproximado de ? pode ser calculado usando-se a s´erie: 1 1 1 1 1 S = 3 − 3 + 3 − 3 + 3 ··· 1 3 5 7 9 √ 3 sendo π ≈ S × 32. Fazer um algoritmo para calcular e escrever o valor de π com 51 termos. cos(A) = 1 −

7

Usando Matrizes

Matriz ´e um conjunto de vari´aveis, cada uma podendo representar o valor de uma constante, como se fossem vari´aveis simples, mas todas elas compartilhando um nome comum. ´Indices s˜ao associados a este nome comum permitindo 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 s´erie do mesmo tipo. Ex: Deseja-se calcular a m´edia de notas de 10 alunos e determinar quantos ficaram acima da m´edia. Portanto, deve-se calcular a m´edia de 10 n´ umeros lidos e determinar quantos destes n´ umeros est˜ao acima da m´edia. Para calcular a m´edia podemos usar o seguinte algoritmo: 24

Algoritmo Declare cont,soma,num num´ erico cont := 10 soma := 0 Repita Leia num soma := soma+num cont := cont-1 At´ e cont=0 Escreva soma/10 fim_algoritmo Problema: Quando os n´ umeros s˜ao lidos n˜ao conhecemos ainda o valor da m´edia. Ao final do programa anterior n˜ao temos mais acesso aos n´ umeros lidos (pois j´a foram lidos). Lˆe-los novamente seria perda de tempo. Como fazer este algoritmo sem matrizes? Resposta: Ler os 10 n´ umeros e guarda-los em 10 vari´aveis para testar uma a uma ap´os obter a m´edia. Problema: E se fossem 1000 alunos? Teriamos dificuldades de manipular 1000 vari´aveis diferentes. Solu¸c˜ao: uso de uma matriz para armazenar os valores das notas para posteriormente processa-los.

7.1

Declara¸ c˜ ao de Matrizes

Deve-se definir nas declara¸c˜oes: 1. Quais vari´aveis do algoritmo s˜ao do tipo matriz; 2. Quantas dimens˜oes possui cada uma delas; 3. Qual o tamanho de cada dimens˜ao; 4. O tipo dos componentes individuais da matriz. Nota¸c˜ao: Declare ’(’ ’)’ Declare ’(’ ’,’ ... ’)’ 25

Ex: Declare a(5),m(6,8) num´ erico. Conven¸c˜ao: 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 necess´ario ler cada um dos seus componentes individuais. Ex: Ler 5 elementos da matriz a. Algoritmo Declare i,a(5) num´ erico i := 1 Enquanto i10 Escreva soma fim_algoritmo Exerc.: Calcular a m´edia de 10 alunos de uma disciplina, entrando a nota e o nome do aluno. Determinar o n´ umero de alunos que tiveram nota superior a m´edia e imprimir o nome dos alunos que tiveram este feito. Ex. 2.5.1.4. Dado um conjunto de 100 valores num´ericos dispon´ıveis na entrada, fazer um algoritmo para armazen´a-los em uma matriz e calcular e imprimir o valor do somat´orio dado a seguir: S = (v1 − v100 )3 + (v2 − v99 )3 + (v3 − v98 )3 + · · · + (v50 − v51 )3 Determinar a posi¸c˜ao, dentro de uma matriz quadrada, de um elemento pode ser muito u ´ til em alguns tipos de algoritmos. Por exemplo, determinar se determinado elemento est´a acima ou abaixo da diagonal principal da matriz. 27

Figura 2: Posi¸c˜oes em uma Matriz Algumas rela¸c˜oes s˜ao importantes para determinar a posi¸c˜ao dos elementos de uma matriz quadrada (veja Figura 2).         

a11 a12 a21 a22 a31 a32 .. .. . . an1 an2

a13 a23 a33 .. . an3



· · · a1n  · · · a2n   · · · a3n   ..  .. . .   · · · ann

Sendo i e j os ´ındices dos elementos da matriz: • Diagonal principal – i = j; • Diagonal secund´aria – i + j = n + 1; • Abaixo da diagonal principal – i > j; • Acima da diagonal principal – i < j; • Acima da diagonal secund´aria – i + j < n + 1; • Abaixo da diagonal secund´aria – i + j > n + 1. Exerc. Escrever um algoritmo para ler um valor n e a seguir ler uma matriz n × n. Ent˜ao, determinar a soma de todos os elementos acima da diagonal principal e imprimi-lo. Exerc. Escrever um algoritmo para ler uma matriz a de tamanho n × m e outra matriz b de tamanho m × p. Ent˜ao, determinar e imprimir a matriz produto c de tamanho n × p. cij =

m X

k=1

28

aik bkj

CAR CDR

1

2

3

a

c

nil

b

nil

Figura 3: Representa¸c˜ao Gr´afica da Lista

8

Usando Listas

Uma estrutura formada por uma seq¨ uˆencia de elementos de tipos diversos ´e chamada de lista. Importante observar que um elemento de uma lista pode ser 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 outra lista de dois elementos. Na representa¸c˜ao interna de lista, cada elemento de uma lista ´e formado por um nodo com dois elementos (CAR e CDR – pronuncia-se “cuder”) que podem ser preenchidos com valores constantes (num´ericos, literais ou l´ogicos) ou elos. Um elo ´e um indicador da posi¸c˜ao de um outro nodo na mem´oria da m´aquina. Existe um elo especial (nil) que n˜ao aponta para nenhum lugar e ´e usado para indicar o fim de uma lista. nil pode indicar tamb´em uma lista vazia. Observe que uma matriz n˜ao pode ser um elemento de uma lista. Exemplo: [1,2,3,[’a’,’b’],’c’] seria armazenado internamente na mem´oria da m´aquina como ilustrado na Figura 3. Comumente se chama a parte CAR de cabe¸ca da lista e a parte CDR de resto ou rabo da lista. 29

8.1

Constantes Lista

As constantes listas s˜ao qualquer seq¨ uˆencia de num´ericos, literais ou l´ogicos, separados por v´ırgulas e delimitados por [ e ]. Uma constante lista pode ter em um ou mais de seus termos outras listas e assim por diante. Ex: [1,2,[’a’,’b’,[1,’b’]],3]

8.2

Opera¸ c˜ oes com Listas

Est˜ao definidas em nossa linguagem de algoritmos as fun¸c˜oes e opera¸c˜oes sobre 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 interpreta¸c˜ao gr´afica das opera¸co˜es CAR e CDR para a avalia¸c˜ao CDR(CAR(CDR([a,[b,[c]],d]))).

8.3

Declara¸ c˜ ao de Vari´ avel Lista

Uma vari´avel lista ´e declarada da seguinte forma: Declare x lista Podemos agora manipular a vari´avel lista em uma atribui¸ca˜o. Ex: x := [2,3,4] x := CONS(1,x) que resulta em x igual a [1,2,3,4]. Observa¸c˜ao: N˜ao podemos atribuir um valor a uma posi¸c˜ao qualquer da lista. S´o podemos trocar sua cabe¸ca: x := [1,2,3,4] x := CONS(10,CDR(x)) que resulta em x igual a [10,2,3,4]. 30

a

primeiro CDR

CAR

b

d

nil

segundo CDR nil

c

nil

Figura 4: Interpreta¸c˜ao Gr´afica de CAR e CDR

31

Opera¸c˜ao CAR(x) CDR(x) CONS(x,y)

x(i) TAM(x) NIL(x)

Significado Obt´em a cabe¸ca de uma lista (devolve o CAR de x) Obt´em o resto de uma lista (devolve a lista CDR de x) Constroi um nodo tendo como CAR x, e como CDR y (segundo argumento deve ser uma lista) Devolve a i-´esima posi¸c˜ao da lista x (o ´ındice da primeira posi¸c˜ao ´e zero) Tamanho da lista x Verifica se a lista ´e vazia (testa se x ´e igual a nil, retornando verdadeiro ou falso)

Tabela 7: Fun¸c˜oes e Opera¸c˜oes sobre Listas

8.4

Tratando Listas

Listas s˜ao uma estrutura dinˆamica muito poderosa e flex´ıvel para construir algoritmos que tratem com situa¸c˜oes em que os dados est˜ao constantemente sendo inseridos e retirados (pilhas e filas s˜ao exemplos). Tamb´em s˜ao uma boa alternativa `as matrizes, em casos em que o tamanho dos dados ´e conhecido apenas em tempo de execu¸c˜ao. Por exemplo, se desejamos encontrar o n´ umero de elementos que s˜ao menores que a m´edia de um conjunto de num´ericos:

32

Algoritmo Declare x,n,i,acum,m num´ erico Declare a lista Escreva ’Entre a quantidade de valores’ Leia n i := 1 a := nil acum := 0 Enquanto ic 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

Fun¸ c˜ oes

Retornam um valor pelo seu nome (al´em de pelos parˆametros declarados como copia-restaura). Ex: ABS(x), TRUNCA(x) (fun¸c˜oes pr´e-definidas) Declara¸c˜ao: fun¸ c~ ao [’(’100 fim_algoritmo

41





Fun¸c˜oes: Fun¸ c~ ao num´ erico exp2(x num´ erico) Declare soma,ind num´ erico Fun¸ c~ ao num´ erico fatorial(n num´ erico) Declare fat num´ erico fat := 1 Enquanto n>1 fa¸ ca fat := fat*n n := n-1 fim_enquanto Retorna fat fim_fun¸ c~ ao soma := 1 ind := 1 Repita soma := soma+(x**ind)/fatorial(ind) ind := ind+1 at´ e ind>19 Retorna soma fim_fun¸ c~ ao Fun¸ c~ ao num´ erico ln2(x num´ erico) Declare soma,ind num´ erico soma := 0 ind := 1 Repita soma := soma+(((x-1)/x)**ind)/ind ind := ind+1 at´ e ind>20 Retorna soma fim_fun¸ c~ ao Observe que o la¸co da fun¸c˜ao exp2 tem como condi¸c˜ao de parada ind>19, pois ser˜ao somados 20 termos e o primeiro ´e 1 e j´a foi somado (soma := 1). 42

Exerc. A partir das seguintes s´eries do sin e cos, e usando fun¸c˜oes, escreva um 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 valores do sin e do cos com erro m´aximo de 0.0001 (≈ m´odulo do u ´ ltimo termo). sin(x) = x −

x3 x5 x7 + − +··· 3! 5! 7!

cos(x) = 1 −

x2 x4 x6 + − +··· 2! 4! 6!

Rela¸c˜oes: tan(x) =

sin(x) cos(x)

cot(x) =

1 tan(x)

sec(x) =

1 cos(x)

csc(x) =

1 sin(x)

Solu¸c˜ao: Algoritmo Declare x num´ erico { declara¸ c~ oes de fun¸ c~ 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 at´ e x>1.5 fim_algoritmo Fun¸c˜oes: Fun¸ c~ ao num´ erico fatorial(n num´ erico) Declare fat,cont num´ erico cont := 1 fat := 1 Repita fat := fat*cont cont := cont+1 at´ e cont>n Retorna fat fim_fun¸ c~ ao 43

Fun¸ c~ ao num´ erico sen(x num´ erico) Declare acum,soma,ind,termo,sinal num´ erico acum := 0 ind := 1 sinal := 1 Enquanto abs(termo)>0.0001 fa¸ ca termo := sinal*(x**ind)/fatorial(ind) acum := acum+termo sinal := -sinal ind := ind+2 fim_enquanto Retorna acum fim_fun¸ c~ ao Fun¸ c~ ao num´ erico cos(x num´ erico) Declare acum,ind,termo,sinal num´ erico acum := 1 ind := 2 sinal := -1 Enquanto abs(termo)1

(Base) (Passo recursivo)

Outro ex.: A soma dos n´ umeros de 1 a n pode ser definida de forma recursiva como: (

soma(1) = 1 soma(n) = n + soma(n − 1)

n>1

A soma dos n´ umeros ´ımpares de 1 a n pode ser definida de forma recursiva por:   

somaimp(1) = 1 somaimp(n) = somaimp(n − 1)   somaimp(n) = n + somaimp(n − 2)

n par ∧ n > 1 n impar ∧ n > 2

Algoritmo da fun¸c˜ao fatorial definida recursivamente: Fun¸ c~ ao num´ erico fatorial(n num´ erico) Se n=0 OU n=1 ent~ ao Retorna 1 sen~ ao Retorna n*fatorial(n-1) fim_se fim_fun¸ c~ ao A execu¸c˜ao desta fun¸c˜ao para uma chamada fatorial(3) ´e a mostrada na Figura 6. Exerc.: Definir recursivamente a fun¸c˜ao que devolve a soma dos n´ umeros ´ımpares de 1 a n. Exerc.: Definir recursivamente a fun¸c˜ao que determina o n-´esimo termo da s´erie de fibonacci (veja a Tabela 8).

45

fatorial(3) 

3 ∗ fatorial(2) 

//

qq qqq q q qq qqq

2 ∗ fatorial(1) 

3× 88 2 = 6

// 2 × 1 mm66 m mm m m mmm mmm

=2

fatorial(1) = 1 Figura 6: Execu¸c˜ao de fatorial(3)

n 0 1 2 3 4 5 6 .. .

fibonacci(n) 0 1 1 2 3 5 8 .. .

Tabela 8: Tabela do Fibonacci

46

//

6

Solu¸c˜ao: Fun¸ c~ ao num´ erico fibonacci(n num´ erico) Se n=0 OU n=1 ent~ ao Retorna n sen~ ao Retorna fibonacci(n-1)+fibonacci(n-2) fim_se fim_fun¸ c~ ao Exerc.: Considere uma seq¨ uˆencia de n´ umeros onde cada termo ´e dado pela combina¸c˜ao dos 4 termos anteriores An = An−4 +2×An−3 +3×An−2 +4×An−1 e os 4 primeiros termos s˜ao por defini¸c˜ao: A1 = 1 A2 = 2 A3 = 3 A4 = 4 Escreva uma fun¸c˜ao recursiva SEQ que receba um n´ umero n e retorne o termo An . Solu¸c˜ao: Fun¸ c~ ao num´ erico seq(n num´ erico) Se n1 partic(x,x1,elem,x2) quick(x1) quick(x2) x := concat(x1,CONS(elem,x2)) fim_se fim_sub-rotina Fun¸c˜ao concat: Fun¸ c~ 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_fun¸ c~ ao

52

Fun¸c˜oes auxiliares de partic: Fun¸ c~ ao adiciona_final(l lista, e num´ erico) lista Se NIL(l) ent~ ao Retorna CONS(e,nil) sen~ ao Retorna CONS(CAR(l),adicional_final(CDR(l),e)) fim_fun¸ c~ ao Fun¸ c~ 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_fun¸ c~ ao Particionador:

53

sub-rotina partic(x lista, CR x1 lista, CR elem num´ erico,\ CR x2 lista) Declare esq l´ ogico { fun¸ c~ oes auxiliares } elem := x(0) x := CDR(x) esq := verdadeiro x1 := nil x2 := nil Enquanto N~ ao NIL(x) fa¸ ca 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 elem0 fa¸ ca x := CONS(x2(ind-1),x) ind:=ind-1 x2 := retira_ultimo(x2) fim_enquanto ind := TAM(x1) Enquanto ind>0 fa¸ ca x := CONS(x1(ind-1),x) ind:=ind-1 x1 := retira_ultimo(x1) fim_Enquanto Retorna x fim_fun¸ c~ ao Ex4: Verifica se um elemento e pertence a uma lista l. Fun¸ c~ 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 fun¸c˜ao lambda que inclua um elemento no final de uma lista. Exerc´ıcio: Escrever uma fun¸c˜ao lambda que apaga o u ´ ltimo elemento de uma lista. Exerc´ıcio: Escrever uma fun¸c˜ao que obt´em a derivada de um polinˆomio ordem n. Ex:  d  5 3x + 2x3 − x + 1 = 15x4 + 6x2 − 1 dx 58

Representado como [[5,3],[3,2],[1,-1],[0,1]], que produzir´a [[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]. Solu¸c˜ao: Fun¸ c~ ao lambda inverte(x)( COND(NIL(x),nil,concat(inverte(CDR(x)),CONS(CAR(x),nil))) ) Exerc´ıcio: Escrever uma fun¸c˜ao lambda que ordene uma lista por sele¸c˜ao direta.

59

c Copyright 2005-2006 Carlos A. P. Campani. ´ E garantida a permiss˜ao para copiar, distribuir e/ou modificar este documento sob os termos da Licen¸ca de Documenta¸c˜ao Livre GNU (GNU Free Documentation License), Vers˜ao 1.2 ou qualquer vers˜ao posterior publicada pela Free Software Foundation; sem Se¸c˜oes Invariantes, Textos de Capa Frontal, e sem Textos de Quarta Capa. Uma c´opia da licen¸ca ´e inclu´ıda na se¸c˜ao intitulada ”GNU Free Documentation License”. veja: http://www.ic.unicamp.br/~norton/fdl.html.

60