Conceitos Fundamentais de
Algoritmos
e Programação para iniciantes
[email protected]
REFERÊNCIA: Material dos Profs. Reinaldo Gomes
(UFRPE) e Robson Fidalgo (UFPE)
www.xiscanoe.org
Algoritmo Textual Informal
• Modo de preparo:
Quão cremoso?!?
– Bata a margarina, as gemas e o açúcar até ficar
Quanto tempo?!?
cremoso
– Junte o leite, o coco e a farinha e continue
batendo
De uma vez só?!?
– Acrescente o fermento e, por último, as claras em
neve
Quanto tempo?!?
– Unte uma forma com manteiga e leve ao forno
para assar
Algoritmo Textual Informal
Refinado
• Modo de preparo:
– Bata a margarina, as gemas e o açúcar por 15
minutos
– Junte o leite, o coco e a farinha e continue
batendo por mais 15 minutos
– Acrescente 20 g de fermento e, por último, as
claras em neve
– Unte uma forma com manteiga e leve ao forno
para assar por 30 minutos
Algoritmo Gráfico-Textual Informal
• Montagem de um Aeromodelo
– Material
•
•
•
•
•
Cola especial para plásticos
Estilete
Lixas finas
Durex ou fita crepe
Pregador de roupas, elásticos
Algoritmo Gráfico-Textual
Informal
• Identificação das peças
Algoritmo Gráfico-Textual
Informal
• Instruções
– Leia e entenda as instruções antes de começar a
montagem
– Lave as peças com água e detergente. Na lavagem
serão removidos desmoldantes e sujeiras, que
dificultam a colagem e a pintura. Faça isto dentro de
uma bacia, para evitar perder peças pequenas, que
porventura se soltem
– Encontre as peças que devem ser usadas na
primeira parte da montagem (figura do slide anterior)
– Lixe as peças com cuidado eliminando as rebarbas
– ...
Algoritmo Textual Informal 2
• Troca de pneu
“Abra o porta-mala e verifique se todos
acessórios estão lá. Em caso negativo,
feche o porta-malas e peça carona a
alguém. Em caso positivo, retire o
triângulo, posicione-o a cerca de 30 m do
carro, e, depois, retire o estepe e o macaco.
Levante o carro... “
Algoritmo Gráfico Informal
• Troca de pneu
Algoritmo Gráfico Semi-formal
• Troca de pneu (Fluxograma)
Abre porta-malas
Sim
Acessórios
OK?
Não
Fecha
porta-malas
Pega triângulo
Algoritmo Textual Formal
• Troca de pneu
abre(porta_malas)
Se acessorio_ok = FALSO
Então
fecha(porta_malas)
espera_carona()
Senão
pega_triangulo()
...
Algoritmo: Problemas Complexos
• Problema da Torre de Hanói
– Seja a seguinte situação:
• deve-se mover todos os discos do primeiro eixo para o
terceiro mantendo-se a ordem original
• em cada movimento, pode-se mover apenas um disco
• um disco nunca poderá ser sobreposto por outro maior
Algoritmo: Problemas Complexos
• Passo 1:
mova disco menor para terceiro eixo
Algoritmo: Problemas Complexos
• Passo 2:
mova disco médio para segundo eixo
Algoritmo: Problemas Complexos
• Passo 3:
mova disco menor para segundo eixo
Algoritmo: Problemas Complexos
• Passo 4:
mova disco maior para terceiro eixo
Algoritmo: Problemas Complexos
• Passo 5:
mova disco menor para primeiro eixo
Algoritmo: Problemas Complexos
• Passo 6:
mova disco médio para terceiro eixo
Algoritmo: Problemas Complexos
• Passo 7:
mova disco menor para terceiro eixo
Algoritmo: Problemas Complexos
• Seqüência de passos completa:
Passo 1: mova disco menor para terceiro eixo
Passo 2: mova disco médio para segundo eixo
Passo 3: mova disco menor para segundo eixo
Passo 4: mova disco maior para terceiro eixo
Passo 5: mova disco menor para primeiro eixo
Passo 6: mova disco médio para terceiro eixo
Passo 7: mova disco menor para terceiro eixo
Algoritmo: CONCEITO
• O que é um ALGORITMO?
• OBS.: Não existe um algoritmo para
construir algoritmos
– a criação de um algoritmo é um exercício de criatividade
(conhecimento) e experiência (técnica e prática)
O que é Programação? =
ABSTRAÇÃO!
A realidade é complexa
e rica em detalhes!
Abstração
Realidade
O que você abstrai dessa realidade?
Abstração
O que é abstração?
Abstração
Abstração
=
Operação mental que
observa a realidade e
captura apenas os
aspectos relevantes
para um contexto
MASLOW
• A tarefa de programar
sistemas computacionais
envolve o exercício
constante da abstração da
realidade e sua codificação
em uma linguagem de
programação
Abstração
Realidade
Abstração
+
Programação
Sistema de Locadora de Veículo
Sistema Computacional
O que é um
Sistema Computacional?
Sistema Computacional
Sistema
Computacional
Software
Hardware
Peopleware
Programação de Sistema
Computacional
• A programação de um sistema computacional
pode ser resumida em 3 passos básicos
Entrada
Processamento
Saída
Dispositivo
de Entrada
UCP
Dispositivo
de Saída
Memória
Programação de Sistema
Computacional
• Exemplo 1 – Exibir a média de dois números
Entrada
Processamento
Saída
Dispositivo
de Entrada
UCP
Dispositivo
de Saída
Memória
6,8
(6 + 8) / 2
7
Programação de Sistema
Computacional
• Exemplo 2 – Exibir se o aluno está aprovado ou reprovado
Entrada
Processamento
Saída
Dispositivo
de Entrada
UCP
Dispositivo
de Saída
Memória
Ana, 5, 3
Se (5+3)/2>=7
aprovado
Senão
reprovado
Ana, reprovado
Programação de Sistema Computacional
• Tipos de Linguagens de Programação
– 1 - Totalmente codificadas em binário (0´s e 1´s)
– 2 - Usa instruções simbólicas para representar os 0´s e 1´s
– 3 - Voltadas para facilitar o raciocínio humano
Baixo Nível
Linguagem
de
Máquina
Alto Nível
Linguagem
Assembly
(Mnemônica)
0010 0001 1110 LOAD R1, val1
Linguagem
de
Alto N ível
val2 = val1+val2
0010 0010 1111 LOAD R2, val2
0001 0001 0010 ADD R1, R2
0011 0001 1111 STORE R1, val2
(1)
(2)
(3)
Noções de Lógica
• Exemplos de aplicação da lógica
– O quarto está fechado e que meu livro está no quarto. Então,
preciso primeiro abrir o quarto para pegar o livro
– Rosa é mãe de Ana, Paula é filha de Rosa, Júlia é filha de Ana.
Então, Júlia é neta de Rosa e sobrinha de Paula
– Todo mamífero é animal e todo cavalo é mamífero. Então, todo
cavalo é animal
– Todo mamífero bebe leite e o homem bebe leite. Então, todo
homem é mamífero e animal (mas não é um cavalo)
Atividade 1 (10min)
• Resolva os seguintes problemas de lógica
– P1 – Uma lesma deve subir um poste de 10m de
altura. De dia sobe 2m e à noite desce 1m. Em
quantos dias atingirá o topo do poste?
– P2 - Três gatos comem três ratos em três minutos.
Cem gatos comem cem ratos em quantos minutos?
– P3 - O pai do padre é filho do meu pai. O que eu sou
do Padre?
– P4 - Se um bezerro pesa 75 kg mais meio bezerro,
quanto pesa um bezerro inteiro?
Atividade 1 (10min)
• Resolva os seguintes problemas de lógica
– P5 – Qual o próximo número da seqüência
7,8,10,13,17,?
– P6 – Um pai de 80kg e suas 2 filhas (40kg cada),
precisam sair de uma ilha com um barco. Porém a
capacidade do barco é de 80kg. Como farão para sair
da ilha?
– P7 – Usando uma jangada, um camponês precisa
atravessar uma cabra, um leão e um fardo de capim
para a outra margem do rio. A jangada só tem lugar
para ele e mais outra coisa. O que ele deve fazer
para atravessar o rio com seus pertences intactos?
RESPOSTAS - Atividade 1
• Respostas
– R1 - 9(nove) dias. No nono dia a lesma sobe 2(dois) metros,
atinge o topo e evidentemente não desce 1 metro
– R2 – 3 (três) minutos
– R3 – Tio
– R4 – 150 (cento e cinqüenta) kg
– R5 – 22
– R6 – Vão as duas filhas. Uma delas volta. O pai sai. A outra filha
volta. As duas filhas saem juntas.
– R7 - Primeiro leve a cabra, volte e pegue o capim; deixe o capim
e leve a cabra de volta; deixe a cabra e leve o leão, depois é só
voltar e pegar a cabra.
Noções de Lógica
Em Lógica um conceito importante
é o de “Proposição”
Você sabe o que é uma
PROPOSIÇÃO?
Noções de Lógica
• Proposição: é um enunciado verbal, ao qual deve ser atribuído,
sem ambigüidade, um valor lógico verdadeiro (V) ou falso (F).
– Exemplos de proposições:
• Robson Fidalgo é Professor (V)
• 3 + 5 = 10 (F)
• 5 < 8 (V)
– Contra-exemplos de Proposições:
• Onde você vai ?
• 3+5
• Os estudantes jogam vôlei. (quais ?)
Noções de Lógica
• Operações Lógicas: são usadas para formar novas proposições a
partir de proposições existentes.
– Considerando p e q duas proposições genéricas, pode-se
aplicar as seguintes operações lógicas básicas sobre elas
Operação Símbolo
Negação
~
Conjunção
^
Disjunção
v
Significado
Não
E
OU
– Definindo a prioridade:
• Usar parênteses Ex:((p v q)^(~q)) ou
• Obedecer (~) > (^) > (v)
Noções de Lógica
• Exemplos de aplicação das operações lógica
– Considere:
• p = 7 é primo = (V)
• q = 4 é impar = (F)
– Então:
• 4 NÃO é impar = ~q = (~F) = (V)
• 7 NÃO é primo = ~p = (~V) = (F)
• 7 é primo E 4 NÃO é impar = p ^ ~q = (V ^ (~F)) = (V ^ V) =
(V)
• 7 é primo E 4 é impar = p ^ q = (V ^ F) = (F)
• 4 é impar E 7 é primo = q ^ p = (F ^ V) = (F)
• 4 é impar E 7 NÃO é primo = q ^ ~p = (F ^ (~V)) = (F ^ F) =
(F)
Noções de Lógica
• Exemplos de aplicação das operações lógica (Cont.)
– Considere:
• p = 7 é primo = (V)
• q = 4 é impar = (F)
– Então:
• 7 é primo OU 4 NÃO é impar = p v ~q = (V v (~F)) = (V v V)
= (V)
• 7 é primo OU 4 é impar = p v q = (V v F) = (V)
• 4 é impar OU 7 é primo = q v p = (F v V) = (V)
• 4 é impar OU 7 NÃO é primo = q v ~p = (F v (~V)) = (F v F
) = (F)
Noções de Lógica
• Exemplos de aplicação das operações lógica
– Resumindo:
p q
~p
p^q
pvq
V
V
F
F
V
F
V
F
F
F
V
V
V
F
F
F
V
V
V
F
– Ou seja:
• Não (~) troca o valor lógico. Se é F passa a ser V e viceversa
• E (^) só tem valor V quando as duas proposições forem V,
basta uma proposição ser F para o resultado ser F
• OU (v) só tem valor F quando as duas proposições forem F,
basta uma proposição ser V para o resultado ser V
Atividade 2
• Considerando p = V e q = F, resolva as seguintes expressões
lógicas
– ~p
– ~q
– p^q
– pvq
– (~p) ^ q
– (~p) v q
– p ^ (~q)
– p v (~q)
– (~p) ^ (~q)
– (~p) v (~q)
RESPOSTAS - Atividade 2
• Considerando p = V e q = F, resolva as seguintes expressões
lógicas
– ~p = F
– ~q = V
– p^q=F
– pvq=V
– (~p) ^ q = F
– (~p) v q = F
– p ^ (~q) = V
– p v (~q) = V
– (~p) ^ (~q) = F
– (~p) v (~q) = V
Lógica de Programação &
Algoritmo
O que é
Programação
de computadores?
 INSTRUÇÕES
Instruções Delimitadoras
• Servem para especificar o início e o fim do
algoritmo.
início
...
fim
Declaração de Variáveis
• Utilizado para especificar os nomes e os
respectivos tipos das variáveis
necessárias no algoritmo
declare <variáveis>: <tipo>;
onde:
<variáveis> - lista de nomes de variáveis
separados por vírgula
<tipo> - inteiro, real, caracter, string, lógico
Declaração de Variáveis
• Exemplos:
declare a,b,c: real;
declare nome: string;
declare sexo: caracter;
declare pratica_esporte: lógico;
Bloco de Comentário
• Serve para explicar um determinado
trecho do algoritmo, para torna-lo mais
claro, facilitando seu entendimento por
outras pessoas ou posteriormente.
{ <comentário> }
Exemplo:
{ Isto é um exemplo de comentário }
Instrução de Entrada
• Usada para ler dados de entrada do
algoritmo.
leia(<variáveis>);
onde:
<variáveis> - conterão os dados lidos.
Instrução de Entrada
• Exemplos:
leia(a,b,c);
leia(nome);
leia(sexo);
leia(pratica_esporte);
Instrução de Saída
• Usada para mostrar os resultados do
processamento dos dados de entrada.
escreva(<resultados>);
onde:
<resultados> - geralmente é o conteúdo de uma
ou mais variáveis com a resposta do
problema.
Instrução de Saída
• Exemplos:
escreva(“O valor de D é: ”, D);
escreva(nome, sexo);
escreva(“Pratica esporte.”);
Instrução de Atribuição
• Utilizado para atribuir um determinado
valor a uma variável.
<variável>
<expressão>;
onde:
<variável> - nome de uma variável
<expressão> - um valor do mesmo tipo da
variável ou uma expressão lógica ou
aritmética.
Instrução de Atribuição
• Exemplos
D
B^2-4*A*C;
nome
“Paulo”;
Pratica_Esporte
Sexo
‘M’;
TRUE;
Estruturas de Controle
• Baseado na lógica estruturada, Bohn e
Jacopini provaram que apenas três
estruturas são suficientes para explicar a
solução de qualquer problema, inclusive
tornando-os estruturados e mais legíveis.
Estruturas de Controle
• São elas:
– Estrutura Seqüencial: os comandos ou
instruções vão sendo executados na ordem
em que aparecem no algoritmo.
Estruturas de Controle
• Estrutura de Repetição: comandos são
executados repetidas vezes até que uma
condição de parada seja satisfeita
Estruturas de Controle
• Estrutura de Seleção: Conforme o
resultado de uma expressão lógica,
determinados comandos são executados
e outros não, caracterizando assim uma
seleção de comandos
TRUE
FALSE
Instruções de Seleção
• Tipo simples:
se <sentença> então
<comandos>;
fim-se
OBS.:
<comandos> serão executados apenas se
<sentença> resultar em TRUE.
Instruções de Seleção
• Exemplo:
se A>0 então
B
A + 1;
A
0;
fim-se
Instruções de Seleção
• Tipo composto:
se <sentença> então
<comandos1>;
senão
<comandos2>;
fim-se
OBS.:
<comandos1> serão executados apenas se
<sentença> resultar em TRUE. Em caso contrário,
<comandos2> serão executados.
Instruções de Seleção
• Exemplo:
se A>B então
B
A + 1;
A
0;
senão
A
0;
B
A + 1;
fim-se
Instruções de Repetição
• Enquanto / Fim-Enquanto
enquanto <sentença> faça
<comandos>;
fim-enquanto;
OBS.:
<comandos> serão executados enquanto
<sentença> resultar em TRUE.
Instruções de Repetição
• Exemplo:
enquanto A>0 faça
leia(B);
escreva(B);
A
A - 1;
fim-enquanto;
Instruções de Repetição
• Repita / Até
repita
<comandos>;
até <sentença>;
OBS.:
<comandos> serão executados até que
<sentença> resulte em TRUE.
Instruções de Repetição
• Exemplo:
repita
leia(B);
escreva(B);
A
A - 1;
até A<1;
Instruções de Repetição
• Para / Até / Fim-Para
para <variável>
<inicial> até <final> faça
<comandos>;
fim-para;
OBS.:
<variável> - contador do tipo inteiro
<inicial> - valor inicial da variável
<final> - valor final da variável
Instruções de Repetição
• Exemplo:
{ Comandos para escrever 10 vezes uma frase
na tela do computador }
para i
1 até 10 faça
escreva(“Último tipo de repetição”);
fim-para;
Estrutura de um Algoritmo
• Um algoritmo em Portugol tem a seguinte
estrutura:
início
<declaração de variáveis>
<inicialização de variáveis>
<corpo lógico do algoritmo>
fim
Lógica de Programação & Algoritmo
• Estruturas básicas de um algoritmo:
– Seqüência – Início/Fim
• Define uma estrutura onde as instruções serão
executadas na ordem que aparecem.
– Seleção – Se-Então/Senão
• Define uma estrutura condicional que dada a sua
avaliação (V ou F) determina qual “caminho” do
algoritmo será executado
– Repetição – Repita, Enquanto ou Para
• Define uma estrutura de iteração condicional (V ou
F) ou contada (pré-definida) de instruções
Lógica de Programação &
Algoritmo
•
Algoritmo para ligar de um telefone público - Seqüência
Início
1. Tirar o fone do gancho;
2. Ouvir o sinal de linha;
3. Introduzir o cartão;
4. Teclar o número desejado;
5. Conversar;
6. Desligar;
7. Retirar o cartão;
Fim.
Este algoritmo só usa uma
estrutura de seqüência
“Início/Fim”
Lógica de Programação & Algoritmo
• Algoritmo para ligar de um telefone
público – Seleção
E se o telefone público estiver com defeito?
Início
1. Tirar o fone do gancho;
2. Se ouvir o sinal de linha, então
Este algoritmo usa uma
1. Introduzir o cartão;
estrutura de decisão
2. Teclar o número desejado;
“Se-então/Senão”
3. Conversar;
4. Desligar;
5. Retirar o cartão;
3. Senão
1. ir para o próximo telefone;
Fim.
Lógica de Programação & Algoritmo
•
Algoritmo para ligar de um telefone público – Repetição
E se o próximo telefone público também estiver com defeito?
Início
1. Repita
1. Tirar o fone do gancho;
2. Se ouvir o sinal de linha então
1. Introduzir o cartão;
2. Teclar o número desejado;
Este algoritmo usa uma
3. Conversar;
estrutura de repetição
4. Desligar;
5. Retirar o cartão;
“Repita/Até”
3. Senão
1. ir para o próximo telefone;
2. Até ouvir o sinal de linha
Fim.
Lógica de Programação & Algoritmo
•
Algoritmo para ligar de um telefone público – Repetição
•
E se o telefone chamado estiver com defeito?
•
E se o telefone chamado estiver ocupado?
•
E se acabarem os créditos do cartão telefônico?
•
E se ...?
Um algoritmo
SEMPRE sofre melhorias sucessivas.
(Técnica de refinamentos sucessivos)
Fluxogramas - Exemplo 1
• Achar o valor da expressão: D = B2 - 4AC.
Início
Ler A, B, C
1
D = B^2 - 4*A*C
1
Escrever D
Fim
Fluxogramas:
Exemplo 2
• Achar o maior de
dois números A e
B.
Início
Ler A, B
Comparar
A com B
A=B
Escrever:
“A e B iguais”
A>B
Escrever:
“A é maior”
Fim
A<B
Escrever:
“B é maior”
Português Estruturado - Exemplo 1
• Achar o valor da expressão: D = B2 - 4AC.
Ler os valores de A, B e C
Calcular a expressão D = B2 - 4AC
Mostrar o resultado desse cálculo
Português Estruturado - Exemplo 2
• Achar o maior de dois números A e B.
Ler dois números A e B
Comparar A com B
Mostrar o resultado dessa comparação
Pseudocódigo - Exemplo 1
• Achar o valor da expressão: D = B2 - 4AC.
Início
Declare A,B,C,D; { Declaração de variáveis }
Leia(A,B,C);
D
B^2 - 4*A*C; { Operação de atribuição }
Escreva(D);
Fim.
Pseudocódigo - Exemplo 2
• Achar o maior de dois números A e B.
Início
Declare A,B; { Declaração de variáveis }
Leia(A,B);
Se A = B Então Escreva(“A e B iguais”);
Senão Se A>B Então Escreva(“A é maior”);
Senão Escreva(“B é maior”);
Fim-Se
Fim-Se
Fim.
Atividade 3
• Reescreva corretamente o algoritmo
abaixo
•
Algoritmo aprovação
Início
1. Obter as 2 notas do aluno;
2. Repita
1. Se Média do aluno >=7, então
1. Repita
1. Informar que o aluno está REPROVADO;
2. Até Média < 7
2. Senão Média >= 7
1. Informar que o aluno está APROVADO;
3. Até último aluno;
Fim.
RESPOSTA - Atividade 3
•
Algoritmo aprovação
Início
1. Repita
1. Obter as 2 notas do aluno;
2. Se Média do aluno >=7, então
1. Informar que o aluno está APROVADO
3. Senão
1. Informar que o aluno está REPROVADO;
2. Até último aluno
Fim
•
#! /usr/bin/perl -w
•
my $file = $ARGV[0];
•
open NEW, $file;
•
•
•
my $numero_g=0;
my $numero_c=0;
my $numero_total=0;
•
my $um=0;
•
•
•
•
•
•
•
•
while (<NEW>) {
if (/\>/) {
#
if ($um == 2) {
#
last;
#
}
#
$um++;
next;
}
•
#
print $_;
•
chomp;
•
•
•
•
•
•
•
•
•
•
for ($i=0; $i<length($_); $i++) {
$numero_total++;
if (uc(substr($_,$i,1)) eq "C" ) {
$numero_c++;
}
if (uc(substr($_,$i,1)) eq "G") {
$numero_g++;
}
}
}
UM EXERCÍCIO
• Construa um algoritmo para escolher as
duas maiores laranjas de um balaio
Outros exercícios...
1) leia um número inteiro e mostre uma mensagem indicando se
este número é par ou ímpar, e se é positivo ou negativo
2) leia quatro números inteiros e encontre a média aritmética
simples entre as que correspondem a números pares. Lembrese que não pode haver divisão por zero
3) leia 4 notas, calcule a média dessas e escreva: Reprovado
(média < 5), Recuperação (média >= 5 e < 7) e Aprovado
(média >= 7)
mais exercícios...
4)
leia a idade de um nadador e exiba sua categoria segundo as
regras: A(5 até 7); B(8 até 10); C(11 até 13); D(14 até 18) e E(
Idade > 18)
5) leia dois números inteiros, uma operação matemática
(+,-,*,/) e faça o calculo destes números segundo a operação
lida
6) leia o nome e a idade de três pessoas e informe o nome da
pessoa mais velha e o nome da pessoa mais nova. Considere
que não existem idades iguais
ainda mais exercícios...
7)
leia os números inteiros A e B e informe se A é múltiplo, divisor
ou nada de B
8) leia três números e mostre-os em ordem crescente
9) leia uma milhar e informe se esse número é palíndromo.
Exemplos de números palíndromos: 9889, 7337 e 2002
10) leia um número inteiro entre 20 e 59 e mostre seu extenso.
Exiba um erro se o número estiver fora do intervalo
AMBIENTES/LINGUAGENS DE
PROGRAMAÇÃO
LA
PASCAL
declare
Var
Início
Begin
Fim
End
Caracter
Char
Inteiro
Integer
Real
Real
Lógico
Boolean
Leia
Read
Escreva
Write
AMBIENTES/LINGUAGENS DE
PROGRAMAÇÃO
LA
C
declare
Início
{
Fim
}
Caracter
Char
Inteiro
Int
Real
Double
Lógico
Boolean
Leia
Scanf
Escreva
Printf
Próximos passos?
• Praticar a leitura e entendimento de
Algoritmos de sua área de aplicação
• Aprender uma Linguagem de
Programação para Computadores
• Programação!