Prof Richard Fluxogramas de algoritmos

Prévia do material em texto

DIM0436
32. Fluxogramas
20141125
DIM0436 20141125 1 / 19
Outline
1 Fluxograma
2 Exercícios
DIM0436 20141125 2 / 19
1 Fluxograma
2 Exercícios
DIM0436 20141125 3 / 19
Grafo
Definição
Um grafo é definido como um triplo
(V ,E , s)
V : conjunto de vértices
E : conjunto de arestas
s : E 7→ V × V : mapa que associa
uma aresta a 2 vertices, a fonte e o
alvo.
Exemplo
a
b
1
c
3
d
2 4
Detalhes
V = {a, b, c , d}
E = {1, 2, 3, 4}
s = {1 7→ (a, b), 2 7→ (b, d), 3 7→ (a, c), 4 7→ (c , d)}
DIM0436 20141125 4 / 19
O que é um fluxograma ?
Um fluxograma é uma representação do algoritmo em forma de grafo.
É uma vista alternativa do programa textual
É focada nas decisões do programa e mostra todos os caminhos possíveis de
execução.
Nós do fluxograma = instruções do programa
Setas / arestas = caminhos de controle duma instrução à proxima
DIM0436 20141125 5 / 19
Nós inicial/final
Todo módulo (função / procedimento / módulo principal) tem:
um nó de entrada
um nó de saída
I toda instrução retorne é ligada ao nó de saída
esses nós são estruturais e não fazem parte do programa original
Entrada
in_algoritmo
Saída
out_algoritmo
DIM0436 20141125 6 / 19
Instrução / comando básico
Nó retângulo
1 nó / 1 instrução
a <- x + 1
DIM0436 20141125 7 / 19
Entradas / saídas
Instruções de entrada e de saída tem nós especiais
Um é o simétrico geométrico do outro
Entradas
leia(x)
Saídas
escreval(x)
DIM0436 20141125 8 / 19
Decisão
Os nós de decisão usam o losango
Tem 2 nós alvos para uma única fonte, um para cada decisão possível
Código
1 se x > 1 entao
2 y <- x + 1
3 senao
4 y <- x * 2
5 fimse
Fluxograma
x > 1
y <- x + 1
verdadeiro
y <- x * 2
falso
DIM0436 20141125 9 / 19
Laços
1 algoritmo "Chamada"
2 var y, i: inteiro
3 v: vetor[1..8] de inteiro
4 achado: logico
5
6 inicio
7 escreva("Entre com um inteiro: ")
8 leia(y)
9 para i de 1 ate 8 faca
10 v[i] <- i * 2
11 fimpara
12 i <- 1
13 achado <- falso
14 enquanto i < 9 faca
15 se v[i] = y entao
16 achado <- verdadeiro
17 fimse
18 i <- i + 1
19 fimenquanto
20 escreval(achado)
21 fimalgoritmo
Laços são os únicos comandos
com arestas que “voltam” a uma
etapa anterior do algoritmo.
O último comando do corpo do
laço volta para a o nó de
decisão
O nó de decisão tem 2 nós
alvos:
I o primeiro comando do corpo
do laço
I a instrução que segue o corpo
do laço
DIM0436 20141125 10 / 19
Chamada de função
Código
1 algoritmo "Chamada"
2 var y: inteiro
3 funcao q(x: inteiro): inteiro
4 inicio
5 retorne x * x
6 fimfuncao
7
8 inicio
9 y <- q(3) + 1
10 escreval(y)
11 fimalgoritmo
DIM0436 20141125 11 / 19
Resumo
1 Fluxograma
2 Exercícios
DIM0436 20141125 12 / 19
Perguntas ?
http://dimap.ufrn.br/~richard/dim0320
DIM0436 20141125 13 / 19
1 Fluxograma
2 Exercícios
DIM0436 20141125 14 / 19
Fluxograma / escopo
1 algoritmo "foo"
2 var a: inteiro
3
4 funcao g(x: inteiro): inteiro
5 inicio
6 a <- 10
7 retorne 2 * x
8 fimfuncao
9
10 funcao f(x: inteiro): inteiro
11 var v: inteiro
12 inicio
13 v <- 1
14 retorne g(x) + v
15 fimfuncao
16
17 inicio
18 a <- 3
19 escreval(f(6) + a)
20 fimalgoritmo
1 Desenhe o fluxograma desse
programa
2 O que escreva o programa
abaixo ? Por que ?
DIM0436 20141125 15 / 19
Fluxograma
1 algoritmo "Soma de um vetor"
2 var a: vetor [1..10] de real
3 i, n :inteiro
4 soma : real
5 inicio
6 repita
7 leia(n)
8 ate (n > 0) e (n <= 10)
9 soma <- 0
10 para i de 1 ate n faca
11 soma <- soma + a[i]
12 fimpara
13 escreva(soma)
14 fimalgoritmo
Desenha o fluxograma desse
programa
DIM0436 20141125 16 / 19
Leitura/interpretação
Assunto
Dada a implementação:
1 funcao f(n: inteiro): inteiro
2 inicio
3 se n < 4 entao retorne (3 * n)
4 senao retorne (2 * f(n - 4) + 5)
5 fimse
6 fimfuncao
Escreva as árvores de chamada de função para f(3) e f(7) ? Quais são os
valores obtidos?
DIM0436 20141125 17 / 19
Elemento máximo de um vetor
Assunto
Implemente uma função recursiva max que retorne o maior valor de um vetor de n
números inteiros.
DIM0436 20141125 18 / 19
Combinações
Assunto
Considere a função comb(n, k), que representa o número de grupos distintos com
k pessoas que podem ser formados a partir de n pessoas. Por exemplo,
comb(4, 3) = 4, pois com 4 pessoas (A, B, C, D), é possível formar 4 diferentes
grupos: ABC, ABD, ACD e BCD. Sabe-se que:
comb(n, k) =

n k = 1
1 k = n
comb(n − 1, k − 1) + comb(n − 1, k) 1 < k < n
Implemente em portugol uma função recursiva para comb (n, k) e mostre o
diagrama de execução para chamada comb(5, 3).
Sabendo-se ainda comb(n, k) = n!/(k!(n− k)!), implemente uma função não
recursiva de comb(n, k).
DIM0436 20141125 19 / 19
	Fluxograma
	Exercícios