(Parte 1 de 4)

Algoritmos

Carlos A. P. Campani 6 de setembro de 2006

Sumario 1 Introducao 2

2.1 Comando de Escrita4
2.2 Constantes6
2.3 Variaveis6
2.4 Atribuicao7
2.5 Comando de Leitura8
2.6 Expressoes Aritmeticas10
2.7 Expressoes Logicas13

2 Conceitos Basicos 3 3 Estrutura Condicional 14 4 Estrutura de Repeticao 16 5 Algoritmos com Acumulador 19 6 Refinamentos Sucessivos 21

7.1 Declaracao de Matrizes25
7.2 Tratando com Matrizes26
8.1 Constantes Lista30
8.2 Operacoes com Listas30
8.3 Declaracao de Variavel Lista30
8.4 Tratando Listas32

8 Usando Listas 29

9.1 Sub-rotinas37
9.2 Funcoes39
1.1 BUBLE SORT50
1.2 SELEC AO DIRETA50
1.3 QUICK SORT51

1 Algoritmos de Ordenacao 50

12.1 Declaracao de Funcoes Lambda5
12.2 Estruturas de Programacao Funcional5
12.3 Escrevendo Funcoes56

Bibliografia

• FARRER, H. et alii. Algoritmos Estruturados. Rio de Janeiro, Editora Guanabara, 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 algoritmos e uma ferramenta valiosa, nao so para o aprendizado de linguagens de programacao, mas para o estudo das mais variadas disciplinas da area. Um exemplo poderia ser dado se lembrarmos que boa parte da teoria matematica da computacao baseia-se no conceito de “algoritmo”, como uma ideia primitiva.

Nesta disciplina, desenvolveremos os algoritmos usando uma linguagem hipotetica, cuja estrutura e funcionamento serao descritos ao longo do desenvolvimento da disciplina. A linguagem adotada aqui foi projetada para que fosse facil a implementacao dos exemplos apresentados em uma linguagem de programacao usual, particularmente visando Python como linguagem alvo.

Algoritmo e a descricao de um conjunto de comandos que, efetuados, resultam numa sucessao finita de acoes. Uma outra forma: Algoritmo e uma lista de instrucoes (comandos) ordenadas que tem por finalidade resolver um 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.

Esta versao e mais completa e detalhada que a anterior. Para que um algoritmo possa ser executado e necessario que seu usuario conheca a terminologia 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, 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 programacao chama-se sintaxe da linguagem de programacao.

Os algoritmos estudados na disciplina de Algoritmos serao desenvolvidos utilizando uma sintaxe que sera apresentada progressivamente ao longo do semestre. Esta sintaxe pode ser chamada de portugues estruturado e os algoritmos nela desenvolvidos podem ser facilmente adaptaveis as diversas linguagens 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. Note a endentacao dos comandos dentro do ambiente Algoritmo-fim_algoritmo.

Vamos imaginar uma maquina 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 maquina nao 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 programacao 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 } onde { lista-de-express~oes } e uma lista de uma ou mais expressoes e uma expressao pode ser uma constante, uma expressao aritmetica, variavel ou 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 podemos colocar mais de um comando por linha (opcao nao muito interessante pois esconde a estrutura do algoritmo e confunde a sua leitura).

O primeiro comando manda escrever uma lista de tres constantes, no segundo deve escrever uma constante e no terceiro deve escrever o resultado de uma expressao aritmetica. Quando um comando de escrita tiver mais de um valor a ser escrito como no primeiro, os diversos valores sao separados por vırgula.

Observe que ’Jo~ao Vitor’ e um literal, ou seja, tudo que estiver entre dois ’ sera impresso exatamente da forma com que esta escrito. A utilidade do ’ ’ e efetuar a separacao entre os diversos termos a serem impressos ja que 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

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 como iguais.

2.2 Constantes

Uma constante e um valor que nao se modifica com o tempo. As constantes com que trabalharemos podem ser de tres tipos diferentes, numericas, logicas ou literais. Constantes numericas podem conter quaisquer valores numericos, reais ou inteiros, positivos ou negativos, etc. Exemplos de constantes numericas sao:

Constantes literais podem conter um ou mais caracteres alfabeticos ou numericos. Sao delimitados por aspas. Exemplos de constantes literais sao:

’Jose da Silva’ ’1245’

Constantes logicas podem conter somente dois valores, verdadeiro e falso. Normalmente sao utilizadas em testes em algoritmos.

2.3 Variaveis

Uma variavel e um valor que pode ser alterado em um algoritmo. Cada variavel tem um nome associado a ela que a identifica. O identificador de uma variavel deve comecar por uma letra e pode conter letras ou dıgitos. Ex:

A X5 Joao

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 seja declarada no inıcio do algoritmo, ou seja, defina-se no inıcio do algoritmo qual o tipo de valor com que a variavel ira trabalhar ( numerico, logico ou literal ). 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

Uma variavel pode armazenar qualquer valor e seu valor pode ser alterado a qualquer momento no algoritmo. O comando utilizado para alterar o valor de 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, variavel ou chamada de funcao. Por exemplo:

O comando acima (le-se “A recebe cinco”) faz com que a variavel A passe a valer 5. O valor anterior da variavel A e perdido e seu novo valor passa a ser 5. Assim, por exemplo:

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:

No primeiro exemplo a variavel A recebe o resultado da expressao aritmetica 3 + 2, expressao esta que contem somente constantes. No segundo exemplo a variavel A recebe o conteudo da variavel B e no terceiro exemplo a variavel X5 recebe o resultado da expressao aritmetica A + 1, expressao esta que contem a variavel A e a constante 1. Um exemplo interessante:

{A=10} A := A+1 {A=1}

Ou seja, a expressao A+1 e avaliada, tendo como resultado 10 + 1 = 1 e o valor e atribuido a variavel 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 <lista-de-variaveis>

Este comando faz com que a primeira variavel da lista receba o primeiro valor digitado no teclado, a segunda variavel receba o segundo valor e assim por diante. Ex:

Leia A,B

Ao executar este comando o computador espera que sejam fornecidos dois valores na entrada virtual ( p.ex: 10 e 20 ). A variavel A recebera entao o primeiro valor (10) e a variavel B recebera o segundo valor (20).

Ex 2.8 - Escrever um algoritmo que le tres numeros, calcula as medias aritmetica, harmonica e geometrica e escreve os numeros lidos e as medias calculadas.

Ex 2.9 - Escrever um algoritmo que le o nome de um funcionario, o numero do funcionario, seu numero de horas trabalhadas, o valor que recebe por hora, o numero de filhos com idade menor que 14 anos e calcula o salario deste funcionario.

Ex 2.10 - Escrever um algoritmo que calcula o fatorial de 5. Ex 2.1 - 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 entre 10 e 20.

Ex 2.13 - Escrever um algoritmo que le p, u e r, respectivamente o primeiro termo de uma progressao aritmetica, o ultimo termo da progressao e a razao desta progressao. Determinar a soma dos termos desta progressao aritmetica.

Ex 2.14 - Escrever um algoritmo que le o codigo da peca 1, o numero de pecas 1, o valor unitario da peca 1, o codigo da peca 2, o numero de pecas 2, o valor unitario da peca 2 e a percentagem do IPI a ser acrescentado e calcula o valor total a ser pago.

Operacao Sımbolo Precedencia

Adicao + 3

Subtracao - 3

Multiplicacao * 2

Divisao / 2 Potenciacao ** 1

Tabela 1: Operacoes Aritmeticas

2.6 Expressoes Aritmeticas

Para que uma expressao possa ser avaliada em um algoritmo ela deve seguir uma sintaxe bem definida. As operacoes utilizadas nas expressoes aritmeticas em nossa linguagem sao as mostradas na Tabela 1 junto com as suas precedencias. A precedencia dos operadores indica a ordem que eles serao avaliados em uma expressao.

A precedencia dos operadores e relevante para o resultado da avaliacao de uma expressao. Por exemplo, a avaliacao da expressao 3 + 4 * 2 pode resultar 14 se a soma for efetuada em primeiro lugar ou 1 se a multiplicacao for efetuada em primeiro lugar. Para isto se define a prioridade das operacoes. Ao avaliar uma expressao primeiro sao efetuada as potenciacoes, apos sao efetuadas as multiplicacoes e divisoes e por fim as adicoes e subtracoes. Quando houverem duas operacoes de mesma prioridade para serem efetuadas, a ordem de execucao e da esquerda para a direita.

E possıvel alterar a ordem de execucao das operacoes em uma expressao com o uso de parenteses. Em uma expressao com parenteses em primeiro lugar sao efetuadas as operacoes entre parenteses.

Ex: Expressao para o calculo das raızes de uma equacao de segundo grau segundo 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 funcoes pre-definidas da Tabela 2.

Funcao Especificacao

LOG(x) logaritmo de x na base 10 LN(x) logaritmo natural de x EXP(x) e elevado na x-esima potencia ABS(x) modulo ( valor absoluto ) de x

TRUNCA(x) valor inteiro de x

ARREDONDA(x) inteiro mais proximo a x

QUOCIENTE(x,y) quociente inteiro da divisao de x por y RESTO(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 de

E usando a serie abaixo considerando primeiro 3 termos, depois 4 termos e finalmente 5 termos:

Ex 2.17 - Escrever um algoritmo que le o valor de um emprestimo e calcula o valor de cada amortizacao considerando 24 amortizacoes a uma taxa de 48%. Depois fazer o mesmo algoritmo lendo os valores da taxa e do numero de amortizacoes.

onde VAMORT e o valor da amortizacao, VEMPREST e o valor do emprestimo, TAXA e a taxa, e NAMORT e o numero de amortizacoes.

Ex 2.18 - Escrever um algoritmo que le um valor em cruzeiros e calcula qual 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 a relacao de notas necessarias.

Ex 2.19 - Escrever um algoritmo que le o numero do vendedor, o seu salario fixo, o total de vendas por ele efetuadas e o percentual que ganha sobre o total de vendas. Calcular o salario total do vendedor. Escrever o numero do vendedor e o salario total.

Ex 2.20 - Escrever um algoritmo que le 3 valores a, b e c que sao lados de um triangulo e calcule a area deste triangulo.

Ex 2.21 - Um sistema de equacoes lineares do tipo:{ ax+by = c pode ser resolvido segundo mostrado abaixo:

ae − bd y = af − cd ae − bd

Escrever um algoritmo que le os coeficientes a, b, c, d, e, e f, e calcula e escreve os valores de x e y.

Ex 2.2 - O custo ao consumidor, de um carro novo, e a soma do custo de fabrica com a porcentagem do distribuidor e dos impostos ( aplicados ao custo 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 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 funcionarios vendedores, um salario fixo por mes, mais uma comissao tambem fixa para cada carro vendido e mais 5% do valor das vendas por ele efetuadas. Escrever um algoritmo que le o nome do vendedor, o numero do vendedor, o numero de carros por ele vendidos, o valor total de suas vendas, o salario fixo e o valor 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 INPC e mais um percentual de produtividade discutido com a empresa. Escrever um algoritmo que le o nome do funcionario, o numero do funcionario, seu salario atual, o valor do INPC e o ındice de produtividade conquistado e escreve 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: ”E o maior”.

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 operando

E Verdadeiro se e somente se os dois opeandos sao verdadeiros

Ou Verdadeiro se pelo menos um dos dois operandos e verdadeiro

(Parte 1 de 4)

Comentários