1  

INF 1005 Programação I - Prof. Hélio Lopes 8/7/12

   

Algoritmos e Pseudocódigo

1

INF1005 – Programação I

Prof. Hélio Lopes

lopes@inf.puc-rio.br

sala 408 RDC

algoritmos e pseudocódigo

tópicos algoritmo – definições

representação e resolução de problemas

representação de programa

pseudocódigo

fluxograma

construções

entrada e saída

condicionais

repetições

2

2  

INF 1005 Programação I - Prof. Hélio Lopes 8/7/12

algoritmos

3

algoritmo - definições

especificação precisa (não ambígua) de um comportamento que visa resolver um problema bem

definido

sequência finita de instruções precisas que podem ser executadas mecanicamente num período de tempo

finito e com uma quantidade de esforço finito

programa de computador algoritmo codificado em uma linguagem de programação

4

3  

INF 1005 Programação I - Prof. Hélio Lopes 8/7/12

algoritmo - definições

especificação precisa (não ambígua) de um comportamento que visa resolver um problema bem

definido

Uma receita culinária é um algoritmo?   "sal a gosto" vs. "1/4 colher (chá) de sal"

  "bata bem" vs.

"bata até a massa ficar homogênea"

  "forno médio" vs. "forno a 220°C"

5

algoritmo – definições

especificação precisa (não ambígua) de um comportamento que visa resolver um problema bem

definido

condições iniciais (estado de problema)   como as coisas são

objetivos (estado desejado)   como as coisas deveriam ser

recursos   meios ou métodos para transformar um estado de problema

desde as condições iniciais até os objetivos

ex: movimentos possíveis em um jogo 6

4  

INF 1005 Programação I - Prof. Hélio Lopes 8/7/12

exemplo

Escreva um algoritmo com objetivo de matar a fome “na rua”

1.  ______________________________________________  

2.  ______________________________________________  

3.  ______________________________________________  

4.  ______________________________________________  

5.  ______________________________________________  

6.  ______________________________________________  

EX. 01

algoritmo pessoa com fome pessoa sem fome

7

exemplo – isto é um algoritmo?

objetivo: matar a fome “na rua”

1.  decidir onde comer, conforme tempo e dinheiro disponível

2.  ir até o local escolhido

3.  decidir o que comer, conforme cardápio, tempo e dinheiro disponível

4.  fazer o pedido

5.  pagar

6.  aguardar o pedido

7.  comer

8

5  

INF 1005 Programação I - Prof. Hélio Lopes 8/7/12

resolver o problema antes de programar Qual é a situação inicial? Já temos todos os dados de entrada?

Esses dados são específicos a uma única situação ou podemos generalizar?

Existe alguma notação para representar de forma sucinta os dados e os estados intermediários?

Qual é o objetivo? / Quais são os objetivos? Há um único objetivo, ou são vários?

Cada objetivo pode ser dividido em sub-objetivos, ou não?

Os (sub-)objetivos são independentes, ou não?

Há obstáculos a serem vencidos? Como podem ser vencidos?

Há restrições na elaboração da solução? (tempo, espaço em memória, custo)

Quais são os recursos (movimentos, operações, procedimentos, regras, transformações)?

Para cada recurso, há restrições ou pré-condições para sua aplicação?

Há outros recursos mais simples que satisfaçam essas pré-condições?

Quando você aplica um recurso, o que muda? (variantes)

Quando você aplica um recurso, o que permanece igual? (invariantes)

Há outros recursos mais poderosos para resolver esse problema?

adaptado de Blank & Barnes (1998) The Universal Machine. 9

exemplo – Como chegar ao destino?

Av.2 Av.3 Av.4

Rua 7

Rua 6

Rua 5

Rua 4

Av.1

10

6  

INF 1005 Programação I - Prof. Hélio Lopes 8/7/12

problemas e soluções

  um problema pode ter várias soluções

  algumas soluções são melhores do que outras

  um problema pode ter soluções parciais

  restrições no espaço de problema podem ajudar na

busca por uma solução

11

representação do espaço de problema

descrição do “mundo”: ruas: [4,7]

avenidas: [1,4]

convenções de representação: posição: (r,a)

obstáculo: (r1,a1,r2,a2)

condições iniciais: posição: (7,1)

obstáculos: { (6,2,7,2), (4,2,5,2), (5,3,6,3), (6,4,7,4) }

objetivo: posição: (4,3)

Av.2 Av.3 Av.4

Rua 7

Rua 6

Rua 5

Rua 4

Av.1

Quais as consequências dessa representação?

12

7  

INF 1005 Programação I - Prof. Hélio Lopes 8/7/12

algoritmo - exemplo

objetivo: verificar se um aluno está aprovado (média das 3 notas >= 5.0) ou reprovado (caso

contrário)

13

como representar um algoritmo

1.  Obter as três notas das provas do aluno

2.  Calcular a média aritmética das três notas

3.  Se a média for maior ou igual a 5, escrever “aprovado”

4.  Caso contrário, escrever “reprovado”

linguagem natural

variáveis media, nota1, nota2, nota3 início leia nota1, nota2, nota3 media = (nota1+nota2+nota3)/3 se (media >= 5) então

escreva “aluno aprovado” senão

escreva “aluno reprovado” fim-se fim

pseudocódigo

fluxograma

início

leia (nota1, nota2, nota3);

media ← (nota1+nota2+nota3)/3;

media >= 5.0?

escreva (“aprovado”);

fim

escreva (“reprovado”);

sim

não

14

8  

INF 1005 Programação I - Prof. Hélio Lopes 8/7/12

algoritmo em pseudocódigo

variáveis media, nota1, nota2, nota3

início

leia nota1, nota2, nota3

media = (nota1+nota2+nota3)/3

se (media >= 5) então

escreva “aluno aprovado”

senão

escreva “aluno reprovado”

fim-se

fim

15

algoritmo em pseudocódigo

variáveis media, nota1, nota2, nota3

início

leia nota1, nota2, nota3

media = (nota1+nota2+nota3)/3

se (media >= 5) então

escreva “aluno aprovado”

senão

escreva “aluno reprovado”

fim-se

fim

variáveis armazenam valores (dados, informações) necessários à solução do problema:

  dados de entrada: nota1, nota2, nota3

  dados utilizados no processamento: média

  dados de saída

16

9  

INF 1005 Programação I - Prof. Hélio Lopes 8/7/12

algoritmo – exemplo

objetivo: a partir de três notas de um aluno, verificar se ele está:

aprovado (média >= 5.0)

em prova final (média < 5.0 e média >= 3.0) ou

reprovado (média < 3)

17

sim

fluxograma (com defeito)

início

leia (nota1, nota2, nota3);

media ← (nota1+nota2+nota3)/3;

media >= 5.0?

escreva (“aprovado”);

fim

escreva (“reprovado”);

sim

não

escreva (“em prova final”);

media > 3.0?

não

objetivo: a partir de três notas de um aluno, verificar se ele está:

aprovado (média >= 5.0)

em prova final (média < 5.0 e média >= 3.0) ou

reprovado (média < 3)

18

10  

INF 1005 Programação I - Prof. Hélio Lopes 8/7/12

sim

fluxograma (com defeito)

início

leia (nota1, nota2, nota3);

media ← (nota1+nota2+nota3)/3;

media >= 5.0?

escreva (“aprovado”);

fim

escreva (“reprovado”);

sim

não

escreva (“em prova final”);

media > 3.0?

não

objetivo: a partir de três notas de um aluno, verificar se ele está:

aprovado (média >= 5.0)

em prova final (média < 5.0 e média >= 3.0) ou

reprovado (média < 3)

19

sim

fluxograma (corrigido)

início

leia (nota1, nota2, nota3);

media ← (nota1+nota2+nota3)/3;

media >= 5.0?

escreva (“aprovado”);

fim

escreva (“reprovado”);

sim

não

escreva (“em prova final”);

media >= 3.0?

não

objetivo: a partir de três notas de um aluno, verificar se ele está:

aprovado (média >= 5.0)

em prova final (média < 5.0 e média >= 3.0) ou

reprovado (média < 3)

20

11  

INF 1005 Programação I - Prof. Hélio Lopes 8/7/12

algoritmo em pseudocódigo

variáveis media, nota1, nota2, nota3

início

leia nota1, nota2, nota3

media = (nota1+nota2+nota3)/3

se (media >= 5) então

escreva “aluno aprovado”

senão

se (media >= 3) então

escreva “aluno em prova final”

senão

escreva “aluno reprovado” fim-se

fim-se

fim

variáveis media, nota1, nota2, nota3

início

leia nota1, nota2, nota3

media = (nota1+nota2+nota3)/3

se (media >= 5) então

escreva “aluno aprovado”

senão se (media >= 3) então

escreva “aluno em prova final”

senão

escreva “aluno reprovado”

fim-se fim

21

entrada e saída

22

12  

INF 1005 Programação I - Prof. Hélio Lopes 8/7/12

entrada e saída

23

variáveis media, nota1, nota2, nota3 início leia nota1, nota2, nota3 media = (nota1+nota2+nota3)/3 se (media >= 5) então

escreva “aluno aprovado” senão

escreva “aluno reprovado” fim-se fim

pseudocódigo

exercício

Escreva o pseudocódigo ou desenhe o fluxograma de um programa que leia do teclado uma temperatura em Fahrenheit e

escreva na tela a temperatura equivalente em Celsius (tempC =

(tempF-32)/1.8).

EX. 02

______________________________________________________________________

______________________________________________________________________

______________________________________________________________________

______________________________________________________________________

______________________________________________________________________

______________________________________________________________________

______________________________________________________________________

______________________________________________________________________

______________________________________________________________________

______________________________________________________________________

24

13  

INF 1005 Programação I - Prof. Hélio Lopes 8/7/12

condicionais

25

controle de execução: condicionais

variáveis media, nota1, nota2, nota3 início leia nota1, nota2, nota3 media = (nota1+nota2+nota3)/3 se (media >= 5) então

escreva “aluno aprovado” senão

escreva “aluno reprovado” fim-se fim

pseudocódigo fluxograma

início

leia (nota1, nota2, nota3);

media ← (nota1+nota2+nota3)/3;

media >= 5.0?

escreva (“aprovado”);

fim

escreva (“reprovado”);

sim

não … se (condição) então

instrução V1 instrução V2 … instrução Vn

senão instrução F1 instrução F2 … instrução Fn

fim-se

instruções executadas se a condição for verdadeira

instruções executadas se a condição for falsa

26

14  

INF 1005 Programação I - Prof. Hélio Lopes 8/7/12

dúvidas?

27

exercício

Escreva o pseudocódigo ou desenhe o fluxograma de um programa que leia do teclado a probabilidade de chuva e escreva

na tela “sol”, caso a probabilidade seja menor que 60%; e “chuva”,

caso contrário.

EX. 03

______________________________________________________________________

______________________________________________________________________

______________________________________________________________________

______________________________________________________________________

______________________________________________________________________

______________________________________________________________________

______________________________________________________________________

______________________________________________________________________

______________________________________________________________________

______________________________________________________________________

28

15  

INF 1005 Programação I - Prof. Hélio Lopes 8/7/12

condicionais – expressões booleanas

uma condição é representada por uma expressão booleana, que resulta em um valor verdadeiro ou falso

exemplos:

media > 5 maior que

media >= 5 maior ou igual a

media < 5 menor que

media <= 5 menor ou igual a

media == 5 igual a

media != 5 diferente de

29

condicionais – combinando expressões

se (media < 5 e media >= 3) escreva (“em prova final”)

fim

se (nota1 == 10 ou nota2 == 10) escreva (“excelente!”)

fim

A B A e B

V V V

V F F

F V F

F F F

A B A ou B

V V V

V F V

F V V

F F F

conjunção (E)   resultado só é verdadeiro se

ambos os valores forem verdadeiros

disjunção (OU)   resultado só é falso se ambos

os valores forem falsos

30

16  

INF 1005 Programação I - Prof. Hélio Lopes 8/7/12

exercício

Escreva o pseudocódigo ou desenhe o fluxograma de um programa que obtém as 3 notas de um aluno, calcula sua média e,

caso o aluno tenha sido aprovado, escreva na tela “aprovado”. O

aluno é aprovado se ele teve média maior ou igual a 5 e nenhuma

nota menor que 3.

EX. 04

31

________________________________________________________________  ________________________________________________________________  ________________________________________________________________  ________________________________________________________________  ________________________________________________________________  ________________________________________________________________  ________________________________________________________________  ________________________________________________________________  ________________________________________________________________  

repetições

32

17  

INF 1005 Programação I - Prof. Hélio Lopes 8/7/12

controle de execução: repetições variáveis

num, media, nota1, nota2, nota3 início leia num enquanto (num > 0) faça

leia nota1, nota2, nota3 media = (nota1+nota2+nota3)/3 se (media >= 5) então escreva “aluno aprovado” senão escreva “aluno reprovado” fim-se num= num – 1

fim-enquanto fim

pseudocódigo fluxograma início

leia (nota1, nota2, nota3);

media ← (nota1+nota2+nota3)/3;

media >= 5.0?

escreva (“aprovado”);

fim

escreva (“reprovado”);

sim

não … enquanto (condição) faça

instrução V1 … instrução Vn

fim-enquanto …

instruções executadas enquanto a condição for verdadeira

instruções executadas quando a condição é ou se torna falsa

num = num - 1

num > 0?

leia num

sim

não

33

exercício

Qual é a saída dos seguintes programas?

EX. 05

_______________________________  _______________________________  _______________________________  _______________________________    

variáveis num

início num = 0 enquanto (num < 3) faça escreva num num= num + 1 fim-enquanto

fim

variáveis num

início num = 0 enquanto (num < 3) faça escreva num num= num - 1 fim-enquanto

fim

_______________________________  _______________________________  _______________________________  _______________________________  

valor de num a cada iteração

I0 I1 I2 I3 I4 I5 I6 I7 I8

num

saída saída

valor de num a cada iteração

I0 I1 I2 I3 I4 I5 I6 I7 I8

num 34

18  

INF 1005 Programação I - Prof. Hélio Lopes 8/7/12

exercício EX. 06

Escreva o pseudocódigo de um programa que lê o número de alunos de uma turma e, para cada aluno, lê as suas três notas,

escreve sua média e, no final, escreve a média da turma.

35

________________________________________________________________  ________________________________________________________________  ________________________________________________________________  ________________________________________________________________  ________________________________________________________________  ________________________________________________________________  ________________________________________________________________  ________________________________________________________________  ________________________________________________________________  ________________________________________________________________  ________________________________________________________________  

exercício EX. 06

Escreva o pseudocódigo de um programa que lê o número de alunos de uma turma e, para cada aluno, lê as suas três notas,

escreve sua média e, no final, escreve a média da turma.

variáveis num_alunos, i media, media_turma, nota1, nota2, nota3

início leia num_alunos i = 0 media_turma = 0 enquanto (i < num_alunos) faça leia nota1, nota2, nota3 media = (nota1+nota2+nota3)/3 media_turma = media_turma + media i = i + 1 fim-enquanto media_turma = media_turma / num_alunos escreva media_turma

fim

Em que situações este programa falha?

36

19  

INF 1005 Programação I - Prof. Hélio Lopes 8/7/12

exercício EX. 07

Escreva o pseudocódigo ou desenhe o fluxograma de um programa que lê um número não negativo e escreve na tela o seu

fatorial. Lembrando: n! = n x (n-1) x ... x 1

37

________________________________________________________________  ________________________________________________________________  ________________________________________________________________  ________________________________________________________________  ________________________________________________________________  ________________________________________________________________  ________________________________________________________________  ________________________________________________________________  ________________________________________________________________  ________________________________________________________________  ________________________________________________________________  

exercício EX. 07

Escreva o pseudocódigo de um programa que lê um número não negativo e escreve na tela o seu fatorial.

Lembrando: n! = n x (n-1) x ... x 1

variáveis f, n

início

leia n

f = 1

enquanto (n > 1) faça

f = f * n

n = n - 1

fim-enquanto

escreva f

fim

Em que situação esse programa falha?

38

20  

INF 1005 Programação I - Prof. Hélio Lopes 8/7/12

dúvidas? Prof. Hélio Lopes lopes@inf.puc-rio.br sala 408 RDC

39