742189_pc1_slides_02

Prévia do material em texto

Pontif´ıcia Universidade Cato´lica de Minas Gerais
Instituto de Cieˆncias Exatas e Informa´tica
Instituto Polite´cnico
Programac¸a˜o de Computadores I
Prof. Joa˜o Leonardo Ribeiro Neto
12 de Fevereiro de 2014
Algoritmo - conceituac¸a˜o
• Quando escrevemos um programa para ser executado por um
computador, concebemos pre´viamente um me´todo para
solucionar um determinado problema. Este me´todo,
geralmente independe de um computador e/ou de uma
linguagem de programac¸a˜o em particular. Este me´todo, mais
do que uma linguagem de programac¸a˜o em particular e´ que
sera´ o nosso objeto de estudo.
• O algoritmo, e´ utilizado em Programac¸a˜o de Computadores,
para descrever um me´todo capaz de solucionar um
determinado problema e que seja adequado para ser
implementado utilizando uma linguagem de programac¸a˜o.
Algoritmo - conceituac¸a˜o
• Na maioria dos algoritmos e´ tambe´m importante considerar a
organizac¸a˜o dos dados envolvidos, o que os torna tambe´m um
item fundamental na programac¸a˜o de computadores.
• Podemos enta˜o adotar a seguinte definic¸a˜o de algoritmo:
Algoritmo e´ a descric¸a˜o de um conjunto de comandos
que, obedecidos, resultam numa sucessa˜o finita de
ac¸o˜es.[Farrer et al. (1999)]
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
• Constantes: um determinado valor fixo que na˜o se modifica
ao longo do tempo:
• Constante nume´rica: 25; 3.14,...
• Constante lo´gica: falso ou verdadeiro
• Constante literal: “Joa˜o da Silva”, “Mensagem”,
“10/02/2014”, ...
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
• Exerc´ıcio
• Identificar o tipo de cada uma das constantes abaixo:
1 21;
2 “BOLA”;
3 “VERDADEIRO”;
4 0.21 × 102;
5 falso.
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
• Varia´veis na matema´tica: e´ a representac¸a˜o simbo´lica dos
elementos de um certo conjunto;
• Varia´veis nos algoritmos, destinados a resolver um problema
no computador: corresponde a uma posic¸a˜o de memo´ria, cujo
conteu´do pode variar ao longo do tempo durante a execuc¸a˜o
de um programa.[Farrer et al. (1999)]
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
• Formac¸a˜o dos identificadores:
• Permitidos: A, NOTA, X5, MATR´ICULA, A32B,....
• Na˜o permitidos: 5B, X-Y, E(13), A:B, B*D, ...
• Declarac¸a˜o de varia´veis: As varia´veis podem armazenar
valores de um mesmo tipo, de maneira que tambe´m sa˜o
classificadas como sendo nume´ricas, lo´gicas e literais;
• declare lista-de-identificadores nome-do-tipo
• Exemplos:
• declare NOTA, CO´DIGO, X5 nume´rico
• declare TESTE lo´gico
• declare NOME literal
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
• Os identificadores sa˜o escritos sempre com letra maiu´scula,
enquanto as palavras chaves sa˜o escritas em letra minu´scula
e grifadas;
• Denomina-se palavra-chave aquela que tem significado
pro´prio, independente do algoritmo em que esteja inserida.
Portanto na˜o podem ser utilizadas como identificadores, que
por sua vez identificam uma posic¸a˜o de memo´ria.
Figura : 1
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
Comenta´rios: Facilitar o entendimento do algoritmo:
declare MAT, {nu´mero de matr´ıcula do aluno}
nume´rico
Expresso˜es aritme´ticas:
Os operadores sa˜o aritme´ticos e operandos sa˜o constantes e/ou
varia´veis do tipo nume´rico. A notac¸a˜o utilizada para expresso˜es
aritme´ticas nos algoritmos e´, basicamente, a mesma da
matema´tica, a menos das seguintes restric¸o˜es:
• omitir o operador de multiplicac¸a˜o, o que e´ comum nas
expresso˜es matema´ticas. Evitar confusa˜o quanto ao nome de
varia´veis;
• nas expresso˜es aritme´ticas, as operac¸o˜es guardam entre si
uma relac¸a˜o de prioridade, tal como na matema´tica. Para se
obter uma sequeˆncia de ca´lculo diferente utilizar somente
pareˆnteses.
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
Exemplos:
X + Y
X - Y
Z × NOTA
TOTAL/N√
F1 + G 2 - H√
P × (P − A)× (P − B)× (P − C )
A-B×(C + D/(E-1)-F)+G
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
Func¸o˜es:
LOG10(EA) - logaritmo na base 10 de EA
LN(EA) - logaritmo neperiano de EA
EXP(EA) - o nu´mero e(base de LN) elevado a EA
ABS(EA) - valor absoluto de EA
TRUNCA(EA) - a parte inteira de um nu´mero fraciona´rio
ARREDONDA(EA) - transforma , por arredondamento, um
nu´mero fraciona´rio em inteiro
QUOCIENTE(EAX, EAY) - quociente da divisa˜o de EAX por EAY
RESTO(EAX, EAY) - resto da divisa˜o de EAX por EAY
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
= igual a < menor que
6= diferente de ≥ maior ou igual a
> maior que ≤ menor ou igual a
Tabela : Operadores relacionais
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
X Y Z NOME X 2+Y>Z NOME6=”JOSE´”
1 2 5 “PAULO” falso verdadeiro
4 3 1 “JOSE´” verdadeiro falso
1 1 2 “PEDRO” falso verdadeiro
Tabela : Expresso˜es lo´gicas
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
Dadas as varia´veis nume´ricas A e B, a varia´vel literal NOME,
completar o quadro a seguir, preenchendo os espac¸os em branco
com os resultados lo´gicos(falso ou verdadeiro) obtidos como
resultado das relac¸o˜es, tendo em vista os valores atribu´ıdos a estas
varia´veis.
A B NOME A+1≥ √B NOME 6=”ANA”
3 16 “MARIA”
5 64 “PEDRO”
2.5 9 “ANA”
Tabela : Expresso˜es lo´gicas
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
Operadores lo´gicos: A algebra das proposic¸o˜es define treˆs
conectivos usados na formac¸a˜o de novas proposic¸o˜es a partir de
outras ja´ conhecidas.
e - para a conjunc¸a˜o
ou - para a disjunc¸a˜o
na˜o - para a negac¸a˜o
Neste contexto considera-se uma proposic¸a˜o como sendo uma
varia´vel, uma relac¸a˜o ou uma expressa˜o lo´gica composta.
Conjunc¸a˜o das proposic¸o˜es p e q
p e q
Disjunc¸a˜o das proposic¸o˜es p e q
p ou q
Negac¸a˜o da proposic¸a˜o p
na˜o p
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
p q p e q p ou q na˜o p na˜o q
V V V V F F
V F F V F V
F V F V V F
F F F F V V
Tabela : Expresso˜es lo´gicas
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
Exerc´ıcio:
Considerando A, B, e C varia´veis nume´ricas, contendo os valores 1,
4.5 e 8, respectivamente; NOME e COR varia´veis literais contendo
as sequeˆncias de caracteres “TANIA” e “BRANCO” e TESTE
varia´vel lo´gica contendo o valor verdadeiro, determinar os
resultados obtidos da avaliac¸a˜o das seguintes expresso˜es lo´gicas:
1 A=1 e TESTE
2 NOME = “PEDRO” ou COR 6= “BRANCO”
3 na˜o TESTE ou RESTO(C,2) = 1
4 C < 10 ou TESTE e COR = “PRETO”
5 A2 + C 1/3=3 e (A+TRUNCA(B+C)>13 ou NOME=”ANA”
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
Comando : Pode ser descrito como uma ac¸a˜o a ser executada em
um dado momento.
Comando de atribuic¸a˜o:
identificador ← expressa˜o
onde:
identificador: e´ o nome da varia´vel a` qual esta´ sendo atribu´ıdo o
valor;
←: e´ o s´ımbolo de atribuic¸a˜o;
expressa˜o: pode ser uma expressa˜o aritme´tica, expressa˜o lo´gica ou
expressa˜o literal de cuja avaliac¸a˜o e´ obtido o valor a ser atribu´ıdo a`
varia´vel.
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
Exemplos:
1 K ← 1
2 COR ← “VERDE”
3 TESTE ← falso
4 A ← B
5 ME´DIA ← SOMA/N
6 COD ← N2 + 1 ≥ 5
7 SIM ← X = 0 e Y 6= 2
8 TOTAL ← √N + X 2+Y
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
Comandosde entrada e sa´ıda:
Seja a seguinte situac¸a˜o: ı´nicio da execuc¸a˜o de um programa que
se encontra armazenado na memo´ria principal do computador.
Como e quem determina o momento da entrada dos dados para o
programa e a sa´ıda dos resultados obtidos?
Isto e´ tarefa do programador e ele assim o faz quando, no
desenvolvimento do algoritmo, descreve as ac¸o˜es a serem
executadas pelo computador.
leia lista-de-identificadores
escreva lista-de-identificadores e/ou constantes
Exemplos:
• leia X
• leia NOME,N,Y
• escreva K, SOMA
• escreva 21, “NOME”, N
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
Estrutura sequencial:
Num algoritmo aparece em primeiro lugar as declarac¸o˜es seguidas
por comandos que, se na˜o houver indicac¸a˜o em contra´rio, devera˜o
ser executados numa sequeˆncia linear, seguindo-se o texto em que
esta˜o escritos, de cima para baixo. Iniciaremos os algoritmos com a
palavra Algoritmo e terminaremos com a expressa˜o fim algoritmo.
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
Estrutura sequencial:
Figura : 2
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
Estrutura sequencial:
Figura : 3
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
Estrutura condicional: A estrutura condicional permite a escolha
do grupo de ac¸o˜es e estruturas a ser executado quando
determinadas condic¸o˜es, representadas por expresso˜es lo´gicas, sa˜o
ou na˜o satisfeitas.
Estrutura condicional simples:
Figura : 4
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
Estrutura condicional simples:
Figura : 5
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
Estrutura condicional composta
Figura : 6
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
Estrutura condicional composta
Figura : 7
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
Fazer um algoritmo que leia treˆs valores inteiros, determine e
imprima o menor deles
No exemplo seguinte, sera´ usada a te´cnica de refinamentos
sucessivos.
Figura : 8
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
Figura : 9
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
Figura : 10
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
Figura : 11
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
Exerc´ıcios:
1) Dados treˆs valores X,Y,Z, verificar se eles podem ser os
comprimentos dos lados de triaˆngulo e, se forem, verificar se e´ um
triaˆngulo equila´tero, iso´sceles ou escaleno. Se eles na˜o formarem
um triaˆngulo escrever uma mensagem.
2) Dados treˆs valores distintos, coloca´-los em ordem crescente.
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
Estrutura de repetic¸a˜o: A estrutura de repetic¸a˜o permite que
uma sequeˆncia de comandos seja executada repetidamente ate´ que
uma determinada condic¸a˜o de interrupc¸a˜o seja satisfeita.
Figura : 12
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
Estrutura de repetic¸a˜o:
Figura : 13
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
Estrutura de repetic¸a˜o:
Figura : 14
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
Estrutura de repetic¸a˜o:
Figura : 15
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
Estrutura de repetic¸a˜o:
Figura : 16
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
Estrutura de repetic¸a˜o:
Figura : 17
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
Exerc´ıcios:
3) Fazer um algoritmo que calcula o valor de N!(fatorial de N),
sendo que o valor inteiro de N encontra-se dispon´ıvel em uma
unidade de entrada de dados e que
a) N! = 1 x 2 x 3 x . . . x (N-1) x N;
b) 0! = 1, por definic¸a˜o.
4) A conversa˜o de graus Farenheit para cent´ıgrados e´ obtida por
C =
5
9
(F − 32)
Fazer um algoritmo que calcule e escreva uma tabela de
cent´ıgrados em func¸a˜o de Farenheit, que variem de 50 a 150 de 1
em 1.
Conjunto particular de regras e convenc¸o˜es
para o desenvolvimento de um algoritmo
Exerc´ıcios:
5) Desenvolver um algoritmo que verifique e escreva todos os
valores inteiros no intervalo de 0 a 1000 que tenham, ao mesmo
tempo, as seguintes caracter´ısticas:
• A soma de seus algarismos maior ou igual a 13;
• Contenha o algarismo 0(zero);
• Seja ı´mpar.
6)Desenvolva um algoritmo para ler um nu´mero inteiro e exibir o
maior nu´mero primo que seja menor do que o nu´mero digitado.
7) Desenvolva um algoritmo que solicite ao usua´rio treˆs nu´meros
a,b e c , onde a e´ maior do que 1. Seu algoritmo deve somar todos
os inteiros entre b e c que sejam divis´ıveis por a. Escreva a soma.
Bibliografia
Farrer, H., Becker, C., Faria, E., Matos, H., Santos, M., & Maia,
M. L. (1999). Algoritmos estruturados. LTC - Livros Te´cnicos e
Cient´ıficos Editora S.A.