Aula Expositiva 9

3.3 Funções3.3.1 Sintaxe3.3.2 Funções, Arquivos Fonte e o Scilab3.3.3 Funções, Matrizes, Loops e Indução3.3.3.1 Soma dos Elementos de um Vetor3.3.3.2 Menor Valor Presente em um Vetor3.3.4 Recursividade3.3.5 Funções e Desenvolvimento Top-down

DCC 001Programação de Computadores

2° Semestre de 2011Prof. Osvaldo Carvalho

Funções

DCC001 2011-1 2

Cálculo do número de combinações

Faça um programa que1. Leia 2 inteiros n e k2. Calcule e imprima o número de

combinações de n por k, dado pela fórmula

3DCC001 2011-1

Pare reaproveitarmos o código

devemos adaptá-lo para o cálculo dos fatoriais de n, n-k e k

Fatorial – Reaproveitamento do Código

fat = 1;for i = 1:n fat = fat*i;end

4DCC001 2011-1

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)

5DCC001 2011-1

Combinações n/k – Com Funções

n=input("n="); k=input("k=");

nComb = fatorial(n)/(fatorial(n-k) * fatorial(k))

function fat = fatorial(n) fat = 1; for i = 1:n fat = fat*i; end endfunction

Programa Principal

Função Chamadas da função

Código da função

6DCC001 2011-1

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

7DCC001 2011-1

Arquivo com uma Função

8DCC001 2011-1

O comando exec

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 mesmo diretório do programa que chama a função

exec("fatorial.sci") n=input("n="); k=input("k="); nComb = fatorial(n)/... fatorial(n-k)*fatorial(k)

9DCC001 2011-1

Ganhos com o uso de Funções

O uso de parâmetros permite um melhor reaproveitamento do código

Programação mais claraPossível divisão do trabalho:

um programador faz o programa principal,

outro faz a função 10DCC001 2011-1

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; end endfunctionParâmetro de Saída

É calculado pela função

Parâmetro de Entrada

É fornecido na chamada da

função12DCC001 2011-1

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

[raiz1,raiz2] = eq2g(x,y,z)

Chamada da função eq2g

13DCC001 2011-1

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

14DCC001 2011-1

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 15DCC001 2011-1

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

16DCC001 2011-1

Encadeamento de Chamadas

function nComb = Combinacoes(n,k) nComb = fatorial(n)/... (fatorial(n-k) * fatorial(k))endfunction

exec("Combinacoes.sci")exec("fatorial.sci")n=input("n="); k=input("k=");printf("nComb(%d,%d) = %d",n,k,Combinacoes(n,k))

Nosso programa

transformado em função

Programa principal

17DCC001 2011-1

Encadeamento de Chamadas

DCC001 2011-1 18

Programa Principal

Função nComb

Função Fatorial

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

19DCC001 2011-1

Funções como Parâmetros de uma Função

DCC001 2011-1 20

function y = MinhaFunc(x) y = exp(- x .^ 2);endfunction

// Testador PlotaPontosexec("PlotaPontos.sci");exec("MinhaFunc.sci");x = 0:0.1:2*%pi;PlotaPontos(sin,x);PlotaPontos(MinhaFunc,x);

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 vetor22DCC001 2011-1

Cabeçalho de uma Função

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

function s = Soma(A) // Calcula a soma dos elementos de Aendfunction

23DCC001 2011-1

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

24DCC001 2011-1

O Programa Soma_Teste.sce - 1

exec("Soma.sci");// Programa que testa a função Somaa = 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)

25DCC001 2011-1

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

26DCC001 2011-1

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 e s = 0 (o conjunto {A(1),...,A(0)} é vazio)

27DCC001 2011-1

Um Passo do Algoritmo

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

Para k = 4, s = 101 + 46 = 147

Para k = 0, s = 0

28DCC001 2011-1

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: 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 A29DCC001 2011-1

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); endendfunction

30DCC001 2011-1

Saída do Soma_Teste.scea = 6. 3. 9. 2. -->sa = Soma(a) sa = 20. b = 3. 3. 2. 5. 4. 3. -->sb = Soma(b) sb = 20. c = 5. 5. 4. 2. 6. 4. 9. 0. 4. -->sc = Soma(c) sc = 39.

31DCC001 2011-1

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 33DCC001 2011-1

Cabeçalho da Função Minimo.sci

Temos: Um nome significativo para a função 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

function m = Minimo(A) // Encontra o menor valor // presente no vetor Aendfunction

34DCC001 2011-1

O Programa Minimo_Teste.sci

// Programa que testa a função Minimoexec("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)

35DCC001 2011-1

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) 36DCC001 2011-1

Dois passos do algoritmo Mínimo

DCC001 2011-1 37

1 2 3 4 5 6 7

34 56 27 45 12 44 34

Para k=2, min = 34

Para k=3, min = menor(34,27) = 27

1 2 3 4 5 6 7

34 56 27 45 12 44 34

Para k=3, min = 27

Para k=4, min = menor(27,45) = 27

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 endendfunction

38DCC001 2011-1

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

40DCC001 2011-1

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 endendfunction

41DCC001 2011-1

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 Problema suficientemente pequeno para ter

solução não dependente de problemas menores

42DCC001 2011-1

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

43DCC001 2011-1

Fatorial Recursivo – 3

n = 5

Iniciando FatorialR(5)Iniciando FatorialR(4)Iniciando FatorialR(3)Iniciando FatorialR(2)Iniciando FatorialR(1)Retornando Fatorial(1) = 1Retornando Fatorial(2) = 2Retornando Fatorial(3) = 6Retornando Fatorial(4) = 24Retornando Fatorial(5) = 1205! = 120

Saída:

44DCC001 2011-1

Pilha de Execução - Chamadas

Prog ProgFat(5)

ProgFat(5)Fat(4)

ProgFat(5)Fat(4)Fat(3)

ProgFat(5)Fat(4)Fat(3)Fat(2)

ProgFat(5)Fat(4)Fat(3)Fat(2)Fat(1)

45DCC001 2011-1

Pilha de Execução – Retornos

ProgFat(5)Fat(4)Fat(3)Fat(2)Fat(1

ProgFat(5)Fat(4)Fat(3)Fat(2)

ProgFat(5)Fat(4)Fat(3)

ProgFat(5)Fat(4)

ProgFat(5)

Prog

46DCC001 2011-1

Pilha de ExecuçãoChamadas e Retornos

DCC001 2011-1 47

Prog ProgFat(5)

ProgFat(5)Fat(4)

ProgFat(5)Fat(4)Fat(3)

ProgFat(5)Fat(4)Fat(3)Fat(2)

ProgFat(5)Fat(4)Fat(3)Fat(2)Fat(1)

ProgFat(5)Fat(4)Fat(3)Fat(2)

ProgFat(5)Fat(4)Fat(3)

ProgFat(5)Fat(4)

ProgFat(5)

Prog

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: 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)

48DCC001 2011-1

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 endendfunction

49DCC001 2011-1

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 52DCC001 2011-1

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çãon = 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

53DCC001 2011-1

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 endendfunction

54DCC001 2011-1

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 dfunction ePrimo = Primo(n) d = 2; while modulo(n,d) ~= 0 d = d+1; end ePrimo = (d == n);endfunction

55DCC001 2011-1

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

56DCC001 2011-1