Aula 02 15ago2017

Prévia do material em texto

Algoritmos e Programac¸a˜o Computacional
Aula 02 - 15/agosto/2017
Wilson H. Hirota
Universidade Federal de Sa˜o Paulo
wilson.hirota@gmail.com
Algoritmos e Lo´gica de Programac¸a˜o
• Convenc¸o˜es para as expresso˜es: Operac¸o˜es relacionais
◦ As operac¸o˜es relacionais permitem efetuar comparac¸o˜es entre duas
varia´veis. Essas operac¸o˜es sa˜o largamente utilizadas em
estruturas condicionais e de repetic¸a˜o
◦ Ja´ que essas operac¸o˜es dependem de teste de valores e, todo resultado
de um teste so´ pode ser VERDADEIRO ou FALSO, seu
resultado e´ um valor booleano
Operador Significado Operador Significado
= igualdade ≥ maior ou igual
6= diferente < menor
> maior ≤ menor ou igual
2 / 30
Algoritmos e Lo´gica de Programac¸a˜o
• Convenc¸o˜es para as expresso˜es: Operac¸o˜es lo´gicas
◦ Sa˜o operac¸o˜es efetuadas com os valores booleanos (verdadeiro ou
falso), resultando em valores booleanos
◦ Essas operac¸o˜es sa˜o largamente utilizadas em estruturas
condicionais e em estruturas de repetic¸a˜o, ja´ que essas
estruturas dependem de teste de valores
◦ Os operadores lo´gicos teˆm a func¸a˜o de adve´rbio na linguagem de
programac¸a˜o. Cada operador lo´gico tem a sua ”tabela
verdade”composta por: E, OU e NA˜O
◦ O operador na˜o representa a negac¸a˜o do valor booleano. O operador e
realiza o teste simultaˆneo de duas condic¸o˜es (resulta o valor verdadeiro
somente quando ambos operando sa˜o verdadeiros. Ja´ para o operador
ou, basta que uma das condic¸o˜es seja verdadeiro, para que o resultado
seja verdadeiro
3 / 30
Algoritmos e Lo´gica de Programac¸a˜o
• Convenc¸o˜es para as expresso˜es: Operac¸o˜es lo´gicas
Operador lo´gico 1o operando 2o operando Resultado Simbologia
Na˜o
V Na˜o aplica´vel F
z ← na˜o x
F Na˜o aplica´vel V
E
V V V
z ← x e yV F F
F V F
F F F
OU
V V V
z ← x ou yV F V
F V V
F F F
• Exemplo: Assim, considerando-se as seguintes varia´veis com valores iniciais
indicados, x = 3, y = 7, z = −1, a expressa˜o
na˜o ((z > 0) e ((y − x) > 2))
e´ verdadeira, resultando a operac¸a˜o e aplicado nessas expresso˜es em falso. Por fim,
o resultado na˜o(falso) fornece seu inverso lo´gico, ou seja, verdadeiro
4 / 30
Algoritmos e Lo´gica de Programac¸a˜o
• Comandos de entrada e sa´ıda
◦ As linguagens de programac¸a˜o esta˜o preparadas para receber entradas
e apresentar sa´ıdas
◦ Desta forma, durante a execuc¸a˜o de um programa, um usua´rio podera´
informar valores (entrada) para que estes sejam processados pelo
computador, que, por sua vez, retornara´ o resultado do processamento
(sa´ıda)
◦ A entrada e´ o meio pelo qual o usua´rio pode informar dados que sera˜o
utilizados pelo programa em seu processamento. Desta forma, na˜o
havera´ necessidade de adaptac¸a˜o do co´digo para atender a` maioria das
demandas particulares do usua´rio
◦ A entrada e´ feita pelo comando:
ler(<varia´vel>);
5 / 30
Algoritmos e Lo´gica de Programac¸a˜o
• Comandos de entrada e sa´ıda
◦ Para que o usua´rio possa ter acesso aos resultados do processamento do
programa, toda linguagem de programac¸a˜o fornece mecanismos de
apresentac¸a˜o (sa´ıda) dos dados
◦ A sa´ıda e´ feito pelo comando:
escrever(<varia´vel>);
◦ O valor a ser escrito na tela do monitor pode ser um texto (nesse caso,
entre aspas duplas) ou o conteu´do de uma varia´vel e/ou constante. A
sa´ıda pode intercalar textos com varia´veis, separando-os com v´ırgulas
◦ Exemplos:
1. escrever(”O resultado eh: ”, variavel1);
2. escrever(”O valor”, variavel1, ”eh o resultado final”);
6 / 30
Algoritmos e Lo´gica de Programac¸a˜o
• Estruturas de Programac¸a˜o: Estruturas de decisa˜o
◦ Sa˜o estruturas que permitem a tomada de uma decisa˜o sobre qual o
caminho a ser escolhido, de acordo com o resultado de uma expressa˜o
lo´gica.
◦ Existem treˆs formas ba´sicas desse tipo de estrutura:
• se-enta˜o (estrutura condicional simples),
• se-enta˜o-sena˜o (estrutura condicional composta)
• caso (estrutura de mu´ltipla escolha)
7 / 30
Algoritmos e Lo´gica de Programac¸a˜o
• Estruturas de Programac¸a˜o: Estruturas de decisa˜o
◦ se-enta˜o
Pseudoco´digo
se <condic¸a˜o> enta˜o
<comandos>;
fim
Fluxograma
condic¸a˜o comandos
V
F
• Essa estrutura e´ representada por um comando que avalia uma condic¸a˜o
lo´gica, resultando um valor que pode ser verdadeiro ou falso
• Como consequeˆncia desse resultado, o processamento seguira´ por um de
dois caminhos: se o resultado for verdadeiro, sera˜o executados os
comandos encontrados no caminho indicado por V; caso contra´rio, nenhum
comando sera´ executado
8 / 30
Algoritmos e Lo´gica de Programac¸a˜o
• Estruturas de Programac¸a˜o: Estruturas de decisa˜o
◦ se-enta˜o-sena˜o
Pseudoco´digo
se <condic¸a˜o> enta˜o
<comandos A>
sena˜o
<comandos B>
fim
• Se o resultado da condic¸a˜o lo´gica for
verdadeiro, sera˜o executados os
comandos encontrados no caminho
indicado por V
• Caso contra´rio, sera˜o executados os
comandos encontrados no caminho
indicado por F
Fluxograma
condic¸a˜o <comandos A>
<comandos B>
V
F
9 / 30
Algoritmos e Lo´gica de Programac¸a˜o
• Estruturas de Programac¸a˜o: Estruturas de decisa˜o
◦ estrutura caso (ou estrutura de mu´ltipla escolha)
Pseudoco´digo
selecione varia´vel fac¸a
caso valor1 fac¸a
<comandos 1>;
fim
caso valor2 fac¸a
<comandos 2>;
fim
caso valor3 fac¸a
<comandos 3>;
fim
. . .
sena˜o
<comandos n>;
fim
fim
• A estrutura caso possibilita escolher mais de um
caminho, de acordo com o valor de uma varia´vel
• Nessa estrutura na˜o se avalia uma condic¸a˜o lo´gica, e,
sim, uma varia´vel, cujo resultado nume´rico vai
determinar o caminho a ser seguido
• Se o valor armazenado na varia´vel for igual a valor1, o
programa executara´ um conjunto de um ou mais
comandos representados por <comandos 1>. Se for
igual a valor2, vai executar um conjunto de um ou mais
comandos representados por <comandos 2> e assim por
diante
• Se o valor da varia´vel na˜o for igual a nenhum dos valores
predefinidos (os diferentes casos), podemos definir um
caminho-padra˜o (opc¸a˜o sena˜o) que sera´ executado, caso
nenhuma das alternativas anteriores sejam atendidas
10 / 30
Algoritmos e Lo´gica de Programac¸a˜o
• Estruturas de Programac¸a˜o: Estruturas de decisa˜o
◦ Exemplo 2: Fac¸a um algoritmo que leia um nu´mero inteiro diferente de
zero e diga se este e´ par ou ı´mpar
Algoritmo 1: par ou ı´mpar
Entrada: num
Sa´ıda: se num e´ par ou impar
1 in´ıcio
2 declare num, resto: inteiro;
3 escrever(”Digite um inteiro diferente
de zero:”);
4 ler(num);
5 resto ← num mod 2;
6 se resto = 0 enta˜o
7 escrever(”Eh par”);
8 sena˜o
9 escrever(”Eh impar”);
10 fim
11 fim
inicio
num
resto ← num mod 2
resto = 0 Escrever e´ par
Escrever e´ impar fim
S
N
11 / 30
Algoritmos e Lo´gica de Programac¸a˜o
• Estruturas de Programac¸a˜o: Estruturas de decisa˜o
Algoritmo 2: maior valor
Entrada: num1, num2, num3
Sa´ıda: o maior valor de treˆs valores informados
1 in´ıcio
2 declare num1, num2, num3: inteiro;
3 escrever(”Digite treˆs nu´meros inteiros”);
4 ler(num1,num2,num3);
5 se num1 > num2 e num1 > num3 enta˜o
6 escrever(”O numero maior eh: ”, num1);
7 sena˜o
8 se num2 > num1 e num2 > num3 enta˜o
9 escrever(”O numero maior eh: ”, num2);
10 sena˜o
11 escrever(”O numero maior eh: ”, num3);
12 fim
13 fim
14 fim
Exemplo 3: Fac¸a um
algoritmo que leia treˆs
nu´meros inteiros e
determine qual dos treˆs
e´ maior. Considere que
os treˆs nu´meros sera˜o
diferentes.
No algoritmo ao lado
temos duas estruturas
de decisa˜o encadeadas
(ou aninhadas). A fim
de evitar ambiguidades
e facilitar a leitura e´ re-
comenda´vel indentar o
co´digo.
12 / 30
Algoritmos e Lo´gica de Programac¸a˜o
• Estruturas de Programac¸a˜o: Estruturasde repetic¸a˜o
◦ No mundo real, e´ comum a repetic¸a˜o de procedimentos para se realizar
tarefas. Esses procedimentos na˜o sa˜o repetidos eternamente, mas se
encerram quando o objetivo e´ atingido
◦ Todas as repetic¸o˜es teˆm uma caracter´ıstica comum: o fato de haver
uma verificac¸a˜o de condic¸a˜o que pode ser representada por um
valor lo´gico, para determinar se a repetic¸a˜o prossegue ou na˜o
◦ As estruturas de repetic¸a˜o sa˜o estruturas que permitem a repetic¸a˜o
controlada de comandos. Existem treˆs formas ba´sicas desse tipo de
estrutura:
• PARA-ATE´-FAC¸A
• ENQUANTO-FAC¸A
• REPITA-ATE´
13 / 30
Algoritmos e Lo´gica de Programac¸a˜o
• Estruturas de Programac¸a˜o: Estruturas de repetic¸a˜o
◦ enquanto-fac¸a
Pseudoco´digo
enquanto <condic¸a˜o> fac¸a
<comandos>
fim
• A estrutura enquanto-fac¸a permite a
execuc¸a˜o repetitiva de comandos
enquanto a condic¸a˜o lo´gica for
verdadeira. Quando for falso,
segue-se para algum outro comando
fora da repetic¸a˜o
• Cada execuc¸a˜o do bloco de instruc¸o˜es e´
chamada iterac¸a˜o. O pro´prio
comando de repetic¸a˜o em conjunto com
seu bloco de instruc¸o˜es e´ conhecido
como lac¸o ou loop
Fluxograma
condic¸a˜o comandos
V
F
Erro comum
Na˜o fornecer no corpo da estrutura en-
quanto uma ac¸a˜o que eventualmente fara´
com que a condic¸a˜o lo´gica se torne falsa.
Normalmente, essa estrutura de repetic¸a˜o
nunca termina. Esse erro e´ chamado de
”loop”infinito
14 / 30
Algoritmos e Lo´gica de Programac¸a˜o
• Estruturas de Programac¸a˜o: Estruturas de repetic¸a˜o
◦ Exemplo 4: Fac¸a
um algoritmo que
leia uma sequeˆncia
de nu´meros reais
na˜o-nulos,
terminada por zero,
e retorna a soma dos
nu´meros positivos.
Simule a execuc¸a˜o
do algoritmo. Use
como entrada a
seguinte sequeˆncia:
100 2 3 -1 -7 0
Algoritmo 3: soma dos nu´meros positivos de uma sequeˆncia
Entrada: num
Sa´ıda: soma dos nu´meros positivos
1 in´ıcio
2 declare num, soma: real;
3 soma ← 0;
4 escrever(”Digite um numero:”);
5 ler(num);
6 enquanto num 6= 0 fac¸a
7 se num > 0 enta˜o
8 soma ← soma + num;
9 fim
10 escrever(”digite outro numero: ”);
11 ler(num);
12 fim
13 escrever(”soma dos positivos = ”, soma);
14 fim
15 / 30
Algoritmos e Lo´gica de Programac¸a˜o
• Exemplo 4: Simulac¸a˜o (Entrada: 100 2 3 -1 -7 0)
Comando num soma condic¸a˜o sa´ıda
soma ← 0 0
escrever(”Digite um
nu´mero”)
Digite um nu´mero
ler(num) 100
enquanto-fac¸a num 6= 0 (V)
se-enta˜o num > 0 (V)
soma ← soma + num 100
escrever(”digite outro
nu´mero”)
digite outro numero
ler(num) 2
enquanto-fac¸a num 6= 0 (V)
se-enta˜o num > 0 (V)
soma ← soma + num 102
escrever(”digite outro
nu´mero”)
digite outro numero
ler(num) 3
enquanto-fac¸a num 6= 0 (V)
se-enta˜o num > 0 (V)
soma ← soma + num 105
16 / 30
Algoritmos e Lo´gica de Programac¸a˜o
• Exemplo 4: Simulac¸a˜o (Entrada: 100 2 3 -1 -7 0)
Comando num soma condic¸a˜o sa´ıda
soma ← soma + num 105
escrever(”digite outro
nu´mero”)
digite outro numero
ler(num) -1
enquanto-fac¸a num 6= 0 (V)
se-enta˜o num > 0 (F)
escrever(”digite outro
nu´mero”)
digite outro numero
ler(num) -7
enquanto-fac¸a num 6= 0 (V)
se-enta˜o num > 0 (F)
textbfescrever(”digite outro
nu´mero”)
digite outro numero
ler(num) 0
enquanto-fac¸a num 6= 0 (F)
escrever(”Soma dos positi-
vos= ”)
Soma dos positivos
= 105
17 / 30
Algoritmos e Lo´gica de Programac¸a˜o
• Estruturas de Programac¸a˜o: Estruturas de repetic¸a˜o
◦ Exemplo 5: Escreva um algoritmo
que leia um nu´mero inteiro n e
retorna o valor do somato´rio
n∑
i=1
i.
Simule a execuc¸a˜o do algoritmo
para n = 3.
Algoritmo 4: Exemplo 5
Entrada: n
Sa´ıda: Soma dos n primeiros naturais
1 in´ıcio
2 declare n, cont, soma: inteiro;
3 soma ← 0;
4 cont ← 1;
5 escrever(”Digite um inteiro: ”);
6 ler(n);
7 enquanto cont ≤ n fac¸a
8 soma ← soma + cont;
9 cont ← cont + 1;
10 fim
11 escrever(”soma = ”, soma);
12 fim
18 / 30
Algoritmos e Lo´gica de Programac¸a˜o
• Exemplo 5: Simulac¸a˜o (Entrada: n = 3)
Comandos n cont soma condic¸a˜o sa´ıda
soma ← 0 0
cont ← 1 1
escrever(”Digite um inteiro) Digite um inteiro
ler(n) 3
enquanto-fac¸a cont ≤ n (V)
soma ← soma + cont 1
cont ← cont + 1 2
enquanto-fac¸a cont ≤ n (V)
soma ← soma + cont 3
cont ← cont + 1 3
19 / 30
Algoritmos e Lo´gica de Programac¸a˜o
• Exemplo 5: Simulac¸a˜o (Entrada: n = 3)
Comandos n cont soma condic¸a˜o sa´ıda
soma ← soma + cont 3
cont ← cont + 1 3
enquanto-fac¸a cont ≤ n (V)
soma ← soma + cont 6
cont ← cont + 1 4
enquanto-fac¸a cont ≤ n (F)
escrever(”soma = ”, soma) soma = 6
20 / 30
Algoritmos e Lo´gica de Programac¸a˜o
• Estruturas de Programac¸a˜o: Estruturas de repetic¸a˜o
◦ Repita-ate´
Pseudoco´digo
repita
<comandos>;
ate´ condic¸a˜o;
• A estrutura repita-ate´ possibilita a
execuc¸a˜o repetitiva de comandos
enquanto a condic¸a˜o lo´gica for falsa
• A estrutra repita-ate´ funciona de
forma similar ao comando
enquanto-fac¸a, exceto pelo fato de
que a condic¸a˜o lo´gica so´ e´ testada apo´s
a execuc¸a˜o do bloco de comandos, e
na˜o antes, como e´ o caso da estrutura
enquanto-fac¸a
Fluxograma
comandos
condic¸a˜o
VF
• Assim, podemos usar o comando
repita sempre que tivermos certeza de
que o bloco de comandos sera´
executado ao menos uma vez, sem a
necessidade do teste na entrada do
bloco.21 / 30
Algoritmos e Lo´gica de Programac¸a˜o
• Estruturas de Programac¸a˜o: Estruturas de repetic¸a˜o
◦ para-ate´-fac¸a
Pseudoco´digo
para contador ← valor inicial ate´ valor final fac¸a
<comandos>;
fim
• A estrutura para-fac¸a e´ usado quando
precisamos executar um bloco de comandos um
nu´mero fixo de vezes
• Possui uma varia´vel de controle chamada de
contador, que controla o nu´mero de vezes que
o lac¸o e´ executado
Fluxograma
cont ← vi
cont ≤ vf
comandos
cont ← cont + 1
F
V
22 / 30
Algoritmos e Lo´gica de Programac¸a˜o
• Estruturas de Programac¸a˜o: Estruturas de repetic¸a˜o
◦ para-ate´-fac¸a
para contador ← valor inicial ate´ valor final
fac¸a
<comandos>;
fim
• A estrutura para-fac¸a e´ equivalente a` seguinte
estrutura:
contador ← valor inicial;
enquanto contador ≤ valor final fac¸a
<comandos>;
contador ← contador + 1;
fim
• A estrutura para-fac¸a e´ um
caso particular da estrutura
enquanto-fac¸a. E´ particular,
pois implementa uma
estrutura enquanto-fac¸a que
vai repetir os comandos,
utilizando-se de um contador
que possui um certo valor
inicial e que, por meio de
incrementos /
decrementos unita´rios e
inteiros, vai alcanc¸ar um valor
final predefinido
23 / 30
Algoritmos e Lo´gica de Programac¸a˜o
• Estruturas de Programac¸a˜o: Estruturas de repetic¸a˜o
◦ Exemplo 6: Escreva um algoritmo
que leia um nu´mero inteiro n e
retorna o valor do somato´rio
n∑
i=1
i.
Algoritmo 5: Adaptac¸a˜o do Exemplo 5:
estrutura para-fac¸a
Entrada: n
Sa´ıda: Soma dos n primeiros naturais
1 in´ıcio
2 declare n, cont, soma: inteiro;
3 soma ← 0;
4 escrever(”Digite um inteiro: ”);
5 ler(n);
6 para cont ← 1 ate´ n fac¸a
7 soma ← soma + cont;
8 fim
9 escrever(”soma = ”, soma);
10 fim
24 / 30
Algoritmos e Lo´gica de Programac¸a˜o
• Estruturas de Programac¸a˜o: Estruturas de repetic¸a˜o
◦ Exemplo 7: Escreva um algoritmo que leia um nu´mero inteiro n e calcule o
seu fatorial. Simule a execuc¸a˜o do algoritmo para n = 4.
Algoritmo 6: Incremento do contador
Entrada: n
Sa´ıda: Fatorial de n
1 in´ıcio
2 declare n, i, fat: inteiro;
3 fat ← 1;
4 ler(n);
5 se n = 0 enta˜o
6 escrever(”fatorial =”, fat);
7 sena˜o
8 para i ← 1 ate´ n fac¸a
9 fat ← fat*i;
10 fim
11 escrever(”fatorial =”, fat);
12 fim
13 fim
Algoritmo 7: Decremento do contador
Entrada: n
Sa´ıda: Fatorial de n
1 in´ıcio2 declare n, i, fat: inteiro;
3 fat ← 1;
4 ler(n);
5 se n = 0 enta˜o
6 escrever(”fatorial =”, fat);
7 sena˜o
8 para i ← n ate´ 1 fac¸a
9 fat ← fat*i;
10 fim
11 escrever(”fatorial =”, fat);
12 fim
13 fim
25 / 30
Algoritmos e Lo´gica de Programac¸a˜o
• Exemplo 7: Simulac¸a˜o (Entrada: n = 4)
Comandos n i fat condic¸a˜o sa´ıda
fat ← 1 1
ler(n) 4
se-sena˜o n = 0 (F)
para-fac¸a 1 i ≤ n (V)
fat ← fat*i 1
para-fac¸a 2 i ≤ n (V)
fat ← fat*i 2
para-fac¸a 3 i ≤ n (V)
fat ← fat*i 6
para-fac¸a 4 i ≤ n (V)
fat ← fat*i 24
para-fac¸a 5 i ≤ n (F)
escrever(”fatorial= ”, fat) fatorial = 24
26 / 30
Algoritmos e Lo´gica de Programac¸a˜o
Exerc´ıcios
• Exerc´ıcio 01: Dados treˆs nu´meros reais a, b e c, escreva uma algoritmo
que retorne as ra´ızes reais de uma equac¸a˜o de 2o grau da forma
ax2 + bx+ c = 0.
• Exerc´ıcio 02: Escreva um algoritmo que leia treˆs nu´meros inteiros e
determina quantos sa˜o iguais.
• Exerc´ıcio 03: Escreva um algoritmo que leia treˆs nu´meros inteiros
diferentes entre si e imprima os treˆs valores em ordem crescente
• Exerc´ıcio 04: Escreva um algoritmo que leia uma ano e informa se este e´
um ano bissexto ou na˜o. Para o ano ser bissexto basta que seja divis´ıvel por
400. Caso contra´rio, precisa ser divis´ıvel por 4 e na˜o ser divis´ıvel por 100.
Fac¸a uma condic¸a˜o composta que englobe todas as regras para a definic¸a˜o
do ano bissexto.
27 / 30
Algoritmos e Lo´gica de Programac¸a˜o
Exerc´ıcios
• Exerc´ıcio 05: Escreva um algoritmo que retorne a soma e o produto dos n
primeiros nu´meros naturais
• Exerc´ıcio 06: Os pontos (x,y) que pertencem a` regia˜o H sa˜o tais que
x ≥ 0, y ≥ 0 e x2 + y2 ≤ 1. Escreva um algoritmo que leia n pontos reais
(x,y) e informa se cada ponto pertence ou na˜o a` regia˜o H.
x
y
1
1
H
28 / 30
Algoritmos e Lo´gica de Programac¸a˜o
Exerc´ıcios
• Exerc´ıcio 07: Escreva um algoritmo que leia uma sequeˆncia de nu´meros
inteiros positivos e retorne o maior nu´mero digitado
• Exerc´ıcio 08: Escrever um algoritmo que leia um nu´mero inteiro e
determine se este e´ primo ou na˜o
• Exerc´ıcio 09: Escrever um algoritmo que leia um nu´mero natural e
informa se o nu´mero digitado e´ triangular. Na matema´tica dizemos que um
nu´mero e´ triangular se ele for igual ao produto de treˆs nu´meros naturais
consecutivos. Exemplo:
24 e´ triangular, pois 24 = 2× 3× 4
120 e´ triangular, pois 120 = 4× 5× 6
29 / 30
Algoritmos e Lo´gica de Programac¸a˜o
Exerc´ıcios
• Exerc´ıcio 10: Escrever um algoritmo que leia um nu´mero bina´rio e
converta para a base decimal. Exemplo: se a entrada for 10010 a sa´ıda sera´
18, pois
1× 24 + 0× 23 + 0× 22 + 1× 21 + 0× 20 = 18
• Exerc´ıcio 11: Escrever um algoritmo que leia um nu´mero natural maior
que 1 e retorne a sua decomposic¸a˜o em fatores primos
30 / 30