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