Baixe o app para aproveitar ainda mais
Prévia do material em texto
ALGORITMOS Subalgoritmos Modularização Subalgoritmos Muitas aplicações exigem algoritmos complexos e extensos. Entretanto sempre é possível dividir problemas grandes e complicados em problemas menores e de solução mais simples. Desta forma, pode-se solucionar cada um destes pequenos problemas separadamente, criando algoritmos parciais para resolvê-los. Tais algoritmos parciais são conhecidos como subalgoritmos. •Subprogramação: � é um método que consiste na divisão de programas grandes em módulos menores chamados de subprogramas. Subalgoritmos Algoritmo principal � Um dos subalgoritmos, por onde começa a execução do problema, recebe o nome de ou algoritmo principal e os outros são os subalgoritmos propriamente ditos, os quais serão executados sempre que forem chamados, através de comandos especiais. Após a execução de um subalgoritmo, o controle da execução retorna para o módulo que o solicitou, que pode ser o programa principal ou outro subprograma. O principal objetivo da subprogramação é permitir gerenciar a complexidade no desenvolvimento de algoritmos de grande porte. Subalgoritmos IMPORTÂNCIA •Subdivisão de algoritmos complexos: facilita o entendimento; •Estruturação de algoritmos: facilita a detecção de erros e documentação de sistemas; •Modularização de sistemas: facilita a manutenção de softwares e a reutilização de subalgoritmos já implementados VANTAGENS •Um Subalgoritmo pode ser solicitado várias vezes para valores diferentes de seus parâmetros, gerando economia de tempo e de trabalho; •Diferentes programadores podem trabalhar simultaneamente na solução de um mesmo problema, codificando, compilando e testando separadamente os subprogramas. Subalgoritmos Funcionamento •Um problema é dividido em um algoritmo principal e vários subalgoritmos (tantos quantos forem necessários e convenientes). •O algoritmo principal é aquele por onde a execução do algoritmo sempre se inicia e pode eventualmente invocar os demais subalgoritmos � Durante a execução do algoritmo principal, quando se encontra um comando de invocação de um subalgoritmo, a execução do mesmo é interrompida. � A seguir, passa-se à execução dos comandos do corpo do subalgoritmo. � Ao seu término, retorna-se a execução do algoritmo que o chamou (no caso, o algoritmo principal) no ponto onde foi interrompida (comando de chamada do subalgoritmo) e prossegue-se pela instrução imediatamente seguinte. � Note também que é possível que um subalgoritmo chame outro através do mesmo mecanismo. Subalgoritmos DEFINIÇÃO DE SUBALGORITMOS A definição de um subalgoritmo consta de: Cabeçalho: onde estão definidos o nome e o tipo do subalgoritmo e seus parâmetros e variáveis locais ; Corpo: onde são definidas as ações que serão executadas todas as vezes que o subalgoritmo for chamado; Finalização do subalgoritmo. • Nome do subalgoritmo: é o nome com o qual ele é invocado; • Variáveis locais: são aquelas definidas dentro do subalgoritmo e só podem ser utilizadas por ele; • Parâmetros: são os canais por onde os dados são transferidos pelo algoritmo invocador ao subalgoritmo e vice-versa (recebimento de dados e transmissão de resultados). Subalgoritmos LOCALIZAÇÃO DE SUBALGORITMO Os subalgoritmos podem ser digitados e compilados: � juntos com o algoritmo principal �em um arquivo separado, ( biblioteca). cabeçalho <definições dos subalgoritmos> Algoritmo <nome> <declaração de variáveis> Início <corpo do algoritmo> Fim. cabeçalho <chamada da biblioteca> Algoritmo <nome> <declaração de variáveis> Início <corpo do algoritmo> Fim. Subalgoritmos TIPOS DE SUBALGORITMO O tipo do Subalgoritmo é definido em função do número de valores que este retorna ao algoritmo que o chamou. Podem ser: �Funções – retornam um único valor ao algoritmo invocador; � Função Predefinida ( Sin(x); Mod(k,l); ....); � Tipo Função �Procedimentos – retornam zero, um ou vários valores ao algoritmo invocador. Na realidade, a tarefa desempenhada por um subalgoritmo do tipo função pode perfeitamente ser feita por outro tipo de procedimento (o primeiro é um caso particular deste). Esta diferenciação é feita por que um grande número de subalgoritmos se encaixa na categoria de funções. Subalgoritmos SUBPROGRAMA DO TIPO FUNÇÃO PRÉ-DEFINIDA Os Subprogramas do tipo Função Predefinida são fornecidos pelos fabricantes das linguagens computacionais, inseridos internamente nas Bibliotecas de Subprogramas da maioria dos compiladores. Estes podem ser utilizados pelos programadores através de instruções que os solicitam, quando necessários, referenciando seus respectivos nomes. Cada tipo de Subprograma possui regras próprias para ser referenciado, e, cada linguagem de programação define suas próprias regras quanto a utilização e implementação de subprogramas. Exemplos: abs(x)� retorna o valor absoluto de x min( )� retorna o valor mínimo sin(x) � retorna o seno de x log(x) � retorna o logaritmo de x Subalgoritmos – Tipo Função SUBALGORITMO DO TIPO FUNÇÃO � RETORNA 0 OU UM ÚNICO VALOR Tipo Função NOME ( <tipo parâmetros formais ) <declaração de variáveis> <instruções do subalgoritmo> Retorne (um único valor) Fim_Função Exemplos de chamada: Var=NOME (parâmetros reais) Y= X+NOME(parâmetros reais ) Escreva “O resultado da funcao eh”, NOME(parâmetros reais ) Subalgoritmos – Tipo Função SUBPROGRAMA DO TIPO FUNÇÃO � RETORNA UM ÚNICO VALOR Exemplos de chamada: Var=NOME (parâmetros reais) Y= X+NOME(parâmetros reais ) Escreva “O resultado da funcao eh”, NOME(parâmetros reais ) •Só retorna um valor, do mesmo tipo primitivo da função; •O comando RETURN pode aparecer em qualquer ponto do subprograma e promove o retorno ao programa principal; •O tipo do nome da função define o tipo do valor que ela calcula; •O nome da função segue as mesmas regras dos nomes de variáveis; •Os argumentos podem ser variáveis indexadas; •O valor de retorno não pode ser uma variável indexada. Pode ser apenas um valor desta variável. Exemplo: Se A for um vetor, retorne A[2] Função Tipo NOME ( <tipo parâmetros formais ) <declaração de variáveis> <instruções do subalgoritmo> Retorne (um único valor) Fim_Função Subalgoritmos – Tipo Função A INSTRUÇÃO RETORNE As funções podem ou não retornar valores ao algoritmo solicitante. Não há obrigatoriamente necessidade de uma instrução retorne. O comando retorne causa a atribuição de qualquer expressão entre parênteses à função contendo o retorne. Este comando tem dois usos importantes: �A instrução retorne( ) é usada para enviar um valor e � retornar, imediatamente para a próxima instrução do código de chamada. Retorne sem parênteses, é usado para causar uma saída imediata da função na qual ele se encontra; isto é, retorne fará com que a execução do programa volte para o código de chamada assim que o computador encontrar este comando, o que ocorre, em geral, antes da última instrução da função. → Uma função pode conter mais de uma instrução Retorne. Subalgoritmos – Tipo Função •Subalgoritmo tipo função Sem passagem de parâmetro e Com retorno Algoritmo horas_minutos Inicio /* calcula a diferença entre dois tempos*/ inteiro mins1,mins2 Escreva"Digite a primeira hora (hora:min): " mins1=minutos() Escreva "Digite a segunda hora (hora:min): " mins2=minutos(); Escreva "A diferenca eh”, |mins2-mins1| minutos." Fim_Algoritmo // funcao minutos /*solicita hora e minutos*/ /* retorna hora em minutos*/ Função inteiro minutos() Inteiro hora,min leia hora,min retorne (hora*60+min) Fim Função � A função minutos() é chamada duas vezes pelo algoritmo principal. � A função lê a hora e os minutos e retorna em minutos. Subalgoritmos – Tipo Função •Subprogramatipo função COM passagem de um parâmetro e COM retorno. Considere a função que retorna o valor absoluto de um número. Algoritmo valor_absoluto_inteiro Escreva “valor absoluto de 0=”, absoluto(0) Escreva “valor absoluto de -3=”,absoluto(-3) Escreva “valor absoluto de 10=”, absoluto(10) Fim algoritmo /* retorna o valor absoluto de um número inteiro*/ inteiro absoluto(inteiro x) se (x>=0) então retorne (x) senão retorne (-x) fim se � A definição da função começa com a declaração do tipo da função e do tipo das variáveis. � A função minutos() é chamada três vezes pelo algoritmo principal. � A função recebe um valor inteiro qualquer e retorna seu valor absoluto. Argumento formal : - A variável x é uma nova variável e é chamada de argumento “formal”; Funciona como uma variável local da função, isto é, é criada quando a função inicia sua execução e destruída quando a função termina. Subalgoritmos – Tipo Função •Subprograma tipo função COM passagem de vários parâmetros e COM retorno. Considere a função que retorna o valor absoluto de um número. Algoritmo horas_minutos /* calcula a diferença entre dois tempos*/inteiro mins1,mins2,y,hora,min; Inicio Escreva"Digite a primeira hora (hora,min): " Leia hora, min mins1=minutos(hora,min) Escreva "Digite a segunda hora (hora,min): " Leia hora, min mins2=minutos(hora,min) y=|mins2-mins1| Escreva "A diferenca eh", y,"minutos" Fim_Algoritmo /* retorna hora em minutos*/ Funçao inteiro minutos(inteiro h, inteiro m) Retorne (h*60+m) fim função Recebe dois parâmetros: h� corresponde á hora m � corresponde á min Os parâmetros são do mesmo tipo do principal. Subalgoritmos – Tipo Função •ARGUMENTOS – CHAMADA POR VALOR Todos os parâmetros de funções são passados “por valor”. Isto significa que à função chamada é dada uma cópia dos valores dos argumentos, e ela cria outras variáveis temporárias para armazenar estes valores. Na passagem por valor, uma função chamada não pode alterar o valor de uma variável da função que chama; ela só pode alterar sua cópia temporária. Algoritmo chamada_valor Início int i para I de 0 até 5 passo 1 faça escreva "i=", i, pot(2,i), pot(3,i) fim para fim algoritmo inteiro pot(inteiro x,inteiro n) inteiro p,i p=1 para i de 1 até n passo 1 faça p=p*x retorne(p) fim para A variável n recebe uma cópia da variável i do algoritmo principal. A variável i da função não altera o valor da variável i do algoritmo principal. Algoritmo que calcula a potência de um número Subalgoritmos – Tipo Subrotina SUBALGORITMO DO TIPO SUBROTINA � RETORNA 0 , 1 ou mais valores NOME ( tipo a1, tipo a2, tipo an ) <declaração de variáveis> <comandos do subalgoritmo> Fim subrotina Chamada: NOME (b1,b2,....bn) a1 corresponde á b1 a2 corresponde á b2 an corresponde á bn � São do mesmo tipo. Subalgoritmos – Tipo Subrotina SUBALGORITMO DO TIPO SUBROTINA � Nome: é o nome escolhido pelo programador para identificar a sub-rotina; � Os valores são sempre retornados através dos parâmetros ou de variáveis globais; � a1, a2, ..., an são os parâmetros formais. Podem ser interpretados como os valores de retorno. � Na passagem por valor a1 recebe uma cópia do valor de b1, a2 recebe uma cópia do valor de b2 , an recebe uma cópia do valor de bn � Retorna zero, um ou mais valores de tipos diferentes pelos argumentos � O nome da subrotina segue as mesmas regras dos nomes de variáveis; � Os argumentos podem ser variáveis indexadas. � Uma subrotina pode executar subprogramas e chamar outras subrotinas. Algumas linguagens de programação permitem chamar a si própria. � A sub-rotina pode ou não conter o comando RETURN para voltar o controle da execução ao módulo que a chamou e pode aparecer em qualquer ponto do subprograma Subalgoritmos – Tipo Subrotina CHAMADA POR REFERÊNCIA Na passagem de argumentos para subalgorimtos usando “passagem por valor”, o subalgoritmo chamado não pode alterar diretamente uma variável no subalgoritmo solicitante. Para que um subalgoritmo possa alterar o valor do argumento do solicitante, é necessária a passagem de parâmetros por referência. Para que uma subrotina gere o efeito de chamada por referência: � ponteiros devem ser usados na declaração da lista de argumentos � a subrotina chamadora deve mandar endereços como argumentos. Subalgoritmos – Tipo Subrotina PONTEIROS CONSTANTES E PONTEIROS VARIÁVEIS � Um ponteiro variável tem como conteúdo um endereço de memória. � Este endereço é a localização de outra variável de memória. � Dizemos que uma variável aponta para outra variável quando a primeira contém o endereço da segunda. � Um ponteiro constante é um endereço; um ponteiro variável é um lugar para guardar endereços. Subalgoritmos – Tipo Subrotina Passagem de endereços para uma subrotina � Existem várias situações em que um subprograma necessita comunicar mais de um valor para o programa chamador. � Nos subalgoritmos vistos até o momento, foi possível passar vários valores para uma subalgoritmo e este retornar um único valor. � Entretanto, para fazer com que uma subalgoritmo altere mais de um valor do subalgoritmo solicitante, não existe mecanismos próprios de subalgoritmo, e para realizar esta tarefa são utilizados os ponteiros. Subalgoritmos – Tipo Subrotina Alteração de duas variáveis do subalgoritmo solicitante Para realizar esta tarefa dois procedimentos são necessários. � Primeiro: o algoritmo solicitante, em vez de passar os valores para o subalgoritmo, passa seus endereços. • Estes endereços são locais onde o algoritmo solicitante quer que subalgoritmo coloque os dados gerados; em outras palavras são endereços de variáveis do algoritmo chamador onde desejamos armazenar os novos valores. � Segundo: o subprograma chamado deve declarar os endereços recebidos como ponteiros. Subalgoritmos – Tipo Subrotina •Não envia nada e Não retorna nenhum valor. – Passagem sem parâmetros Algoritmo sem_retorno Início linha() Escreva "\xDB Um programa em C \xDB" linha() fim algoritmo // subalgoritmo que desenha uma linha sólida Subrotina linha() inteiro j para j de 1 até 20 passso 1 escreva "\xDB" fim para fim subrotina �Não há passagem de parâmetros do solicitante (principal ) para a função �Não há retorno da função para o solicitante. Subalgoritmos – Tipo Subrotina Alteração de duas variáveis do subalgoritmo solicitante Algoritmo troca inteiro x,y altera(&x,&y) Escreva "O primeiro eh”,x, “o segundo eh",y Escreva "Fim do programa" Fim algoritmo altera(inteiro *px, inteiro *py) *px=3; *py=5; Fim subrotina O algoritmo chamador revela ao subalgoritmo altera() onde colocar os valores através da passagem de seus endereços usando o operador de endereços (&). A expressão altera(&x,&y); causa a passagem dos endereços de x e y para a subalgoritmo, que os armazena em localizações privadas de memória somente conhecidas por ela. A estes endereços são dados nomes: px e py, para que a subalgoritmo possa referenciá-los, justamente como é feito com qualquer outro tipo de variável. Subalgoritmos – Tipo Subrotina Alteração de duas variáveis do subalgoritmo solicitante Algoritmo troca inteiro x,y altera(&x,&y) Escreva "O primeiro eh”,x, “o segundo eh",y Escreva "Fim do programa" Fim algoritmo altera(inteiro *px, inteiro *py) *px=3; *py=5; Fim subrotina O algoritmo chamador revela ao subalgoritmo altera() onde colocar os valores através da passagem de seus endereços usando o operador de endereços (&). A expressão altera(&x,&y); causa a passagem dos endereços de x e y para a subalgoritmo, que os armazena em localizações privadas de memória somente conhecidas por ela. A estesendereços são dados nomes: px e py, para que a subalgoritmo possa referenciá-los, justamente como é feito com qualquer outro tipo de variável. Subalgoritmos – Tipo Subrotina Uma vez conhecido pelo subalgoritmo, os endereços e os tipos das variáveis do algoritmo chamador, ele pode não somente colocar valores nestas variáveis como também altera-las. Ponteiros podem ser usados não somente para que a subalgoritmo passe valores para o algoritmo chamador, mas também para passar valores do algoritmo para o subalgoritmo. Algoritmo altera2 Inteiro x, y x=4 y=7 altera3(&x,&y) Escreva “O primeiro e “, x, "o segundo eh“, y Escreva “ Fim” Fim do algoritmo altera2(inteiro *px, inteiro*py) *px=*px+10 *py=*py+10 fim subrotina – Tipo Subrotina � Em C o relacionamento entre ponteiros e matrizes é tão estreito que ponteiros e matrizes deveriam ser tratados juntos. � O compilador transforma matrizes em ponteiros quando compila, pois a arquitetura do microcomputador entende ponteiros e não matrizes. � Qualquer operação que possa ser feita com índices de uma matriz pode ser feita com ponteiros. � O nome de uma matriz é um endereço, ou seja, um ponteiro. Ponteiros e matrizes são idênticos na maneira de acessar a memória. Na verdade o nome de uma matriz é um ponteiro constante. Um ponteiro variável é um endereço onde é armazenado outro endereço. � Desta forma nenhuma notação especial é necessária para Subalgoritmos a passagem de valores de matrizes do subprograma para o subprograma chamador. VETORES, MATRIZES E PONTEIROS – Tipo Subrotina Exemplo : Subprogramas – Passagem por Valor e por Referência Faça um algoritmo que leia e imprima duas matrizes A e B e imprima o resultado da multiplicação entre elas. Algoritmo multiplicao_matrizes inteiro la,ca,lb,cb,a[10][10],b[10][10],c[10][10]; Escreva " Digite as dimensoes da matriz A" Leia dimensao(&la,&ca) Escreva " Digite as da matriz B" Leia dimensao(&lb,&cb) Se (ca==lb) então Escreva " Matriz A" leia_matriz(a,la,ca) Escreva "Matriz B " leia_matriz(b,lb,cb) Escreva “Matriz A " imprima_matriz(a,la,ca) Escreva " Matriz B" imprima_matriz(b,lb,cb) Escreva " Matriz Resultante da multiplicacao" multiplica_matriz(a,b,c,la,ca,lb,cb) imprima_matriz(c,la,cb) Senão Escreva " Nao eh possivel multiplicar as matrizes" Fim Se Fim Chama a subrotina leia_matriz para ler a matriz a. As dimensões la e ca são passagem por valor. A matriz a é passagem por referência. Chama a subrotina leia_matriz para ler a matriz b Chama a subrotina imprima_matriz para imprimir a matriz a Chama a subrotina imprima_matriz para imprimir a matriz b Chama a subrotina imprima_matriz para imprimir a matriz c Chama a subrotina dimensao. Passagem por referência. Chama a subrotina dimensao. Passagem por referência. – Tipo Subrotina Exemplo : Subprogramas – Passagem por Valor Faça um algoritmo que leia e imprima duas matrizes A e B e imprima o resultado da multiplicação entre elas. leia_matriz(int q[10][10],int lm,int cm) Inteiro i,j Escreva " Digite os valores da matriz " Para i=1,lm,1 Para j=1,cm,1 Leia q[i][j] Fim para Fim para Fim subrotina multiplica_matriz(int ma[10][10], int mb[10][10], int r[10][10], int mla, int mca, int mlb,int mcb) inteira i,j,k; Para i=1,mla,1 Para j=1,mcb;1 r[i][j]=0; Para k=1,mca,1 r[i][j]=+r[i][j]+ma[i][k]*mb[k][j]; Fim Para Fimpara Fim para Fim subrotina dimensao(inteiro *lx,inteiro *cx) Leia *lx, *cx Fim subrotina imprima_matriz( int q[10][10], int lm, int cm) inteira i,j Escreva " Matriz " Para i=1,lm,1 Escreva ( q[i][j], j=1,cm,1) Fim para Fim subrotina Exemplos Exemplo : Faça um subalgoritmo para ler dimensões de uma matriz qualquer dimensoes(int *lm,int *cm) Escreva “Digite as dimensoes da matriz” Leia *lm, *cm Fim subrotina // chamada no solicitante (principal) dimensões (&la, &ca) No algoritmo solicitante (principal) � declarar la e ca como inteiro Inteiro la,ca � passagem por referência. Como são dois valores, não pode ser utilizada a função Exemplos Exemplo : Faça um subalgoritmo tipo função que receba uma matriz inteira e retorne a soma dos elementos da matriz Função inteiro soma_elementos_matriz(int q[10][10],int lm,int cm) Inteiro i,j,soma soma=0 Para i=1,lm,1 Para j=1,cm,1 soma=soma +q[i][j] Fim para Fim para retorne (soma) Fim função // chamada no solicitante (principal) Y= soma_elementos_matriz(A,la,ca) No algoritmo solicitante (principal) antes de chamar a função � declarar a matriz A como inteira com dimensão maxima 10x10 e declarar as dimensões que vai usar la e ca Inteiro A[10][10], la,ca � Ler a matriz A e as suas dimensões la e ca dimensão(&la,&ca) leia_matriz(A,la,ca) Exemplos Exemplo : Faça um subalgoritmo que receba uma matriz e dois vetores VP e Vs. Transporte para o vetor Vp os elementos da diagonal principal e para um vetor Vs os elementos da diagonal secundaria. O subalgoritmo deve retornar os vetores. vetores_diagonais(int q[10][10],int lm,int Vp[10], int Vs[10]) Inteiro i,j,contVp, contVs contVp=0 contVs=0 soma=0 Para i=1,lm,1 Para j=1,lm,1 se (i==j) então contVp=contVp+1 Vp[contVp]=q[i][j] senão se (i+j=lm+1) então contVs=contVs+1 Vs[contVs]=q[i][j] fim se Fim para Fim para Fim subrotina No algoritmo solicitante (principal) antes de chamar a subrotina � declarar a matriz A como inteira com dimensão maxima 10x10 e declarar as dimensões que vai usar la e ca. Declarar os vetores Inteiro A[10][10], la,ca, Vprincipal[10], Vsecundaria[10] � Ler a matriz A e as suas dimensões reais la e ca dimensão(&la,&ca) leia_matriz(A,la,ca) � Diagonal principal: i = =j � Diagonal secundári i+j = dimensao+1 // dimensão da matriz quadrada � contVp: contador e indice do vetor Vp � contVs: contador e indice do vetor Vs � As dimensões dos vetores é a ordem da matriz // chamada no solicitante (principal) vetores_diagonais(A,la,Vprincipal,Vsecundaria) Exemplos Exemplo : Faça um subalgoritmo que receba uma matriz e dois vetores VP e VI. Transporte para o vetor VP os elementos da pares da matriz e para um vetor VI os elementos impares. O subalgoritmo deve retornar os vetores e suas dimensões. vetores_par_impar(int q[10][10],int lm,int cm, int VP[100], int VI[100],int *contpx, int *contix) Inteiro i,j,contVp, contVs contpx=0 contixs=0 ara i=1,lm,1 Para j=1,cm,1 se (q[i][j]%2==0) então *contpx=*contpx+1 VP[*contpx]=q[i][j] senão * contix=*contix+1 VI[*contix]=q[i][j] fim se Fim para Fim para Fim subrotina // chamada no solicitante (principal) vetores_par_impar(A,la,ca, Vpar,Vimpar,&contp,&conti) No algoritmo solicitante (principal) antes de chamar a subrotina � declarar a matriz A como inteira com dimensão maxima 10x10 � declarar as dimensões que vai usar la e ca. � Declarar os vetores e os contadores com passagem por referência já que eles serão preenchidos nos subalgoritmo Inteiro A[10][10], la,ca, Vpar[100], Vimpar[100] � Ler a matriz A e as suas dimensões reais la e ca dimensão(&la,&ca) leia_matriz(A,la,ca) � contpx: contador e indice do vetor VP � contp de Vpar � contix: contador e indice do vetor VI �conti de Vimpar � Dimensoes máxima dos vetores é o quadrado da dimensão da matriz já que todos os elementos podem ser pares ou todos podem ser impares � contpx e contix determinam a quantidade de elementos de VP e VI
Compartilhar