Algoritmo- ricardo reis, Notas de estudo de Algoritmos

Baixe Algoritmo- ricardo reis e outras Notas de estudo em PDF para Algoritmos, somente na Docsity! ALGORITMOS RICARDO REIS Algoritmos Ricardo Reis 2 CONTEÚDO UNIDADE 1 1. Fundamentos 1.1. A Idéia de Algoritmos 1.2. Construção de Algoritmos 1.3. Execução de Algoritmos 1.4. Finalização e Suspensão de Algoritmos 1.5. Sintaxe e Semântica 2. Entrada e Saída 2.1. Dispositivos de E/S 2.2. Entrada Padrão 2.3. Saída Padrão 3. Variáveis 3.1. A Memória Principal e as Variáveis 3.2. Os Tipos de Variáveis 3.2.1. Tipos Numéricos: Inteiros e Reais 3.2.2. Tipo Caractere 3.2.3. Tipo Lógico 3.3. A Declaração de Variáveis UNIDADE 2 4. Operadores 4.1. A Atribuição 4.2. Operadores Aritméticos 4.3. Operadores Relacionais 4.4. Operadores Lógicos 4.5. Expressões 4.5.1. Precedência de Operadores 4.5.2. Associatividade de Operadores 4.5.3. Expressões Booleanas 5. Estruturas de Controle 5.1. Decisão 5.1.1. Decisão Unidirecional 5.1.2. Decisão Bidirecional 5.1.3. Decisão Múltipla 5.1.4. Aninhamento de Decisões 5.2. Repetição 5.2.1. Laços Controlados por Contador 5.2.2. Laços Controlados por Teste 5.2.3. Aninhamento de Laços 5.2.4. Quebra e Continuação de Laços UNIDADE 3 6. Matrizes 6.1. INTRODUÇÃO A MATRIZES E VETORES 6.2. MATRIZES NA MEMÓRIA 6.3. DECLARAÇÃO, INICIALIZAÇÃO E USO DE VETORES 6.4. AS CADEIAS DE CARACTERES 6.5. VETORES DINÂMICOS 6.6. USANDO MAIS DE UMA DIMENSÃO UNIDADE 4 7. Modularização 7.1. O que é Modularizar? 7.2. Funções, Procedimentos, Processos e Controle 7.3. Escopo de Variáveis 7.4. Passando Parâmetros por Valor e por Referência 7.5. Passando Vetores como Argumentos 7.6. Recursividade Algoritmos Ricardo Reis 5 Há inúmeras linguagens de programação projetadas para fins diversos que vão entre criação de sistemas operacionais a desenvolvimento de aplicações Web. Bom domínio sobre construção de algoritmos é pré-requisito necessário para o ingresso no estudo de uma linguagem de programação. 1.2. CONSTRUÇÃO DE ALGORITMOS Há muitas formas de se representar um algoritmo. As mais comuns são por texto livre, por fluxogramas e por pseudocódigos. Num algoritmo em texto livre a idéia é expressa utilizando-se todos os recursos existentes numa linguagem natural específica (português, inglês, etc.). Um exemplo comum desta abordagem são as receitas de bolo normalmente apresentadas em dois parágrafos: aquele com a lista de ingredientes e outro descrevendo a preparação passo a passo. A lista de ingredientes corresponde à fase declarativa do algoritmo, ou seja, a parte que antecede o próprio algoritmo e visa buscar os recursos necessários a sua realização. Algoritmos representados por fluxogramas utilizam obviamente a estratégia gráfica para se expressarem. Cada uma das etapas (ou grupo de etapas) é representada por um elemento geométrico (retângulo, círculo, etc.). Todos os elementos constituintes são então conectados logicamente por arestas orientadas (setas). Efetuar cada uma das ações requeridas nos elementos geométricos na seqüencia das setas corresponde à execução do algoritmo. O fluxograma a seguir ilustra um algoritmo simples para fazer uma viagem a cidade de Fortaleza (os retângulos representam ações e os losangos decisões). A construção de algoritmos via pseudocódigos é a preferencial deste texto. Nesta representação são usados recursos de linguagem natural, mas com quantidade bastante reduzida de vocábulos e estruturas para melhor assimilação. Os vocábulos desta metodologia são divididos em duas categorias: de aplicação pré- determinada, chamadas palavras reservadas e de definição customizada (durante criação do algoritmo), mas com regras pré-estabelecidas. Palavras reservadas podem ser comandos ou elementos de estruturas. Os comandos são invocações de tarefas específicas nos algoritmos, por exemplo, um comando de impressão deve imprimir uma mensagem de texto. A invocação de um comando é conhecida como chamada do comando. Os elementos de estruturas associam-se nas estruturas de controle para efetuar decisões ou repetições (dependendo do Ônibus Carona Como pagar? Ônibus ou de carona? Ir à fortaleza Dividir Gasolina À vista À prazo Usar cartão Sacar dinheiro Pegar o ônibus Chegar à Fortaleza Algoritmos Ricardo Reis 6 contexto). Importantes comandos e estruturas de controle serão estudados ao decorrer deste texto. As regras de sintaxe de um algoritmo tratam-se das restrições pré-estabelecidas para possibilitar a criação de pseudocódigos. Neste texto são definidas várias regras de sintaxe e mantidas até o final. É bom lembrar que tais regras não são universais, mas que em qualquer apresentação de metodologia algorítmica, um conjunto de regras de sintaxe se mostrará necessário para garantir concisão e clareza dos algoritmos. A palavra semântica será esporadicamente utilizada para se referir ao significado lógico dos elementos ou estruturas que constituem um algoritmo. Isso é importante porque muitas construções feitas não são intuitivas e a compreensão só será possível se houver prévio conhecimento do que elas se propõem a fazer. Algoritmos em pseudocódigo apresentam-se como um texto contendo diversas linhas de código. Uma mesma linha pode conter um ou mais comandos ou ainda estruturas de controle. Várias linhas de código podem estar encapsuladas por um conceito lógico denominado bloco. O código de um bloco possui dessa forma início e fim e representa um sub-processo do processo geral de execução do algoritmo. Veja o exemplo esquemático: //bloco de instruções instrução 1 instrução 2 instrução 3 Um mesmo algoritmo pode conter diversos blocos seriados ou blocos dentro de outros blocos. Se um bloco está dentro de outro dizemos que há aninhamento de blocos. O aninhamento é construído por indentação, ou seja, colocando-se recuos no texto-código para produzir uma hierarquia. Veja o exemplo esquemático: //bloco 1 instrução 1-1 instrução 1-2 // bloco 2 indentado instrução 2-1 instrução 2-2 instrução 2-3 instrução 1-3 Neste exemplo o bloco 2 é parte integrante do bloco 1, mas tem significado lógico independente dentro deste bloco e desta forma é indentado. Vários níveis de indentação são permitidos num mesmo pseudocódigo. Mais tarde será estudado como a indentação auxilia fortemente na legibilidade de algoritmos. Blocos também permitem a criação de módulos. Módulos são blocos do pseudocódigo com ações a executarem através de uma chamada, ou seja, são comandos personalizados. Um mesmo algoritmo pode possuir diversos módulos onde um deles, exatamente aquele onde a execução principia, é chamado bloco principal ou função principal. Até o estudo dos módulos, os pseudocódigos apresentados neste texto serão constituídos apenas do bloco principal. Algoritmos Ricardo Reis 7 O par de barras //, utilizado nos exemplos esquemáticos anteriores, marca a linha como comentário de forma que a mensagem que ele precede possui apenas valor informativo. 1.3. EXECUÇÃO DE ALGORITMOS Executar um algoritmo significa executar seqüencialmente cada uma das linhas que formam o bloco principal onde pode haver dezenas ou mesmo centenas de linhas. Não necessariamente todas as linhas serão processadas. Poderão ocorrer as seguintes possibilidades: (i) algumas linhas poderão ser saltadas; (ii) um grupo de linhas poderá ser diversas vezes repetido (iii) um comando ou módulo poderá ser chamado principiando o processamento de linhas de outro bloco processamento; (iv) a execução é encerrada porque a última linha foi executada ou porque foi suspenso explicitamente. O salto e a repetição em algoritmos serão estudados mais adiantes. Para suspender um algoritmo antes da última linha utilizaremos o comando pare, como segue. instrução 1 instrução 2 pare instrução 3 instrução 4 Neste exemplo a execução de pare implica suspensão imediata de processamento (sem realização das duas últimas linhas). Linhas são elementos construtivos de textos e normalmente tem significado impreciso em algoritmos. Ao invés de linhas consideraremos o conceito de instruções. Uma instrução corresponde a cada porção do pseudocódigo tomada para execução. Comumente há uma instrução por linha (o que torna linhas e instruções sinônimas), entretanto há instruções montadas normalmente utilizando mais de uma linha. No restante deste texto abordaremos algoritmos como listagens de instruções e não mais de linhas. Algoritmos Ricardo Reis 10 3. VARIÁVEIS 3.1. A MEMÓRIA PRINCIPAL E AS VARIÁVEIS A memória principal é a memória volátil do computador, ou seja, só armazenará alguma informação enquanto corrente elétrica cruzar seus circuitos (A memória projetada para manter informações, mesmo com o equipamento desligado, é a memória secundária, como por exemplo, os discos rígidos). Na memória principal serão colocados os programas para que sejam executados. Estes por sua vez precisarão de memória adicional para realizar suas tarefas. Nos computadores modernos muitos programas podem estar em execução ao mesmo tempo e assim concorrerem pela mesma memória livre no momento em que suas atividades requererem mais espaço. A problemática geral sobre o gerenciamento de memória em computadores é a seguinte: como impedir que programas distintos não sejam gravados na mesma área de memória e ainda, como impedir que eles concorram pela mesma região livre de memória no momento em que requerem espaço adicional? De fato esta responsabilidade é do sistema operacional através do gerenciador de memória. Os projetistas de um sistema operacional devem prever que os programas, que rodarão sobre ele, farão tais exigências em relação à memória principal. Tal delegação de controle da memória ao sistema operacional implica no seguinte fato: qualquer demanda por memória será resolvida mediante requisição formal ao sistema operacional mantendo-o sempre no controle da memória principal. Uma analogia deste comportamento é o funcionamento de alguns espaços para estacionamento de carros: o cliente faz a solicitação formal por uma vaga à entrada do estabelecimento. O funcionário na guarita (que trabalha como o gerenciador de memória) registra a entrada do cliente e marca como usada a vaga que ele preencherá. Quando ele volta e recolhe seu carro, espaço é liberado e o funcionário atualiza o status daquela vaga como livre. Se um cliente qualquer requer uma vaga não há risco de ser indicado a um lugar já ocupado. Na memória secundária os dados são gerenciados através de blocos de bytes chamados arquivos que se encontram em diretórios (pastas) estruturadas numa grande árvore de diretórios. Essa metodologia é transparente aos usuários de computadores os quais contam com as possibilidades de adicionar e remover arquivos e pastas. E na memória principal, como ocorre o gerenciamento? Cada processo (programa) consiste num conjunto de instruções gravadas numa parte da memória que foi requisitada ao sistema. O sistema busca por essa memória e a marca como ocupada numa tabela de controle. Quando o processo se encerra (fim da execução do programa) seu espaço é liberado removendo-se a marca da tabela: esta área agora está apta ao uso por outros processos. E quando cada processo requer por memória adicional? Neste caso instruções do próprio programa fazem a requisição de memória ao sistema operacional. Os programas devem dizer quanto precisam e o sistema responde marcando áreas livres de memória que assumirão e manterão o status de ocupadas enquanto estiverem sobre a tutela daquele processo que as requereu. E como os programas gerenciarão internamente cada bloco de memória requisitado? Para tanto existe um mecanismo denominado vinculação: ele consiste em ligar uma entidade abstrata interna definida no código do programa (pelo programador) a uma parte finita da memória. Tais entidades são denominadas variáveis do programa e a região a que são vinculadas de células de memória. Algoritmos Ricardo Reis 11 Um programa pode requerer quantas células de memória adicional precisar através do uso de variáveis. Cada variável conterá seu próprio nome e seu escopo (este conceito será abordado mais adiante). Devido ao caráter formal de requisição de memória as variáveis precisam ser referenciadas no programa antes de serem utilizadas. Esse referenciamento é denominado declaração de variáveis. Variáveis podem ser primitivas ou derivadas. As variáveis primitivas tratam da representação de dados elementares como números e caracteres. Existem categorias distintas de variáveis primitivas as quais se diferenciam basicamente pelo tipo de dados que se propõem a armazenar e pela faixa de representação destes dados. Variáveis derivadas (como os vetores) são aquelas constituídas por mais de um elemento primitivo e serão estudadas mais adiante. 3.2. OS TIPOS DE VARIÁVEIS São quatro os principais tipos primitivos de variáveis: Inteiros, Reais, Caracteres e Lógicos. A seguir fazemos a descrição de cada um. 3.2.1. TIPOS NUMÉRICOS: INTEIROS E REAIS É muito comum em programação de computadores o uso de valores numéricos. Eles dividem-se basicamente em dois grandes grupos: o dos inteiros e o dos reais. Freqüentemente há confusão entre o conceito de inteiros e reais em computação e em matemática. Nesta última tais definições correspondem a conjuntos com quantidade infinita de números além do fato de o conjunto dos inteiros ser contido no dos reais. Em computação valores inteiros e reais também representam conjuntos de números, mas neste caso de quantidade finita de elementos. Além do mais a idéia de inteiros contido nos reais não se aplica com exatidão neste caso. Analisaremos estes dois aspectos nos parágrafos seguintes. Por que há finitos inteiros e reais nos tipos numéricos dos computadores? A resposta é simples: cada célula de memória possui uma quantidade finita de bits. Assim cada número em base decimal é representado em circuito por um layout de um grupamento de bits (base binária) previamente vinculado a uma variável. De fato o que se faz é pré-estabelecer uma quantidade fixa de bytes para variáveis de um dado tipo e verificar que faixa de valores pode ser representada. Por exemplo, com 1-byte podem-se montar até no máximo 256 combinações de zeros e uns que poderão tanto representar números inteiros entre -128 e 127 (denominados inteiros de 1-byte com sinal) quanto de 0 a 255 (inteiros de 1-byte sem sinal). Para mais detalhes sobre bases numéricas e suas transformações o leitor pode consultar #. 3.2.2. TIPO CARACTERE A maior parte da informação em formato eletrônico contido nos computadores em todo mundo é textual, ou seja, é formada de caracteres das diversas linguagens naturais (português, inglês, francês, alemão etc.). É obviamente importante desenvolver métodos computacionais seguros que permitam o armazenamento e recuperação deste tipo de informação. Algoritmos Ricardo Reis 12 Como uma máquina intrinsecamente numérica pode armazenar texto? Na realidade qualquer informação registrada e recuperada por computadores será binária, e ainda, após um tratamento de conversão, por exemplo, binário para decimal, estas seqüências de bits se apresentarão como números inteiros. Então onde entram os caracteres? Estes são mantidos por tabelas existentes em várias categorias de softwares como editores de textos ou mesmo o próprio sistema operacional. Nestas tabelas há duas colunas relacionadas: na primeira encontram- se números normalmente inteiros sem sinal; na segunda um conjunto de grafemas de uma ou mais línguas naturais: são os caracteres. Nestas tabelas existe um único inteiro para cada caractere e vice-versa. As tabelas de caracteres podem ter tamanhos variados de acordo com a quantidade de bits dedicados a representação dos valores inteiros da primeira coluna. Com 1-byte, por exemplo, tem-se 8-bits e logo números entre 0 e 255: assim com 1-byte 256 caracteres distintos podem ser representados. Uma das mais comuns tabelas de caracteres utiliza 7-bits e denomina-se ASCII (American Standard Code for Information Interchange, que em português significa "Código Padrão Americano para o Intercâmbio de Informação”). Este padrão tem uso difundido em todo o mundo e é aceito praticamente por todos os softwares de edição de texto. Neste texto os algoritmos tomarão seus caracteres do padrão ASCII. A representação em pseudocódigo ora aparecerá como número (que neste caso está na faixa 0 a 27-1, ou seja, 0 a 127) ora aparecerá como o caractere propriamente dito (grafema). Neste último caso os grafemas correspondentes serão escritos sempre entre aspas simples (‘ ’). A seguir ilustramos parcialmente a tabela ASCII fazendo pares do valor numérico com o caractere (entre aspas simples) equivalente: 32 ' ' 48 '0' 64 '@' 80 'P' 96 '`' 112 'p' 33 '!' 49 '1' 65 'A' 81 'Q' 97 'a' 113 'q' 34 '"' 50 '2' 66 'B' 82 'R' 98 'b' 114 'r' 35 '#' 51 '3' 67 'C' 83 'S' 99 'c' 115 's' 36 '$' 52 '4' 68 'D' 84 'T' 100 'd' 116 't' 37 '%' 53 '5' 69 'E' 85 'U' 101 'e' 117 'u' 38 '&' 54 '6' 70 'F' 86 'V' 102 'f' 118 'v' 39 ''' 55 '7' 71 'G' 87 'W' 103 'g' 119 'w' 40 '(' 56 '8' 72 'H' 88 'X' 104 'h' 120 'x' 41 ')' 57 '9' 73 'I' 89 'Y' 105 'i' 121 'y' 42 '*' 58 ':' 74 'J' 90 'Z' 106 'j' 122 'z' 43 '+' 59 ';' 75 'K' 91 '[' 107 'k' 123 '{' 44 ',' 60 '<' 76 'L' 92 '\' 108 'l' 124 '|' 45 '-' 61 '=' 77 'M' 93 ']' 109 'm' 125 '}' 46 '.' 62 '>' 78 'N' 94 '^' 110 'n' 126 '~' 47 '/' 63 '?' 79 'O' 95 '_' 111 'o' 127 '
' Na prática muitos editores de texto simples salvam e recuperam seus arquivos de texto pela leitura byte a byte considerando cada um destes como um caractere ASCII: o oitavo bit obviamente não é representativo. Por englobar apenas 128 grafemas (27), ele é pouco representativo no que diz respeito às inúmeras línguas naturais e seus diversificados caracteres. A representação de letras acentuadas, por exemplo, em língua portuguesa não é suportada convenientemente em tal sistema. Por isso é muito comum encontrar fontes de dados em formato eletrônico (na internet, por exemplo) com erros de acentuação. Um sistema mais universal e mais complexo, o UNICODE, substitui progressivamente o ASCII na representação de caracteres. E como funcionam os tipos caracteres em programação? Cada variável declarada como caractere num programa armazena de fato um número inteiro. Na maioria Algoritmos Ricardo Reis 15 A próxima instrução executada é uma chamada a escreva. Ela não provoca espera, pelo contrário, envia à saída padrão (neste caso a tela) conteúdo textual. Neste exemplo a informação escrita tem duas partes separadas por uma vírgula: a primeira é uma mensagem de texto que será enviada para a tela tal como foi escrita; a segunda é uma referência a célula x e neste caso a CPU necessita recorrer à memória principal, buscar pelo conteúdo numérico em x, transformar este conteúdo em texto e por fim enviá-lo à saída padrão. De fato apenas uma mensagem de texto é enviada à saída padrão: se duas ou mais partes separadas por vírgulas estão presentes o processamento em série individual será feito, várias componentes textuais geradas e por fim concatenadas numa única a qual será enviada. O termo concatenação surge comumente em computação representando a fusão de informação numa só, normalmente textual. As vírgulas possuem papel importante tanto em leia como em escreva. Para o comando leia a vírgula permite leitura de vários valores em uma única chamada do comando. Veja o exemplo a seguir: declare x, y: inteiro leia x, y escreva ‘A soma vale =’, x+y A linha de instrução contendo leia neste exemplo é exatamente equivalente a duas chamadas ao comando, uma para x e outra para y, em linhas distintas, como em: leia x leia y Se na execução o usuário fornecer um valor e pressionar ENTER a execução não prosseguirá, pois leia aguarda por um segundo valor. Enquanto este não for digitado, confirmações com ENTER serão incapazes de permitir o prosseguimento. Em outras palavras: apesar de uma única chamada a leia, cada variável em sua lista (que são separadas por vírgulas) necessitará de sua própria confirmação. É possível digitar todos os valores pretendidos às variáveis e confirmar a entrada com um único ENTER? Sim. Neste caso todas as entradas devem ser digitadas numa única linha e separadas entre si por espaços. A seguir temos a saída obtida em tela para as duas abordagens descritas (<ENTER> apenas representa a tecla de confirmação sendo pressionada): 25 <ENTER> 32 <ENTER> A soma vale = 57 25 32 <ENTER> A soma vale = 57 Confirmações uma a uma Confirmação única A última linha impressa nos esquemas acima ilustra a flexibilidade do comando escreva. Ao passo que leia pode apenas manipular listas de variáveis, escreva pode manipular listas contendo mensagens, variáveis ou mesmo expressões. A expressão x+y do exemplo demanda da CPU processamento adicional que efetua a soma dos conteúdos das células x e y antes da conversão em texto e da concatenação. Mais detalhes sobre as expressões serão vistos mais adiante. O exemplo a seguir ilustra a leitura de um número e a exibição se seu quadrado: declare n: inteiro leia n Algoritmos Ricardo Reis 16 escreva n, ‘ ao quadrado vale ’, n*n Neste pseudocódigo o comando escreva concatena o valor de n, uma mensagem de texto e o valor da expressão, n*n (produto de n por n). Um exemplo de execução segue: 6 <ENTER> 6 ao quadrado vale 36 Caracteres podem ser lidos normalmente por leia e escritos normalmente por escreva. Entretanto alguns cuidados devem ser tomados. Se uma instrução como, leia c, com c caractere, é executada, muitos caracteres poderão ser escritos pelo usuário antes da confirmação: neste caso c só receberá o primeiro caractere e os demais serão desconsiderados. Se uma instrução como, escreva c, com c caractere é executada, será impresso um caractere contido em c, mas sem as aspas simples. Valores lógicos não podem ser lidos ou escritos diretamente com leia e escreva. Mais adiante analisaremos exemplos que, entretanto, permitem aos usuários modificarem ou inspecionarem variáveis deste tipo. Se o comando leia aguarda por valores numéricos e, por exemplo, texto é digitado, então uma conversão apropriada não poderá ser feita pela CPU e ocorrerá um erro em tempo de execução. Nesta abordagem sobre algoritmos, quando um erro ocorre necessariamente a execução é suspensa. Algoritmos Ricardo Reis 17 UNIDADE 2 4. OPERADORES Variáveis são vinculações com a memória real do computador e funcionam como meros armazenadores temporários de informação digital. Entretanto, para a construção de algoritmos funcionais, deve ser possível também operar entre si tais variáveis. Operar neste contexto pode significar tanto alterar o conteúdo de uma variável quanto associar duas ou mais destas numa expressão válida para se obter um novo valor (por exemplo, x+y envolve duas variáveis numa operação de soma cujo resultado é um novo valor). Operadores são objetos de construção de algoritmos, de simbologia própria e semântica bem definida, destinados às operações com ou entre variáveis. Por exemplo, na expressão, a+b, o símbolo + é um operador e sua semântica é a execução da soma entre os valores nas variáveis a e b. Operadores podem ser unários ou binários, ou seja, podem ou operar um ou dois operandos respectivamente. O exemplo mais comum de operador unário é o de mudança de sinal. A sintaxe é -x, onde o sinal de menos é o operador, x é a variável e o valor retornado é o valor na variável (numérica) com sinal invertido. Outro exemplo de operador unário é valor absoluto. A sintaxe é |x|, onde as duas barras verticais representam o operador, x é a variável e o valor retornado é o módulo do valor na variável (numérica). Operadores aritméticos são exemplos de operadores binários. Na expressão, a*b, o asterisco denota um operador binário operando as variáveis a e b e cuja semântica é a multiplicação numérica. Nesta expressão o valor retornando é o produto entre o conteúdo existente nessas variáveis. Operadores podem ser infixos, pré-fixos ou pós-fixos. Esta classificação refere- se à posição relativa dos operadores nas expressões em que aparecem. Por exemplo, em, a+b, o operador de adição, +, é infixo, ou seja, é disposto entre seus operandos. Na expressão de mudança de sinal, -a, o operador é pré-fixo, ou seja, disposto antes do operando. Na expressão de calculo de um fatorial, x!, o operador é pós-fixo, ou seja, é disposto depois do operando. Usualmente a maioria dos operadores binários é usada infixamente e dos unários pré-fixamente. Há situações em que operadores tradicionalmente infixos são utilizados como pré ou pós-fixação. Em notação polonesa, por exemplo, a expressão, AB+, é legal e denota a soma das variáveis A e B com operador de adição pós-fixado. Esta notação é conveniente aos computadores no que diz respeito a avaliação de expressões (úteis no projeto de compiladores, por exemplo). Operadores são funções, ou seja, ao invés da notação apresentada até então, uma dada operação pode ser expressa utilizando uma função nomeada com seus operandos entre parênteses e separados por vírgula. Assim, por exemplo, a expressão, SOMA(A, B), tem exatamente o mesmo efeito de, A+B. Na notação funcional o símbolo + é substituído pela função SOMA(). Em outras sintaxes propostas para algoritmos, ou mesmo em linguagens de programação, operadores são introduzidos apenas pela notação funcional. Se um operador não possui símbolo que permita prefixação, in-fixação ou pós-fixação, então a notação funcional é única opção. Algoritmos Ricardo Reis 20 mod Resto de divisão entre valores inteiros abs Módulo de valor numérico Todos os operadores, com exceção de abs, são usualmente binários e infixos O operador abs é unário e com notação funcional. Por exemplo, a expressão, abs(x), representa o módulo do valor em x. Os operadores, +, e, –, possuem também versões unárias e pré-fixas como nas expressões, +x-3 (ênfase de sinal), e, –a+b (inversão de sinal). O operador / é utilizado para dividir dois valores reais retornando um valor real de saída. Se algum dos operandos for inteiro então este será primeiramente convertido em real antes da divisão. Na expressão, a←b/c, se b e/ou c são inteiros, então eles são primeiramente convertidos em reais, depois divididos e o resultado da divisão atribuído a variável a. Se a é uma variável real, o valor integral da divisão é atribuído, por exemplo, se b contém 7 e c contém 2, então a receberá 3.5. Entretanto, se a é uma variável inteira ocorrerá truncamento, ou seja, o real oriundo da avaliação da expressão do lado direito da atribuição perderá a parte fracionária e o valor inteiro restante é atribuído à a. Neste caso o valor 3.5 é truncado para 3 para então haver atribuição. As expressões, a←b div c, e, a←b mod c, só serão legais se b e c forem variáveis inteiras. Se a for real, o inteiro oriundo da operação no lado direito será convertido em real para então ocorrer a atribuição. 4.3. OPERADORES RELACIONAIS Operadores relacionais são operadores binários e infixos cujo resultado da expressão que constituem é sempre um valor lógico, ou seja, Verdadeiro ou Falso. A tabela a seguir lista símbolos e nomes dos operadores relacionais utilizados neste estudo de algoritmos: Operadores Nomes = Igual a > Maior que < Menor que ≥ Maior ou igual a ≤ Menor ou igual a ≠ Diferente de A seguir alguns exemplos de expressões relacionais legais, ou seja, cada uma delas quando avaliada será Verdadeira ou Falsa. a > 100 400 ≤ y a+b ≠ c x+y < a+b Nos dois últimos casos acima o operador relacional contém em um dos lados (ou em ambos) expressões aritméticas. Esta sintaxe é perfeitamente legal e será analisada logo adiante. 4.4. OPERADORES LÓGICOS Algoritmos Ricardo Reis 21 Operadores lógicos são aqueles que operam valores lógicos e retornam valores lógicos. Utilizando a notação mais usual da lógica clássica, montamos a listagem dos operadores lógicos, juntamente com seus nomes conforme tabela a seguir. Operadores Nomes ∧ Conjunção ∨ Disjunção ⊕ Disjunção Exclusiva ¬ Negação Os operadores de conjunção, disjunção e disjunção exclusiva são todos binários e infixos ao passo que o de negação é unário e pré-fixo. A seguir algumas expressões lógicas legais: X ∨ Y B ⊕ (A ∧ B) (A ∨ B ∧ C) ∧ (¬A ⊕ C) Nos exemplos acima são utilizados apenas variáveis e operadores lógicos. As variáveis poderiam ser substituídas, por exemplo, por expressões relacionais. O resultado da avaliação destas expressões é também um valor lógico. Como cada variável do tipo lógico só assume dois valores, Falso ou Verdadeiro (F ou V) é possível listar todas as possibilidades de resposta de uma expressão lógica (em contrapartida às expressões numéricas com inúmeras possibilidades). Tais listagens são conhecidas como Tabelas-Verdade. A seguir são listadas as tabelas verdades para as expressões lógicas elementares (que possuem apenas um operador). A B A∧B A∨B A⊕B A ¬A F F F F F F V F V F V V V F V F F V V V V V V F 4.5. EXPRESSÕES Expressões podem ser constituídas pela associação de diversas variáveis de tipos não necessariamente compatíveis, mas que se arranjem de forma lógica e avaliável. Uma vez definidas tais expressões, a avaliação implica num processo sistemático que finaliza num valor final cujo tipo dependerá da expressão. Por exemplo, na expressão, x+1 > y-p*p, resolvem-se primeiramente as expressões aritméticas em cada lado do operador relacional para depois fazer a comparação que resultará num valor lógico. Este procedimento de escolha de “quem operar primeiro” numa expressão segue na verdade dois conjuntos de regras de operadores. São eles o de precedência de operadores e de associatividade de operadores. Os analisaremos a seguir. 4.5.1. PRECEDÊNCIA DE OPERADORES Nas primeiras lições sobre matemática ensina-se que numa expressão numérica primeiramente devem-se fazer as divisões e multiplicações para por fim fazer as adições e subtrações. Ensina-se também que se existem componentes entre parênteses elas são prioritárias na ordem de resolução. Sem tais regras uma expressão como, 2+4*7, seria ambígua, ou seja, com duas possibilidades de Algoritmos Ricardo Reis 22 resposta dependo de qual operação fosse realizada em primeiro lugar. Esta predefinição de quem opera primeiramente numa família de operadores é comumente chamada de precedência de operadores. A ordem convencional de precedência dos operadores aritméticos, do de maior para o de menor, é a seguinte: (maior precedência) abs +, – (unários) *, /, mod, div (menor precedência) +, - (binários) A precedência convencional dos operadores lógicos é a seguinte: (maior precedência) ¬ ∧ ∨ (menor precedência) ⊕ Por exemplo, na expressão, A⊕B∧¬C, o booleano C é primeiro invertido, depois a conjunção entre este valor e B é feita; por fim a disjunção exclusiva fecha o processo de avaliação e um valor final lógico é obtido. Convencionalmente não existe precedência entre operadores relacionais, o que será mais bem compreendido na sessão seguinte. 4.5.2. ASSOCIATIVIDADE DE OPERADORES Permitir a associatividade de operadores significa permitir que dois operadores de uma mesma família (aritmético, relacional ou lógico) e de mesma precedência apareçam adjacentes em uma mesma expressão sem afetar operabilidade. Por exemplo, na expressão, A+B-C, quem deve ser feita primeira? Adição ou subtração? A forma usual de resolver a associatividade é definindo um sentido fixo de avaliação; por exemplo, da direita para a esquerda (no exemplo anterior a subtração seria então feita primeiro). A associatividade nem sempre é possível. Para que dois operadores possam ser associados o tipo da saída do operador deve ser do mesmo tipo dos operandos, do contrário ocorrerá inconsistência. Por exemplo, a avaliação da expressão, A+B- C, da esquerda para a direita, possui o seguinte esquema: A+B-C <número>+<número>-<número> <número>+<número> <número> Cada redução na resolução acima transforma um par de números num novo número que entra na etapa seguinte da avaliação. De uma forma geral, operadores aritméticos são sempre associáveis. O mesmo não acontece na expressão, A>B>C, onde A, B e C são inteiros. O processo de avaliação desta expressão, da esquerda para direita, é interrompido por uma inconsistência, como se vê a seguir: A>B>C <número> > <número> > <número> Algoritmos Ricardo Reis 25 contrário ela não o será. A impressão da mensagem ‘fim da execução!’ não pertence ao processo de decisão (ver indentação) e logo ocorre incondicionalmente. 5.1.2. DECISÃO BIDIRECIONAL Na decisão bidirecional dois blocos de pseudocódigo competem para que um deles, e apenas um, seja executado. Caso a expressão booleana de controle seja avaliada como Verdadeira, então o primeiro bloco de pseudocódigo será executado, do contrário o segundo bloco que o será. A sintaxe básica da decisão bidirecional é: se (...) então ... senão ... Onde a primeira reticência entre parênteses refere-se à expressão booleana de controle, a segunda refere-se ao primeiro bloco de pseudocódigo e a terceira reticência refere-se ao segundo bloco de pseudocódigo. Veja o exemplo: declare num, x: inteiro leia num se (num mod 2 = 0) então x ← num div 2 escreva x senão x ← (num+1) div 2 escreva x + 1 As linhas com as palavras-chave se e senão são colocadas no mesmo nível de indentação para acusar que fazem parte da mesma estrutura. Os blocos encapsulados são dispostos um nível de indentação acima estando o primeiro antes e o segundo após o senão. Se a expressão booleana de controle, num mod 2=0, é avaliada como verdadeira então x recebe o resultado na expressão, num div 2, e tem em seguida o valor impresso. Do contrário x recebe o resultado da expressão, (num+1) div 2, e o valor, x+1, é que é impresso. Apenas uma atribuição explícita e uma impressão ocorrem. Outro exemplo: declare n: inteiro leia n se (n mod 2 = 0) então escreva ‘número par!’ senão escreva ‘número ímpar!’ Cada um dos blocos no algoritmo anterior é constituído por uma única linha de instrução. Estudo de caso – Existência de Triângulo: Consideremos agora o algoritmo que determina se um triângulo existe ou não. Há duas maneiras de abordar o problema: (I) pode-se testar se cada um dos lados é menor que a soma dos outros dois e (II) pode- Algoritmos Ricardo Reis 26 se testar se um lado qualquer é menor que soma dos outros dois e maior que o módulo da subtração entre os mesmos. O algoritmo para (I) será: declare a, b, c: inteiro leia a, b, c se (a<b+c ∧ b<a+c ∧ c<a+b) então escreva ‘O triâmgulo existe!’ senão escreva ‘O triângulo não existe!’ A única diferença para o caso (II) está na expressão booleana de decisão que deve se tornar: a<b+c ∧ a>abs(b-c) O caso (I) ilustra o uso das expressões booleanas e a importância dos operadores lógicos quando expressões relacionais precisam ser conectadas. O caso (II) reafirma o caso (I) e ilustra o uso do operador módulo, abs, em componentes aritméticas de expressões booleanas. 5.1.3. DECISÃO MÚLTIPLA Em algoritmos, a decisão múltipla é um processo de decisão que envolve muitas entradas, ou seja, entre várias rotas possíveis de código será escolhida uma, e apenas uma, para ser executada. Devido à natureza binária das expressões booleanas, elas não se aplicam em processos da decisão múltipla. Ao invés disso é utilizada uma expressão aritmética com valor resultante inteiro (usualmente expressões de controle aparecem como uma única variável de tipo inteiro conhecida como variável de controle). Espera-se naturalmente da expressão de controle que o valor proveniente da avaliação esteja numa faixa finita de valores inteiros. Cada um destes valores deve conduzir ao seu próprio bloco de código. Se a avaliação resulta um valor fora da faixa então nenhum bloco é executado e o processo de decisão encerrado. Blocos em decisões múltiplas precisam de um rótulo para indicar onde principiam. O rótulo deve conter o valor inteiro esperado pela avaliação da expressão de controle que induza a execução do bloco que rotula. A estrutura de decisão múltipla, conhecida como caso...seja..., possui a seguinte sintaxe geral: caso <varável ou expressão de controle> seja <rótulo 1>: <bloco 1> <rótulo 2>: <bloco 2> ... <rótulo n>: <bloco n> Cada rótulo da estrutura acima possui o próprio bloco e é separado dele pela marca, : (dois pontos). Todos os rótulos são dispostos um nível de indentação acima no nível onde esta a palavra chave seja. Blocos dispõem-se um nível de indentação acima daquele onde estão os rótulos. Em síntese, após a avaliação da expressão (ou variável) de controle um valor inteiro é obtido, o rótulo com este valor selecionado e por fim o bloco executado. Quando a execução encerra, ocorre um desvio para fora da estrutura para que outros blocos não sejam executados. O exemplo a seguir ilustra a estrutura caso...seja: Algoritmos Ricardo Reis 27 declare n: inteiro leia n caso (n) seja 1: escreva ‘Olá mundo!’ 2: escreva ‘Hello world!’ 3: escreva ‘Hallo Welt!’ A execução deste pseudocódigo implica impressão de uma entre três mensagens (caso o valor em n seja 1, 2 ou 3) ou em finalização sem impressão alguma (caso outros valores sejam fornecidos). Nunca duas mensagens são simultaneamente impressas. A estrutura caso..seja pode ser estendida na sintaxe seguinte: caso <varável ou expressão de controle> seja <rótulo 1>: <bloco 1> <rótulo 2>: <bloco 2> ... <rótulo n>: <bloco n> senão <bloco n+1> A palavra chave senão funciona neste contexto como um rótulo alternativo a todos os valores não rotulados anteriormente. Ou seja, se a avaliação da variável ou expressão de controle resulta um valor fora da faixa dos rótulos, então o bloco n+1 será executado. Neste contexto sempre algum bloco é executado. Uma prática bastante comum é o uso da sessão senão para imprimir mensagens de erro. Veja o exemplo: declare n: inteiro leia n caso (n) seja 1: escreva ‘Olá mundo!’ 2: escreva ‘Hello world!’ 3: escreva ‘Hallo Welt!’ senão escreva ‘Opção inválida!!’ Se for fornecido a variável n um valor diferente de 1, 2 e 3 então a mensagem de erro ‘Opção inválida!!’ será impressa. O exemplo a seguir contém blocos, numa estrutura caso..seja, com mais de uma linha de instrução: declare ch: caractere raio, base, altura, lado: inteiro escreva ‘pressione: C para cículo, T para triângulo, Q para quadrado’ ch ← tecla caso ch seja ‘C’: escreva ‘Valor do raio:’ leia raio escreva ‘área = ’, 3.14159235*raio*raio ‘T’: escreva ‘Valores da base e da altura: ’ leia base, altura escreva ‘área = ’, base*altura/2 ‘Q’: escreva ‘Valor do lado: ’ leia lado escreva ‘área = ’, lado*lado senão escreva ‘Opção inválida!!’ Algoritmos Ricardo Reis 30 estará obviamente em B ou C. Assim se o valor em B é menor que em C, B contém o menor, do contrário, C é que contém. Uma das três atribuições ocorrerá devido aos testes de decisão e colocará na variável menor a solução. Estudo de Caso – Equação do Segundo Grau: Uma equação do segundo grau tem forma, a⋅x2 + b⋅x + c = 0, onde a, b e c são coeficientes constantes e x a variável independente. Tais equações possuem raízes reais se o coeficiente a é não nulo e ainda se ∆ é maior ou igual a zero, onde, ∆ = b2 - 4⋅a⋅c. O algoritmo seguinte resolve o problema de determinação das raízes de uma equação de segundo grau cujos coeficientes são fornecidos via entrada padrão: declare a, b, c, delta, x0, x1: real escreva ‘Forneça coeficientes da equação: ’ leia a, b, c se (a≠0) então delta ← b*b – 4*a*c se (delta≥0) então x0 ← (-b + raiz(delta))/(2*a) x1 ← (-b - raiz(delta))/(2*a) escreva ‘Raízes: ’, x0, x1 senão escreva ‘Raízes Complexas!’ senão escreva ‘A equação não é de segundo grau!’ Neste algoritmo o primeiro processo de decisão verifica nulidade do coeficiente em a. Se o valor em a é nulo a mensagem ‘A equação não é de segundo grau!’ é impressa e o algoritmo se encerra. Caso não seja nulo significa que se trata de uma equação de segundo grau e que o primeiro bloco indentado será executado. Este bloco inicia com o calculo do delta da equação o qual é colocado na variável delta. Com este valor um novo processo de decisão é iniciado (aninhamento de decisão) o qual trata da existência de raízes reais. Se o valor em delta é maior ou igual a zero então as raízes são calculadas (a função raiz() calcula a raiz quadrada de um valor real), impressas e o processo finalizado. Do contrário a mensagem ‘Raízes Complexes!’ é impressa e o algoritmo se encerra. Estudo de Caso – Tipo de Triângulo em Relação aos Lados: Um triângulo pode possuir os três lados idênticos (eqüilátero), dois lados idênticos e o terceiro diferente (isósceles) e os três lados diferentes (escaleno). O algoritmo seguinte resolve o problema de determinação do tipo de um triângulo cujos lados são fornecidos via entrada padrão: declare a, b, c: inteiro leia a, b, c se (a<b+c ∧ b<a+c ∧ c<a+b) então se (a=b ∧ a=c) então escreva ‘Eqüilátero!’ senão se (a=b ∨ a=c ∨ b=c) então escreva ‘Isósceles!’ senão escreva ‘Escaleno!’ senão escreva ‘O triângulo não existe!’ Algoritmos Ricardo Reis 31 Este algoritmo possui três níveis de indentação de decisões aninhadas. O primeiro avalia a existência do triângulo exibindo a mensagem ‘O triângulo não existe!’ caso os lados (lidos através das variáveis a, b e c na entrada padrão) não formem um triângulo válido. Se o triângulo existe o processo de decisão do segundo nível de indentação decide entre triângulos eqüiláteros e não eqüiláteros. Caso seja, a mensagem ‘Equilátero!’ é impressa e o algoritmo se encerra. Caso não, outro processo de decisão se inicia no terceiro nível de indentação o qual decidirá se o triângulo não-equilátero é isósceles ou escaleno. Para ser isósceles basta haver igualdade de pelo menos um par de lados (por isso a expressão booleana, a=b ∨ a=c ∨ b=c). Neste caso a mensagem ‘Isósceles!’ é impressa e o algoritmo finaliza. Do contrário (nenhum par de lados se iguala) a mensagem ‘Escaleno!’ é impressa e o algoritmo se encerra. 5.2. REPETIÇÃO As estruturas de decisão permitem a modelagem de apenas parte dos problemas resolvidos por algoritmos. As estruturas de controle de repetição estendem largamente esta capacidade de modelagem. Elas fornecem meios de repetição de execução de blocos de códigos específicos. A associação entre capacidades de decisão e repetição constitui prática comum na construção de algoritmos. Uma estrutura de controle de repetição encapsula apenas um bloco de código e o repete mediante um critério que notavelmente muda durante o processo (Naturalmente este bloco pode conter internamente outros blocos com nível de indentação acima e que também terão execução repetida). Cada repetição é conhecida como iteração. Estruturas de repetição são comumente chamadas de laços ou loops. A seguir são estudadas as principais estruturas de laços utilizadas na construção de algoritmos. 5.2.1. LAÇOS CONTROLADOS POR CONTADOR Um laço é controlado por contador quando uma variável auxiliar, chamada contador, usualmente de tipo inteiro, é responsável pela contabilização das iterações. A estrutura de controle para laço com contador é, para...até...faça, e possui a seguinte sintaxe geral: para <contador> ← <limite inferior> até <limite superio> faça <bloco> Esta estrutura efetua a repetição sistemática do código presente no bloco encapsulado posto nas linhas logo abaixo do cabeçalho da estrutura e indentado um nível acima deste. A execução deste laço se faz pela progressão aritmética do contador desde o limite inferior ate o limite superior. Esta progressão é automática e acrescenta uma unidade ao contador ao final de cada iteração. Conseqüentemente em cada iteração todo o bloco encapsulado executa com o mesmo valor de contador que terá uma unidade a mais na iteração seguinte. Quando o laço encerra o último valor atribuído a variável de contagem é o do limite superior. O operador ← é constituinte desta estrutura enfatizando que em cada iteração do laço ocorre uma atribuição (ao contador). O exemplo a seguir ilustra o uso desta estrutura: declare i: inteiro para i ← 1 até 100 faça escreva i Algoritmos Ricardo Reis 32 A execução deste algoritmo imprime os números de 1 a 100 na saída padrão. O bloco da estrutura é formado por uma única linha de instrução. Um outro exemplo: declare i, x: inteiro para i ← 1 até 50 faça x ← 2*i escreva x A execução deste algoritmo imprime na saída padrão os números pares entre 2 e 100. Em cada iteração o valor em x é recalculado em função do valor do contador i. Uma alternativa sintática ao laço com contador, e que melhora o desempenho de muitos algoritmos, é o uso do passo. Por definição o passo é um valor inteiro que deve ser somado ao contador quando encerrar uma iteração de laço e iniciar outra. O passo nos laços mostrados anteriormente valem 1. A sintática básica do laço com contador e passo é a seguinte: para <contador> ← <limite inferior>, <limite superio>, <passo> faça <bloco de pseudocódigo> As mudanças nesta nova versão em relação a anterior foram: removeu-se a palavra chave até e no seu lugar colocou-se uma vírgula; após o limite superior marcou-se uma nova vírgula seguindo-a com o valor do passo; por fim a palavra chave faça. O exemplo dos números pares pode ser reescrito da seguinte forma: declare i: inteiro para i ← 2, 100, 2 faça escreva i Neste algoritmo o contador i inicia com valor 2 e em cada iteração é incrementado de 2 (passo) até atingir 100. Note que dependendo do passo o contador pode passar por cima do limite superior. Quando isso acontece o laço encerra naturalmente quando o contador atinge o primeiro valor acima do limite superior, mas sem processá-lo. Exemplo: declare i: inteiro para i ← 7, 30, 3 faça escreva i, ‘ ’ Este laço imprimirá: 7 10 13 16 19 22 25 28 O valor 31 não será impresso porque extrapola o limite superior do laço. Quando o valor do passo é negativo é possível montar laços com contador decrescente porque neste caso ocorre sucessivamente a subtração ao invés da adição. Exemplo: declare i: inteiro para i ← 20, 0, -1 faça escreva i, ‘ ’ Algoritmos Ricardo Reis 35 ocorrer do contrário o laço deverá encerrar-se. Nenhuma instrução do bloco é executada se na primeira avaliação o resultado for Falso. Segue um exemplo: declare x: inteiro x ← 0 enquanto (x<20) faça escreva x, ‘ ’ x ← x + 2 Neste algoritmo, enquanto a expressão, x<20, for Verdadeira as duas instruções encapsuladas serão executadas. É importante observar que a variável n funciona como contador, apesar de não ser integrante da estrutura. Por essa razão o valor nesta variável precisa ser explicitamente inicializado fora do laço (x←0, na terceira linha) e modificado manualmente dentro do laço (x←x+2, na última linha). A saída deste algoritmo é a seguinte: 0 2 4 6 8 10 12 14 16 18 O valor 20 não é impresso porque não satisfaz a expressão booleana (20 é igual a 20 e não menor). Observe que, ao contrário do que ocorre nos laços por contador, é possível mudar o local onde a variável de controle se modifica. Se, por exemplo, as duas linhas do bloco encapsuladas por enquanto no algoritmo anterior fossem trocadas de posição o código ainda seria válido, mas a saída impressa se modificaria para: 2 4 6 8 10 12 14 16 18 20 Esta saída deixa de imprimir o 0 e imprime 20 simplesmente porque as impressões agora vêem depois da modificação da variável x.. Laços de pós-teste são aqueles que ao final de cada iteração realizam um teste para determinar sua continuidade. A estrutura de controle para pós-teste é, repita...até, e possui sintaxe geral como segue: repita <bloco> até <expressão booleana> A semântica funcional desta estrutura é descrita a seguir. O bloco encapsulado é repetido diversas vezes (iterações). Após o final de cada iteração a expressão booleana à saída é avaliada. Se seu valor for Falso significa que a próxima iteração deverá ocorrer do contrário o laço deverá encerrar-se. O bloco encapsulado é executado pelo menor uma vez independente da expressão booleana. Ao passo que a estrutura enquanto...faça executa código enquanto algo é verdade, repita..até executa código até que algo seja verdade. Segue um exemplo: declare x: inteiro x ← 0 repita escreva x, ‘ ’ x ← x + 2 até (x>20) Algoritmos Ricardo Reis 36 O funcionamento deste algoritmo e similar ao último algoritmo com pré-teste apresentado. Como o teste fica na saída, o valor em x é sempre impresso na primeira iteração (mesmo que fosse maior que 20). O laço só é interrompido quando o valor em x atinge 22 (o qual não é impresso).A saída deste algoritmo é: 0 2 4 6 8 10 12 14 16 18 20 5.2.3. ANINHAMENTO DE LAÇOS Aninhar laços significa encapsular laços dentro de outros. Se um laço A é encapsulado por um laço B então para cada iteração de B o laço A efetuará sistematicamente todas suas possíveis iterações naquele contexto. Por exemplo: declare i, j: inteiro para i ← 1 até 10 faça para j ← 1 até 10 faça escreva i+j Os dois laços no algoritmo anterior são construídos para executar 10 vezes cada. O primeiro tem contador em i e o segundo contador em j. Entretanto o primeiro lado encapsula o segundo laço (posto um nível de indentação acima). Isso faz com que cada iteração do primeiro laço execute todas as 10 iterações do segundo laço e conseqüentemente execute 100 vezes a instrução escreva (posta um nível de indentação acima do segundo laço). Os limites dos contadores dos laços podem ser expressos como função de qualquer variável inteira do programa (exceto o próprio contador). Isso inclui também os contadores de laços hierarquicamente acima em um dado aninhamento. Veja o exemplo: declare i, j, cnt: inteiro cnt ← 0 para i ← 1 até 10 faça para j ← i até 10 faça cnt ← cnt + 1 escreva cnt Neste algoritmo o segundo laço é aninhado no primeiro. O limite inferior do segundo laço (de contador j) é o valor corrente do contador do primeiro laço, i. À proporção que o primeiro laço avança o número de iterações do segundo laço diminui como indica a tabela a seguir: Valor de i 1 2 3 4 5 6 7 8 9 10 Número de iterações do segundo laço 10 9 8 7 6 5 4 3 2 1 O algoritmo utiliza acumulação por soma para guardar na variável cnt o total de iterações. Este valor também pode ser calculado pela somatória dos valores na segunda linha da tabela anterior, ou seja, 10+9+8+7...+1 = 55. Este será o valor impresso na saída padrão. Não há restrições sobre os tipos de estruturas de repetição aninhadas. Assim, por exemplo, laços de contagem podem estar aninhados a laços de teste ou vice-versa. Também não há restrições sobre aninhamento entre estruturas de decisão e de Algoritmos Ricardo Reis 37 repetição. De fato a associação coerente de todas estas estruturas é que possibilita a criação de algoritmos aplicáveis. 5.2.4. QUEBRA E CONTINUAÇÃO DE LAÇOS Um laço controlado por teste é denominado laço infinito quando a expressão booleana de controle é sempre avaliada como Verdadeira (no caso de enquanto...faça) ou sempre como Falsa (no caso de repita...até). Laços infinitos são aplicados em situações onde o critério de parada não se encaixa na entrada (ou na saída) do laço. Quando instruções internas ao bloco de laço promovem sua suspensão forçada (sem uso da expressão booleana de controle) diz-se que houve quebra de laço. Uma quebra de laço é construída utilizando o comando pare. Veja o exemplo: declare ch: caractere enquanto (V) faça ch ← tecla caso (ch) seja ‘x’: escreva ‘olá mundo!!’ ‘y’: escreva ‘hello world!’ ‘z’: escreva ‘hallo Welt!!’ senão pare No algoritmo anterior o laço construído com enquanto é infinito devido à expressão de controle ter sido substituída por um V (Verdadeiro). Em cada iteração uma tecla é solicitada pelo comando tecla e seu caractere armazenado na variável ch. Caso o valor em ch seja ‘x’, ‘y’ ou ‘z’ então uma de três mensagens é enviada a saída padrão e o laço inicia novamente com nova solicitação de tecla. Se a tecla pressionada não é nenhuma das três então o pare do bloco rotulado senão é executado suspendendo o laço. As regras de funcionamento do comando pare são as seguintes: • Se pare for executado fora de laços, mesmo encapsulado por alguma estrutura de decisão, ocorrerá suspensão da execução do algoritmo como um todo. • Se pare for executado dentro de um laço sem aninhamento com outros laços, mesmo que esteja encapsulado por alguma estrutura de decisão, apenas tal laço será suspenso, mas o algoritmo não necessariamente. • Se pare for executado em um aninhamento de laços, mesmo havendo aninhamento de estruturas de decisão, apenas o laço hierarquicamente mais próximo a este comando será suspenso, mas o algoritmo não necessariamente. Estudo de Caso – Números Primos: Um número primo é aquele que é divisível apenas por um e por ele mesmo. Como um número não é divisível pelos que o sucedem é razoável acreditar que um dado inteiro n, que se quer testar se é primo ou não, deva ser dividido pelos números no intervalo fechado [2, n-1] sendo primo se todas estas divisões obtiverem resto não nulo e não primo se pelo menos uma for nula (encontrada uma divisão com resto nulo o número não é mais primo e as demais divisões, se ainda restarem, tornam-se desnecessárias). Matematicamente, entretanto, tantas divisões não são necessárias Um intervalo suficiente de testes pode ser reduzido para [2, d] tal que d2 ≤ n. Com base no critério anunciado acima foi construído um algoritmo capaz de escrever, na saída padrão, todos os números primos menores que cinco mil. Segue: Algoritmos Ricardo Reis 40 vetor. Encontrado o bloco ele é então marcado como usado e vinculado a variável vetor no programa. Seja, por exemplo, um vetor formado de 50 células de inteiros de 2-bytes vinculado à variável X. Assim, após alocação, um bloco de 100 bytes estará vinculado a X e as 50 células poderão ser acessadas independentemente por X[1], X[2], X[3],..., X[50]. O único endereço real disponível é o do início do bloco de memória (chamaremos ξ). E o de cada célula? Como funciona uma chamada a X[k], com k inteiro e entre 1 e 50? A resposta é simples: através de aritmética elementar, ou seja, manipular X[k] significa manipular diretamente o conteúdo no endereço de memória ξ+(k-1)⋅2. O acesso a células individuais via vetores é o mais eficaz se comparada a outras formas de armazenamento linear (como listas encadeadas). E as matrizes de mais de uma dimensão? Também tem células contiguas em memória? A resposta é sim. Quando mais de uma dimensão está envolvida a memória total utilizada será o produto entre o tamanho do tipo base e todos os comprimentos das dimensões. Por exemplo, seja Q uma matriz bidimensional 3×3 de inteiros como segue: |12 -7 14| |1 -9 -5| |11 78 25| Se Q é composto por inteiros de 2-bytes então o bloco de memória alocado terá 18 bytes. O aspecto em memória (mais comumente adotado) para o exemplo anterior é: 12 -7 14 1 -9 -5 11 78 25 6.3. DECLARAÇÃO, INICIALIZAÇÃO E USO DE VETORES A sintaxe geral para declaração de vetores é a seguinte: declare <variável>[comprimento]: <tipo> Segue um exemplo: declare M[20], i: inteiro para i ← 1 até 20 faça M[i] ← i*i Neste código duas variáveis são declaradas: um inteiro i e um vetor de inteiros M. A variável M comporta vinte valores inteiros e é utilizada para armazenar, por ação de um laço, os quadrados dos números de um a vinte. Vale observar que o contador i do laço funciona tanto como índice do vetor quanto como componente de expressão. Há duas aplicações para o par de colchetes. A primeira é declarativa, ou seja, eles abrigam o comprimento do vetor declarado conforme se verifica na definição da sintaxe geral. A segunda é evocativa, ou seja, o conteúdo entre os colchetes é um valor de índice entre 1 e seu comprimento (definido na declaração) e possibilita o acesso a uma célula específica do vetor. Tal acesso permite tanto leitura quanto modificação do que está na célula indexada. Algoritmos Ricardo Reis 41 Consideremos o exemplo seguinte: declare M[10], i, imax: inteiro para i ← 1 até 10 faça leia M[i] imax ← 1 para i ← 2 até 10 faça se (M[i] > M[imax]) então imax ← i escreva M[imax] Este algoritmo solicita dez valores do usuário e imprime como saída o maior entre eles. O primeiro laço é o responsável pela entrada de dados. Em cada iteração o comando leia modifica uma célula distinta do vetor M de modo a preenchê-lo convenientemente. O restante do código é um processo de busca. Tal busca começa com a hipótese de que o maior valor está na primeira posição (assim imax recebe 1). As demais posições são testadas progressivamente pelo laço para: cada vez que uma célula verificada possui valor maior que aquele de índice imax, então imax recebe o valor do contador. Quando o laço encerra imax possui a posição contendo o maior valor e assim M[imax] é impresso. Não há aninhamento de laços neste exemplo e por essa razão os dois laços estão no mesmo nível de indentação. Apesar de não estar disponível na maioria das linguagens de programação introduzimos nessa abordagem uma opção de inicialização de vetores diretamente do código. A sintaxe geral é a seguinte: declare <variável_1>[c1]: <tipo> //... <variável_1> ← {<valo1_1>, <valo1_2>, <valo1_3>,..., <valo1_c1>} //... Um exemplo de aplicação: declare M[10], i, imax: inteiro M ← {12, -9, 33, 8, -23, 17, 6, -5, 31, 2} imax ← 1 para i ← 2 até 10 faça se (M[i] > M[imax]) então imax ← i escreva M[imax] Nesta sintaxe de inicialização de vetores, o par de colchetes não é necessário, as chaves (que envolvem os elementos) são obrigatórias e ainda deve haver vírgulas entre os elementos. A execução deste algoritmo imprime 33 na saída padrão. Estudo de Caso – Dois maiores Valores de um Vetor. O algoritmo seguinte encontra num vetor dado os dois maiores valores que ele contém. declare M[10], i, im1, im2: inteiro M ← {-12, 9, 30, 18, 13, 7, -6, 5, 31, 1} im1 ← 1 im2 ← 2 Algoritmos Ricardo Reis 42 se (M[im1] < M[im2]) então i ← im1 im1 ← im2 im2 ← i para i ← 3 até 10 faça se (M[i] > M[im1]) então im2 ← im1 im1 ← i senão se (M[i] > M[im2]) im2 ← i escreva M[im1], ‘ e ’, M[im2] Este algoritmo modifica im1 e im2 para conterem respectivamente, no final do processo, os índices do maior e do segundo maior valor em M. A primeira hipótese feita no algoritmo é a de que o maior valor está na posição 1 e o segundo maior está na posição 2.(atribuições, im1←1 e im2←2). No passo seguinte a estrutura de decisão, se, verifica e possivelmente corrige esta hipótese (troca de valores) considerando apenas os dois primeiros valores em M. As demais posições do vetor (3 a 10) são verificadas no laço para e tratadas da seguinte forma: quando contiverem um valor maior que o maior até então (em im1) então a nova posição do segundo maior valor passa a ser a em im1 (im2←im1) e a nova posição do maior valor passa a ser a do contador (im1←i); mas se o valor em i não for maior que aquele em im2, então ainda poderá ser maior que aquele em im2 e neste caso faz-se, im2←i. As variáveis im1 e im2 valem no final respectivamente 9 e 3 e a mensagem impressa é ’31 e 30’. Estudo de Caso – Ordenação de Vetores. O algoritmo seguinte implementa a ordenação de vetores pelo método da seleção: declare M[10], i, j, t, x: inteiro M ← {-12, 9, 30, 18, 13, 7, -6, 5, 31, 1} //Ordenação por seleção: para i ← 1 até 9 faça t ← i para j ← i+1 até 10 faça se (M[j] < M[t]) então t ← j x ← M[t] M[t] ← M[i] M[i] ← x // Impressão: para i ← 1 até 10 faça escreva M[i] A ordenação por seleção é construída pelo aninhamento de dois laços. O laço externo percorre o vetor da primeira à penúltima posição. O laço interno busca pela posição, entre a posição corrente do laço externo e o fim do vetor, contendo o menor valor. Esta busca usa a variável t e principia com a hipótese de que o menor valor tem posição em i (assim, t←i). A execução do laço interno (e conseqüentemente de seus testes de decisão) modifica t (possivelmente) para conter o índice do menor valor entre o valor em i e 10 (observe que este laço inicia em i+1 para excluir a hipótese inicial). As últimas três linhas do laço externo (a indentação mostra que elas não fazem parte do laço interno) fazem a troca entre o elemento na posição em t e aquele na posição em i, ou seja, na posição em i fica o menor elemento do intervalo [i corrente, 10]. O laço externo provoca 9 processos de busca que acabam por ordenar o vetor. O último elemento do Algoritmos Ricardo Reis 45 Neste algoritmo a cadeia é impressa caractere a caractere sendo um caractere por iteração de laço. Cada um dos caracteres é denotado pela expressão S[i] como convém a qualquer vetor. Se o nulo é encontrado, então o laço para (não é impresso). Outra aplicação de leitura caractere a caractere de uma cadeia é mostrada a seguir: declare S[100]: caractere t, i: inteiro leia S t ← 0 enquanto (S[t+1] ≠ φ) faça t ← t+1 para i ← t, 1, -1 faça escreva S[i] Este algoritmo recebe uma cadeia via entrada padrão e a escreve de trás para frente. A idéia é medir primeiramente o comprimento da cadeia usando a variável t cujo valor inicial é zero. Com o fim do primeiro laço (enquanto) t conterá o comprimento da cadeia e um laço por contagem (para) poderá fazer o trajeto reverso do vetor a fim de imprimi-lo de trás para frente. 6.5. VETORES DINÂMICOS Todas as declarações de vetores nas sessões anteriores possuíam vinculação estática de espaço em memória, ou seja, o tamanho que o vetor possuirá em tempo de execução precisa ser definido no código pelo programador. O efeito direto disso é a inflexibilidade, ou seja, se mais memória for necessária não será possível expandir o vetor durante a execução. Para resolver esta limitação, introduzimos os comandos alocar e limpar. Eles interagem diretamente com o gerenciador de memória requisitando e devolvendo respectivamente quantidades de memória. Cada solicitação de memória com alocar está associada a uma devolução com limpar. Memória não devolvida mantém o status de ocupada não podendo ser usada por outros processos. Em máquinas reais, a ocorrência desse quadro causa queda de desempenho ou mesmo parada do sistema (crash). Denominamos vetor dinâmico ao vetor com capacidade de definir seu comprimento em tempo de execução. A sintaxe geral de um vetor dinâmico é a seguinte: declare <vetor>[]: <tipo base> A diferença para vetores estáticos é a ausência de um comprimento entre os colchetes. Exemplos: declare X[]: inteiro VET[]: inteiro Para alocar e limpar memória de um vetor dinâmico utiliza-se respectivamente os comandos alocar e limpar. A sintaxe básica segue: alocar <vetor>[<comprimento>] ... limpar <vetor> Algoritmos Ricardo Reis 46 O exemplo a seguir ilustra o uso de vetores dinâmicos: declare X[], n, i: inteiro leia n alocar X[n] para i ← 1 até n faça X[i] ← 2*i-1 limpar X No exemplo acima o vetor dinâmico X tem seu comprimento alocado com um valor de comprimento, n, fornecido via entrada padrão. Após a alocação o vetor é carregado com a máxima quantidade de números ímpares que suporta e finalmente desalocado ao final. Estudo de Caso – Números Pandigitais: um número natural é denominado pandigital se seus algarismos forem todos distintos entre si. O algoritmo seguinte determina se um valor fornecido pelo usuário é ou não pandigital: declare Q[], t, n, i, j: inteiro b: lógico leia n // PARTE I t ← 0 j ← n enquanto (j>0) faça t ← t + 1 j ← j div 10 // PARTE II alocar Q[t] // PARTE III j ← n para i ← t, 1, -1 faça Q[i] ← j div 10 j ← j div 10 // PARTE IV b ← V para i ← 1 até t-1 faça para j ← i+1 até t faça se (Q[i] = Q[j]) então b ← F pare se (¬ b) então pare // PARTE V se (b) então escreva ‘o número é pandigital!’ senão escreva ‘o número NÃO é pandigital!’ limpar Q O algoritmo anterior é seccionado em seis partes explicadas a seguir. (I) O comprimento em dígitos do valor em n é medido. Isso é feito pelo laço enquanto que, utilizando uma cópia de n, neste caso em j, efetua sucessivas divisões por dez. Obviamente este laço se encerra quando um total de iterações igual ao número de dígitos do valor em n é realizado (o que conduz j a zero e logo ao Algoritmos Ricardo Reis 47 encerramento do laço). Haja vista que t é anulado fora do laço e incrementa em um em cada iteração deste, então o valor final de t é o comprimento em dígitos do valor em n. (II) O vetor Q tem seu espaço alocado. A estratégia é dedicar uma célula para cada dígito do valor em n. (III) Os dígitos do valor em n são dispostos no vetor Q. Para realizar tal tarefa, novamente uma cópia de n é feita em j que mais uma vez, por cíclicas operações de divisão por dez, é reduzido à zero. O laço não é mais por teste e sim de contagem com t iterações (isso provoca o mesmo efeito). Antes de cada divisão, o valor j mod 10 é colocado na posição i de Q. Esta operação consiste exatamente em ler o último digito do inteiro em j. Como o valor em j reduz em cada iteração, então j mod 10 retorna sistematicamente cada último dígito do número. Assim tais dígitos são tomados de trás para frente justificando o laço de contagem decrescente (observe que nele o contador i inicia com o valor em t e decresce até 1 causando acesso de trás para frente no vetor). Com o fim do laço o vetor Q conterá os dígitos do atual valor em n na seqüência correta (para simples verificação de pandigitalidade isso não faz diferença, mas ilustramos aqui por ser útil em outros problemas). (IV) É testado se o vetor Q de dígitos possui ou não elementos repetidos. Os dois laços aninhados efetuam sistemáticas comparações entre elementos sendo suspensos (ambos) se alguma igualdade é encontrada. A variável b, inicialmente marcada como Verdadeira, indica a hipótese inicial de que há repetições. Se uma igualdade é encontrada tal variável recebe Falso. As chamadas a pare que suspendem os laços estão associadas ao valor em b. A expressão ¬b representa negação do valor em b e é necessária para testar se o laço externo (de contador i) deve ser ou não suspenso. (V) Uma mensagem apropriada é impressa na saída padrão de acordo com o último valor em b. O vetor Q é desalocado. Estudo de Caso – Transformação em Hexadecimal: a base hexadecimal conta com 16 distintos algarismos para representação de valores numéricos. Os dez primeiros coincidem com aqueles da base decimal ao passo que os seis restantes são denotados pelas cinco primeiras letras do alfabeto. Como há letras e números envolvidos, então hexadecimais são preferencialmente representados como cadeias de caracteres. Para transformar um decimal em hexadecimal deve-se submetê-lo a sucessivas divisões pela base 16. Os restos destas divisões são progressivamente tomados e seus correspondentes caracteres colocados na string resposta. Se o resto de divisão está entre 0 e 9 então os caracteres correspondentes são respectivamente ‘0’ a ‘9’. Se o resto está entre 10 e 15 então os caracteres são respectivamente ‘A’ a ‘F’. Os caracteres devem ser postos na string resposta de trás para frente porque os caracteres constituintes são obtidos na ordem inversa. Para resolver o problema descrito é o sugerido o algoritmo a seguir: declare H[], B[17]: caractere t, n: inteiro b: lógico // PARTE I B ← ‘0123456789ABCDEF’ leia n // PARTE II t ← 0 Algoritmos Ricardo Reis 50 UNIDADE 4 7. MODULARIZAÇÃO 7.1. O QUE É MODULARIZAR? Há dois importantes níveis de abstração em computação: abstração de dados e abstração de processos. A abstração de dados explora como diferentes tipos de informações podem ser representados e ainda quais as restrições de operabilidade entre eles. A abstração de processos trata da simplificação do processo de execução de uma dada aplicação pela divisão deste em partes menores (sub-processos) que podem ser testadas separadamente. A modularização está estreitamente ligada à abstração de processos. Modularizar significa dividir um programa em subprogramas cujos funcionamentos podem ser testados separadamente. Os subprogramas são nada mais que abstrações com alguma sintaxe adicional (em nível de código). 7.2. FUNÇÕES, PROCEDIMENTOS, PROCESSOS E CONTROLE Modularizar algoritmos significa separar o pseudocódigo em funções. As funções, módulos ou subprogramas, como são conhecidos, podem aparecer em grande quantidade em um mesmo algoritmo, mas apenas uma destas funções tem papel de acionador, ou seja, sempre a partir dela se iniciará a execução. É a chamada função principal. Todas as demais funções são secundárias. Cada função tem um nome e, num mesmo algoritmo, todas as funções devem ter nomes distintos entre si. Além do nome uma função pode conter parâmetros. Parâmetros, ou argumentos, são variáveis especiais que agem como entrada de dados para estas funções. A sintaxe geral de uma função é a seguinte: <nome_da_função> (<arg_1>: <tipo_1>, <arg_2>: <tipo_2>, ..., <arg_n>: <tipo_n>) //declaração de variáveis da função //instruções da função Na sintaxe de funções os argumentos são arranjados em uma lista de variáveis com seus respectivos tipos e ainda separados por vírgula. Apesar de não existir a palavra declarar, os argumentos de entrada são, por definição, variáveis ali declaradas. A primeira linha da função (composta por seu nome e seus argumentos entre parênteses) é chamada de cabeçalho da função. O corpo da função é todo o código abaixo do cabeçalho e cuja indentação é pelo menos um nível acima (relação de encapsulamento de código em funções). O corpo de uma função pode possuir uma sessão declarativa (variáveis da função) e possui obrigatoriamente (logo abaixo) a sessão de código (bloco de código). Se um grupo de argumentos de entrada tiver mesmo tipo eles podem ser declarados com a seguinte sintaxe: <nome_da_função> (<arg_1>,<arg_2>,<arg_3>,...,<arg_n>: <tipo>) // corpo da função Algoritmos Ricardo Reis 51 Para que seja executada, uma função precisa ser chamada. Uma chamada de função é realizada pela invocação de seu nome juntamente com valores para seus parâmetros. Para executar uma dada função secundária, ela deve ser chamada de dentro da função principal ou então de dentro de outra função secundária. Cada função de um algoritmo deve ser chamada pelo menos uma vez em algum lugar daquele algoritmo. Se uma dada função nunca é chamada ela pode ser removida do projeto. A execução de uma aplicação é nada mais que a execução de sua função principal. Quando uma aplicação inicia sua execução diz-se que a função principal recebe o controle de fluxo ou simplesmente que recebe o controle. Se a função principal chama uma função secundária então esta função receberá o controle do fluxo enquanto estiver executando e o devolverá a função principal quando sua execução se encerrar. De modo geral quando uma função A, seja ela principal ou não, chama outra função B ocorre repassagem provisória do controle de fluxo de A para B e depois seu retorno para A quando B se encerra. Sistematicamente o controle migra de função para função durante toda execução. Em algum momento cada uma das funções do projeto manterá o controle. Se uma mesma função for chamada várias vezes ela manterá o controle em momentos diferentes. Apenas uma, entre as várias funções, se existirem, terá o controle durante a execução da aplicação. (Uma aplicação deverá conter pelo menos a função principal). Funções podem retornar valores. O retorno (ou saída) de uma função pode ser, por exemplo, um número, um caractere ou um booleano. A ação de retorno de uma função é sumária, ou seja, quando invocada a função automaticamente se encerra devolvendo o controle à função chamadora. Para provocar o retorno usa-se a palavra chave retorne seguida do valor que se deve retornar. Veja o exemplo a seguir: soma (x, y: inteiro) declare s: inteiro s ← x + y retorne s principal() declare a, b, c: inteiro leia a, b c ← soma(a,b) escreva c Neste exemplo há duas funções: a principal (que sempre denotaremos pelo nome principal) e a função secundária soma(). A função secundária possui dois parâmetros, x e y e sua chamada é feita na função principal passado como argumentos os valores nas variáveis a e b. O uso da atribuição, c ← soma(a, b), entra em concordância com o retorne da função soma(), ou seja, só é possível atribuir a c algum valor porque este valor existe e é o retorno da função em questão. As variáveis x e y são denominadas argumentos formais da função soma() ao passo que a e b são denominadas de argumentos reais da mesma função. Os argumentos reais de uma função podem ser tanto constantes como variáveis. Já os argumentos formais aparecem no próprio corpo construtivo da função e são representados apenas por variáveis. Para cada argumento real deve haver um formal equivalente. A ordem em de disposição dos argumentos formais deve ser mantida pelos argumentos reais, por exemplo, se uma dada função possui três argumentos cujos tipos são respectivamente inteiro, real e booleano, então os argumentos reais Algoritmos Ricardo Reis 52 repassados no momento da chamada devem também estar listados nesta ordem de tipo, ou seja, inteiro, real e booleano. Consideremos outro exemplo: e_primo (n: inteiro) declare d: inteiro d ← 2 enquanto (d*d ≤ n) faça se (n mod d = 0) então retorne F d ← d + 1 retorne V principal() declare k: inteiro para k ← 1 até 200 faça se ( e_primo(k) ) então escreva k A função e_primo() acima é uma versão modularizada do algoritmo apresentado no estudo de caso Números Primos. O objetivo desta função é receber um inteiro e retornar um booleano onde retorno Verdadeiro significa que a entrada é um valor primo e retorno Falso significa o inverso. Se durante os testes de divisibilidade internos ao laço enquanto algum dos restos for nulo, então não haverá mais sentido continuar testando outras divisões porque o número já não é mais primo. A estratégia do estudo de caso anterior fora o uso de um pare e uma variável booleana auxiliar. Neste novo contexto se invoca apenas um, retorne F, porque este comando força o encerramento da função independente de onde ele apareça dentro da função. Como um F (Falso) segue o retorne então a função retorna convenientemente para valores não primos. Caso o valor seja primo o laço se encerrará normalmente e a instrução, retorne F, jamais será executada. Em contrapartida a continuação da execução encontrará a linha, retorne V, que forçará o encerramento e retorno Verdadeiro: de fato apenas valores primos causarão o alcance desta linha de instrução. A função principal faz uso intenso da função e_primo() testando quais números entre 1 e 200 são ou não primos. Caso sejam, eles são impressos. A expressão booleana do se é a própria chamada da função e_primo() haja vista que o retorno dela é um valor booleano e desta forma não desobedece a sintaxe da estrutura. Há funções que não precisam retornar. Elas são denominadas de procedimentos. Veja o exemplo a seguir: print_primo (t: inteiro) declare i: inteiro para i ← 1 até t faça se ( e_primo(i) ) então escreva(i) O procedimento anterior deve ser parte integrante do algoritmo apresentado anteriormente, pois faz uso da função e_primo(). Este procedimento simplesmente imprime na saída padrão todos os primos entre 1 e o valor no argumento de entrada t. Obviamente o conteúdo impresso pode ser interpretado como saída da função. Entretanto, por convenção, diremos que uma função possui saída se ela gerar alguma informação que puder ser repassada adiante por uma ação conjunta de um retorne e Algoritmos Ricardo Reis 55 j ← 5 inc(j) escreva j // deve imprimir 6 O comportamento esperado no código acima é a impressão do valor 6 na saída padrão. Entretanto, pelo modelo da passagem por valor tal função não pode ser escrita. Vejamos uma tentativa para inc(): inc(k: inteiro) k ← k + 1 Caso esta função seja utilizada o valor impresso na saída padrão será 5 e não 6 simplesmente por que quem incremente em uma unidade é k e não j. Como k e j não se relacionam a função não se comporta como desejado. Para resolver o problema apresentamos outro modelo de passagem de argumento conhecido como passagem por referência. Uma referência por definição é um apelido de variável que pode ser manipulada como se fosse a própria variável que ela apelidou. Por exemplo, se r é uma referência da variável x então uma atribuição a r será de fato uma atribuição para x. Na passagem por referência alguns ou todos os argumentos formais de uma função são transformados em referências: assim quando os argumentos reais são repassados não ocorre cópia alguma e sim a definição de apelidos em outro escopo! Uma vez de posse de tais referências a função pode mudar variáveis fora de seu escopo. Para transformar um argumento formal numa referência basta preceder a declaração da variável com a palavra chave ref. Assim a função inc() pode ser agora corretamente escrita: inc(ref k: inteiro) k ← k + 1 principal() declare j: inteiro j ← 5 inc(j) escreva j Nesta nova versão k deixa de ser uma variável de tipo inteiro e torna-se uma referência para valor inteiro. Assim quando j é repassado como argumento, então k torna-se provisoriamente uma referência para ele. A adição de uma unidade à referencia k na função inc() afeta de fato a variável j. O valor impresso na função principal é então 6. 7.5. PASSANDO VETORES COMO ARGUMENTOS Algumas linguagens de programação não permitem que vetores sejam repassados por valor. Isso acontece porque não é possível garantir que o vetor repassado sempre tenha o mesmo comprimento do vetor argumento de entrada. Mesmo que seja possível impedir a execução de uma função quando se tentar repassar a ela um vetor de comprimento inválido, isso implicaria em restrições de uso desta função. A saída utilizada nestas linguagens é o uso de referências. Adotaremos estas mesmas regras nos algoritmos que seguem. Para utilizar referências na repassagem de vetores seguiremos a seguinte sintaxe geral: Algoritmos Ricardo Reis 56 <nome_da_função>(ref <arg>[]: <tipo>) //corpo da função Apesar de um par de colchetes vazios, o argumento não se trata de um vetor dinâmico. A associação entre ref e [ ] no argumento de entrada (e apenas aí) significa vetor repassado por referência. Quando repassado por referência um vetor torna-se modificável no escopo da função. Entretanto a função aparentemente perde uma informação importante: o comprimento do vetor. Para resolver o problema utilizaremos uma importante função chamada comp() que recebe como argumento um vetor, ou referencia de vetor, e retorna seu comprimento. Exemplo: soma(ref M[]: inteiro) declare i, res: inteiro res ← 0 para i ← 1 até comp(M) faça res ← res + M[i] retorne res A função soma() recebe um vetor de valores inteiros e retorna a somatória de seus elementos. A variável res é um acumulador que recebe zero no princípio e depois muda em cada iteração do laço até conter a soma de todos os elementos. A função comp() retorna o comprimento do vetor recebendo-o como argumento (sem colchetes). Estudo de Caso – Números Pandigitais. A modularização do problema dos pandigitais fornece uma solução mais natural como indica o algoritmo seguinte. Nesta nova abordagem procura-se determinar quantos números pandigitais existem abaixo de um milhão. ndig(num: inteiro) declare s: inteiro s ← 0 enquanto (num>0) faça s ← s + 1 num ← num div 10 retorne s carregar(ref R[], num: inteiro) declarar i: inteiro para i ← comp(R), 1, -1 faça R[i] ← num div 10 num ← num div 10 e_pandig(ref R[]: inteiro) declare i, j: inteiro para i ← 1 até comp(R)-1 faça para j ← i+1 até comp(R) faça se (R[i] = R[j]) então retorne F retorne V principal() declare Algoritmos Ricardo Reis 57 cnt, Q[], t, n: inteiro cnt ← 0 para n ← 0 até 1000000 faça alocar Q[ ndig(n) ] carregar(Q, n) se ( e_pandig(Q) ) então cnt ← cnt + 1 limpar Q escreva cnt O algoritmo acima possui três funções secundárias e a função principal. Na função principal o laço para testa cada valor que o contador n assume. Cada teste consiste em: (I) alocar dinamicamente o vetor Q com comprimento igual à quantidade de dígitos do atual valor de n; (II) carregar Q com os dígitos de n e; (III) testar se o vetor Q possui elementos repetidos; caso seja o contador cnt (iniciado com zero fora do laço) é incrementado em uma unidade. Quando o laço se encerra o valor em cnt é o total de pandigitais menores que um milhão. As quantidades de dígitos de n em cada iteração são calculadas por chamadas a ndig() cujo modelo de passagem de seu único argumento é por valor (por isso a inexistência de uma variável auxiliar j como no estudo de caso anterior sobre pandigitais). O procedimento carregar() distribui os dígitos do valor em num (segundo argumento) dentro do vetor referenciado por R (primeiro argumento). Quando invocada dentro do laço para na função principal, esta função configura Q para conter os dígitos do atual valor em n. A função e_pandig() testa se um dado vetor referenciado por seu único argumento de entrada, R (referência a vetor em outro escopo), possui repetição de elementos. Quando isso acontece o par de laços aninhado são encerrados por um, retorne F; do contrário a instrução, retorne V, é alcançada. Assim, apenas números pandigitais distribuídos no vetor referenciado por R, farão e_pandig() retornar Verdadeiro. Como a saída desta função é um booleano então ela é usada como expressão de decisão no se da função principal. 7.6. RECURSIVIDADE Recursividade é a técnica que permite a uma função fazer, no corpo de seu código, uma chamada a si própria. Para ilustrar a recursividade apresentamos a seguir duas versões de funções para cálculo de fatorial: uma não-recursiva (iterativa) e outra recursiva. //versão iterativa fat(n: inteiro) declare res: inteiro enquanto (n>0) faça res ← res * n n ← n - 1 retorne res // versão recursiva fat(n: inteiro) se (n<2) então retorne 1 senão