Aula Expositiva 9
3.3 Funções
3.3.1 Sintaxe
3.3.2 Funções, Arquivos Fonte e o Scilab
3.3.3 Funções, Matrizes, Loops e Indução
3.3.3.1 Soma dos Elementos de um Vetor
3.3.3.2 Menor Valor Presente em um Vetor
3.3.4 Recursividade
3.3.5 Funções e Desenvolvimento Top-down
DCC 001
Programação de Computadores
2° Semestre de 2011
Prof. Osvaldo Carvalho
Funções
DCC001 2011-1
2
Cálculo do número de combinações
 Faça um programa que
1. Leia 2 inteiros n e k
2.
DCC001 2011-1
Calcule e imprima o número de
combinações de n por k, dado pela
fórmula
3
Fatorial – Reaproveitamento do Código
 Pare reaproveitarmos o código
fat = 1;
for i = 1:n
fat = fat*i;
end
 devemos adaptá-lo para o cálculo dos
fatoriais de n, n-k e k
DCC001 2011-1
4
Combinações n/k – Sem Funções
n=input("n="); k=input("k=");
fat_n = 1; // Cálculo do fatorial de n
for i = 2:n
fat_n = fat_n * i;
end
fat_n_k = 1; // Cálculo do fatorial de n-k
for i = 2:(n-k)
fat_n_k = fat_n_k * i;
end
fat_k = 1; // Cálculo do fatorial de k
for i = 2:k
fat_k = fat_k * i;
end
nComb = fat_n/(fat_n_k * fat_k)
DCC001 2011-1
5
Combinações n/k – Com Funções
Programa Principal
n=input("n="); k=input("k=");
nComb = fatorial(n)/(fatorial(n-k) * fatorial(k))
Função
function fat = fatorial(n)
fat = 1;
for i = 1:n
fat = fat*i;
end
endfunction
DCC001 2011-1
Chamadas
da função
Código da
função
6
Arquivos com Código de Funções
 Uma função é normalmente escrita em um arquivo
separado do arquivo com o programa principal
 O arquivo com a função deve ter

o mesmo nome da função

a extensão .sci (um programa tem a extensão .sce)
 Para “incorporar” uma função ao Scilab, use
exec(<nome do arquivo com a função>)
no programa cliente
DCC001 2011-1
7
Arquivo com uma Função
DCC001 2011-1
8
O comando exec
exec("fatorial.sci")
n=input("n="); k=input("k=");
nComb = fatorial(n)/...
fatorial(n-k)*fatorial(k)
 O Scilab só toma conhecimento da existência
de uma função através do comando exec
 O arquivo com a função deve estar no
DCC001 2011-1
mesmo diretório do programa que chama a
função
9
Ganhos com o uso de Funções
 O uso de parâmetros permite um
melhor reaproveitamento do código
 Programação mais clara
 Possível divisão do trabalho:
 um
programador faz o programa
principal,
 outro faz a função
DCC001 2011-1
10
Parâmetros Formais e Reais
DCC001 2011-1
11
Parâmetros Formais
function fat = fatorial(n)
fat = 1;
for i = 1:n
fat = fat*i;
Parâmetro de
end
Entrada
É fornecido na
Parâmetro
de Saída
endfunction
É calculado pela
função
DCC001 2011-1
chamada da
função
12
Funções com mais de um parâmetro de saída
function [r1, r2] = eq2g(a,b,c)
delta = b^2 - 4*a*c
r1 = (-b + sqrt(delta))/(2*a)
r2 = (-b - sqrt(delta))/(2*a)
endfunction
Chamada da função eq2g
[raiz1,raiz2] = eq2g(x,y,z)
DCC001 2011-1
13
Chamada de Função
 Os parâmetros reais (que podem ser
expressões) são copiados sobre os
parâmetros formais
 O controle é transferido para a função, que
trabalha sobre os parâmetros formais
 Parâmetros formais somente ganham
existência como variáveis durante a execução
da função
DCC001 2011-1
14
Execução de Função
 Alterações feitas pela função sobre
parâmetros formais não afetam os
parâmetros reais de entrada
 Variáveis utilizadas pela função não têm nada
a ver com variáveis de mesmo nome
existentes no programa que chama a função;
 Estas variáveis locais ganham existência
somente durante a execução da função
DCC001 2011-1
15
Retorno de Função
 Os parâmetros reais de saída
(normalmente termos em uma
expressão, como em y = 1 +
sin(x) ) recebem os valores dos
parâmetros formais de saída calculados
pela função
 O controle é devolvido para o ponto de
chamada
DCC001 2011-1
16
Encadeamento de Chamadas
function nComb = Combinacoes(n,k)
nComb = fatorial(n)/...
(fatorial(n-k) * fatorial(k))
endfunction
Nosso
programa
transformado
em função
Programa principal
exec("Combinacoes.sci")
exec("fatorial.sci")
n=input("n="); k=input("k=");
printf("nComb(%d,%d) = %d",n,k,Combinacoes(n,k))
DCC001 2011-1
17
Encadeamento de Chamadas
Programa
Principal
Função
nComb
Função
Fatorial
DCC001 2011-1
18
Funções como Parâmetros de uma Função
 Parâmetros de entrada e de saída de uma função
podem ser qualquer coisa:





números,
strings,
booleanos,
matrizes de qualquer tipo,
e até mesmo outra função!
function PlotaPontos(f,x)
y = f(x);
plot2d(x,y);
endfunction
DCC001 2011-1
19
Funções como Parâmetros de uma Função
function y = MinhaFunc(x)
y = exp(- x .^ 2);
endfunction
// Testador PlotaPontos
exec("PlotaPontos.sci");
exec("MinhaFunc.sci");
x = 0:0.1:2*%pi;
PlotaPontos(sin,x);
PlotaPontos(MinhaFunc,x);
DCC001 2011-1
20
Soma dos Elementos de um Vetor
DCC001 2011-1
21
Função Soma dos elementos de um vetor
 Queremos programar uma função para
calcular a soma de todos os elementos de um
vetor (a função sum do Scilab faz isso)
 Primeiro passo: determinação das entradas e
saídas da função
 Entrada: um vetor
 Saída: um número igual à soma dos
elementos do vetor
DCC001 2011-1
22
Cabeçalho de uma Função
function s = Soma(A)
// Calcula a soma dos elementos de A
endfunction
 Avanços? Sim:
 Demos um nome significativo para a função;
 Determinamos e demos nomes para seus
parâmetros formais de entrada e de saída
 A isto se dá o nome de cabeçalho da função
DCC001 2011-1
23
Teste de Unidade
 Construir um programa que testa o
funcionamento de uma função
antes mesmo de construir a função
é uma prática muito recomendável
 Vamos programar um teste de
unidade para a função Soma
DCC001 2011-1
24
O Programa Soma_Teste.sce - 1
exec("Soma.sci");
// Programa que testa a função Soma
a = int(10*rand(1,4))
sa = Soma(a)
b = int(10*rand(1,6))
sb = Soma(b)
c = int(10*rand(1,9))
sc = Soma(c)
DCC001 2011-1
25
O Programa Soma_Teste.sce - 2
 O programa gera 3 pequenos vetores de inteiros
entre 0 e 10
 Repare que o “;” foi omitido para que o Scilab
imprima automaticamente os vetores gerados
 A função Soma é chamada três vezes com


três parâmetros reais de entrada: a, b e c
três parâmetros reais de saída: sa, sb e sc
 A cada chamada os parâmetros formais s e A
recebem os valores dos parâmetros reais
DCC001 2011-1
26
Algoritmo para a Soma dos Elementos de um Vetor
 Raciocínio indutivo
 Hipótese de indução:

Uma variável s contém a soma dos k primeiros elementos de A,
ou seja, s = A(1) + ... + A(k)
 Passo:

Fazendo s = s + A(k+1) , teremos
s = A(1) + ... + A(k) + A(k+1)

Repetindo este passo até o último elemento de A, teremos em s a
soma de todos os elementos
 Início

k = 0
DCC001 2011-1
e s = 0 (o conjunto {A(1),...,A(0)} é vazio)
27
Um Passo do Algoritmo
Para k = 0,
s =0
1
2
3
4
5
6
7
8
9
10
44 13 44 46 29 30 34 34 42 13
Para k = 3,
s = 101
DCC001 2011-1
Para k = 4,
s = 101 + 46 = 147
28
Tamanho de Parâmetros Formais
 Problema: qual é o tamanho do
parâmetro formal A, se a função Soma
pode ser chamada com parâmetros
reais de diversos tamanhos?
 Soluções:
DCC001 2011-1

a função length(A) retorna o número de
elementos em A

a função size(A) retorna o número de linhas e
de colunas de A
29
A função Soma
function s = Soma(A);
// Calcula a soma dos
// elementos do vetor A
s = 0;
for k = 1:length(A)
s = s + A(k);
end
endfunction
DCC001 2011-1
30
Saída do Soma_Teste.sce
a
=
6.
3.
9.
-->sa = Soma(a)
sa =
20.
b =
3.
3.
2.
-->sb = Soma(b)
sb =
20.
c =
5.
5.
4.
-->sc = Soma(c)
sc =
39.
DCC001 2011-1
2.
5.
4.
3.
2.
6.
4.
9.
0.
4.
31
Menor valor presente em um Vetor
DCC001 2011-1
32
Menor valor presente em um vetor
 Queremos programar uma função que
encontre o menor valor presente em
um vetor (a função min do Scilab faz
isso)
 Etapas:
Construir o cabeçalho da função
 Construir um programa que teste a função
 Desenvolver a função

DCC001 2011-1
33
Cabeçalho da Função Minimo.sci
function m = Minimo(A)
// Encontra o menor valor
// presente no vetor A
endfunction
 Temos:
 Um nome significativo para a função
DCC001 2011-1

Um parâmetro formal de entrada, o vetor A

Um parâmetro formal de saída, m, que deve receber
o menor valor presente em A
34
O Programa Minimo_Teste.sci
// Programa que testa a função Minimo
exec("Minimo.sci");
a = int(10*rand(1,4))
ma = Minimo(a)
b = int(10*rand(1,6))
mb = Minimo(b)
c = int(10*rand(1,9))
mc = Minimo(c)
DCC001 2011-1
35
Algoritmo para encontrar o Menor Valor presente em um
Vetor
 Raciocínio indutivo
 Hipótese de indução:
 Uma variável m contém o menor valor dentre os k
primeiros elementos de A
 Passo:
 if A(k+1) < m then m = A(k+1)
 Repetindo este passo até o último elemento de A,
teremos em m o menor dentre todos os elementos
 Início
 k = 1 e m = A(1)
DCC001 2011-1
36
Dois passos do algoritmo Mínimo
DCC001 2011-1
37
A função Minimo.sci
function m = Minimo(A)
// Encontra o menor valor
// presente no vetor A
m = A(1);
for k = 2:length(A)
if m > A(k)
m = A(k);
end
end
endfunction
DCC001 2011-1
38
Funções Recursivas
DCC001 2011-1
39
Recursividade
 Uma função pode chamar outra função
 que pode chamar outra função
 que pode chamar outra função

...
 E uma função também pode chamar a si própria!
 Uma função que chama a si própria é uma
função recursiva
 A formulação recursiva é muitas vezes a forma
mais natural para a descrição de um algoritmo
DCC001 2011-1
40
Fatorial Recursivo
 Nós sabemos que:
1! = 1, e que
 n! = n*(n-1)! para n > 1

function fat = fatorialR(n)
if n > 1 then
fat = n*fatorialR(n-1)
else
fat = 1
end
endfunction
DCC001 2011-1
41
Raciocínio Recursivo
 n! = n*(n-1)! para n > 1

Solução de um problema é definida utilizando a
solução de um problema menor
 1! = 1

DCC001 2011-1
Problema suficientemente pequeno para ter
solução não dependente de problemas menores
42
Fatorial Recursivo – 2
function fat = FatorialR(n)
// Comente os printf para não imprimir
printf("\nIniciando FatorialR(%d)",n);
if n > 1 then
fat = n * FatorialR(n-1);
else
fat = 1;
end
printf("\nRetornando Fatorial(%d) = %d",n,fat)
endfunction
DCC001 2011-1
43
Fatorial Recursivo – 3
 Saída:
n = 5
Iniciando FatorialR(5)
Iniciando FatorialR(4)
Iniciando FatorialR(3)
Iniciando FatorialR(2)
Iniciando FatorialR(1)
Retornando Fatorial(1)
Retornando Fatorial(2)
Retornando Fatorial(3)
Retornando Fatorial(4)
Retornando Fatorial(5)
5! = 120
DCC001 2011-1
=
=
=
=
=
1
2
6
24
120
44
Pilha de Execução - Chamadas
Fat(1)
Prog
DCC001 2011-1
Fat(2)
Fat(2)
Fat(3)
Fat(3)
Fat(3)
Fat(4)
Fat(4)
Fat(4)
Fat(4)
Fat(5)
Fat(5)
Fat(5)
Fat(5)
Fat(5)
Prog
Prog
Prog
Prog
Prog
45
Pilha de Execução – Retornos
Fat(1
Fat(2)
Fat(2)
Fat(3)
Fat(3)
Fat(3)
Fat(4)
Fat(4)
Fat(4)
Fat(4)
Fat(5)
Fat(5)
Fat(5)
Fat(5)
Fat(5)
Prog
Prog
Prog
Prog
Prog
DCC001 2011-1
Prog
46
Pilha de Execução
Chamadas e Retornos
Fat(1)
Prog
DCC001 2011-1
Fat(2)
Fat(2)
Fat(2)
Fat(3)
Fat(3)
Fat(3)
Fat(3)
Fat(3)
Fat(4)
Fat(4)
Fat(4)
Fat(4)
Fat(4)
Fat(4)
Fat(4)
Fat(5)
Fat(5)
Fat(5)
Fat(5)
Fat(5)
Fat(5)
Fat(5)
Fat(5)
Fat(5)
Prog
Prog
Prog
Prog
Prog
Prog
Prog
Prog
Prog
Prog
47
Mínimo Recursivo - 1
 É possível formular o algoritmo de descoberta do
menor valor presente em um vetor como uma
função recursiva
 Uma possibilidade:


DCC001 2011-1
Se length(A) == 1, o menor valor em A é A(1)
Se length(A) > 1, o menor valor em A é o menor
dentre (o menor valor na metade esquerda de A) e (o
menor valor na metade direita de A)
48
A função MinimoRecursivo.sci
function m = MinimoR(x)
if length(x) == 1 then
m = x(1)
else
half = int(length(x)/2);
minLeft = MinimoR(x(1:half));
minRight = MinimoR(x(half+1:length(x)));
if minLeft <= minRight then
m = minLeft
else
m = minRight
end
end
endfunction
DCC001 2011-1
49
Funções e Desenvolvimento Top-Down
DCC001 2011-1
50
Funções e Desenvolvimento
top-down
 Técnica: chamada da função antes de
seu desenvolvimento
 O programador deve especificar o
resultado desejado da função,
postergando o trabalho de determinar
como obter este resultado
DCC001 2011-1
51
Menor primo ≥ n
 Problema:
 Construir um programa que lê uma série de
números e, para cada número lido, encontra o
menor primo que seja maior ou igual a ele
 Se, por exemplo, o número lido for 4, o programa
deve encontrar o número primo 5; se for 11, o
programa deve encontrar o próprio 11.
 O programa deve terminar quando o número lido
for menor ou igual a 1
 Sabe-se que o conjunto dos números primos é
infinito
DCC001 2011-1
52
Menor primo ≥ n
 Programa principal
 Cuida da interação com o usuário
 O problema de encontrar o menor primo ≥ n é
“empurrado” para uma função
n = input("n = ");
while n >= 2
// Encontra o menor primo >= n
// e imprime o resultado
printf("O menor primo >= %d é %d",...
n,MenorPrimoMaiorOuIgual(n))
// Lê n
n = input("n = (use n < 2 se quiser parar):");
end
DCC001 2011-1
53
Menor primo ≥ n
 Função MenorPrimoMaiorOuIgual



Loop de procura por um primo
Não interage com o usuário
Empurra o problema de saber se um número é primo para
outra função
function p = MenorPrimoMaiorOuIgual(n)
p = n;
while ~Primo(p)
p = p+1
end
endfunction
DCC001 2011-1
54
Menor primo ≥ n
 Função Primo



Testa se um número é primo
A saída é booleana: %t se for primo, %f senão
Usa a função modulo(n,d) que calcula o resto da divisão
de n por d
function ePrimo = Primo(n)
d = 2;
while modulo(n,d) ~= 0
d = d+1;
end
ePrimo = (d == n);
endfunction
DCC001 2011-1
55
Conclusões
 Funções são uma ferramenta muito útil de
modularização
 Seu uso permite o reaproveitamento de código e o
encapsulamento de detalhes
 Funções recursivas são uma outra forma de se
prescrever comportamentos repetitivos e, algumas
vezes (como veremos), a forma mais natural de se
expressar um algoritmo
 O uso de funções permite o desenvolvimento gradual
de programas por refinamentos sucessivos
DCC001 2011-1
56
Download

Módulo_08-2011