Aulas AED 1

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

1
Algoritmos e Estruturas de Dados 1
Prof.: Bruno Schneider
DCC - UFLA
2
Sites de AED1
● Homepage
– http://www.dcc.ufla.br/~bruno/aulas/aed1/
(ler o material sobre arquivos e diretórios, interface de 
linha de comando, entrada e saída padrão de dados e 
codificação de texto)
● Moodle
– http://alunos.dcc.ufla.br/
● AlGod
– http://asteroide.dcc.ufla.br/algod/
3
Sistema de Avaliação
● Exercícios práticos
– Exercícios valendo nota em quase toda aula prática.
– As notas são juntadas em três notas que são 
lançadas no SIG.
● Quem não alcança 60% nas notas juntadas tem 
direito a substituir a nota por outra avaliação.
● Quem passa por meio da recuperação passa 
com 60 pontos.
4
Definições de Algoritmos
● Algoritmo é uma sequência finita de 
instruções ou operações cuja execução, em 
tempo finito, resolve um problema 
computacional, qualquer que seja sua 
instância. (SAVETTI, 1999)
● Algoritmo é uma sequência de passos que visa 
atingir um objetivo bem definido. 
(FORBELLONE, 1999)
5
Algoritmos (importância)
● Algoritmos são muito importantes como forma 
de planejamento.
● Algoritmos são importantes como um passo em 
direção à formalização de uma ideia.
● Algoritmos permitem a comunicação de 
procedimentos, para comparação, verificação, 
discussão.
6
Algoritmos (tipos)
● Descrição Narrativa (linguagem natural, 
sujeitos à ambiguidade)
● Fluxograma (linguagem gráfica, simbologia 
com muito detalhes, custoso de produzir)
● Pseudocódigo ou Portugol (linguagem formal, 
próxima a uma linguagem de programação).
7
Algoritmos (exemplos)
● Fazer um sanduíche (Ascencio, 2007)
1.Pegar o pão.
2.Cortar o pão ao meio.
3.Pegar a maionese.
4.Passar a maionese no pão.
5.Pegar e cortar alface e tomate.
6.Colocar alface e tomate no pão.
7.Pegar o Hambúrguer.
8.Fritar o Hambúrguer.
9.Colocar o Hambúrger no pão.
8
Algoritmos (exemplos)
● Trocar uma Lâmpada (ASCENCIO, 2007)
1. Pegar uma lâmpada nova.
2. Pegar uma escada.
3. Posicionar a escada embaixo da lâmpada queimada.
4. Subir na escada com a lâmpada nova na mão.
5. Retirar a lâmpada queimada.
6. Colocar a lâmpada nova.
7. Descer da escada.
8. Testar o interruptor.
9. Guardar a escada.
10. Jogar a lâmpada velha no lixo.
9
Algoritmos (elementos importantes)
● Cada item do algoritmo é uma instrução ou 
uma ordem.
– Cortar o pão ao meio.
– Corta o pão ao meio.
– Corte o pão ao meio.
● Existe uma sequência.
● Existe um início e um final bem definidos.
10
Algoritmos (dificuldades)
● Nível de detalhe
– Pega o pão - onde está o pão?
– Corta o pão - tenho uma faca para cortar o pão?
● Ordens disponíveis
– Frita o hambúger - eu sei como se frita um 
hambúrguer?
● Ordens que contém outras ordens
11
Algoritmos (exercício)
● Escreva um algoritmo (descrição narrativa) 
para sacar dinheiro no caixa automático.
12
Algoritmos (conclusão do exercício)
● Não existem dois algoritmos iguais, cada um 
fez um algoritmo um pouco diferente.
● Não existe “a resposta certa” na programação, 
porém existem soluções que funcionam e 
soluções que não funcionam.
13
Algoritmos para Computação
● A escolha de um subconjunto para os 
algoritmos reduz as dificuldades da criação.
● Algoritmos são baseados em:
– operações matemáticas,
– atribuição (alteração de valores),
– controle de fluxo (quem é a próxima ordem?).
● Operações matemáticas não são 
ordens/instru ções!
14
Abstração
● Abstrair é eliminar detalhes 
que não são importantes 
num determinado contexto.
● As operações disponíveis 
variam muito.
● Quando uma operação 
desejada não existe pronta, 
ela deve ser produzida por 
meio de operações mais 
simples.
Soma Soma Soma
Multiplicação Multiplicação
Potenciação
Ex.: alto nível
baixo nível
15
Algoritmos (exercício)
● Escreva um algoritmo (descrição narrativa) que 
permite calcular a área de um (qualquer) 
retângulo.
– Identificar as informações necessárias para o 
cálculo
– Providenciar interface
16
Algoritmo (área de um retângulo)
1. Ler a altura e a largura.
2. Atribuir (associar) à área do retângulo, a 
multiplicação da altura pela largura.
3. Escrever a área do retângulo.
17
Algoritmos (exercício)
● Escreva um algoritmo que calcula a média 
aritmética de três números.
18
Algoritmo (média de 3 números)
1. Ler três números (a, b e c).
2. Atribuir ao resultado a soma de a e b.
3. Atribuir ao resultado a soma do valor anterior 
do resultado com c.
4. Atribuir ao resultado a divisão do valor anterior 
do resultado por 3.
5. Escrever o resultado.
19
Implementação em C++
● Computadores não entendem descrições 
narrativas.
● Algoritmos precisam ser transcritos para uma 
linguagem de programação.
● A linguagem de programação adotada é C++.
● A transcrição de um algoritmo para uma 
linguagem de programação é um programa 
(código fonte).
20
Esqueleto de um programa em C++
#include <iostream>
using namespace std;
int main()
{
 return 0;
}
21
Programa (área de um retângulo)
#include <iostream>
using namespace std;
int main()
{
 float altura;
 cin >> altura;
 float largura;
 cin >> largura;
 float area = altura * largura;
 cout << area << endl;
 return 0;
}
22
Programa (área de um retângulo)
#include <iostream>
using namespace std;
int main()
{
 cout << "Este programa calcula a area de um retangulo "
 << "qualquer.\nDigite a altura do retangulo: ";
 float altura;
 cin >> altura;
 cout << "Digite a largura do retangulo: ";
 float largura;
 cin >> largura;
 float area = altura * largura;
 cout << "A area do retangulo e': " << area 
 << " unidades quadradas.\n";
 return 0;
}
23
Programa (área de um retângulo)
#include <iostream>
using namespace std;
int main()
{
 cout << "Este programa calcula a area de um retangulo "
 << "qualquer.\nDigite a altura do retangulo: ";
 float altura;
 cin >> altura;
 cout << "Digite a largura do retangulo: ";
 float largura;
 cin >> largura;
 cout << "A area do retangulo e': " 
 << altura * largura 
 << " unidades quadradas.\n";
 return 0;
}
24
Compilação
● Compilar um programa é transformar o código 
fonte (texto resultante da transcrição do 
algoritmo para uma linguagem de 
programação) num arquivo executável 
(instruções que o computador entende).
● A compilação é feita por um programa que 
chamamos de compilador.
25
Uso do compilador
$ g++ area-retangulo.cpp
$ g++ -Wall area-retangulo.cpp
$ g++ -Wall area-retangulo.cpp -o area-retangulo
$ g++ -Wall area-retangulo.cpp && ./a.out
26
Programa (média de 3 números)
int main()
{
 cout << "Este programa calcula a media de 3 numeros.\n"
 << "Por favor, digite o primeiro numero: ";
 float numero1;
 cin >> numero1;
 cout << "Por favor, digite o segundo numero: ";
 float numero2;
 cin >> numero2;
 cout << "Por favor, digite o terceiro numero: ";
 float numero3;
 cin >> numero3;
 cout << "A media dos tres numeros e': "
 << (numero1+numero2+numero3)/3 << "\n";
 return 0;
}
27
Programa (média de 3 números)
cout << "Este programa calcula a media de 3 numeros.\n"
 << "Por favor, digite o primeiro numero: ";
float numero;
cin >> numero;
float soma = numero;
cout << "Por favor, digite o segundo numero: ";
cin >> numero;
soma = soma + numero;
cout << "Por favor, digite o terceiro numero: ";
cin >> numero;
soma = soma + numero;
cout << "A media dos tres numeros e': "
 << soma/3 << "\n";
return 0;
28
Variáveis
● Na matemática usamos letras para representar 
valores desconhecidos ou parametrizados.
● Na programação
usamos identificadores 
(nomes) que são associados à posições na 
memória, que por sua vez contém um valor.
– o valor é alterado ao longo do tempo
● Variáveis são também associadas a tipos.
● Constantes não mudam de valor.
29
Identificadores
● Nem todo valor precisa ter um nome. Use 
nomes para reaproveitar valores já 
computados. Use expressões se o valor será 
usado somente uma vez.
● As linguagens têm regras para criação de 
identificadores.
● Use nomes significativos.
30
Tipos de Dados
● Inteiros
● Reais (Racionais)
● Caractere
● String
31
Tipos de Dados em C++
● Naturais: unsigned int.
● Inteiros: int.
● Racionais: float (ou double).
● Lógico (booleano): bool.
● Existem outros tipos (na linguagem e STL).
● Compiladores têm mais tipos.
● O programador cria seus próprios tipos.
32
Instruções de C++ (algumas)
● Atribuição: 
✔ =
✔ +=, -=, *=, /=, %=
✔ ++
✔ --
● Leitura: >>
● Escrita: <<
● Operadores lógicos e 
aritméticos (não são 
ordens):
✔ +, -, *, /, %
✔ >, <, <=, >=, ==, !=
33
A biblioteca padrão cmath
● Com #include <cmath> você ganha:
– Potenciação (pow(base, expoente), sqrt)
– Trigonometria (cos, sin, tan, acos, asin, atan)
– Arredondamento (ceil, floor)
– Valor absoluto (abs)
– Π (M_PI)
34
Exercícios
● Faça um programa que leia três notas e seus 
respectivos pesos, calcule e escreva a média 
ponderada dessas notas.
● Faça um programa que receba o salário de um 
funcionário, calcule e escreve o novo salário, 
sabendo-se que este sofreu um aumento de 
25%.
● Idem, porém o percentual também é lido pelo 
programa.
35
Exercícios
● Faça um programa que receba o salário base 
de um funcionário, calcule e mostre o salário a 
receber, sabendo-se que o funcionário tem 
gratificação de 5% sobre o salário base e paga 
imposto de 7% sobre este salário.
● Faça um programa que receba o valor de um 
depósito e o valor da taxa de juros, calcule e 
escreva o valor do rendimento e o valor total 
depois do rendimento.
36
Exercícios
● Faça um programa que converte uma certa 
quantidade de tempo expressa em minutos 
para dias, horas e minutos (todos juntos, 
valores inteiros).
● Faça um programa que converte de dias, horas 
e minutos para minutos.
37
Controle de Fluxo
● Seletores (estrutura condicional):
– unidirecional,
– bidirecional,
– aninhados,
– múltiplos.
● Testes são expressões que representam 
valores booleanos.
38
Seletores
● Unidirecional (um comando opcional)
– Se parece que vai chover, então leve um 
guarda-chuva.
– formato: se teste então instrução
● Bidirecional (escolher entre dois comandos)
– Se o número é par, então escreva “é par”, senão 
escreva “é impar”.
– formato: se teste então comando senão comando
39
Seletores (cont.)
● Aninhados
– Um dos comandos de um seletor é outro seletor.
● Múltiplos
– escolher um dentre vários comandos
– Caso a nota esteja entre 0 e 59, atribuir “F” ao 
conceito, caso esteja entre 60 e 79, atribuir “B” ao 
conceito, caso contrário, atribuir “A” ao conceito.
40
Seletores em C++
● if (teste) comando;
ex.:
if (numero < 0) cout << “negativo”;
● if (teste) comando; else comando;
ex.:
if (numero < 0)
 cout << “negativo”;
else
 cout << “positivo”;
41
Seletores em C++ (cont.)
● É permitido aninhar seletores. Um else é 
sempre considerado parte do if imediatamente 
anterior.
Ex.:
if (numero != 0)
 if (numero > 0)
 cout << “positivo”;
 else
 cout << “negativo;
42
Seletores em C++ (cont.)
● O seletor múltiplo tem seus testes limitados à 
verificação de equivalência.
Ex.: cout << "Digite um numero inteiro entre 1 e 3: ";
cin >> escolha;
switch (escolha)
{
 case 1:
 cout << "Voce digitou 1.\n";
 break;
 case 2:
 cout << "Voce digitou 2.\n";
 break;
 case 3:
 cout << "Voce digitou 3.\n";
 break;
 default:
 cout << "Voce nao digitou um numero entre 1 e 4.\n";
}
43
Controle de Fluxo (cont.)
● Comandos compostos são grupos de 
instruções que podem ser usados onde a 
linguagem determina a presença de um 
comando.
● Nomes de variáveis declarados num comando 
composto só têm validade dentro do comando 
composto.
● Em C++:
{
 comando;
 comando;
 ...
 comando;
} 44
Controle de Fluxo (cont.)
● Instruções de iteração (estruturas de 
repetição) são instruções que determinam que 
um (ou mais) comandos serão executados 
várias vezes.
● Alguma coisa precisa ser alterada em cada 
passo da repetição.
45
Instruções de iteração
● Controle por lógica: um teste determina se a 
repetição deve continuar ou não.
– o teste pode ser realizado antes ou depois da 
repetição
– o teste pode ser usado para sinalizar que a 
repetição continua ou para sinalizar que a repetição 
termina (lógica positiva ou lógica negativa)
● Existem outros tipos de controle.
46
Instruções de iteração no C++
47
Instruções de iteração nos 
algoritmos
● Atribuir 0 ao número.
Enquanto o número for menor que 5:
 - escrever o número;
 - incrementar o número.
● Atribuir 0 ao número.
Repetir:
 escrever o número;
 incrementar o número;
até que o número seja maior que 5.
Note que as iterações 
foram construídas, para 
repetir uma determinada 
quantidade de vezes, 
com uma variável 
mudando de valor a 
cada passo.