EMB5013 Aula Teo 03 algoritmos

Prévia do material em texto

Introdução aos algoritmos
Introdução à programação de 
computadores – EMB 5013
Objetivos da aula
• Definir algoritmo;
• Apresentar diferentes maneiras de 
representar um algoritmo;
• Apresentar os conceitos necessários para 
elaborar algoritmos utilizando pseudocódigo;
2
Definições
• Um algoritmo é uma seqüência de passos bem 
definidos que têm por objetivo solucionar um 
determinado problema.
Forbellone (2005)
• Um algoritmo é a descrição de um número finito de 
passos capazes de especificar precisamente os 
processos que produzirão um resultado específico.
Guimarães (2009)
Algoritmo ≠ programa
3
Definições
• Um conjunto de instruções para o 
computador, descrevendo como executar o 
algoritmo, é chamado programa.
Guimarães (2009)
• Um programa (...) só é útil na medida em que 
represente um conjunto de passos a serem 
dados na resolução de um problema.
Guimarães (2009)
4
Importância
5
• Um algoritmo representa mais fielmente o 
raciocínio envolvido na lógica de programação;
• Abstrai detalhes computacionais;
• Foca no que realmente é importante;
• Uma vez construído o algoritmo, pode-se traduzi-
lo para qualquer linguagem, chama-se isto de 
codificação;
Tipos
• É possível representar um algoritmo utilizando 
diferentes formalismos:
– Descrição narrativa � pouco utilizada;
– Exemplo (troca de lâmpada):
6
1. Pegar uma escada; 
2. Posicionar a escada embaixo da lâmpada;
3. Buscar uma lâmpada nova;
4. Subir na escada;
5. Retirar a lâmpada velha;
6. Colocar a lâmpada nova;
7. Descer da escada.
Tipos
• É possível representar um 
algoritmo utilizando diferentes 
formalismos (cont.):
– Fluxogramas � forma universal 
de representação;
7
Fim
Início
Buscar uma lâmpada nova
Colocar a lâmpada nova
Descer da escada
Pegar uma escada
Posicionar a escada 
embaixo da lâmpada
Subir na escada
Retirar a lâmpada velha
Tipos
• É possível representar um algoritmo utilizando 
diferentes formalismos:
– Pseudocódigo � bastante utilizado;
– Exemplo:
8
lógico: A, B;
inteiro: X;
X ← 8 + 13 div 5;
B ← 5 = 3;
A ← B;
X ← 2;
Descrição narrativa
• A sequência de ações rege o fluxo de execução do 
algoritmo, determinando qual a primeira ação a 
ser executada e qual ação vem a seguir
• E se por acaso no exemplo da lâmpada, ela não 
estivesse queimada?
– Aconteceria uma troca desnecessária e o algoritmo 
não trataria esta situação;
• O que poderia ser feito para melhorar o 
algoritmo?
9
Descrição narrativa
• Exemplo (troca de lâmpada com teste):
• O teste poderia ser realizado em outra etapa?
10
1. Pegar uma escada; 
2. Posicionar a escada embaixo da lâmpada;
3. Buscar uma lâmpada nova;
4. Acionar o interruptor (ligar);
5. Se a lâmpada não acender, então
a) Subir na escada;
b) Retirar a lâmpada queimada;
c) Colocar a lâmpada nova;
d) Descer da escada.
Descrição narrativa
• Exemplo (troca de lâmpada com teste 2):
• E se a lâmpada nova não acender?
11
1. Acionar o interruptor (ligar);
2. Se a lâmpada não acender, então 
a) Pegar uma escada;
b) Posicionar a escada embaixo da lâmpada;
c) Buscar uma lâmpada nova;
d) Acionar o interruptor;
e) Subir na escada;
f) Retirar a lâmpada queimada;
g) Colocar a lâmpada nova;
h) Descer da escada.
Descrição narrativa
• Ex. (troca de lâmpada com teste e repetição):
• Até quando se repete?
12
i ) Acionar o interruptor (ligar)
j ) Se a lâmpada não acender, então
I) Buscar uma lâmpada nova;
II ) Acionar o interruptor (desl.);
III ) Subir na escada;
IV ) Retirar a lâmpada queimada;
V ) Colocar a lâmpada nova;
VI) Descer da escada;
VII) Acionar o interruptor (ligar);
VII) Se a lâmpada não acender, 
então
1) …
1. Acionar o interruptor (ligar);
2. Se a lâmpada não acender, então 
a) Pegar uma escada;
b) Posicionar a escada embaixo da 
lâmpada;
c ) Buscar uma lâmpada nova;
d ) Acionar o interruptor (desligar);
e ) Subir na escada;
f ) Retirar a lâmpada queimada;
g ) Colocar a lâmpada nova;
h ) Descer da escada;
Descrição narrativa
• Falta especificar até quando será feito o teste;
• O algoritmo termina quando a lâmpada 
funcionar, caso contrário ficará testando novas 
lâmpadas indefinidamente;
• Há um conjunto de instruções se repete;
• É possível alterar o fluxo de execução sequencial 
e representar uma repetição de ações com 
condição de parada;
13
Descrição narrativa
• Ex. (troca de lâmpada com teste e repetição 2):
• Até quando se repete?
14
i) Acionar o interruptor (ligar)
j) Enquanto a lâmpada nova não 
acender, faça:
I) Buscar uma lâmpada nova;
II) Acionar o interruptor (desl.);
III) Subir na escada;
IV) Retirar a lâmpada queimada;
V) Colocar a lâmpada nova;
VI) Descer da escada;
VII) Acionar o interruptor (ligar);
1. Acionar o interruptor (ligar);
2. Se a lâmpada não acender, então 
a) Pegar uma escada;
b) Posicionar a escada embaixo da 
lâmpada;
c) Buscar uma lâmpada nova;
d) Acionar o interruptor (desligar);
e) Subir na escada;
f) Retirar a lâmpada queimada;
g) Colocar a lâmpada nova;
h) Descer da escada;
Fluxograma
• Uma maneira gráfica de representar um 
algoritmo;
• Muitas vezes é a maneira mais sucinta de 
escrever um algoritmo;
• Para compreender um fluxograma (simplificado) 
é preciso conhecer os seus elementos:
– Início e fim do algoritmo
– Tarefas ou ações
– Testes
– Sequência
15
Fluxograma
16
Início
Fim
Sequência
Fluxograma
17
Ação ou Tarefa
Teste
condicional
Falso
Verdadeiro
• Exemplo (troca de lâmpada
com teste e repetição):
Fluxograma
18
Fim
Início
Buscar uma lâmpada nova
Colocar a lâmpada nova
Descer da escada
Pegar uma escada
Posicionar a escada
Subir na escada
Retirar lâmpada queimada
Acendeu?
V
F
Acionar o interruptor (lig.)
Acionar o interruptor (de.)
Acionar o interruptor (lig.)
Acendeu?
V
F
Pseudocódigo
• Forma de representação de algoritmos que 
utiliza uma linguagem flexível, intermediária 
entre a linguagem natural e a linguagem de 
programação;
• O nome pseudocódigo significa “falso código”, 
e esse nome se deve à proximidade que existe 
entre um algoritmo escrito em pseudocódigo 
e a maneira que um programa é representado 
em uma linguagem de programação.
19
Pseudocódigo
• Exemplo:
20
Início //começo do algoritmo
real: N1, N2, N3, N4,MA; //declaração de variáveis
leia (N1, N2, N3, N4); //entrada de dados
MA ← (N1 + N2 + N3 + N4) / 4; //processamento
escreva(MA); //saída de dados
se (MA >= 7) então
escreva(“Aluno aprovado!”);
fimse;
Fim. //término do algoritmo
Pseudocódigo
• Para escrever algoritmos em pseudocódigo é 
preciso antes abordar alguns conceitos 
importantes:
– tipos primitivos;
– constantes;
– variáveis;
– expressões aritméticas, lógicas e relacionais;
– comando de atribuição;
– comandos de entrada e saída;
– blocos;
21
Pseudocódigo
• Tipos primitivos:
– Inteiro:
• Qualquer informação numérica que pertença ao 
conjunto dos números inteiros (negativo, nulo ou 
positivo);
• Ex: ..., -1, 0, 1, 2, 3, 4, ...
• Algumas proposições declarativas usando tipo inteiro:
– Ele tem 15 irmãos.
– A escada possui 8 degraus.
– Meu vizinho comprou 2 carros novos.
22
Pseudocódigo
• Tipos primitivos (cont.):
– Real:
• Qualquer informação numérica que pertença ao 
conjunto dos números reais (negativo, nulo ou 
positivo);
• Ex: 13,48; 105,56; 0,0001; -15,545;
• Algumas proposições declarativas usando tipo real:
– Ela tem 1,73metros de altura.
– Meu saldo bancário é R$ 1,00.
– No momento estou pesando 54,0 kg.
23
Pseudocódigo
• Tipos primitivos (cont.):
–Caractere:
• Qualquer informação composta por um conjunto de 
caracteres alfanuméricos: numéricos (0...9), alfabéticos 
(A...Z, a...z) e especiais (!, @, #, $, %, <, ...)
• Ex: Tatiana, EMB5013, UFSC, tatiana@joinville.ufsc.br
• Algumas proposições declarativas usando tipo 
caractere:
– Constava na prova: “Use somente caneta!”
– Aviso “Não pise na grama”.
– Meu nome é “Tatiana Garcia”.
24
Pseudocódigo
• Tipos primitivos (cont.):
– Lógico:
• Qualquer informação que possa assumir apenas duas 
situações, ou seja, somente dois estados.
• Ex: Sim ou Não; 0 ou 1; Homem ou Mulher;
• Algumas proposições declarativas usando tipo lógico:
– A porta pode ficar aberta ou fechada.
– A lâmpada pode estar acesa ou apagada.
25
Pseudocódigo
• Variáveis e constantes:
– Identificadores:
• A sintaxe que vamos adotar segue as seguintes regras 
para os identificadores: 
– Devem começar por um caractere alfabético;
– Podem ser seguidos por mais caracteres alfabéticos ou 
numéricos;
– Não devem ser usados caracteres especiais (símbolos que 
podem representar alguma operação);
– Não deve conter espaços;
• Identificadores válidos: alpha, BJ153, K7, Media, INPS
• Identificadores inválidos: 5X, E(13), X-Y, Nota/2, AWQ*3
26
Pseudocódigo
• Constantes:
– Um dado é constante quando não sofre nenhuma 
variação no decorrer do tempo;
– O valor é constante desde o início até o fim da 
execução do algoritmo, assim como é constante 
para diferentes execuções no tempo;
– Exemplo: π = 3,1416;
– Constantes do tipo lógico assumem um de dois 
valores: Verdadeiro (V) ou Falso (F).
27
Pseudocódigo
• Variáveis:
– Um dado é classificado como variável quando tem 
a possibilidade de ser alterado em algum instante 
no decorrer do tempo;
– São as variáveis que podem sofrer alterações 
durante a execução do algoritmo;
– Exemplo: A fórmula para calcular a área de uma 
circunferência pode ser expressa utilizando 
constante e duas variáveis: � = ���
• � é uma constante e � e � variáveis
28
Pseudocódigo
• Variáveis (cont.):
– Declaração de variáveis:
• Todas as informações que serão usadas em nossos 
algoritmos ficam armazenadas na memória do 
computador;
• Para poder gravar as informações e posteriormente 
resgatá-las é preciso associar um tipo e identificador a 
esta informação;
• Este processo recebe o nome de Declaração de 
Variáveis;
• As variáveis servem para identificar os dados ;
29
Pseudocódigo
• Variáveis (cont.):
– Declaração de variáveis (cont.):
• Será adotada a seguinte regra sintática:
– Tipo da Variável: identificador 1, identificador2, ... ; 
» Tipo: um dos 4 tipos primitivos;
» Identificador: o nome que desejo dar para minha variável;
– Uma vez definido o tipo da variável ela não pode receber 
valores de outros tipos;
– Exemplos:
» Inteiro: numero, valor, soma;
» Real: juros, salário;
» Caractere: nome, sobrenome, rua;
» Lógico: resposta;
30
Pseudocódigo
• Variáveis (cont.):
– Declaração de variáveis (cont.):
• Cuidados na hora de declarar variáveis:
– Não criar mais de uma variável com o mesmo identificador;
– Respeitar os tipos de dados;
– Definir os identificadores com nomes que associem ele ao 
valor que armazena
31
Pseudocódigo
• Expressões aritméticas:
– Denomina-se expressão aritmética aquela cujos 
operadores são aritméticos e cujos operandos são 
constantes ou variáveis do tipo numérico (Inteiro 
ou Real)
32
Pseudocódigo
• Expressões aritméticas:
– Operadores aritméticos: Os operadores aritméticos 
são utilizados para realizar os cálculos matemáticos;
33
Operador Função Exemplos
+ Adição 2 + 3, X + Y
- Subtração 4 - 2, N – M
* Multiplicação 3 * 4, A * B
/ Divisão 10 / 2, C / D
pot(x,y) Potenciação (x elevado a y) pot(2, 3)
rad(x) Raiz quadrada (de x) rad(9)
Mod Resto da divisão 9 mod 4 resulta 1
Div Quociente da divisão inteira 9 div 4 resulta 2
Pseudocódigo
• Expressões aritméticas (cont.):
– Operadores aritméticos (cont.):
• Alguns operadores não são convencionais, como mod e 
o div
• Eles são bastantes utilizados na construção de 
algoritmos
• Uma expressão aritmética pode conter vários 
operadores diferentes, e as operações devem seguir 
uma hierarquia de execução � regras de precedência
34
Pseudocódigo
• Expressões aritméticas (cont.):
– Operadores aritméticos (cont.):
• Prioridades dos operadores aritméticos
1. parênteses mais internos
2. pot; rad;
3. *; /; div; mod;
4. + ; -;
• Em caso de empate (mesma prioridade), devemos 
resolver a expressão da esquerda para a direita
35
Pseudocódigo
• Expressões aritméticas (cont.):
– Operadores aritméticos (cont.):
• Exemplos:
36
X = 5 + 9 + 7 + 8 / 4 
X = 5 + 9 + 7 + 2
X = 23
Y = 4/2 + rad(1 + 3 * 5) / 2
Y = 4/2 + rad(1 + 15) / 2
Y = 4/2 + rad(16) /2
Y = 4/2 + 4 /2
Y = 2 + 4/2
Y = 2 + 2
Y = 4
Pseudocódigo
• Expressões lógicas e relacionais:
– Denominamos expressão lógica aquela cujos 
operadores são lógicos ou relacionais e cujos 
operandos são relações, variáveis ou constantes 
do tipo lógico;
– Denominamos expressão relacional aquela cujos 
operadores são relacionais e cujos operandos são 
variáveis ou constantes comparáveis;
37
Pseudocódigo
• Expressões lógicas e relacionais (cont.):
– Operadores relacionais:
• Utilizados para a estabelecer relação de comparação 
entre valores de mesmo tipo primitivo;
38
Operador Função Exemplos
= Igual a 3 = 3, X = Y
> Maior que 5 > 4, X > Y
< Menor que 3 < 6, X < Y
>= Maior ou igual a 5 >= 3, X >= Y
<= Menor ou igual a 3 <= 5, X <= Y
<> Diferente de 8 <> 9, X <> Y
Pseudocódigo
• Expressões lógicas e relacionais (cont.):
– Operadores relacionais (cont.):
• O resultado obtido de uma relação é sempre um valor 
lógico:
39
2 * 4 = 24 / 3
8 = 8
V
Pseudocódigo
• Expressões lógicas e relacionais (cont.):
– Operadores lógicos:
• Utilizaremos três operadores para efetuar avaliações 
lógicas entre valores:
40
Operador Função Exemplos
não Negação não V, não X
e Conjunção V e V, X e Y
ou Disjunção V ou V, X ou Y
Pseudocódigo
• Expressões lógicas e relacionais (cont.):
– Operadores lógicos (cont.):
• Tabela verdade:
– É o conjunto de todas as possibilidades combinatórias entre 
os valores de diversas variáveis lógicas e um conjunto de 
operadores lógicos;
– Constrói-se uma tabela verdade com o objetivo de dispor de 
uma maneira prática os valores lógicos envolvidos em uma 
expressão lógica;
– Cada operador tem a sua tabela verdade;
41
Pseudocódigo
• Expressões lógicas e relacionais (cont.):
– Operadores lógicos (cont.):
• Tabela verdade (cont.):
42
A não A
F V
V F
A B A e B
F F F
F V F
V F F
V V V
A B A ou B
F F F
F V V
V F V
V V V
Pseudocódigo
• Expressões lógicas e relacionais (cont.):
– Operadores lógicos (cont.):
• Exemplos:
1) Se chover e relampejar, eu fico em casa.
» Quando eu fico em casa?
2) Se chover ou relampejar eu fico em casa.
» Quando eu fico em casa? 
43
Pseudocódigo
• Expressões lógicas e relacionais (cont.):
– Operadores lógicos (cont.):
• Exemplos:
1) Se chover e relampejar, eu fico em casa.
» Quando eu fico em casa?
» Quando acontecerem as duas ações – chover e
relampejar
2) Se chover ou relampejar eu fico em casa.
» Quando eu fico em casa? 
» Quando pelo menos uma das ações acontecerem –
chover ou relampejar
44
Pseudocódigo
• Expressões lógicas e relacionais (cont.):
– Operadores lógicos (cont.):
• Prioridades dos operadores lógicos
1) não;
2) e;
3) ou;
• Prioridades entre todos os operadores:
1) parênteses maisinternos;
2) operadores aritméticos;
3) operadores relacionais;
4) operadores lógicos;
(Esta regra pode sofrer alterações dependendo da linguagem de 
programação)
45
Pseudocódigo
• Expressões lógicas e relacionais (cont.):
– Exemplo:
46
pot(2,4) <> 4 + 2 ou 2 + 3 * 5/3 mod 5 < 0
16 <> 4 + 2 ou 2 + 3 * 5 / 3 mod 5 < 0
16 <> 4 + 2 ou 2 + 15/3 mod 5 < 0
16 <> 4 + 2 ou 2 + 5 mod 5 < 0
16 <> 4 + 2 ou 2 + 0 < 0
16 <> 6 ou 2 + 0 < 0
16 <> 6 ou 2 < 0
V ou 2 < 0
V ou F
V
Pseudocódigo
• Expressões lógicas e relacionais (cont.):
– Exemplo:
47
não ((5 <> 10/2) ou V e 2 – 5 > 5 – 2 ou V) 
não ((5 <> 5) ou V e 2 – 5 > 5 – 2 ou V) 
não (F ou V e 2 – 5 > 5 – 2 ou V)
não (F ou V e -3 > 5 – 2 ou V)
não (F ou V e -3 > 3 ou V)
não (F ou V e F ou V)
não (F ou F ou V)
não (F ou V)
não (V)
F � resultado final da expressão
Pseudocódigo
• Comando de atribuição:
– Um comando de atribuição em um algoritmo 
permite associar um valor a uma variável;
– O tipo de dado deve ser compatível com tipo que 
a variável foi declarada;
– Cada variável pode receber apenas um valor de 
cada vez. O segundo valor sobrepõe-se ao anterior
– Sintaxe: variável ← valor;
48
Pseudocódigo
• Comando de atribuição (cont.):
– Podem ser atribuídos: constantes, variáveis e 
expressões (aritméticas, relacionais ou lógicas);
– Exemplos:
49
inteiro: idade;
idade ← 28;
inteiro: idade;
idade ← 3,5;
ERRO
Pseudocódigo
• Comando de atribuição (cont.):
– Exemplos:
• Qual os valores gravados nas variáveis depois do 
processamento?
50
lógico: A, B;
inteiro: X;
X ← 8 + 13 div 5;
B ← 5 = 3;
A ← B;
X ← 2;
Pseudocódigo
• Comando de atribuição (cont.):
– Que erros existem nos comandos de atribuição 
abaixo:
51
lógico: A;
real: B, C;
inteiro: D;
A ← B = C;
D ← B;
C+1 ← B+C;
C e B ← 3.5;
B ← pot(6,2)/3 <= rad(9) * 4
Pseudocódigo
• Comando de atribuição (cont.):
– Que erros existem nos comandos de atribuição 
abaixo:
52
lógico: A;
real: B, C;
inteiro: D;
A ← B = C;
D ← B; //inteiro recebendo real
C+1 ← B+C; //operação no lado esq.
C e B ← 3.5; //operação no lado esq.
B ← pot(6,2)/3 <= rad(9)*4 //real recebendo lógico
Pseudocódigo
• Comando de atribuição (cont.):
– Algumas regras (para pseudocódigo):
• 1) À esquerda do símbolo só deve existir uma variável:
– Certo: x ← 20;
– Errado: x, y, t ← 10;
• 2) Podemos atribuir expressões aritméticas e lógicas às 
variáveis, porém primeiro as expressões devem ser 
resolvidas para depois fazermos as atribuições. 
– Certo: c ← b + c + 1; 
– Errado: c + 1 ← b + c;
53
Pseudocódigo
• Comandos de entrada e saída:
– Os algoritmos precisam ser alimentados com 
dados provenientes do meio externo para 
efetuarem as operações e cálculos que são 
necessários a fim de alcançar o resultado 
desejado;
– Algoritmo = Entrada + Processamento + Saída
54
Pseudocódigo
• Comandos de entrada e saída (cont.):
– O comando utilizado para representar a entrada 
de dados é o leia();
– O comando simplesmente atribui um valor lido da 
entrada (geralmente o teclado) para uma variável; 
– Exemplos:
– Sintaxe:
55
leia(X);
leia(nota1, nota2);
leia(variável1, variável2, ...);
Pseudocódigo
• Comandos de entrada e saída (cont.):
– O comando utilizado para representar a saída de 
dados é o escreva();
– O comando simplesmente exibe valores das 
variáveis ou mensagens ao mundo exterior;
– Exemplos:
– Sintaxe:
56
escreva(X);
escreva(“Nota1 = ”, nota1);
escreva(variável1, variável2, ...);
Pseudocódigo
• Blocos:
– Um bloco pode ser definido como um conjunto de 
ações com uma função definida;
– Um algoritmo pode ser visto como um grande 
bloco e pode conter vários blocos;
– Serve para definir os limites nos quais as variáveis 
declaradas em seu interior são conhecidas;
– Delimitadores utilizados: início e fim
57
Pseudocódigo
• Blocos:
– Sintaxe:
58
início //início do bloco (algoritmo)
//declaração de variáveis
//sequência de ações (eventualmente mais blocos)
fim. //fim do bloco (algoritmo)
Pseudocódigo
• Blocos:
– Sintaxe:
59
Início 
inteiro: x, y;
leia(x);
y ← pot(x,3)
escreva(x, “elevado ao cubo = “, y)
Fim.
Avisos
• Conteúdo desta aula:
– Capítulos 1 e 2 do livro do Forbellone e 
Eberspacher.
• Lista de exercícios:
– Disponível no moodle.
60