Algoritmos - Técnicas De Programação 1h6d5u

Algoritmos Técnicas de Programação

José Augusto N. G. Manzano Ecivaldo Matos André Evandro Lourenço

Algoritmos Técnicas de Programação

1ª Edição

www.editoraerica.com.br

1

Dados Internacionais de Catalogação na Publicação (CIP) (Câmara Brasileira do Livro, SP, Brasil) Manzano, José Augusto N. G. Algoritmos : técnicas de programação / José Augusto N. G. Manzano, Ecivaldo Matos, André Evandro Lourenço. -- 1. ed. -- São Paulo : Érica, 2014. Bibliografia ISBN 978-85-365-0737-8 1. Algoritmos 2. Linguagens de programação (Computadores) 3. Programação (Computadores eletrônicos) I. Matos, Ecivaldo. II. Lourenço, André Evandro. III. Título. 14-01498

CDD-005.1

Índices para catálogo sistemático: 1. Algoritmos : Computadores : Programação : Processamento de dados 005.1 Copyright © 2014 da Editora Érica Ltda. Todos os direitos reservados. Nenhuma parte desta publicação poderá ser reproduzida por qualquer meio ou forma sem prévia autorização da Editora Érica. A violação dos direitos autorais é crime estabelecido na Lei nº 9.610/98 e punido pelo Artigo 184 do Código Penal.

Coordenação Editorial: Rosana Arruda da Silva Capa: Maurício S. de França Preparação e Edição de Texto: Beatriz M. Carneiro, Bruna Gomes Cordeiro, Carla de Oliveira Morais Tureta, Juliana Ferreira Favoretto, Nathalia Ferrarezi, Silvia Campos Produção Editorial: Adriana Aguiar Santoro, Alline Bullara, Dalete Oliveira, Graziele Liborni, Laudemir Marinho dos Santos, Rosana Aparecida Alves dos Santos, Rosemeire Cavalheiro Editoração: ERJ Composição Editorial Os Autores e a Editora acreditam que todas as informações aqui apresentadas estão corretas e podem ser utilizadas para qualquer fim legal. Entretanto, não existe qualquer garantia, explícita ou implícita, de que o uso de tais informações conduzirá sempre ao resultado desejado. Os nomes de sites e empresas, porventura mencionados, foram utilizados apenas para ilustrar os exemplos, não tendo vínculo nenhum com o livro, não garantindo a sua existência nem divulgação. Eventuais erratas estarão disponíveis para no site da Editora Érica. Conteúdo adaptado ao Novo Acordo Ortográfico da Língua Portuguesa, em execução desde 1º de janeiro de 2009. A ilustração de capa e algumas imagens de miolo foram retiradas de <www.shutterstock.com>, empresa com a qual se mantém contrato ativo na data de publicação do livro. Outras foram obtidas da Coleção MasterClips/MasterPhotos© da IMSI, 100 Rowland Way, 3rd floor Novato, CA 94945, USA, e do CorelDRAW X5 e X6, Corel Gallery e Corel Corporation Samples. Copyright© 2013 Editora Érica, Corel Corporation e seus licenciadores. Todos os direitos reservados. Todos os esforços foram feitos para creditar devidamente os detentores dos direitos das imagens utilizadas neste livro. Eventuais omissões de crédito e copyright não são intencionais e serão devidamente solucionadas nas próximas edições, bastando que seus proprietários contatem os editores. Seu cadastro é muito importante para nós Ao preencher e remeter a ficha de cadastro constante no site da Editora Érica, você ará a receber informações sobre nossos lançamentos em sua área de preferência. Conhecendo melhor os leitores e suas preferências, vamos produzir títulos que atendam suas necessidades.

Contato com o editorial: [email protected]

Editora Érica Ltda. | Uma Empresa do Grupo Saraiva Rua São Gil, 159 - Tatuapé CEP: 03401-030 - São Paulo - SP Fone: (11) 2295-3066 - Fax: (11) 2097-4060 www.editoraerica.com.br

2

Algoritmos - Técnicas de Programação

Agradecimentos Agradecemos a todos aqueles que acreditam na educação como um dos elementos fundamentais para a mudança social.

3

Sobre os autores José Augusto N. G. Manzano, brasileiro, nascido em São Paulo, em 26 de abril de 1965, é professor e mestre com licenciatura em Matemática. Atua na área de Tecnologia da Informação (desenvolvimento de software, ensino e treinamento) desde 1986. Participou do desenvolvimento de aplicações computacionais para as áreas de telecomunicações e comércio. Na carreira docente, iniciou sua atividade em cursos livres, trabalhando posteriormente em empresas de treinamento e atuando nos ensinos técnico e superior. Trabalhou em empresas da área, como: ABAK, SERVIMEC, CEBEL, SPCI, BEPE, ORIGIN, OpenClass, entre outras. Atualmente, é professor com dedicação exclusiva ao IFSP (Instituto Federal de Educação, Ciência e Tecnologia de São Paulo, antiga Escola Técnica Federal). Em sua carreira como docente, tem condições de ministrar componentes curriculares de Lógica de Programação (Algoritmos), Estrutura de Dados, Microinformática, Informática, Linguagens de Programação Estruturada, Linguagens de Programação Orientada a Objetos, Engenharia de Software, Tópicos Avançados em Processamento de Dados, Sistemas de Informação, Engenharia da Informação, Arquitetura de Computadores e Tecnologias Web. Possui conhecimento de uso e aplicação das linguagens de programação CLASSICBASIC, COMAL, Assembly, LOGO, PASCAL, FORTRAN, C, C++, JAVA, MODULA-2, STRUCTUREDBASIC, C#, Lua, HTML, XHTML, JavaScript, VBA e ADA. Possui mais de oitenta obras publicadas, além de artigos publicados no Brasil e no exterior. Ecivaldo Matos, doutor em Educação (Didática, Teorias de Ensino e Práticas Escolares) pela Faculdade de Educação da Universidade de São Paulo (USP), com apoio do Programa Internacional de Bolsas de Pós-graduação da Fundação FORD (IFP - Ford Foundation International Fellowships Program), mestre em Informática pela Universidade Federal de Campina Grande e bacharel em Ciência da Computação com especialização em Sistemas Distribuídos pela Universidade Federal da Bahia. Atuou como professor efetivo do Colégio Pedro II (RJ), na área de Ciência da Computação e como pesquisador do Laboratório de Estudos da Aprendizagem Humana da Universidade do Estado do Rio de Janeiro (LEAH/UERJ). Atualmente, é professor e coordenador da área de Informática do Instituto Federal de Educação, Ciência e Tecnologia de São Paulo - IFSP (Campus São Paulo), pesquisador do Grupo Alpha (USP), membro da Association for Computing Machinery (ACM) e da Comissão de Educação da Sociedade Brasileira de Computação (SBC). André Evandro Lourenço, mestre em Engenharia Elétrica (Processamento em Alto Desempenho e Sistemas Digitais) pela Universidade de São Paulo (USP) e bacharel em Ciência da Computação pela Universidade Federal de Mato Grosso do Sul (UFMS). Atualmente, é professor e coordenador do Instituto Federal de Educação, Ciência e Tecnologia de São Paulo - IFSP (Campus São Paulo) e docente do Centro Universitário Fundação Instituto de Ensino para Osasco (UNIFIEO). Tem experiência técnica e docente nas áreas de programação em ambiente internet, data mining, webmining, algoritmos e estruturas de dados, sistemas operacionais, arquitetura de computadores, computação gráfica, gestão empresarial, marketing e propaganda, além de trabalhos envolvendo banco de dados.

4

Algoritmos - Técnicas de Programação

Sumário Capítulo 1 - Introdução aos Algoritmos........................................................................................ 9 1.1 Breve história da computação..........................................................................................................................................9 1.2 Lógica de programação e algoritmos............................................................................................................................13 1.3 Paradigmas de programação..........................................................................................................................................14 1.4 Diagrama de blocos.........................................................................................................................................................15 1.5 Linguagem de projeto de programação........................................................................................................................16 1.6 Interpretadores, compiladores e tradutores.................................................................................................................17 1.6.1 Interpretadores.......................................................................................................................................................17 1.6.2 Compiladores..........................................................................................................................................................18 1.6.3 Tradutores................................................................................................................................................................18 1.7 Recomendações para resolução de problemas.............................................................................................................19 1.8 Tabela ASCII.....................................................................................................................................................................20 Agora é com você!..................................................................................................................................................................24 Capítulo 2 - Programação Sequencial......................................................................................... 25 2.1 Etapas operacionais.........................................................................................................................................................25 2.2 Tipos de dados.................................................................................................................................................................26 2.2.1 Dado numérico inteiro..........................................................................................................................................26 2.2.2 Dado numérico real...............................................................................................................................................26 2.2.3 Dado caractere/cadeia...........................................................................................................................................27 2.2.4 Dado lógico.............................................................................................................................................................27 2.3 Variáveis............................................................................................................................................................................27 2.4 Constantes........................................................................................................................................................................28 2.5 Operadores aritméticos...................................................................................................................................................29 2.6 Expressões aritméticas....................................................................................................................................................29 2.7 Instruções e comandos....................................................................................................................................................31 Agora é com você!..................................................................................................................................................................36 Capítulo 3 - Programação com Desvios...................................................................................... 37 3.1 Tomada de decisões.........................................................................................................................................................37 3.2 Operadores relacionais....................................................................................................................................................38 3.3 Desvios condicionais.......................................................................................................................................................39 3.3.1 Desvio condicional simples ..................................................................................................................................39 3.3.2 Desvio condicional composto...............................................................................................................................41 3.3.3 Desvio condicional encadeado.............................................................................................................................42 3.3.4 Desvio com múltipla escolha................................................................................................................................44 3.4 Divisibilidade...................................................................................................................................................................45 3.5 Operadores lógicos..........................................................................................................................................................47 3.5.1 Operador lógico .e..................................................................................................................................................47 3.5.2 Operador lógico .ou...............................................................................................................................................48 3.5.3 Operador lógico .não.............................................................................................................................................50 Agora é com você!..................................................................................................................................................................52

5

Capítulo 4 - Programação com Laços......................................................................................... 53 4.1 Controle de ciclos............................................................................................................................................................53 4.2 Laço condicional pré-teste..............................................................................................................................................54 4.3 Laço condicional pós-teste.............................................................................................................................................57 4.4 Laço incondicional..........................................................................................................................................................60 Agora é com você!..................................................................................................................................................................62 Capítulo 5 - Programação com Matrizes..................................................................................... 63 5.1 Estrutura de dados...........................................................................................................................................................63 5.2 Vetores ou matrizes unidimensionais...........................................................................................................................64 5.3 Tabelas ou matrizes bidimensionais..............................................................................................................................68 Agora é com você!..................................................................................................................................................................71 Capítulo 6 - Aplicação Prática de Matrizes.................................................................................. 73 6.1 Ordenação de elementos.................................................................................................................................................73 6.2 Pesquisa de elementos.....................................................................................................................................................79 Agora é com você!..................................................................................................................................................................84 Capítulo 7 - Programação com Registros.................................................................................... 85 7.1 Tipos de dados derivados...............................................................................................................................................85 7.2 Tipo de dado derivado: registro.....................................................................................................................................86 7.3 Estrutura de um registro com matriz............................................................................................................................89 7.4 Tipo de dado derivado: novo tipo.................................................................................................................................90 7.5 Matriz de registro.............................................................................................................................................................92 Agora é com você!..................................................................................................................................................................95 Capítulo 8 - Utilização de Sub-rotinas......................................................................................... 97 8.1 Dividir para conquistar...................................................................................................................................................97 8.2 Programação top-down e bottom-up.......................................................................................................................102 8.3 Procedimentos...............................................................................................................................................................102 8.4 Funções...........................................................................................................................................................................104 8.5 Escopo de variáveis........................................................................................................................................................105 8.6 agem de parâmetros...............................................................................................................................................106 Agora é com você!................................................................................................................................................................108 Capítulo 9 - Medidas de Complexidade de Algoritmos................................................................ 109 9.1 Análise de algoritmos....................................................................................................................................................109 9.2 Modelo de tempo e espaço: otimilidade de algoritmos............................................................................................111 9.3 Busca de padrões em cadeias de caracteres................................................................................................................117 9.4 Fundamentos de retrocesso..........................................................................................................................................121 Agora é com você!................................................................................................................................................................124 Bibliografia........................................................................................................................... 125

6

Algoritmos - Técnicas de Programação

Apresentação Este livro é um trabalho voltado para o ensino de lógica de programação de computadores para jovens e adolescentes dos cursos técnicos de informática da rede brasileira de ensino. O objetivo do estudo e uso das ações de lógica de programação de computadores é permitir ao aluno o o ao conhecimento das etapas necessárias a serem dominadas para a produção de software para as áreas de comércio, educação e indústria de modo geral. A linguagem usada se caracteriza por ser voltada ao público mais jovem. O desenvolvimento deste livro veio da necessidade de conciliarmos o ensino de técnicas de programação com os programas curriculares nacionais de maneira que se encaixasse em um semestre de curso. Esta obra está dividida em nove capítulos que tratam os seguintes temas: O Capítulo 1 apresenta uma pequena introdução aos conceitos essenciais a serem conhecidos para o desenvolvimento do estudo de lógica de programação de computadores. Nesse capítulo, é possível ter uma visão básica sobre a história da computação, o que é a lógica de programação e algoritmos, os paradigmas de programação, diagrama de blocos, linguagem de projeto de programação e os princípios de resolução de problemas entre outros aspectos, entre outros pontos. No Capítulo 2 o aluno tem contato com o primeiro o do que efetivamente é a programação de computadores. Nele estudamos os conceitos de entrada, de processamento e de saída. É apresentado, também, o uso de tipos de dados, variáveis, constantes, operadores aritméticos, expressões aritméticas na elaboração e uso do processamento matemático. A tomada de decisão, segundo o na aprendizagem de aplicação da lógica de programação, é tema do Capítulo 3. Neste estudo é mostrado o uso de condições e seus desvios, além do conhecimento e aplicação dos operadores relacionais e lógicos no uso do processamento lógico. É dada atenção ao uso dos princípios de divisibilidade na tarefa de programar computadores. No Capítulo 4 é apresentado o terceiro o na aprendizagem e uso do conceito de lógica de programação. Nessa etapa de estudo, o conhecimento de uso do processamento lógico é ampliado com o uso das técnicas de laços condicional pré-teste, condicional pós-teste e incondicional. Após a visão da base inicial dada nos Capítulos 2, 3 e 4, o Capítulo 5 apresenta a técnica de programação com matrizes de uma e duas dimensões. Nessa etapa é feita uma introdução ao conceito mais simples de estruturação de dados em memória, com a finalidade de facilitar as ações de programação pelo programador e, assim, aumentar sua produtividade operacional. O Capítulo 6 apresenta um nível de aplicação prática da técnica de programação apresentada no Capítulo 5. Nessa etapa é apresentado o uso de técnicas práticas que visam manter uma matriz com dados classificados de acordo com certa ordem, além de estabelecer um algoritmo para busca e localização de elementos nessas estruturas de dados.

7

No Capítulo 7 é apresentada a técnica de criação e uso de registros, uma maneira de incorporar em uma única matriz dados de tipos diferentes. A organização de um programa em módulos é tema do Capítulo 8, onde são apresentadas as definições e uso de funções, procedimentos e agens de parâmetro. Nesse capítulo são apresentados, ainda, o escopo de uso de variáveis, as ideias de uso dos métodos de trabalho top-down e bottom-up, além da visão sobre os princípios de dividir para conquistar. O Capítulo 9, último deste trabalho, apresenta temas relacionados a princípios de uso de algoritmos. Nesse contexto, é indicada, de forma introdutória, noções sobre fundamentos de medidas de complexidade de algoritmos, fundamentos de otimalidade de algoritmos, fundamentos de backtracking e ações de busca de padrões em strings. Esperamos que este trabalho seja útil não só ao aluno, mas também ao professor. Um abraço a todos! Os autores

8

Algoritmos - Técnicas de Programação

1 Introdução aos Algoritmos

Para começar Com o objetivo de desenvolver um bom raciocínio lógico, é apresentado neste capítulo um breve panorama da história do computador, bem como os conceitos de lógica de programação e, com base em normas internacionais (ISO 5807:1985), as formas de representação em diagrama de bloco e português estruturado. No fim do capítulo, você encontrará uma apresentação do princípio usado para resolução de problemas.

1.1 Breve história da computação Atualmente, o computador está presente em praticamente todas as nossas atividades de forma direta ou indireta. A origem da computação como a conhecemos remete aos primórdios da sociedade humana, pois o homem sempre teve a necessidade de construir equipamentos e máquinas que realizassem cálculos. A primeira máquina construída com o objetivo de auxiliar nas operações matemáticas surgiu por volta de 3500 a.C., na região da Mesopotâmia (vale dos rios Tigre e Eufrades, atual Iraque) e foi batizada de ábaco (ALCALDE; GARCIA; PENUELAS, 1991). O ábaco influenciou muitas outras culturas, como da Babilônia, Egito, Grécia, Roma, Índia, China e Japão durante vários séculos.

9

Wikimedia Commons/Mike Cowlishaw

Figura 1.1 - Ábaco.

Wikimedia Commons/Tieum512

Somente em 1642, o francês Blaise Pascal cria uma máquina com capacidade para realizar somas e subtração de forma automática. Essa máquina, batizada de Pascalina, simulava por meio de rodas dentadas o funcionamento do ábaco. Alguns anos depois, em 1672, Gottfried Wilhelm Leibniz consegue modificar a máquina de Pascal com o objetivo de incluir operações de multiplicar e dividir.

Figura 1.2 - Máquina de somar e subtrair de Pascal.

Diversas máquinas foram criadas ao longo do tempo por diversos inventores. O objetivo das máquinas sempre foi auxiliar em cálculos complexos ou substituir o homem em alguma atividade. Entre as diversas máquinas que foram criadas, temos: máquina de tear (1804), de Joseph Marie Jacquard; máquina de diferenças (1822); máquina analítica, (1837) de Charles Babbage; e máquina de Hollerith (1890), de Hermann Hollerith.

10

Algoritmos - Técnicas de Programação

Wikimedia Commons/GeorgeOnline

Wikimedia Commons/Bruno Barral (ByB)

Figura 1.3 - Máquina de tear de Joseph Marie Jacquard.

Figura 1.4 - Máquina de diferenças e máquina analítica de Charles Babbage.

Introdução aos Algoritmos

11

Wikimedia Commons/Census Machine

Figura 1.5 - Máquina de Hermann Hollerith.

Todas as máquinas criadas até então eram dispositivos mecânicos e não utilizavam nenhum tipo de circuito elétrico. A utilização de circuitos elétricos só foi possível depois que um matemático chamado George Boole criou um sistema lógico no qual tudo poderia ser representado por meio de dois algarismos: 0 ou 1. Nascia aí a Lógica Booleana, utilizada até hoje em todos os modernos computadores. Em sua teoria, 0 (zero) representa algo que esteja desligado, apagado, sem valor. Já o valor 1 (um) representa ligado, aceso. Com a combinação desses algarismos, podemos criar outros valores. Vejamos um exemplo que utilize 2 algarismos: 00 - Apagado 01 - Luz verde 10 - Luz amarela 11 - Luz vermelha Fique de olho! Para cada algarismo utilizado, damos o nome de bit. No exemplo acima, temos dois bits. Para construir os símbolos utilizados em nosso alfabeto (letras e números) utilizamos oito algarismos, ou seja, oito bits. Para um conjunto de oito bits damos o nome de byte. Portanto, para formar uma letra ou número do nosso alfabeto, utilizamos um byte. 1 byte = 8 bits

12

Algoritmos - Técnicas de Programação

1.2 Lógica de programação e algoritmos Antes de entendermos o que vem a ser lógica de programação, devemos entender que um computador nada mais é do que uma máquina com circuitos eletrônicos capaz de executar um algoritmo, e um algoritmo é um conjunto lógico de operações predefinidas que resolva determinado problema. De forma intuitiva, já utilizamos algoritmos em nosso dia a dia para realizar nossas tarefas. Em poucas palavras, um algoritmo é uma receita para resolver um problema bem específico. Por exemplo: »»

Observe os os para se tomar um banho: tirar a roupa, entrar no box, ligar o chuveiro e assim por diante.

»»

Agora, veja os os para imprimir o resultado da soma de dois números. Primeiro, devemos fornecer (ou digitar) os dois números a serem somados. Em seguida, realizamos a operação de soma, armazenando o resultado em algum lugar. Por fim, basta imprimir o resultado da soma.

No exemplo 2, os números fornecidos inicialmente são chamados de dados e a soma final é o resultado do processamento desses dados, ou seja, a informação útil esperada. Todo computador processa um conjunto de dados e os transforma em uma informação. Entrada

Processamento

Saída

Figura 1.6 - Estrutura de processamento de dados.

Para que o tratamento dos dados de entrada ocorra, ou seja, para transformar (processar) os dados em informação de saída, é necessário o uso de um algoritmo desenvolvido para tal finalidade. Os algoritmos são utilizados para descrever os os necessários para que um programa de computador execute uma tarefa que ele foi designado a fazer. Portanto, a lógica de programação é a forma como se escreve esse algoritmo, significando o uso correto das leis do pensamento, da “ordem da razão” e de processos de raciocínio (FORBELLONE; EBERSPACHER, 2000) para resolver o problema proposto. A literatura está repleta de definições para algoritmo: »»

processo sistemático para a resolução de um problema (SZWARCFITER; MARKENZON, 1994);

»»

sequência de os que visam atingir um objetivo bem definido (FORBELLONE; EBERSPACHER, 2000);

»»

sequência ordenada de os que deve ser seguida para a realização de uma tarefa (SALIBA, 1993; BERG; FIGUEIRÓ, 1998).

Um programador de computador poderá criar um projeto de algoritmo utilizando uma representação gráfica (diagrama de blocos) ou até mesmo uma representação textual (português estruturado). Ambas são bastante utilizadas no mercado e podemos defini-las como:

Introdução aos Algoritmos

13

»»

Representação gráfica: conjunto de símbolos que representam todos os os do algoritmo. Cada símbolo possui uma ação específica a ser executada.

»»

Representação textual: o português estruturado é uma forma genérica (sem considerar linguagens de programação) de representar as ações do algoritmo.

1.3 Paradigmas de programação No mundo da programação, existem algumas formas ou metodologias para a construção de algoritmos. A essas metodologias, dá-se o nome de paradigma de programação. As mais conhecidas são o paradigma de programação estruturada e o paradigma da programação orientada a objetos (MANZANO; FIGUEIREDO, 2012). »»

No Paradigma Orientado a Objetos ou simplesmente Programação Orientada a Objetos, o programador abstrai um programa como uma coleção de objetos que interagem entre si;

»»

No Paradigma Estruturado ou apenas Programação Estruturada, o algoritmo é construído como sequência linear de funções ou módulos.

Neste livro, daremos ênfase à programação estruturada que, entre outras, apresenta as seguintes vantagens: »»

acelera o processo de construção do programa;

»»

simplifica e reconhece as falhas apresentadas pelos programas;

»»

por meio de módulos (também chamados de funções ou procedimentos), aprimora a reutilização de códigos;

»»

simplifica a leitura dos programas;

»»

simplifica as alterações e atualizações dos programas;

»»

simplifica a manutenção dos programas.

Na construção de um algoritmo estruturado, fique atento para as recomendações a seguir: »»

preste atenção no problema a ser resolvido, no objetivo a ser alcançado, compreendendo sua complexidade e destacando os pontos principais;

»»

defina os dados de entrada, ou seja, quais dados serão fornecidos ao programa;

»»

defina quais informações saíram do programa depois do processamento;

»»

defina quais cálculos farão parte do processamento.

Se o projeto de determinado algoritmo é extenso e longo, ele poderá consumir semanas ou meses de desenvolvimento. Neste caso, será necessária uma equipe de programadores trabalhando em conjunto sob a supervisão de um programador-chefe. Nesse contexto, recomenda-se observar os seguintes os: »»

as instruções devem estar em sequências e ligadas entre si apenas por estruturas de seleção, tomadas de decisão ou laços de repetição;

»»

escreva instruções em grupos pequenos e combine-as na forma de sub-rotinas ou de módulos estruturados;

14

Algoritmos - Técnicas de Programação

»»

»»

distribua módulos do programa entre os diferentes programadores que trabalharão sob a supervisão de um programador-sênior, chefe de programação ou analista de sistemas de informação; revise o trabalho executado em reuniões regulares e previamente programadas, em que compareçam apenas programadores do mesmo nível.

Fique de olho! Em 1961, no Instituto Tecnológico de Aeronáutica (ITA), foi criado o primeiro computador brasileiro, chamado Zezinho. No ano seguinte, ele foi desmontado e suas peças foram usadas em outros projetos.

1.4 Diagrama de blocos O diagrama de blocos caracteriza-se por um conjunto de símbolos gráficos, cada qual representando uma ação específica e básica a ser executada por um computador. O diagrama de blocos mostra a linha de raciocínio usada pelo programador para resolver o problema proposto. Todos os símbolos adotados pelo diagrama de blocos estão normatizados na ISO 5807:1985 (E) e este deve ser construído de modo que outros profissionais da área de desenvolvimento de programas (analistas de sistemas e programadores) entendam o que certo desenvolvedor quis dizer sobre o que o programa efetivamente faz sem haver preocupação com os rigores sintáticos de qualquer linguagem de programação que tenha sido usada. Tabela 1.1 - Os principais símbolos utilizados Símbolo

Significado Terminal

Representa a definição de início e fim do fluxo lógico a ser definido em um programa. É utilizado também na definição de sub-rotinas.

Entrada manual

Representa a definição de entrada manual de dados, comumente realizada por meio de um teclado conectado ao computador.

Processamento

Representa a definição da execução de ações de processamento normalmente relacionadas a operações matemáticas.

Exibição

Representa a definição de execução da operação de saída de dados em um monitor de vídeo conectado ao computador.

Decisão

Representa a definição de desvios condicionais nas operações de tomadas de decisões e laços condicionais para repetição de trechos de programa.

Preparação

Representa a definição de execução de um laço incondicional que permite a modificação de instruções ou grupo de instruções limitadas no laço.

Processo predefinido

Introdução aos Algoritmos

Descrição

Representa a definição de um grupo de operações relacionadas a uma sub-rotina de processamento.

Conector

Representa pontos de conexão entre trechos de programas apontados a outras partes do diagrama de blocos.

Linha

Representa os vínculos existentes entre os símbolos de um diagrama de blocos. Deve ter a ponta de uma seta indicando a direção que o fluxo de um programa deve seguir.

15

Exercício resolvido Construa o diagrama de bloco para calcular e imprimir a soma de dois números inteiros fornecidos pelo usuário.

Solução Início

N1, N2

RESULTADO

N1+N2

RESULTADO

Fim

Figura 1.7 - Diagrama de bloco para o cálculo da soma de dois números.

1.5 Linguagem de projeto de programação Você viu que um algoritmo pode ser escrito por meio de uma representação gráfica (diagrama de bloco). Contudo, podemos representar o mesmo algoritmo por meio de uma linguagem de projeto de programação, que é muito semelhante à linguagem utilizada para a nossa comunicação. Assim como os diagramas de blocos, a linguagem de projeto de programação deve ser simples ao ponto de qualquer pessoa que não conheça as rotinas de programação entender o raciocínio utilizado para resolver o problema em questão. Neste trabalho, utilizaremos o português estruturado, ou simplesmente pseudocódigo ou algoritmo, para referenciar a resolução de um problema em uma linguagem de projeto de programação. Uma vez que o algoritmo é traduzido para uma linguagem de programação específica (por exemplo, C, C++, Pascal, BASIC, Lua, Java, PHP etc.) o chamaremos de programa. »

Algoritmo: cojunto sequencial finito de instruções definidas em ordem lógica para resolver um problema ou problemas da mesma natureza.

»

Programa: o programa é por sua natureza.

O programador, ao escrever um algoritmo, deverá ficar atento à lógica e à sequência dos os empregados na resolução do problema e não deverá se preocupar com a sintaxe da linguagem de programação, já que não se sabe em qual linguagem será implementado.

16

Algoritmos - Técnicas de Programação

Exercício resolvido Construa o algoritmo para calcular e imprimir a soma de dois números inteiros fornecidos pelo usuário.

Português estruturado programa SOMA var

N1, N2, RESULTADO: real

inicio

leia N1, N2 RESULTADO ← N1 + N2 escreva RESULTADO

fim

Fique de olho! Um computador quântico é um equipamento com a capacidade de executar cálculos com base no uso de propriedades de Mecânica Quântica, como interferência e sobreposição. Um exemplo de computador desse tipo é o D-Wave Two, desenvolvido pela empresa D-Wave Systems, Inc.

1.6 Interpretadores, compiladores e tradutores Para que um programa seja executado por um computador, é necessário que se faça a conversão do algoritmo escrito em linguagem de alto nível (C, C++, Pascal, PHP, Java etc.) para uma linguagem de máquina (codificação binária), pois só dessa forma o computador irá executá-lo. O algoritmo escrito em linguagem de alto nível recebe o nome de código-fonte (ou programa fone) e o algoritmo resultado é denominado código executável (ou programa executável). De modo geral, dá-se o nome de compilador a qualquer software que faz essa conversão, porém, existem três métodos diferentes para se gerar o código executável: »

interpretadores;

»

compiladores;

»

tradutores.

1.6.1 Interpretadores São chamados interpretadores quando o programa conversor lê uma instrução do código-fonte, a converte em instrução de máquina (código binário) e já a executa. Em seguida, ele pega a próxima instrução e repete o processo até que todas as instruções sejam executadas.

Introdução aos Algoritmos

17

»»

Vantagens Correções e alterações são realizadas mais rapidamente. Consome menos memória.

»»

Desvantagens Execução mais lenta (necessidade de interprestar comando por comando). Necessidade de sempre ler o código original (código-fonte) para que ele seja executado.

Exemplos: Javascript, Lua, Ruby, PHP etc.

1.6.2 Compiladores Um compilador trabalha de forma semelhante ao interpretador, porém, ao final do processo de conversão, é gerado um arquivo chamado código executável (programa executável). O código executável é um arquivo binário que será executado diretamente pela máquina sem a necessidade de interpretação linha a linha. »»

Vantagens É executado de forma mais rápida e diretamente ao nível de máquina.

»»

Desvantagens A manutenção só é possível a partir do código-fonte. O código executável gerado só poderá ser executado em máquinas de mesma arquitetura.

Exemplos: C, C++, C#, Pascal etc.

1.6.3 Tradutores Existe um terceiro método que trabalha de forma intermediária entre os compiladores e interpretadores. Um tradutor gera, a partir do código-fonte, um código intermediário, mas que não exige tanto espaço de memória quanto o código original. É gerado, a partir do código intermediário, o código executável da forma que um interpretador funciona. »»

Vantagens Independência da arquitetura que fará a execução final.

»»

Desvantagens Necessidade de um interpretador específico na máquina do usuário final que fará a interpretação.

Exemplo: Java

18

Algoritmos - Técnicas de Programação

A equipe de desenvolvimento deverá escolher entre os diversos tipos de ferramentas de programação, ou linguagens de programação, disponíveis no mercado, levando em consideração diversos fatores como hardware, sistema operacional, velocidade de execução, limitação tecnológica etc.

1.7 Recomendações para resolução de problemas A construção de algoritmos requer tempo e paciência, porém, em diversas literaturas, são citadas algumas técnicas que facilitam e aceleram esse processo. Antes de começar a desenhar o diagrama de blocos, que irá orientar a construção do algoritmo e, por fim, a elaboração do programa, deve-se ficar atento ao problema a ser resolvido, ou seja, ao objetivo a ser alcançado, que é o que o programa deverá gerar de saída. Também deve-se pensar em quais dados serão necessários para o processamento, em como esses dados serão processados e em quais cálculos devem ser criados. Observe, a seguir, quatro regras simples para a construção dos diagramas de blocos de forma correta: 1)

Níveis: divida os diagramas de blocos em vários níveis. Os primeiros devem conter apenas as ideias principais e não os detalhes. Deixe o refinamento para as etapas seguintes.

2)

De cima para baixo: uma boa prática é sempre construir os blocos de cima para baixo.

3)

Não cruzar linhas: evite e, se possível, nunca cruze as linhas de fluxo de dados nos diagramas de bloco.

4)

Português estruturado: assim que os diagramas de blocos forem concluídos, transcreva para o português estruturado.

Exercício resolvido Um funcionário recebe determinado salário mensal. Faça um programa que leia o valor do salário mensal e o índice (em porcentagem) do reajuste a ser concedido. O programa deverá imprimir na tela o novo salário do funcionário.

Solução Em primeiro lugar, devemos entender o principal problema a ser resolvido. Nesse caso, calcular o valor do novo salário. A segunda etapa apresenta um detalhamento no que se refere à entrada e saída, ou seja, deve-se entrar com o valor do salário atual e com o índice do reajuste para que, após o cálculo, seja exibido o valor do novo salário.

Introdução aos Algoritmos

19

Exercício resolvido Na terceira etapa, vamos trabalhar o processo de gerar o cálculo do novo salário, introduzindo o conceito de variáveis (você verá mais sobre isso nos próximos capítulos). Serão digitados dois valores, um para o salário atual e outro para o índice de reajuste (em porcentagem). Com esses dados, será calculado o novo salário. Sendo assim, temos a Figura 1.9. Início

SALÁRIO, ÍNDICE

novoSalário

salário + salário

índice/100

novoSalário

Fim

Figura 1.9 - Diagrama de bloco nível 2 para o cálculo do novo salário.

Você viu, na Figura 1.10, a primeira forma de notação gráfica. Agora, iremos transcrever o diagrama de blocos para uma forma narrativa denominada pseudocódigo ou português estruturado. O português estruturado se aproxima muito da linguagem (por exemplo, PASCAL, C, FORTRAN, BASIC, JAVA, PHP etc.) utilizada pelos computadores para gerarem o programa a ser executado, porém, não tem o mesmo rigor sintático de sua escrita. A seguir, é apresentado um exemplo do algoritmo escrito em português estruturado. programa SALARIO var

SALÁRIO, ÍNDICE, NOVOSALÁRIO: real

inicio

leia SALÁRIO, ÍNDICE NOVOSALÁRIO ← SALÁRIO + SALÁRIO * ÍNDICE / 100 escreva NOVOSALÁRIO

fim

1.8 Tabela ASCII A tabela ASCII (pronúncia é “asqui”), ou American Standard Code for Information Interchange (Código Americano Padrão para Intercâmbio de Informações), é composta por 256 símbolos, que são utilizados pelos computadores eletrônicos. Foi criada entre os anos de 1963 e 1968 com participação e

20

Algoritmos - Técnicas de Programação

colaboração de várias companhias de comunicação norte-americanas, com o objetivo de substituir o até então utilizado código de Baudot, que era limitado apenas a 32 combinações diferentes. As tabelas a seguir mostram, respectivamente, a tabela ASCII padrão e a parte estendida utilizada para a representação de caracteres da página de código 850 definida pela Microsoft, destinadas aos caracteres acentuados usados em diversos idiomas. Tabela 1.2 - Tabela ASCII padrão (códigos de caracteres 0-127) (nul)

041d 29h )

001d 01h ☺ (soh)

042d 2Ah *

002d 02h ☻ (stx)

043d 2Bh +

000d 00h

003d 03h ♥ (etx)

044d 2Ch ,

004d 04h ♦ (eot)

045d 2Dh -

005d 05h ♣ (enq)

046d 2Eh .

006d 06h ♠ (ack)

047d 2Fh /

(bel)

048d 30h 0

008d 08h ◘ (bs)

049d 31h 1

009d 09h ○ (tab)

050d 32h 2

010d 0Ah ◙ (lf)

051d 33h 3

011d 0Bh ♂ (vt)

052d 34h 4

012d 0Ch ♀ (np)

053d 35h 5

013d 0Dh ♪ (cr)

054d 36h 6

014d 0Eh ♫ (so)

055d 37h 7

015d 0Fh ☼ (si)

056d 38h 8

016d 10h ► (dle)

057d 39h 9

017d 11h ◄ (dc1)

058d 3Ah :

018d 12h ↕ (dc2)

059d 3Bh ;

019d 13h ‼ (dc3)

060d 3Ch <

020d 14h ¶

(dc4)

061d 3Dh =

021d 15h §

(nak)

062d 3Eh >

022d 16h ▬ (syn)

063d 3Fh ?

023d 17h ↕ (etb)

064d 40h @

024d 18h ↑ (can)

065d 41h A

007d

07h

•

025d 19h ↓ (em)

066d 42h B

026d 1Ah → (eof)

067d 43h C

027d 1Bh ← (esc)

068d 44h D

028d 1Ch ∟ (fs)

069d 45h E

029d 1Dh ↔ (gs)

070d 46h F

030d 1Eh ▲ (rs)

071d 47h G

031d 1Fh ▼ (us)

072d 48h H

032d 20h

073d 49h I

033d 21h !

074d 4Ah J

034d 22h "

075d 4Bh K

035d 23h #

076d 4Ch L

036d 24h $

077d 4Dh M

037d 25h %

078d 4Eh N

038d 26h &

079d 4Fh O

039d 27h '

080d 50h P

040d 28h (

081d 51h Q

Introdução aos Algoritmos

21

082d 52h R

105d 69h i

083d 53h S

106d 6Ah j

084d 54h T

107d 6Bh k

085d 55h U

108d 6Ch l

086d 56h V

109d 6Dh m

087d 57h W

110d 6Eh n

088d 58h X

111d 6Fh o

089d 59h Y

112d 70h p

090d 5Ah Z

113d 71h q

091d 5Bh [

114d 72h r

092d 5Ch \

115d 73h s

093d 5Dh ]

116d 74h t

094d 5Eh ^ 095d 5Fh _

117d 75h u

096d 60h `

119d 77h w

097d 61h a

120d 78h x

118d 76h v

098d 62h b

121d 79h y

099d 63h c

122d 7Ah z

100d 64h d

123d 7Bh {

101d 65h e

124d 7Ch |

102d 66h f

125d 7Dh }

103d 67h g

126d 7Eh ~

104d 68h h

127d 7Fh ⌂

Tabela 1.3 - Tabela ASCII estendida (códigos de caracteres 128-255; página de código 850)

22

128d 80h Ç

152d 98h ÿ

129d 81h ü

153d 99h Ö

130d 82h é

154d 9Ah Ü

131d 83h â

155d 9Bh ø

132d 84h ä

156d 9Ch £

133d 85h à

157d 9Dh Ø

134d 86h å

158d 9Eh ×

135d 87h ç

159d 9Fh ƒ

136d 88h ê

160d A0h á

137d 89h ë

161d A1h í

138d 8Ah è

162d A2h ó

139d 8Bh ï

163d A3h ú

140d 8Ch î

164d A4h ñ

141d 8Dh ì

165d A5h Ñ

142d 8Eh Ä

166d A6h ª

143d 8Fh Å

167d A7h º

144d 90h É

168d A8h ¿

145d 91h æ

169d A9h ®

146d 92h Æ

170d AAh ¬

147d 93h ô

171d ABh ½

148d 94h ö

172d ACh ¼

149d 95h ò

173d ADh ¡

150d 96h û

174d AEh «

151d 97h ù

175d AFh »

Algoritmos - Técnicas de Programação

176d B0h ░

216d D8h Ï

177d B1h ▒

217d D9h ┘

178d B2h ▓

218d DAh ┌

179d B3h │

219d DBh █

180d B4h ┤

220d DCh ▄

181d B5h Á

221d DDh ¦

182d B6h Â

222d DEh Ì

183d B7h À

223d DFh ▀

184d B8h ©

224d E0h Ó

185d B9h ╣

225d E1h ß

186d BAh ║

226d E2h Ô

187d BBh ╗

227d E3h Ò

188d BCh ╝

228d E4h õ

189d BDh ¢

229d E5h Õ

190d BEh ¥

230d E6h μ

191d BFh ┐

231d E7h Þ

192d C0h └

232d E8h þ

193d C1h ┴

233d E9h Ú

194d C2h ┬

234d EAh Û

195d C3h ├

235d EBh Ù

196d C4h ─

236d ECh ý

197d C5h ┼

237d EDh Ý

198d C6h ã

238d EEh ¯

199d C7h Ã

239d AFh ´

200d C8h ╚

240d F0h -

201d C9h ╔

241d F1h ±

202d CAh ╩

242d F2h =

203d CBh ╦

243d F3h ¾

204d CCh ╠

244d F4h ¶

205d CDh ═

245d F5h §

206d CEh ╬

246d F6h ÷

207d CFh ¤

247d F7h ¸

208d D0h ð

248d F8h °

209d D1h Ð

249d F9h ¨

210d D2h Ê

250d FAh ·

211d D3h Ë

251d FBh ¹

212d D4h È

252d FCh ³

213d D5h ¹

253d FDh ²

214d D6h Ì

254d FEh ■

215d D7h Î

255d FFh

Vamos recapitular? Foi apresentado a você um panorama básico da história do computador, bem como os conceitos de lógica de programação de computadores, suas formas de representação em diagrama de blocos e português estruturado, permitindo um contato inicial com o conteúdo que será abordado mais detalhadamente ao longo desta obra.

Introdução aos Algoritmos

23

Agora é com você! 1)

24

Considerando o que foi estudado neste capítulo, explique: a)

Por que o ábaco tem sido considerado o precursor dos computadores.

b)

A importância do matemático George Boole para a computação.

2)

Apresente as principais recomendações estudadas para a construção de algoritmos em computação.

3)

Explique em poucas palavras a diferença entre algoritmo e programa. Todo algoritmo poderia se tornar um programa? Por quê?

Algoritmos - Técnicas de Programação

2 Programação Sequencial

Para começar Neste capítulo, vamos estudar uma das mais importantes técnicas de programação de computadores: a programação sequencial. Ao final do capítulo, será possível identificar e implementar programas sequenciais usando tipos primitivos de dados, variáveis, constantes, operadores fundamentais e mecanismos básicos de entrada de dados, processamento e saída de dados.

2.1 Etapas operacionais Programa sequencial, como o próprio nome diz, é um conjunto de rotinas programáveis executadas em sequência, ou seja, uma após a outra. Podemos organizar essas rotinas em três macroetapas: »

entrada de dados;

»

processamento de dados;

»

saída de dados.

Durante a entrada de dados, o computador recebe os dados que serão processados. Esses dados podem ser fornecidos pela pessoa que opera o programa ou por outro programa; por exemplo, a altura e o peso (massa corporal) de uma pessoa. Para realizar essa etapa, o computador emprega instruções específicas da linguagem de programação utilizada. Somente após a entrada de algum dado será possível ar à etapa de processamento de dados. Nesse momento, o computador será capaz de transformar os dados inseridos por meio de operações

25

lógicas e/ou aritméticas, como em um cálculo de índice de massa corporal, ou, ainda, utilizá-los para geração de outros dados e informações. A última etapa, saída de dados, só ocorre após haver algum tipo de processamento, pois ela apresenta os dados novos ou transformados por ele, com os quais é possível verificar situações e tomar decisões; por exemplo, procurar estudar mais a fim de aprender e ser considerado aprovado em determinada disciplina, ao verificar que, após o cálculo, a média parcial do aluno está muito abaixo do valor mínimo para aprovação.

2.2 Tipos de dados No mundo real, manipulamos diferentes tipos de dados para representar as mais variadas informações, além de sentimentos, desejos e intenções, como representações visuais (cores, luzes), táteis (texturas) e cinestésicas (feições e gestos). Na computação, os dados devem ser definidos de acordo com tipos predefinidos pela linguagem de programação ou estabelecidos pelo programador. Os tipos predefinidos são conhecidos como tipos primitivos de dados. Para efetuar qualquer uma das etapas da programação sequencial, é necessário definir os dados de modo que o computador compreenda o tipo de informação que eles representam. Os tipos primitivos estão organizados em três grupos: »»

Numéricos: representam valores numéricos, como preços de produtos, volume de uma embalagem, altura de uma pessoa.

»»

Caracteres: representam valores alfabéticos ou que combinem algarismos numéricos e alfabéticos (alfanuméricos), como o nome de uma pessoa, o endereço de um estabelecimento, o telefone de um consultório médico.

»»

Lógicos: representam valores lógicos, ou seja, que só podem ser verdadeiros ou falsos; por exemplo: indicar se alguém está ou não aprovado ou, ainda, se tem direito ou não a isenção de pagamento de agem no transporte coletivo.

Os dados numéricos podem, ainda, ter uma subclassificação, a depender do tipo de número que representam na memória do computador: inteiro ou real. Para entender melhor, acompanhe as explicações nos tópicos a seguir.

2.2.1 Dado numérico inteiro O dado numérico do tipo inteiro, positivo ou negativo, pertence ao conjunto dos números inteiros (o mesmo da Matemática - Z), ou seja, todos aqueles que não são fracionários. São valores numéricos inteiros: 1; −567; 0; 8.980; −8, entre outros.

2.2.2 Dado numérico real O dado numérico do tipo real, positivo ou negativo, pertence ao conjunto dos números reais (o mesmo da matemática - ℜ), ou seja, todos aqueles que são fracionários. São valores numéricos reais: −1.2; −567; 0; 8.980; 8.9 (por questões de paridade computacional, está sendo usado o ponto como separador de casas decimais em vez da forma oficial do idioma), entre outros. Perceba que todo número inteiro também é real, mas o contrário não é verdade.

26

Algoritmos - Técnicas de Programação

2.2.3 Dado caractere/cadeia O dado do tipo caractere costuma ser representado por um único símbolo entre aspas inglesas (“ ”). Os valores podem ser representados isoladamente por letras (maiúsculas ou minúsculas), numerais (0-9) e símbolos do computador, como aqueles presentes no teclado. Quando o valor caractere possui mais de um símbolo (mais de uma letra, número ou outros símbolos do teclado entre aspas inglesas), o dado que o representa é chamado de cadeia de caracteres ou string (que significa cordão ou colar). Podemos considerar exemplos de cadeia os valores: “Programação de computadores”, “CEP: 03909-020”, “Av. São Luiz, 340” e “8.908” e como exemplos de caracteres “A”, “b”, “1” e “-”. Fique de olho! O espaço em branco (“ ”) também é um caractere e deve ser considerado como tal.

Geralmente, não conseguimos fazer cálculos com dados do tipo string, sendo mais utilizados em operações de entrada e saída de dados, como receber o nome de um profissional (entrada de dados) ou emitir um parecer sobre sua habilitação (saída de dados).

2.2.4 Dado lógico Também conhecido como booleano, é o tipo de dado mais simples, caracterizando-se por representar apenas valores binários, ou seja, que indiquem duas possibilidades. São exemplos de valores binários: verdadeiro e falso; 1 e 0; sim e não. Apenas um desses valores pode ser atribuído, por vez, a um dado lógico.

2.3 Variáveis Variável é uma entidade computacional que representa um espaço reservado na memória do computador para armazenamento de dados durante a execução de um programa. Esses dados podem sofrer modificação ao longo da execução do programa, por isso têm esse nome. Para definir as variáveis, é necessário atribuir um nome a elas, conhecido como identificador. Identificar previamente as variáveis é muito importante para usá-las adequadamente no programa. Em muitas linguagens, isso é obrigatório. Antes de identificar as variáveis, é preciso saber que tipo de dado elas representarão. Você pode, inclusive, definir um padrão de nomenclatura para facilitar a identificação do tipo de dado que a variável contém. Além disso, há algumas regras que todo programador deve seguir ao estabelecer o nome de uma variável: »» »»

Inicie o nome apenas por caractere alfabético ou “_” (underline); nenhum outro caractere é aceito no início de um identificador (nome de variável). Não utilize caracteres especiais na nomenclatura de uma variável (é, ç, ã, &, %, #, @, *, -, entre outros), exceto o caractere “_” (underline).

Programação Sequencial

27

»»

»» »» »»

Se a variável for identificada por um nome composto, não pode haver espaço em branco; um modo comum de identificar variáveis com nomes compostos é utilizar o caractere “_” (underline). Não escolha nomes que já sejam utilizados pela linguagem de programação para representar comandos ou instruções predefinidas; esses nomes são chamados de palavras reservadas. Crie identificadores que representem o conteúdo da variável. Não utilize o mesmo nome para mais de uma variável.

São exemplos de nomes válidos: TipoDeInvestimento; F_Titular; FUNCIONAL_SETOR10; endereco. Por sua vez, os identificadores a seguir não são válidos, pois violam as regras expostas anteriormente: Endereço; 1a.Avaliacao; 7FONE; Resultado#Calculo; E-mail. Há, ainda, palavras reservadas às linguagens de programação (mas isso varia conforme a linguagem), as quais foram previamente definidas para funcionarem como comandos ou instruções do computador, não podendo ser usadas para outro fim. Para declarar variáveis em algoritmos, ou seja, criar variáveis com identificador único, utilizamos o comando var. Logo abaixo da palavra var podemos indicar as variáveis que desejamos criar, sempre respeitando a sintaxe apresentada a seguir:

Os identificadores são de uso único. Em geral, algumas palavras reservadas são típicas, tais como: int, integer, real, boolean, function, result, return, entre outras.

var :

2.4 Constantes Além das variáveis, temos as entidades conhecidas como constantes, que são valores fixos, estáveis. Uma vez atribuído, o valor de uma constante mantém-se o mesmo até o final da execução do programa. Constantes são muito úteis na definição de valores que serão usados diversas vezes no programa e que não devem sofrer alteração. Como exemplos, temos a grandeza matemática pi (π), cujo valor aproximado é 3,14159, ou, ainda, a alíquota base de cálculo do INSS (11%). No programa, esses valores poderiam ser definidos como constantes e ser representados pelos identificadores dessas constantes. Por exemplo: pi e aliquota_inss. Para declarar constantes em algoritmos, ou seja, criar constantes com identificador único, utilizamos o comando const. Logo abaixo da palavra const podemos indicar as constantes que desejamos criar, sempre observando a sintaxe apresentada a seguir: const PI = 3.14159 ALIQUOTA_INSS = 0.11

28

Algoritmos - Técnicas de Programação

As regras para definição dos identificadores de constantes são as mesmas utilizadas para nomear variáveis.

2.5 Operadores aritméticos Para realizar cálculos, os programas fazem uso de operadores aritméticos. Todas as operações matemáticas realizadas pelo computador são realizadas por meio de operadores aritméticos, que podem ser binários ou unários. Os operadores binários são aqueles que são utilizados com dois operandos; por exemplo, o operador de soma (+): A + B. Os operadores unários são aqueles que realizam operações aritméticas com apenas um operando; por exemplo, a inversão de sinal: −A. O Quadro 2.1 apresenta alguns dos operadores aritméticos utilizados na concepção de algoritmos programáveis. Assim como na aritmética, na computação os operadores têm ordem de precedência; por isso, sempre que for preciso, utilize parênteses para deixar clara a ordem de prioridade da operação. Quadro 2.1 - Operadores aritméticos Operador

Descrição

Tipo

Prioridade

Resultado

Exemplo

+x

Manutenção de sinal

Unário

sem

Inteiro ou real

+3

–x

Inversão de sinal

Unário

sem

Inteiro ou real

–4

Binário

1

Inteiro ou real

RAIO ↑ 2 VOLUME ↑ (1 / 3)

xa

x↑a

Exponenciação de

x ↑ (1 / a)

Radiciação de a√x

Binário

1

Inteiro ou real

x/z

Divisão de x por z

Binário

2

Real

x*z

Multiplicação de x por z

Binário

2

Inteiro ou real

SALARIO * BONUS

x–z

Subtração de x e z

Binário

3

Inteiro ou real

SALARIO – IRRF

x+z

Adição de x e z

Binário

3

Inteiro ou real

SALARIO + COMISSAO

x div z

Divisão de x por z

Binário

4

Inteiro

MEDIA / 3

QTDPRATOS div CLIENTES

Fique de olho! A operação matemática para o cálculo da exponenciação é definida de maneira muito variada nas linguagens de programação de computadores. Considerando a operação de ax, esse cálculo pode ser executado, dependendo da linguagem de programação em uso, como: pow(a,x); power(a,x); a^x ou a**x, entre outras formas. No entanto, há uma maneira genérica de realizar esse cálculo: por meio das funções dos logaritmos neperiano e exponencial, com base na expressão ex ln a, que pode ser escrita de modo genérico - para as linguagens de programação - pela expressão exp(x * ln(a)), considerando que as funções exp() e ln() podem ser referenciadas, na linguagem em uso, de modo um pouco diferente do apresentado neste livro, mas mantendo essa característica.

2.6 Expressões aritméticas Para a realização de muitos dos processamentos computacionais, é necessário utilizar expressões aritméticas, cuja sintaxe difere da sintaxe matemática.

Programação Sequencial

29

Por exemplo, considere o cálculo do salário dos funcionários de uma empresa de logística, cuja fórmula é a seguinte: SALÁRIO = COMISSÃO2 – (SALÁRIO x ALÍQUOTA DO INSS). SALÁRIO e COMISSÃO contêm valores que variam conforme o funcionário. Por sua vez, ALÍQUOTA DO INSS possui um valor fixo (0.11) que vale para todos os funcionários daquela instituição. Ao converter essa fórmula na linguagem computacional, é preciso fazer algumas adequações. A primeira é definir os identificadores das variáveis e das constantes, de acordo com as regras estudadas. A segunda é substituir os operadores matemáticos pelos aritméticos da computação. Por exemplo, o símbolo que representa a operação de multiplicação - x - será substituído pelo operador *. Logo, a fórmula do salário ora apresentada poderia ser implementada no algoritmo da seguinte forma: SALARIO ← (COMISSAO ↑ 2) – (SALARIO * ALIQUOTA_INSS) ou SALARIO ← (COMISSÃO * COMISSAO) – (SALARIO * ALIQUOTA_INSS) Em programação, utilizamos parênteses para indicar qualquer ordem de prioridade; logo, as chaves e os colchetes empregados em operações aritméticas, na matemática, são substituídos pelos parênteses. O sinal de igual (=) também é substituído pelo sinal de atribuição de valores (←); ele indica que o valor da expressão aritmética será armazenado na variável à esquerda do sinal. No exemplo, o cálculo será armazenado na variável SALARIO. Antes de efetuar a atribuição, o computador limpa o conteúdo da variável para não haver interferência do valor antigo sobre o novo valor. Considere, ainda, a necessidade de representar a fórmula de cálculo da área da coroa circular:

R

Acc = (R2 r2) r

Figura 2.1 - Representação do cálculo da área da coroa circular.

Na fórmula, π é um valor constante (π = 3,14159), R é o raio do círculo e r é o raio do círculo inscrito. Para computarmos essa fórmula, é necessário converter seus símbolos nos correspondentes em computação, ficando da seguinte forma: A ← PI * (R ↑ 2 – r ↑ 2) ou A ← PI * ((R * R) – (r * r)) A constante PI guarda o valor de π.

30

Algoritmos - Técnicas de Programação

O programador deve converter expressões matemáticas em expressões aritméticas computacionais equivalentes, de modo que o cálculo seja realizado corretamente.

2.7 Instruções e comandos Os comandos são definidos pela linguagem de programação utilizada, ou seja, variam conforme a linguagem. São representados por palavras reservadas, definidas no conjunto que chamamos de gramática da linguagem. A gramática da linguagem define todas as regras de uso da linguagem de programação, bem como o seu funcionamento. O conjunto de todas as palavras reservadas da linguagem de programação é conhecido como vocabulário. Portanto, comandos com a mesma função podem ter grafias diferentes em linguagens distintas, mas executar a mesma ação. Por exemplo, para escrever a saída de dados na linguagem C, utilizamos a instrução printf(“%d”, valor). Para a mesma instrução na linguagem Pascal, utilizamos write (valor). Já em português estruturado, usamos a instrução leia valor. Programadores também podem criar os próprios comandos, a depender da linguagem de programação utilizada. De modo geral, os comandos servem para indicar ao computador uma ação a ser tomada, como ler um valor, que pode ser a nota de um aluno ou a quantia solicitada para saque, por exemplo. O conjunto de comandos ordenados denomina-se instrução. Citamos, no início do capítulo, que a programação sequencial pode ser dividida em três etapas: entrada de dados, processamento e saída de dados. Para a leitura de dados, é imprescindível solicitá-los à fonte de dados, a qual pode ser o próprio usuário. Podemos, por exemplo, solicitar que o usuário informe quanto ele deseja sacar. Em português estruturado (uma das notações que utilizamos para construir algoritmos), o comando que informa algo na tela para o usuário é o escreva (por exemplo, escreva “Qual é o valor do saque?”); o comando que lerá o valor digitado pelo usuário no teclado será o leia (por exemplo, leia valor_saque). Esses dois comandos, juntos, formam uma instrução de entrada de dados. As instruções devem ser adas corretamente para o computador; senão, corre-se o risco de ele executar ações não desejadas e, até mesmo, de não funcionar. Portanto, é preciso ter cuidado ao escolher os comandos que serão usados e escrevê-los corretamente, seguindo as regras de cada linguagem. Por enquanto, trabalharemos com a linguagem algorítmica, que é genérica e mais flexível, mas, aos poucos, você conhecerá sintaxes (modos de escrever) de outras linguagens de programação. Citamos a escrita em tela de computador (saída) e a leitura do teclado, mas existem outras formas de entrada e saída de dados. Por exemplo, podemos escrever dados em uma impressora, em fitas magnéticas, em discos (como CD e DVD) etc. O programa também pode ler dados de outras fontes, como discos, arquivos na Internet, leitores ópticos (como aqueles que decodificam códigos de barras), entre outras. Por conta da vasta possibilidade de mecanismos de entrada e saída de dados, os algoritmos serão escritos, neste livro, utilizando leia como comando de entrada de dados e escreva como comando de saída de dados.

Programação Sequencial

31

Diagrama de bloco

Diagrama de bloco é uma notação utilizada para descrever algoritmos. Veja na Figura 2.2 alguns dos símbolos mais comuns.

Entrada manual de dados

Saída-padrão de dados

Figura 2.2 - Estrutura dos símbolos para as instruções de entrada e de saída de dados.

Português estruturado

Outra forma de descrever algoritmos é por meio do formato português estruturado, em que o algoritmo é definido textualmente, muito próximo de como será implementado no computador, mas em idioma português. Por exemplo, podemos utilizar a seguinte sintaxe para escrever um pequeno trecho de programa para saque bancário: [...]

escreva "Quanto deseja sacar?" leia VALOR_SAQUE

se (SALDO >= VALOR_SAQUE) então SALDO ← SALDO – VALOR_SAQUE escreva "Saque realizado com sucesso, retire seu dinheiro."

senão

escreva "Saque não realizado."

fim_se

[...]

Amplie seus conhecimentos Programa é um conjunto estruturado de instruções que permitem ao computador realizar operações de transformação de dados. Para isso, o programa deve apresentar um conjunto de instruções que indiquem ao computador como executar tais operações. Essas instruções são formadas por estruturas de controle que variam de uma linguagem para outra. Os modos mais comuns de estruturação desse controle são: » Estruturação monolítica: baseada em desvios (condicionais ou não). » Estruturação iterativa: baseada em controle de iteração (ciclos); não permite desvios incondicionais. » Estruturação recursiva: baseada em mecanismos de sub-rotinas recursivas, ou seja, que se utilizam de si próprias para definir a próxima operação, sendo uma forma indutiva de especificar operações; assim como a estruturação iterativa, não permite desvios incondicionais. Para saber mais, leia Diverio e Menezes (2011).

32

Algoritmos - Técnicas de Programação

Para auxiliá-lo na compreensão do que foi apresentado, seguem alguns problemas resolvidos com o uso de algoritmos computáveis.

Exemplo Elaborar um programa de computador que calcule e apresente o volume de um cubo.

Solução Para calcular o volume de um cubo, é necessário conhecer dois elementos. O primeiro é a fórmula de cálculo do volume de cubo, sendo V = L3, em que L é o valor de um dos lados do cubo (todos os lados têm o mesmo comprimento) e V é o volume calculado. Sendo assim, basta estabelecer que a fórmula matemática deve ser convertida em uma expressão aritmética algorítmica equivalente, que pode ser: V ← L * L * L ou V ← L ↑ 3.

Diagrama de bloco Início

L

V

L 3

V

Fim

Figura 2.3 - Diagrama de blocos para o cálculo do volume do cubo.

Português estruturado programa VOLUME_CUBO var

L : real V : real

início

leia L V ← L ↑ 3 escreva V

fim

Programação Sequencial

33

Desenvolver um programa que calcule o índice de massa corpórea (IMC) de uma pessoa. Para elaborar o programa, é necessário possuir dois dados: altura e peso da pessoa. Para cálculo do IMC, a fórmula matemática é a seguinte: IMC = peso  (altura x altura).

Solução Para solucionar o problema, é necessário realizar os seguintes os: 1)

Efetuar a leitura do peso da pessoa (quantidade de massa).

2)

Ler a altura da pessoa.

3)

Calcular o IMC.

4)

Exibir o valor do IMC calculado.

A ordem de leitura dos dados de entrada não faz diferença no cálculo e na computação dos dados.

Diagrama de bloco INÍCIO

PESO; ALTURA

IMC PESO / (ALTURA ALTURA)

IMC

FIM

Figura 2.4 - Diagrama de bloco do programa de cálculo do IMC.

Português estruturado programa IMC var

IMC : real

PESO, ALTURA : real

início

leia PESO

leia ALTURA IMC ← PESO / (ALTURA * ALTURA) escreva IMC

fim

34

Algoritmos - Técnicas de Programação

Desenvolver um programa que calcule o IPVA, dado o valor venal do veículo. Considere a alíquota única para cálculo de IPVA.

Solução Para a solução do problema, considere a existência de um valor constante que representará a alíquota do IPVA, não importa o valor do veículo, ou seja, um valor fixo que não mudará ao longo do programa e que será o mesmo para qualquer dado de entrada. Nesse caso, podemos trabalhar com uma constante e duas variáveis. A constante representará a alíquota do IPVA e pode ser nomeada como ALIQUOTA. As variáveis representarão o valor venal do veículo e o resultado do cálculo do IPVA, podendo ser identificadas como VALOR_VENAL e IPVA, respectivamente.

Português estruturado

Diagrama de bloco INÍCIO ALIQUOTA = 0.04

VALOR_VENAL

IPVA

VALOR_VENAL ALIQUOTA

IPVA

FIM

Figura 2.5 - Diagrama de bloco do programa de cálculo do IPVA.

programa CALC_IPVA const

ALIQUOTA = 0.04

var

VALOR_VENAL : real IPVA : real

início

leia VALOR_VENAL

IPVA ← VALOR_VENAL * ALIQUOTA

escreva IPVA

fim

Como regra geral de trabalho e de organização, as constantes com o comando const sempre serão definidas à frente das variáveis com o comando var.

Vamos recapitular? Neste capítulo, estudamos alguns elementos fundamentais da programação sequencial, como a definição dos tipos de dados primitivos e sua finalidade. Vimos, também, identificadores, variáveis, constantes, operadores relacionais, expressões aritméticas e sua adequação à linguagem algorítmica, além das etapas de processamento de um programa sequencial (entrada de dados, processamento e saída de dados).

Programação Sequencial

35

Agora é com você! 1)

Quais sentenças a seguir são verdadeiras? a)

O dado −457,90 é do tipo numérico inteiro.

b)

O dado 0 (zero) é do tipo numérico inteiro.

c)

O dado < > é do tipo lógico.

d)

Todo dado numérico inteiro também é numérico real.

e)

O dado “1,99” é do tipo numérico real.

f)

O dado “Rua A, quadra 2” é do tipo cadeia/string.

g)

O dado −4 é do tipo numérico inteiro.

h)

O dado “cinco” é do tipo numérico inteiro.

i)

Na instrução leia numRG, numRG é considerado um dado de entrada.

j)

Após atribuir valor a uma constante, o computador aceita que esse valor seja alterado apenas uma vez.

k)

Nota é um identificador válido para uma variável/constante.

l)

O identificador enDereco não é válido para uma variável/constante.

m) Fone&Email é um identificador válido para uma variável/constante. n) E-mail não é um identificador válido para uma variável/constante. 2)

36

Elabore algoritmos dos seguintes problemas, utilizando diagramas de blocos e codificação em português estruturado: a)

Ler o valor gasto com combustível nos três primeiros meses do ano, calcular e exibir a média aritmética desse gasto.

b)

Ler a altura de um homem e calcular o peso ideal. O peso ideal, neste problema, deve ser calculado por meio da fórmula Peso ideal = (K x altura) − B, sendo K = 72.7 e B = 58.

c)

Ler os valores X e Y e efetuar o swap, ou seja, a troca de valores entre X e Y. Ao final, apresentar os novos valores de X e Y.

d)

Ler o valor do raio de uma circunferência, calcular seu diâmetro e sua área e exibi-los. A fórmula para cálculo da área de uma circunferência é Área = π x raio2, sendo π = 3.14159.

e)

Ler um valor numérico inteiro e exibi-lo elevado à quarta potência.

Algoritmos - Técnicas de Programação

3 Programação com Desvios

Para começar O objetivo principal deste capítulo é o estudo dos mecanismos para que possamos efetuar uma tomada de decisão simples, composta ou encadeada, por meio do processamento lógico. Para que uma tomada de decisão seja efetuada pela máquina, destacamos, também, operadores lógicos e relacionais.

3.1 Tomada de decisões Na construção de algoritmos, muitas vezes é necessário que uma parte do código só seja executada se determinada condição for satisfeita. Essa condição é definida por uma expressão lógica cujo resultado sempre será um valor falso ou verdadeiro. A expressão lógica, que testará as condições impostas pelo algoritmo, utiliza uma relação entre um par de elementos, o qual pode ser composto por variável versus variável ou variável versus constante, e um operador relacional (apresentado no próximo tópico). Ao desenvolver os diagramas de blocos, deve-se utilizar os símbolos de decisão e conexão, conforme a Figura 3.1.

Figura 3.1 - Símbolos de decisão e conexão, necessários ao desenvolvimento de diagramas de blocos.

37

Amplie seus conhecimentos Você sabia que o ENIAC (Electronic Numerical Integrator and Computer) é considerado o primeiro computador eletrônico digital? Foi construído entre 1943 e 1945, entrando em operação em julho de 1946 com a finalidade de ser usado em cálculos de balística. Para seu funcionamento havia 17.468 válvulas, 1.500 relés, além de diversos outros componentes eletrônicos, pesando 30 toneladas! Os técnicos que o operavam trabalhavam dentro do computador. Para saber um pouco mais, consulte: . o em: 28 jan. 2014.

3.2 Operadores relacionais Um operador relacional é utilizado para comparar a relação entre pares de valores definidos por variáveis ou constantes. Sempre deve existir um par de valores para determinar se a condição é verdadeira ou falsa. Pela análise dos operadores relacionais, um computador consegue determinar as ações a serem tomadas pela máquina. A Tabela 3.1 apresenta os operadores relacionais utilizados na programação de computadores. Tabela 3.1 - Operadores relacionais Operador

Descrição

=

Igual a

>

Maior que

<

Menor que

>=

Maior ou igual a

<=

Menor ou igual a

<>

Diferente de

Veja exemplos de operações válidas entre variáveis e constantes: A = B; A > B; A < B; A >= B; A <= B; A <> B; A = 2; A > 2; A < 2; A >= 2; A <= 2; A <> 2 Observe que sempre deve existir um par de valores para a devida validação. Exemplos de operações NÃO válidas: A = B = C ou A > 5 > 2 Todos os operadores relacionais possuem o mesmo nível de precedência, portanto não há necessidade de se preocupar em alterá-lo.

38

Algoritmos - Técnicas de Programação

3.3 Desvios condicionais Com os conhecimentos adquiridos nos capítulos anteriores, já temos condições de resolver diversos tipos de problemas que envolvam entradas de dados, processamentos e saídas com a utilização de variáveis, constantes e operadores aritméticos. Em diversos casos, porém, para que o processamento seja mais adequado, a máquina deverá decidir quais trechos de código serão ou não executados, por meio dos desvios condicionais. Basicamente, há três modos de desvio condicional: simples, composto e seletivo.

3.3.1 Desvio condicional simples Em um desvio condicional simples, determinado bloco só será executado se a condição imposta for verdadeira; caso contrário, todo o bloco será ignorado. No caso, utilizaremos a instrução: se...então...fim_se. No diagrama de blocos da Figura 3.2, observe que a letra S representa sim, a fim de mostrar o fluxo de execução quando a condição for verdadeira. Já a letra N representa não e será executada quando a condição for falsa. Quando a condição for falsa, note que nada será executado. O símbolo de decisão deve ser utilizado quando houver a necessidade de tomar uma decisão no programa. Diagrama de blocos

N

Condição

S

Bloco de comandos que só será executado quando a condição for verdadeira

Bloco de comandos que sempre será executado

Figura 3.2 - Estrutura do símbolo para a instrução se...então...fim_se.

Português estruturado se ( ) então fim_se

Programação com Desvios

39

Exemplo Construir um programa que faça a leitura de dois números reais e imprima na tela a média aritmética simples. Se a média for maior ou igual a 7.0, deve imprimir também a palavra “aprovado”.

Solução Para este exercício, precisamos definir apenas três variáveis reais, ou seja, numero1, numero2 e media. Após calcular e imprimir a média, devemos testar, por meio de desvio condicional simples, se a média é maior ou igual a 7.0, imprimindo a mensagem “aprovado”.

Diagrama de blocos INÍCIO

NUMERO1, NUMERO2 (NUMERO1+NUMERO2)/2

MEDIA

N

S MEDIA >= 7 ‘‘APROVADO’’

FIM

Figura 3.3 - Exemplo de utilização da estrutura se...então...fim_se.

Português estruturado programa MEDIA var

NUMERO1, NUMERO2, MEDIA : real

início

leia NUMERO1 leia NUMERO2

MEDIA ← (NUMERO1 + NUMERO2)/ 2 escreva MEDIA

se (MEDIA > 7) então

escreva "aprovado"

fim_se

fim

40

Algoritmos - Técnicas de Programação

3.3.2 Desvio condicional composto Em um desvio condicional composto, é possível determinar o bloco a ser executado para uma condição verdadeira e o bloco a ser executado para uma condição falsa. No caso, utilizaremos a instrução: se...então...senão...fim_se. Diagrama de blocos

N

Condição

S

Bloco de comandos que só será executado quando a condição for verdadeira

Bloco de comandos que só será executado quando a condição for falsa

Bloco de comandos que sempre será executado

Figura 3.4 - Diagrama de blocos para a instrução se...então...senão...fim_se.

Português estruturado se ( ) então senão fim_se

Exemplo Construir um algoritmo que leia dois números reais e calcule a média aritmética desses números. O programa deve imprimir APROVADO se a média for maior ou igual a 7.0; caso contrário, deve imprimir REPROVADO.

Solução Para este exemplo, tomaremos como base o exemplo anterior, em que não é possível optar por imprimir APROVADO, se a média for superior ou igual a 7, ou, do contrário, REPROVADO. Note que devemos utilizar, aqui, o SENÃO.

Programação com Desvios

41

Diagrama de blocos INÍCIO

NUMERO1, NUMERO2

MEDIA

(NUMERO1+NUMERO2)/2

MEDIA

N

MEDIA >=7

‘‘REPROVADO’’

S

‘‘APROVADO’’

FIM

Figura 3.5 - Exemplo de utilização da estrutura se...então...senão...fim_se.

Português estruturado programa MEDIA_2 var

NUMERO1, NUMERO2, MEDIA : real

início

leia NUMERO1 leia NUMERO2

MEDIA ← (NUMERO1 + NUMERO2)/ 2 escreva MEDIA

se (MEDIA > 7) então

escreva "aprovado"

senão

escreva "reprovado"

fim_se

fim

3.3.3 Desvio condicional encadeado Se existem muitas possibilidades de resolver determinado problema, o tipo de desvio condicional mais apropriado é o encadeado. No caso, utilizaremos a estrutura no seguinte formato: se...então se...então se... senão...fim_se.

42

Algoritmos - Técnicas de Programação

Diagrama de blocos

N

S

Condição 1

S

N

Condição 2

Ação executada quando Condição 1 e Condição 2 forem verdadeiras

Figura 3.6 - Desvio condicional encadeado com decisão simples.

Português estruturado se( ) então

se( ) então fim_se

fim_se

N

Condição 1

S

Ação executada quando Condição 1 for falsa

Ação executada quando Condição 1 e Condição 2 forem verdadeiras

S

Condição 2

N

Ação executada quando Condição 1 for verdadeira e Condição 2 for falsa

Figura 3.7 - Desvio condicional encadeado com decisão composta.

Programação com Desvios

43

se( ) então

se( ) então senão fim_se

senão

fim_se

3.3.4 Desvio com múltipla escolha Nos casos em que se tem uma mesma condição, porém com múltiplos valores, a estrutura se...senão se... seria muito grande, portanto cansativa de se construir. Nesses casos, é recomendado construir o algoritmo utilizando a estrutura de desvio com múltipla escolha. Como restrição, a condição só aceita o operador relacional de igualdade; na construção da instrução, utilizaremos os comandos caso/seja...faça/senão/fim_caso. Diagrama de blocos

Condição 1

S

Bloco de comandos que só será executado quando a condição 1 for verdadeira

N Condição 2

S

Bloco de comandos que só será executado quando a condição 2 for verdadeira

N S Condição 3

Bloco de comandos que só será executado quando a condição 3 for verdadeira

N Bloco de comandos que só será executado quando todas as condições forem falsas

Bloco de comandos que sempre será executado

Figura 3.8 - Estrutura de tomada de decisão por seleção.

44

Algoritmos - Técnicas de Programação

Português estruturado caso

seja faça [ação para condição 1 verdadeira]

seja faça

[ação para condição 2 verdadeira]

seja faça

[ação para condição 3 verdadeira]

senão

[ação para nenhuma condição satisfeita]

fim_caso

3.4 Divisibilidade Vamos ver agora um assunto que com certeza já é conhecido dos primeiros anos do ensino básico, que são operações aritméticas de divisão realizadas com números naturais1. Operações aritméticas de divisão com números naturais são aquelas que possuem valor de resto com quociente inteiro. A Figura 3.10 nos apresenta os os da divisão do número natural 5 com o número natural 2, que dá como resultado um quociente igual a 2 e um valor de resto igual a 1. 5 2

5 2 2

5 2 2

x Dividendo Divisor

5 2 4 2

5 2 -4 2 1

5

2

-4

2

1

Quociente Resto

Figura 3.11 - Exemplo de divisão de dois números naturais.

A Figura 3.11 nos mostra que para obter o valor do resto, devemos fazer a subtração do valor do quociente multiplicado pelo divisor sob o valor do dividendo. Assim, devemos usar a expressão Resto = Dividendo – Divisor ⋅ Quociente, que, computacionalmente, pode ser escrita como sendo: Resto ← Dividendo – Divisor * (Dividendo div Divisor), onde o operador aritmético div faz o cálculo de divisão com quociente inteiro.

Exemplo Desenvolver um programa de computador que leia um valor numérico inteiro e mostre mensagem informando se o número lido é par ou ímpar.

1

Números naturais são formados pelo conjunto de todos os números inteiros positivos, incluindo-se zero e representado pela letra N maiúscula, sendo: N = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ... }.

Programação com Desvios

45

Solução Para resolver este problema, é necessário verificar se a condição do valor lido é ou não divisível por 2. Para tanto, leia um valor numérico inteiro qualquer (variável N), calcule o resto da divisão de N por 2 (variável R) e verifique se a variável R possui o valor de resto igual a zero e, se sim, apresentar a mensagem “Valor par”; caso contrário, mostrar a mensagem “Valor impar”.

Diagrama de blocos INÍCIO

N

RESTO

N-2

(N DIV 2)

N

S RESTO = 0

‘‘VALOR IMPAR’’

‘‘VALOR PAR’’

FIM

Figura 3.12 - Diagrama de blocos para verificar se N é par ou ímpar.

Português estruturado programa PAR_OU_IMPAR var

N, RESTO : inteiro

início

leia N

RESTO ← N - 2 * (N div 2) se (RESTO = 0) então

escreva "Valor par"

senão

escreva "Valor impar"

fim_se

fim

Observe o uso da expressão RESTO ← N − 2 * (N div 2), que obtém o valor de divisibilidade da operação de divisão entre a variável N (dividendo) e o valor 2 (divisor) gerando o valor do RESTO da divisão entre N e 2. A instrução de tomada de decisão faz uso da condição (RESTO = 0), que é verdadeira se o valor de RESTO for igual a zero.

46

Algoritmos - Técnicas de Programação

3.5 Operadores lógicos Para solucionar determinados problemas, temos a necessidade de combinar várias condições em uma instrução condicional. Nesses casos, utilizamos os operadores lógicos: .e., .ou. e .não..

3.5.1 Operador lógico .e. Com a utilização do operador lógico .e., todas as condições da operação devem ser verdadeiras para que o bloco de comandos seja executado. Observe a Tabela 3.2. Tabela 3.2 - Tabela-verdade para o operador lógico .e. Condição 1

Condição 2

Condição 1 .e. Condição 2

Falsa

Falsa

Falsa

Verdadeira

Falsa

Falsa

Falsa

Verdadeira

Falsa

Verdadeira

Verdadeira

Verdadeira

Diagrama de blocos

Condição 1 .e. Condição 2

N

S

Bloco de comandos que só será executado quando a condição for verdadeira

Bloco de comandos que sempre será executado

Figura 3.8 - Exemplo de utilização do operador lógico .e.

Português estruturado se ( ) .e. ( ) então fim_se

Programação com Desvios

47

O operador lógico .e. permite que uma operação seja executada somente se todas as condições em uso forem verdadeiras. Veja o exemplo a seguir:

Exemplo Construir um algoritmo que leia dois valores. Um valor representa a média aritmética; o outro, o número total de faltas. O programa deve imprimir APROVADO se a média for maior ou igual a 7.0 e o número total de faltas for inferior a 20; caso contrário, deve mostrar REPROVADO. programa APROVADO_REPROVADO var

FALTAS : inteiro MEDIA

início

: real

leia FALTAS leia MEDIA

se (MEDIA >= 7.0) .e. (FALTAS < 20) então escreva "aprovado"

senão

escreva "reprovado"

fim_se

fim

Note que, na sentença do SE, ambas as condições devem ser verdadeiras para que seja impresso “aprovado” na tela. Sendo assim, observe na Tabela 3.3 algumas simulações de digitação: Tabela 3.3 - Exemplo de utilização do operador lógico .e. Média

Faltas

Média >= 7.0

Faltas < 20

Condição 1 .e. Condição 2

8.0

30

Verdadeira

Falsa

Falsa

5.0

15

Falsa

Verdadeira

Falsa

7.0

10

Verdadeira

Verdadeira

Verdadeira

3.5.2 Operador lógico .ou. O operador lógico .ou. será utilizado em situações nas quais basta qualquer uma das condições ser verdadeira para que o resultado também seja verdadeiro e, consequentemente, o bloco de instruções seja executado. Na Tabela 3.4, veja o emprego do operador .ou. para duas condições. Tabela 3.4 - Tabela-verdade para o operador lógico .ou. Condição 1

48

Condição 2

Condição 1 .ou. Condição 2

Falsa

Falsa

Falsa

Verdadeira

Falsa

Verdadeira

Falsa

Verdadeira

Verdadeira

Verdadeira

Verdadeira

Verdadeira

Algoritmos - Técnicas de Programação

Diagrama de blocos

Condição 1 .ou. Condição 2

N

S

Bloco de comandos que só será executado quando a condição for verdadeira

Bloco de comandos que sempre será executado

Figura 3.9 - Exemplo de utilização do operador lógico .ou.

Português estruturado se ( ) .ou. ( ) então fim_se

Veja o exemplo a seguir:

Exemplo programa TESTE_OU var

CODIGO: inteiro

início

leia CODIGO

se (CODIGO = 100) .ou. (CODIGO = 200) então escreva "código válido"

senão

escreva "o código digitado está inválido"

fim_se

fim

Programação com Desvios

49

Observe, no exemplo anterior, que tanto faz o usuário digitar 100 ou 200, pois a mensagem “código válido” sempre será emitida; se, porém, for digitado qualquer outro valor, a mensagem “o código digitado está inválido” será mostrada. A Tabela 3.5 simula algumas digitações para o algoritmo TESTE_OU: Tabela 3.5 - Exemplo de utilização do operador lógico .ou. CODIGO

CODIGO = 100

CODIGO = 200

Condição 1 .ou. Condição 2

50

Falsa

Falsa

Falsa

100

Verdadeira

Falsa

Verdadeira

200

Falsa

Verdadeira

Verdadeira

3.5.3 Operador lógico .não. O operador lógico .não., de negação, será usado quando for necessário inverter o valor de uma condição, ou seja, tornar verdadeiro o que era falso e tornar falso o que era verdadeiro. A Tabela 3.6 demonstra a sua utilização; na Figura 3.10, veja a sua representação em um diagrama de blocos. Tabela 3.6 - Tabela-verdade para o operador lógico .não. Condição

.não. condição

Verdadeira

Falsa

Falsa

Verdadeira

Diagrama de blocos

N

.não. condição

S

Bloco de comandos que só será executado quando a condição for verdadeira

Bloco de comandos que sempre será executado

Figura 3.10 - Exemplo de utilização do operador lógico .não.

50

Algoritmos - Técnicas de Programação

Português estruturado se .não. ( ) então

fim_se

O operador lógico .não. inverte o resultado da condição e é muito utilizado em diversas construções. Veja o exemplo a seguir:

Exemplo programa TESTA_NÃO var

NÚMERO : inteiro

início

escreva "Digite um número par: " leia NÚMERO

RESTO ← NÚMERO – 2 * (NÚMERO div 2) se .não. (RESTO <> 0) então

escreva "Você digitou um número par"

senão

escreva "Você não digitou um número par"

fim_se

fim

Neste exemplo, utilizamos o operador matemático mod (visto brevemente no Capítulo 2), que retorna o resto de uma divisão inteira. No exemplo, mod é utilizado para verificar se o número digitado pelo usuário é divisor de 2. Se o resto da divisão de qualquer número por 2 for igual a 0, indicará que o número é par. No entanto, 0 indica falsidade; sendo assim, para que a condição de SE seja verdadeira, a fim de imprimir corretamente a mensagem desejada, invertemos o conteúdo da variável RESTO de maneira a transformá-la em 1 (verdadeiro). Para compreender melhor, fique atento ao próximo tópico.

Vamos recapitular? Aprendemos, neste capítulo, como fazer a máquina tomar decisões. Esse aprendizado é de suma importância para a compreensão dos próximos capítulos. Outro assunto abordado foram os operadores relacionais e lógicos, que ampliam o uso das estruturas de seleção ao compor mais de uma condição na mesma cláusula de consulta.

Programação com Desvios

51

Agora é com você! 1)

2)

Assuma os seguintes valores: X = 5, A = 2, B = 3, C = 1 e D = 2. Utilizando as tabelas-verdade de .ou., .e. e .não., responda se o resultado das expressões seguintes é verdadeiro ou falso: a)

.não. (A > 3) .ou. (2 < 7)

b)

.não. (X < 5)

c)

(C > 5) .ou. (D > 0)

d)

.não. (D < 0) .e. (B > 7)

e)

.não. (X = 2) .ou. (C < 2)

f)

(X < 2) .ou. .não. (A < D)

g)

(X >= 5)

h)

(X < 6) .e. (B >= D)

i)

(A > B) .e. .não. (C < B)

j)

(A > B) .ou. (C < B)

Para cada um dos problemas a seguir construa o diagrama de blocos e o algoritmo em português estruturado: a)

Determinar o maior entre dois números fornecidos pelo usuário.

b)

Dar continuidade ao exercício do item “a”, mas agora o usuário vai fornecer três valores e o algoritmo deve imprimi-los em ordem crescente.

c)

Em determinada instituição de ensino, um aluno é considerado APROVADO se a média aritmética simples de três provas for igual ou superior a 6. Se a média do aluno for maior que 4, porém menor que 6, o aluno estará de EXAME; agora, se a média do aluno estiver abaixo de 4, ele será considerado REPROVADO.

d)

Dados três valores inteiros: A, B e C, determinar se eles formam um triângulo. Atenção! Triângulo é uma figura geométrica em que a medida de qualquer um dos lados é menor do que a soma das medidas dos outros dois.

e)

Altere o exercício “d” de tal modo a classificar o triângulo em equilátero, isósceles e escaleno. Lembre-se de que: Equilátero: todos os lados possuem a mesma medida. Isósceles: dois lados possuem a mesma medida. Escaleno: todos os lados possuem medidas diferentes.

f)

52

Ler cinco números inteiros e apresentar a diferença (subtração) entre o menor e o maior número lido.

Algoritmos - Técnicas de Programação

4 Programação com Laços

Para começar Neste capítulo, vamos estudar como implementar uma técnica fundamental em programação: laços ou repetições. Ela permite executar trechos de um programa quantas vezes for necessário. A quantidade de vezes pode ser parametrizada pelo programador ou pela própria situação-problema. Vamos explicar o laço com teste prévio de veracidade (pré-teste), o laço com texto de veracidade a posteriori (pós-teste) e o laço incondicional.

4.1 Controle de ciclos Geralmente, ao escrever um programa, precisamos que ele execute a mesma rotina mais de uma vez. Em muitos casos, o número de vezes é muito alto e inviabiliza qualquer tentativa de reescrever a rotina n vezes. Além de trabalhoso, isso geraria um código de programação de difícil e e dificultaria a correção de falhas. Com a técnica de laços resolvemos esse problema, permitindo que o programador controle quantas vezes determinada porção de instruções deve ser repetida. Normalmente, esse controle não é fixo; depende de variáveis dinâmicas. Por exemplo, para calcular o fatorial de um número x, o usuário precisa informar o valor de x como dado de entrada. Ao receber o valor de x, o programa entra em um laço que será executado um número de vezes proporcional ao tamanho de x, ou seja, quanto maior o valor de x, mais repetições o programa fará.

53

Tecnicamente, costumamos chamar o laço pelo seu correspondente em língua inglesa: loop ou looping. Os laços podem ser executados mediante uma condição predefinida pelo programador (laço condicional) ou sem uma condição predefinida (laço incondicional). Além disso, é importante esclarecer que, durante a execução de um laço condicional, podemos ter operações interativas (com a intervenção do usuário) e iterativas (sem o n - sem intervenção do usuário, apenas iteração/repetição). Os laços incondicionais permitem apenas operações iterativas. Veremos adiante os principais comandos para controle de laço ou repetição: enquanto...faça e repita...até que, para loops condicionais, e a instrução para...de...até...o...faça, para loops incondicionais. Amplie seus conhecimentos Todo algoritmo tem um custo de processamento associado. Para analisar esse custo, existe uma área, na Ciência da Computação, chamada Análise de Algoritmos e Otimização. Por meio de estudos nessa área é possível verificar, dentre outras informações, a complexidade do programa (por meios matemáticos), o seu tempo de execução, o espaço de memória necessário e a robustez do programa. O laço tem papel importante no cálculo da complexidade de um algoritmo. Muitos laços podem aumentar o nível de complexidade de processamento do programa, portanto use esse recurso com parcimônia. Para saber mais, consulte: Complexidade de Algoritmos. Série Livros Didáticos Informática – UFRGS. Vol. 13, 3. ed. Laira Vieira Toscani; Paulo A. S. Veloso. Editora Bookman, 2012.

4.2 Laço condicional pré-teste Dentre os laços condicionais, temos aqueles que efetuam o teste condicional antes de executar a rotina de loop (laço condicional pré-teste) e aqueles que executam a rotina e, depois, o teste para verificar se devem ou não continuar executando o laço (laço condicional pós-teste). O laço condicional pré-teste executa um teste lógico no início do laço para confirmar se deve ou não executar a porção de código do laço. Uma das estruturas mais conhecidas para esse tipo de laço é enquanto...faça, que testa se a condição definida no início do loop é verdadeira. Enquanto essa condição for verdadeira, o conjunto de instruções do loop será executado. Assim que a condição se tornar falsa, o processamento deixará o loop e seguirá o caminho de execução sequencial do programa. Vale ressaltar que, caso a condição em seu primeiro teste seja falsa, as instruções internas ao laço jamais serão executadas. Verifique, na Figura 4.1, um exemplo de funcionamento da estrutura de controle enquanto... faça por meio de diagrama de blocos. Diagrama de blocos Teste lógico Condição

N

S Instruções a serem executadas

Figura 4.1 - Exemplo de funcionamento da estrutura enquanto...faça.

54

Algoritmos - Técnicas de Programação

Português estruturado enquanto ( ) faça fim_enquanto

Exemplo Desenvolver um programa de computador que leia um valor inteiro qualquer, divida-o sucessivas vezes por 2, até que o seu valor seja menor que 5, e apresente como resultado a quantidade de sucessivas divisões realizadas.

Solução O programa deve possuir a variável de entrada (N) e uma segunda variável que será usada para calcular a quantidade de ações (divisões sucessivas) realizadas. A variável R será iniciada com valor 0 e, a cada iteração, deverá ser acrescida de 1.

Diagrama de blocos

Português estruturado programa DIVISOES_SUCESSIVAS

Início

var R

N, R : inteiro

0

início

N

R ← 0

leia N

N

enquanto (N >= 5) faça

N >= 5

N ← N div 2

S N

R

R ← R + 1

N div 2

R+1

fim_enquanto fim

escreva R

R

Fim

Figura 4.2 - Exemplo de uso da estrutura enquanto...faça.

No exemplo, utilizamos a variável R para dois propósitos: guardar o resultado final a ser exibido e servir de contador. O laço apresentado efetua um pré-teste antes de permitir a execução da rotina associada à repetição: N >= 5. Isso significa que, se o valor de N for inferior a 5, as instruções subordinadas ao laço não serão (mais) executadas. Ao entrar no laço, o valor de N é alterado por 2 pela divisão inteira (div). Repare que o processamento está sendo realizado e o valor da variável de entrada é alterado por esse processamento. Não foi necessário criar outra variável para guardar o cálculo. Logo em seguida, e ainda dentro do laço, o valor do contador é alterado. Isso se repetirá até que o valor de N se torne menor que 5. Quando isso acontecer, o laço será interrompido e o valor do contador, apresentado como saída do programa.

Programação com Laços

55

Vimos, no exemplo, o uso de um laço pré-teste condicional iterativo. Vejamos, agora, outro exemplo, mas com uma situação interativa, ou seja, com intervenção do usuário no laço.

Exemplo Desenvolver um programa de computador que leia as avaliações de consumidores sobre determinado produto. Essas avaliações são valores reais entre 5 e 10. Calcule a nota média atribuída ao produto. O usuário digitará quantas avaliações considerar necessário, até que o valor digitado seja inválido (menor que 5 ou maior que 10).

Diagrama de blocos Início

R

O programa deve possuir, além da variável de entrada (N), uma segunda variável (R) para acumular os valores lidos e uma terceira variável (CONT) para contar quantos valores já foram lidos. É o valor lido a cada iteração que será acrescido à variável R. A variável CONT será iniciada com valor 0 e, a cada leitura diferente de 0, deve ser acrescida de 1.

Português estruturado

0

CONT

Solução

programa LACO_INTERATIVO var

0

N, R : real

CONT : inteiro

N

início

R ← 0

N >= 5 .e. N <= 10

CONT ← 0

N

leia N

enquanto (N >= 5) .e. (N <= 10) faça R ← R + N

S R

CONT

CONT ← CONT + 1

R+N

leia N

fim_enquanto

CONT + 1

se (CONT > 0) então R ← R / CONT

N

fim S

escreva R

N CONT > 0

R

R / CONT

R

Fim

Figura 4.3 - Exemplo de laço controlado pelo usuário.

56

Algoritmos - Técnicas de Programação

No programa apresentado, enquanto o valor lido estiver dentro do intervalo aceitável, a rotina de repetição será executada. Diferentemente do exemplo anterior, o controle do laço será, agora, do usuário, ou seja, o usuário definirá quantas vezes a rotina será executada. Note que, além das variáveis R (armazena o resultado) e N (variável de entrada), utilizamos a variável auxiliar CONT. Chamamos de auxiliar toda variável criada para ajudar determinado processamento, não sendo, portanto, nem variável de entrada nem de saída. No exemplo, a variável CONT serviu como contador, sendo-lhe atribuído o valor 0 no início da operação, uma vez que as instruções subordinadas ao laço ainda não haviam sido executadas. A instrução enquanto (N >= 5 e N <= 10) verifica se o último valor de N lido está no intervalo desejado. Se estiver, acumulará (soma de valores) em R os valores de N lidos. Caso o valor de N esteja fora do intervalo itido, o laço será interrompido e o contador será conferido, calculando-se o resultado e imprimindo-o. Perceba que o resultado a ser exibido é calculado efetivamente após o laço. Isso mostra que o laço serve para outras ações de processamento, como, no caso, acumular determinado valor após sucessivas leituras de dados de entrada. Verifique o controle condicional ao final do algoritmo, testando se o valor da variável CONT é positivo. Isso é feito para evitar a divisão por 0 (R ← R / CONT), caso o primeiro valor lido para a variável N seja inválido (fora do intervalo definido).

4.3 Laço condicional pós-teste O laço condicional pós-teste funciona de modo similar ao laço condicional pré-teste. A grande diferença é que o teste lógico ocorre somente após a execução das instruções subordinadas ao laço. Logo, primeiro se executam as instruções, depois se verifica, por meio de teste, se elas devem continuar a ser executadas. A estrutura de repetição que executa esse tipo de laço é repita...até que. Nesse tipo de laço, perceba que as instruções são executadas ao menos uma vez antes do teste lógico; já no laço condicional pré-teste (consulte o Tópico 4.2), existe a possibilidade de as instruções subordinadas ao laço nunca serem executadas. Nesse sentido, podemos dizer que repita...até que tem funcionamento invertido quando comparada à estrutura enquanto...faça, pois sempre executa as instruções ao menos uma vez enquanto a condição do laço for falsa. Atente a esta diferença: em repita...até que, as instruções serão executadas enquanto a condição do laço permanecer falsa. Quando o teste lógico dessa condição for verdadeiro, o laço será encerrado, ou seja, o processamento deixará o loop e seguirá o caminho de execução sequencial do programa.

Diagrama de blocos Instruções executadas no período em que a condição permanece falsa N Condição S

Figura 4.4 - Exemplo de funcionamento da estrutura repita...até que.

Na Figura 4.4, veja um exemplo de funcionamento da estrutura de controle repita...até que por meio de diagrama de blocos.

Programação com Laços

57

Português estruturado repita até_que ( )

Para exemplificar o uso do laço condicional pós-teste, considere o exemplo seguinte:

Exemplo Desenvolver um programa de computador que apresente a soma dos cinco primeiros números inteiros.

Solução O programa deve possuir uma variável de processamento do cálculo (R) que será modificada a cada interação. Também será necessária uma segunda variável (I) para controle do laço. A variável I será iniciada com valor 1 e, a cada iteração, deverá ser acrescida de 1 até o limite de 5. Note que este programa é semelhante ao do exemplo anterior, mas, para solucioná-lo, será usado um laço pós-teste.

Diagrama de blocos

Português estruturado Início

programa LACO_POSTESTE var

I

1

R

0

R, I : inteiro

início

I ← 1 R ← 0

R

R+I

I

I+1

repita R ← R + I I ← I + 1

até que (I > 5)

N I>5 S

fim

escreva R

R

Fim

Figura 4.5 - Exemplo de utilização da instrução repita...até_que.

No exemplo, também utilizamos uma variável (I) que servirá como contador. Foi atribuído o valor 1, pois usaremos a estrutura de repetição repita...até que, a qual garante ao menos uma iteração. Portanto, o programa executará as instruções subordinadas ao laço ao menos uma vez.

58

Algoritmos - Técnicas de Programação

Todo o trecho de instruções compreendido entre os comandos repita e até que será repetido enquanto a condição (I > 5) for falsa, ou seja, só deixará de ser executado quando I <= 5. Para que essa condição se torne falsa, é imprescindível que o valor de I seja alterado (aumentado) ao longo das iterações. Se isso não acontecer, o laço pode ser executado “infinitamente”, causando o travamento do programa. A seguir, veja um exemplo em que não se utiliza o contador como forma de controlar quantas vezes uma rotina é executada em uma estrutura de repetição. Considere que o usuário pode encerrar o processamento quando desejar.

Exemplo Desenvolver um programa de computador que leia um número inteiro qualquer, eleve-o ao quadrado e apresente o resultado do cálculo. Essa operação deve ocorrer até que o usuário responda SIM à pergunta “Deseja encerrar cálculo?”.

Solução O programa deve possuir, além das variáveis de entrada (N) e de processamento do cálculo (R) solicitado, uma terceira variável que será usada para guardar a resposta do usuário (ENCER). A variável ENCER é iniciada com valor NÃO e, cada vez que a resposta dada for diferente de SIM, o programa repetirá o laço, que somente será interrompido quando a resposta for SIM.

Diagrama de blocos

Português estruturado programa CALCULO_INTERATIVO

Início

var ENCER

N, R : inteiro

‘‘NÃO’’

ENCER: cadeia

início

N

ENCER ← "NÃO" R

repita

N*N

leia N R ← N * N

‘‘Deseja encerrar?’’

escreva R

escreva "Deseja encerrar?" leia ENCER

RESP

fim

Não

até que (ENCER = "SIM")

ENC = ‘‘SIM’’ Sim Fim

Figura 4.6 - Exemplo de laço controlado pelo usuário.

Programação com Laços

59

4.4 Laço incondicional Até agora, vimos duas estruturas de repetição para laços condicionais: enquanto...faça e repita...até que. Além delas, há uma que costuma facilitar o trabalho do programador; é a estrutura de laço incondicional. Algumas vezes, o laço não depende de uma condição explícita, mas de uma contagem de valores que, ao atingirem determinado patamar, interrompem o laço. Nesse caso, o laço funciona com base em uma variável contador, que controla o fluxo de iterações. Para esse tipo de laço, o programador pode usar a estrutura para..de..até..o..faça. No diagrama de blocos, esse tipo de laço recebe um componente diferenciado com formato hexagonal: o símbolo preparation. Verifique, na Figura 4.7, um exemplo de uso do laço incondicional com diagrama de blocos. Diagrama de blocos

Var Início, Fim, Incremento

Instruções

Figura 4.7 - Exemplo de uso da estrutura para..de...até...o...faça.

Português estruturado para de até o faça fim_para

Atenção! Observe que não houve uso de condição para a escrita desse laço; não há, portanto, teste lógico: verifica-se, apenas, se a variável de controle já chegou ao seu limite superior/inferior. Para exemplificar o uso do laço incondicional, considere o exemplo seguinte:

60

Algoritmos - Técnicas de Programação

Exemplo Desenvolver um programa de computador que some os dez números naturais subsequentes de um número N dado como entrada.

Solução O programa deve receber como dado de entrada o valor de N, que será atribuído a uma variável de mesmo nome. Também criaremos a variável R para guardar o resultado a ser exibido. Para o processamento do laço, será necessário criar outra variável, a ser chamada de variável auxiliar I, cujo objetivo é auxiliar o loop, servindo de variável de controle do laço incondicional. A variável I será inicializada com o valor N + 1 para indicar o primeiro valor subsequente a N. A cada iteração (ciclo do laço), a variável auxiliar terá 1 acrescido ao seu valor, até o limite de 10.

Diagrama de blocos Início

N

I N + 1, N + 10, 1

R

R+I

R

Fim

Figura 4.8 - Exemplo de uso da estrutura para...de...até...o...faça...fim_para.

Português estruturado programa SOMA_NATURAIS var

N, R, I : inteiro

início

leia N

para I de N + 1 até N + 10 o 1 faça R ← R + I

fim_para

escreva R

fim

Verifique a diferença deste exemplo em relação aos demais. Neste, desde o início o programador sabia quantas iterações seriam necessárias; ele não dependia de nenhuma condição a ser verificada a cada ciclo. A variável de controle foi iniciada com o valor N + 1 e incrementada de 1 em 1

Programação com Laços

61

pelo comando o até atingir o valor correspondente a N + 10. Essa estrutura de repetição é a mais adequada quando se conhece a quantidade de iterações que devem ser realizadas, tendo-se os valores inicial e final da variável de controle.

Vamos recapitular? Neste capítulo, estudamos o conceito de laço e as principais técnicas de loop, utilizando as seguintes estruturas de repetição: enquanto...faça, para laços interativos e iterativos com pré-teste condicional verdadeiro; repita...até que, para laços interativos e iterativos com pós-teste condicional falso; e para... de...até...o...faça, para laços incondicionais.

Agora é com você! 1)

62

Escreva algoritmos (diagrama de blocos e português estruturado) para os problemas a seguir. Para tanto, será necessário escolher uma estrutura de repetição dentre as estudadas. Faça isso e explique o porquê da escolha. a)

Ler um número inteiro positivo N e apresentar a contagem regressiva a partir de N.

b)

Apresentar o produto dos dez primeiros números inteiros (1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5...10).

c)

Apresentar o cubo de todos os números inteiros entre 0 e N, sendo N um número inteiro recebido como entrada.

d)

Apresentar a tabuada de um número inteiro N recebido como entrada.

e)

Calcular e exibir a média aritmética das notas recebidas pelos alunos de uma turma. O número de alunos (maior que 0) deve ser informado pelo usuário no início do programa.

f)

Apresentar o quadrado dos números pares entre 0 e N, sendo N um número inteiro positivo recebido como entrada.

g)

Apresentar o somatório de K2, de k = 1 até N (∑1,n k2), sendo N um número natural positivo recebido como entrada.

h)

Apresentar todos os valores numéricos inteiros ímpares situados na faixa entre M e N, sendo M e N números inteiros positivos e M <= N.

i)

A série de Fibonacci é 1, 1, 2, 3, 5, 8, 13, 21, 34, 55... Os dois primeiros termos são iguais a 1 e, a partir do terceiro, o termo é dado pela soma dos dois termos anteriores. Dado um número N, exiba o N-ésimo termo da série de Fibonacci.

Algoritmos - Técnicas de Programação

5 Programação com Matrizes

Para começar Neste capítulo, vamos explicar a criação e o uso das variáveis compostas homogêneas (de uma e duas dimensões, respectivamente denominadas vetores e matrizes), as quais possibilitam o armazenamento de mais de um valor em certa região de memória.

5.1 Estrutura de dados A primeira ação de um projetista de software deve ser a definição dos dados que serão armazenados e processados pelo programa a ser criado. Com base nessa informação será possível especificar os tipos de dados (inteiro, real, cadeia, caractere e lógico) e as estruturas de armazenamento a serem utilizados. Nos capítulos anteriores, vimos diversos exemplos e exercícios que utilizam os chamados tipos de dados primitivos, caracterizados, entre outras coisas, por armazenar um único valor por vez em sua posição de memória. Em diversas aplicações, todavia, é necessário armazenar grande quantidade de informações de um mesmo tipo; por exemplo, as notas de uma prova para uma turma de 80 alunos. Com o conhecimento adquirido até o momento, seria necessário criar 80 variáveis de um mesmo tipo (no caso, do tipo real) para resolver esse problema, o que tornaria o trabalho bastante tedioso e moroso. Para facilitar a criação de programas com esse perfil, podemos utilizar as variáveis compostas homogêneas ou, simplesmente, matrizes ou vetores; assim, em uma única variável podemos armazenar um valor em diversas posições. Ainda vale a restrição de se armazenar um único

63

valor em uma posição de memória, mas podemos criar diversas posições de memória, cada uma com um valor, e chamar esse conjunto de memória por meio de uma única variável. O conjunto de dados referenciado em memória com um único nome recebe diferentes nomes como variável indexada, variável subscrita, arranjo, vetor, matriz, tabela em memória, lista ou arrays. Neste livro ela será chamada apenas de vetor quando se tratar de uma linha e diversas colunas e de matriz quando tratar de diversas linhas e colunas. As variáveis compostas homogêneas podem ter qualquer dimensão (linhas x colunas). Vetores são comumente utilizados para estruturas de dados com uma dimensão; já matrizes são usadas para estruturas com duas dimensões. Neste capítulo, vamos abordar apenas os vetores e as matrizes por serem suficientes para tratar a maioria dos problemas, além de servirem de base para a criação de estruturas com outras dimensões, como os cubos. A criação do nome de uma variável composta segue as mesmas regras atribuídas aos nomes de variáveis simples; o nome também é definido por meio do comando var, com auxílio do comando conjunto. Além disso, a dimensão de uma matriz é formada por constantes inteiras e sempre positivas. Fique de olho! A linguagem de programação BASIC, criada em 1956, não deve ser traduzida literalmente como “básica”. O nome é, na verdade, uma sigla para o termo: Beginner’s All-purpose Symbolic Instruction Code, que significa código de instrução simbólica de uso geral para principiantes.

5.2 Vetores ou matrizes unidimensionais Entende-se por vetor ou matriz unidimensional a estrutura formada apenas por uma linha e várias colunas. Lembramos que em um vetor é possível armazenar várias informações, desde que sejam do mesmo tipo. A Figura 5.1 mostra esse tipo de variável, considerando-se uma variável composta vetorTeste que tem a capacidade de armazenar cinco elementos. vetorTeste

Índice Valor

1 25

2 65

3 10

4 2

5 45

Figura 5.1 - Exemplo de vetor.

Em um vetor, cada posição tem um endereço conhecido como índice. Dependendo da linguagem de programação utilizada, esse índice pode ser iniciado com 0 ou com 1. Para referenciar determinada posição dentro do vetor, devemos utilizar o nome da variável seguido do número do índice. Sendo assim, para o exemplo da Figura 5.1, temos vetorTeste[3] = 10.

Exemplo Desenvolver um programa que leia cinco valores e armazene os dados em um vetor de cinco posições. Em seguida, o programa deve imprimir o valor lido e o quadrado desse número.

Solução Para este exercício, vamos ler cinco números inteiros e, em seguida, apresentar o vetor, imprimindo o valor armazenado e o seu quadrado.

64

Algoritmos - Técnicas de Programação

Exemplo Português estruturado

Diagrama de blocos INÍCIO

I

1, 5, 1

programa QUADRADO var

NUM

: conjunto[1..5] de inteiro : inteiro

I

QUADRADO : inteiro

NUM[I]

início

para I de 1 até 5 o 1 faça

I

leia NUM[I]

1, 5, 1

fim_para QUADRADO

para I de 1 até 5 o 1 faça

NUM[I]*NUM[I]

QUADRADO ← NUM[I] * NUM[I] escreva NUM[I]

NUM[I], QUADRADO

FIM

escreva QUADRADO

fim

fim_para

Figura 5.2 - Diagrama de blocos para cálculo do quadrado de um número por meio de vetor.

Note como o vetor é criado (matriz unidimensional). No código, observe que o vetor num (aparece no espaço de criação de variáveis) é seguido pelo comando conjunto (que indica a utilização de matrizes) e pela indicação de sua dimensão. Sendo assim, a criação de vetores pode utilizar a seguinte regra: VARIÁVEL : conjunto[ ] de Em que: é a indicação dos valores inicial e final do tamanho do vetor; é o tipo de dado utilizado (por exemplo: real, inteiro, lógico ou caractere). Lembre-se de que um vetor pode armazenar diversos valores, mas em cada posição (índice) só é possível armazenar um valor, assim como nas variáveis simples. Observe ainda que, no caso do exemplo anterior, temos o cálculo do quadrado para cada uma das cinco posições do vetor. Se precisarmos ampliar esse cálculo, basta substituir 5 pelo valor desejado. Outro detalhe importante é com relação à variável i, aqui chamada de índice. O índice nada mais é que uma variável do tipo inteiro que indexa o vetor. Para ar determinada posição dentro do vetor, devemos utilizar a variável vetor com o índice: Variável[indice].

Programação com Matrizes

65

Exemplo Construir um programa que tenha dois vetores (matrizes unidimensionais) com tamanho 10 cada. Os elementos do primeiro vetor, chamado de A, serão fornecidos pelo usuário. Já os elementos do vetor B serão gerados dos elementos de A, em que: B[i] = A[i]*i, para i par 2 = 0 B[i]= A[i]*2, para i ímpar 2 <> 0 Após os cálculos, o algoritmo deverá exibir os dados dos dois vetores.

Solução No caso, temos a construção de dois vetores: o primeiro (A) será feito por simples digitação; o segundo (B), construído de forma automática de acordo com a lei de formação indicada. Essa lei diz que, se o índice do vetor A for par, seu conteúdo deve ser multiplicado pelo próprio índice. O resultado desse produto será atribuído ao vetor B. De forma semelhante, caso o índice seja ímpar, o conteúdo do vetor A deve ser multiplicado por 2. Novamente, o resultado do produto será atribuído ao vetor B de mesma posição.

Diagrama de blocos

Português estruturado programa MANIPULACAO_INDICE

INÍCIO

I

var

1, 10, 1

I, RESTO : inteiro

A, B : conjunto[1..10] de real

A[I]

início

para I de 1 até 10 o 1 faça

I

leia A[i]

1, 10, 1

fim_para RESTO

I-2

para I de 1 até 10 o 1 faça

(I DIV 2)

S

RESTO ← I - 2

N

B[I]

A[I]

I

B[I]

(I DIV 2)

se (RESTO = 0) então

RESTO = 0 A[I]

B[I] ← A[I] * I

2

senão B[I] ← A[i] * 2 I

fim_se

1, 10, 1

fim_para

para I de 1 até 10 o 1 faça

A[I], B[I]

escreva A[I], B[I]

FIM

Figura 5.3 - Diagrama de blocos para operação com índice.

66

fim

fim_para

Algoritmos - Técnicas de Programação

Por meio do exemplo apresentado notamos que é possível manipular o índice do vetor. No caso, temos a variável i, que cumpre exatamente esse papel.

Exemplo Desenvolver um programa que leia cinco elementos e armazene-os em um vetor. O programa deve imprimir na tela a média aritmética dos elementos lidos.

Solução Utilizando o princípio de ENTRADA → PROCESSAMENTO → SAÍDA, devemos ler todos os dados, processá-los conforme a solicitação e, por fim, executar a impressão na tela. Sendo assim, faremos três laços, um para cada etapa. A variável i (índice) será utilizada em todas as etapas e vai controlar o o ao conteúdo do vetor.

Diagrama de blocos

Português estruturado programa MEDIA

INÍCIO

var I

1, 5, 1

I, SOMA MEDIA A

A[I]

início SOMA

: inteiro : real

: conjunto[1..5] de inteiro

para I de 1 até 5 o 1 faça

0

leia A[I]

fim_para I

SOMA ← 0

1, 5, 1

para I de 1 até 5 o 1 faça SOMA

SOMA ← SOMA + A[I]

SOMA+A[I]

fim_para MEDIA

escreva soma

SOMA/5

MEDIA

MÉDIA ← SOMA I 5 fim

FIM

Figura 5.4 - Diagrama de blocos para operação em elementos.

Amplie seus conhecimentos Em 2008, s Allen, cientista norte-americana da IBM, foi a primeira mulher a receber o prêmio Turing, aos 75 anos de idade. Para saber mais, consulte: . o em: 28 jan. 2014.

Programação com Matrizes

67

5.3 Tabelas ou matrizes bidimensionais A estrutura com duas dimensões, ou seja, com linhas e colunas, recebe o nome matriz de duas dimensões (tabela) ou, simplesmente, matriz. A Figura 5.5 exibe a matriz A[5,4] e mostra exatamente como podemos visualizar essa importante - e muito utilizada - estrutura de dados. Índice das colunas 1

3

2

4

1

Índice das linhas

2 54

3 4 5

Figura 5.5 - Exemplo de matriz com cinco linhas e quatro colunas.

Os elementos de uma matriz são manipulados de forma individualizada; basta referenciar os índices de linha e coluna dos quais se deseja obter alguma informação ou aos quais se deseja enviar algum dado. Na Figura 5.5, para ar a posição do número 54, devemos indicar A[linha,coluna], ou seja, A[3,2].

Exemplo Considerar uma sala de aula com cinco alunos e uma disciplina, com três provas aplicadas pelo professor. Construir um programa (diagrama de blocos e português estruturado) que leia as notas dessas provas para cada aluno. Ao final, o programa deve imprimir as notas.

Solução Neste exercício, vamos usar uma tabela semelhante à exibida anteriormente na Figura 5.5. Índice das colunas 1

2

3

Índice das linhas

1 2 3 4 5

Figura 5.6 - Matriz que exemplifica o enunciado do exercício.

68

Algoritmos - Técnicas de Programação

Exemplo Note que temos dois índices: um deve gerenciar as linhas; o outro, as colunas. Os índices são manipulados de forma individual. Para facilitar o aprendizado, utilizaremos dois laços encadeados: o mais externo vai gerenciar as linhas; o mais interno, as colunas (você pode gerenciar primeiro as colunas e depois as linhas, mas isso requer mais experiência e estudos). Vamos utilizar o índice i para as linhas e o índice j para as colunas. Após a leitura das notas, vamos imprimi-las na tela.

Diagrama de blocos INÍCIO

I

1, 5, 1

J

1, 3, 1

NOTAS[I,J]

I

1, 5, 1

J

1, 3, 1

NOTAS[I,J]

FIM

Figura 5.7 - Diagrama de blocos para operação com matrizes.

Programação com Matrizes

69

Exemplo Português estruturado programa MANIPULACAO_MATRIZ var

NOTAS : conjunto[1..5, 1..3] de real I, J

início

: inteiro

para I de 1 até 5 o 1 faça

para J de 1 até 3 o 1 faça leia NOTAS[I,J]

fim_para

fim_para

para I de 1 até 5 o 1 faça

para J de 1 até 3 o 1 faça escreva NOTAS[I,J]

fim_para

fim_para

fim

Na criação de um vetor, devemos indicar apenas uma dimensão, ou seja, a quantidade de colunas, já que a quantidade de linhas é sempre igual a 1. Já na criação de uma matriz de duas dimensões, serão atribuídas ao comando conjunto as informações de duas dimensões, isto é, a quantidade de linhas e de colunas. A sintaxe geral de criação é: VARIÁVEL: conjunto[ ] de Em que: e indicam a quantidade de linhas e colunas, respectivamente; é o tipo de dado utilizado (por exemplo: real, inteiro, lógico ou caractere). Nos vetores, devemos processar um elemento por vez; nas matrizes, o procedimento é o mesmo, ou seja, os dados são manipulados o a o, um elemento de cada vez.

70

Algoritmos - Técnicas de Programação

Vamos recapitular? Diversas são as aplicações em que é preciso armazenar grande quantidade de informações de um mesmo tipo; por exemplo, as notas para uma sala de aula. Neste capítulo, aprendemos como usar as estruturas de dados conhecidas como variáveis compostas homogêneas. As mais utilizadas são os vetores e as matrizes que, com a utilização de índices, permitem manipular de forma bem específica cada elemento.

Agora é com você! 1)

Sabendo que os exercícios a seguir envolvem a manipulação de vetores, desenvolva os diagramas de blocos e as representações textuais em português estruturado correspondentes: a)

Considere o seguinte programa e informe o que será impresso na tela: programa EXERCICIO_A var

VETOR : conjunto[1..10] de inteiro I

início

: inteiro

para i de 1 até 10 o 1 faça VETOR[I] ← i * I – 2 * I + 5 fim_para

para i de 1 até 10 o 1 faça escreva VETOR[I]

fim_para fim

1

2

3

4

5

6

7

8

9

vetor

b)

Construa um programa em que o usuário deve ler dois vetores, A e B, cada qual com 20 elementos. O código deve montar os elementos de uma terceira matriz, C, em que cada elemento é o produto dos elementos da matriz A com a B. Ao final, mostre na tela os elementos das três matrizes.

c)

Faça um programa que leia os elementos de dois vetores: o primeiro com dez elementos e o segundo com 15 elementos. O usuário deve digitar os elementos dos dois vetores já em ordem crescente, ou seja, do menor para o maior. O programa deve criar de forma automática um terceiro vetor que seja a junção dos dois vetores lidos, mas todos os elementos devem estar em ordem crescente. Para ilustrar, veja o exemplo a seguir:

Programação com Matrizes

71

Considere um vetor A com três elementos e um vetor B com quatro elementos: Índice

1

2

3

Valor

10

12

23

Índice

1

2

3

4

Valor

5

15

18

25

Índice

1

2

3

4

5

6

7

Valor

5

10

12

15

18

23

25

Vetor A

Vetor B

O vetor C, tido como resultado, será:

Vetor C

2)

72

Agora que já sabemos trabalhar com vetores, vamos exercitar o que aprendemos com matrizes. Para cada um dos exercícios seguintes, desenvolva os diagramas de blocos e o português estruturado: a)

Faça um programa em que o usuário deve digitar números inteiros para uma matriz de ordem 5 (linhas e colunas iguais a 5). Após a digitação dos números, o usuário deve digitar um número aleatório e verificar se ele se encontra na matriz. Ao final, os índices da linha e da coluna devem ser impressos se o elemento for encontrado; caso contrário, a mensagem “elemento não encontrado” deve ser impressa.

b)

Desenvolva um programa que leia duas matrizes de cinco linhas por três colunas e apresente na tela a soma delas. É preciso utilizar uma terceira matriz para armazenar o resultado.

c)

Desenvolva um programa que leia duas matrizes quadradas de ordem 3. Ele deve construir uma terceira matriz que seja o produto das duas matrizes lidas.

Algoritmos - Técnicas de Programação

6 Aplicação Prática de Matrizes

Para começar Neste capítulo, vamos estudar exemplos práticos de matrizes com base em duas técnicas muito importantes: ordenação e busca de elementos. Ao final do capítulo, será possível implementar rotinas para ordenar dados armazenados em matrizes, bem como desenvolver algoritmos para buscar valores armazenados em matrizes.

6.1 Ordenação de elementos Matriz é um elemento de programação usado de diversas formas na computação. Além de conhecer matrizes, é muito importante saber utilizá-las, escolhendo, dentre as diversas possibilidades que essa estrutura apresenta, a mais adequada a determinado fim, principalmente quando se trabalha com um conjunto volumoso de dados. Uma das diversas operações que tipicamente usam matrizes consiste na organização de dados de acordo com alguma regra. A regra pode ser, por exemplo, a classificação (ordenação) dos dados para facilitar sua busca na estrutura. A ordenação pode ser numérica, alfabética ou alfanumérica, em ordem crescente ou decrescente, de acordo com a tabela ASCII (American Standard Code for Information Interchange, que significa código americano padrão para troca de informações), dependendo do tipo de dados armazenado na matriz. Lembre-se de que a matriz só armazena dados de um mesmo tipo (estrutura homogênea).

73

Considerando a ordenação da tabela ASCII, quando a classificação dos dados é alfabética, primeiro se ordenam os caracteres maiúsculos, depois os minúsculos. Além dos caracteres convencionais, esse tipo de ordenação abrange os demais elementos gráficos previstos na tabela ASCII (consulte essa tabela no Capítulo 1). Para classificar dados, há diversos algoritmos clássicos na Ciência da Computação. Cada um tem seus pontos fortes e suas fragilidades. O programador precisa apenas escolher o algoritmo a ser implementado, considerando o seu problema e, principalmente, a quantidade de dados que possui. Dentre os algoritmos de classificação de dados mais conhecidos, destacam-se os seguintes grupos (AZEREDO, 1996): »»

Classificação por inserção: método da inserção direta, método da inserção direta com busca binária, método dos incrementos decrescentes - shellsort.

»»

Classificação por troca: método da bolha - bubblesort, método da agitação - shakesort, método do pente - combsort, método de partição e troca - quicksort.

»»

Classificação por seleção: método da seleção direta, método da seleção em árvore - heapsort, método de seleção em árvore amarrada - threadedheapsort.

»»

Classificação por distribuição de chaves: método de indexação direta - radixsort.

»»

Classificação por intercalação: método da intercalação simples - mergesort, méto­do de intercalação de sequências naturais.

»»

Classificação por cálculo de endereços: método das listas de colisão, método da solução postergada das colisões.

Neste capítulo, você estudará um algoritmo do tipo classificação por troca, por ser um dos métodos mais simples, útil para ordenar um conjunto com poucos dados. Apesar de sua simplicidade e eficácia (atinge o objetivo de ordenar), ele não é eficiente quando comparado a outros mais complexos, como o radixsort, o mergesort ou o quicksort. É importante ressaltar que um algoritmo é considerado não eficiente se o seu tempo de execução for muito alto quando comparado a outros do mesmo gênero/finalidade. O método de classificação de dados a ser apresentado executa trocas sucessivas de valores entre os elementos da matriz até que os dados estejam totalmente ordenados. Por esse motivo, a técnica é considerada um método de classificação por troca. Para facilitar o entendimento, imagine uma matriz de inteiros com cinco elementos, conforme a Tabela 6.1. Tabela 6.1 - Matriz de inteiros com cinco elementos Matriz: A

74

Índice

Elemento

1

45

2

8

3

17

4

5

5

2

Algoritmos - Técnicas de Programação

Considerando a ordem numérica crescente, a matriz está “desordenada”, ou seja, os dados não estão ordenados. Repare que os elementos estão na seguinte ordem: 45, 8, 17, 5 e 2. Após a ordenação, eles devem estar armazenados nesta ordem: 2, 5, 8, 17 e 45. Para efetuar a ordenação, trocaremos os elementos de posição (permutas) até chegarmos à ordem desejada. Temos, então, a seguinte situação: A[1] = 45 | A[2] = 8 | A[3] = 17 | A[4] = 5 | A[5] = 2 Iniciaremos o processo de troca por meio da comparação um a um, ou seja, vamos começar pelo elemento A[1] e compará-lo com todos os demais, um por vez. Assim que encontrarmos um elemento com valor menor que A[1], faremos uma permuta, mas continuaremos o procedimento até que A[1] tenha sido comparado com todos os outros elementos. Após a permuta do elemento A[1], o processo deve ser repetido para A[2]. Não será necessário compará-lo com o novo valor de A[1] porque, após a primeira permuta, já sabemos que esse valor é o menor de todos e, portanto, está na posição adequada. Esse processo será repetido sucessivas vezes com os demais elementos até que tenhamos ordenado todo o conjunto. Vamos, então, executar o algoritmo de troca no conjunto de dados da matriz A. Para iniciar, basta comparar o valor do elemento armazenado em A[1] com o valor do elemento em A[2]. Como o elemento em A[2] é menor que o elemento em A[1], é preciso fazer uma permuta entre A[1] e A[2], deixando a matriz com os elementos nesta ordem: A[1] = 8 | A[2] = 45 | A[3] = 17 | A[4] = 5 | A[5] = 2 Continuaremos a comparação do valor de A[1] = 8 com o valor de A[3] = 17. Nesse caso, A[3] não é menor que A[1], portanto não haverá troca. Seguiremos, assim, com a execução do algoritmo, comparando o valor de A[1] com o de A[4]. O elemento em A[4] é menor que o valor em A[1], então esses elementos serão trocados, deixando a matriz com a seguinte configuração: A[1] = 5 | A[2] = 45 | A[3] = 17 | A[4] = 8 | A[5] = 2 Perceba que, à medida que o algoritmo executa a ordenação, o valor do primeiro elemento fica mais baixo, mais próximo do ideal, que, nesse caso, é o número 2. Continuamos o processo, desta vez comparando o valor de A[1] com o de A[5]. Como A[5] possui o valor 2, que é menor que o valor 5 armazenado em A[1], haverá permuta entre esses dois elementos. Após essa troca, a matriz fica da seguinte forma: A[1] = 2 | A[2] = 45 | A[3] = 17 | A[4] = 8 | A[5] = 5 Não há mais elementos a serem comparados com A[1] e, por esse motivo, já temos o valor final esperado para o elemento A[1]. Assim, não precisamos mais efetuar comparações com o elemento A[1]. A[1] = 2 | A[2] = 45 | A[3] = 17 | A[4] = 8 | A[5] = 5

Aplicação Prática de Matrizes

75

Repetiremos o procedimento no elemento A[2], mas vamos compará-lo com A[3], A[4] e A[5]. Comparando os elementos A[2] e A[3], verificamos que o valor de A[3] é menor que o de A[2], por isso haverá troca. A[1] = 2 | A[2] = 17 | A[3] = 45 | A[4] = 8 | A[5] = 5 Em seguida, o valor de A[2] deve ser comparado com o valor de A[4]. Como 8 é menor que 17, faremos uma permuta entre A[2] e A[4], deixando a matriz com a seguinte configuração: A[1] = 2 | A[2] = 8 | A[3] = 45 | A[4] = 17 | A[5] = 5 Por fim, comparamos o valor do elemento A[2] com o valor de A[5], que também é menor que o atual valor de A[2]; logo, haverá nova permuta, conforme indicado no esquema: A[1] = 2 | A[2] = 5 | A[3] = 45 | A[4] = 17 | A[5] = 8 Agora, vamos comparar a próxima posição (A[3]) com os elementos restantes (A[4] e A[5]). O valor 45 do elemento A[3] será comparado com o valor 17 do elemento A[4]. Como 17 é menor que 45, haverá permuta entre A[3] e A[4]. A[1] = 2 | A[2] = 5 | A[3] = 17 | A[4] = 45 | A[5] = 8 O valor 17 do elemento A[3] será comparado, desta vez, com o valor 8 do elemento A[5]. Como 8 é menor que 17, haverá permuta. A[1] = 2 | A[2] = 5 | A[3] = 8 | A[4] = 45 | A[5] = 17 Não há mais elementos a serem comparados com A[3], portanto o valor 8 já está na posição final. A[1] = 2 | A[2] = 5 | A[3] = 8 | A[4] = 45 | A[5] = 17 Para finalizar o algoritmo, falta apenas comparar o elemento A[4] com o A[5]. Como o valor 17 de A[5] é menor que o valor 45 de A[4], eles serão trocados: A[4] a a ter o valor 17 e A[5], o valor 45: A[1] = 2 | A[2] = 5 | A[3] = 8 | A[4] = 17 | A[5] = 45 Não há mais comparações a serem feitas. Pode-se notar que a classificação foi realizada, ou seja, a matriz está ordenada: A[1] = 2 | A[2] = 5 | A[3] = 8 | A[4] = 17 | A[5] = 45 Para outros tipos de dados, como caractere ou string (cadeia), o processo de classificação segue os mesmos os; o algoritmo é o mesmo, só muda o tipo de dado. Lembre-se de que a ordem a ser considerada é a da tabela ASCII. Logo, “A” tem valor menor (vem antes) que “B” e “A” também é menor que “a”; essa ordem é dada pelo valor numérico associado a cada caractere.

76

Algoritmos - Técnicas de Programação

Exemplo Desenvolver um programa que leia um conjunto de nomes de 20 estudantes inscritos na prova do ENEM. Com esses nomes, realizar uma ordenação crescente para facilitar a localização do nome na lista que será afixada no quadro de avisos da escola.

Solução Deve-se utilizar uma matriz de uma dimensão (vetor) para armazenar os nomes dos estudantes. Essa matriz pode ser preenchida por meio de um laço. A cada iteração o sistema receberá um nome e alimentará o vetor. Para a ordenação, é preciso aplicar o algoritmo de troca estudado, fazendo as devidas comparações, de modo que, ao final, o conjunto esteja ordenado.

Diagrama de blocos

Português estruturado programa LISTA_NOME_ORDENADA

Início

I

var

1, 20, 1

ESTUD : conjunto[1..20] de cadeia I, J : inteiro X : cadeia

ESTUD[I]

início I

1, 19, 1

para I de 1 até 20 o 1 faça leia ESTUD[I]

J

fim_para

1, 20, 1

ESTUD[I] > ESTUD[J] N

para I de 1 até 19 o 1 faça

S

para J de I + 1 até 20 o 1 faça se (ESTUD[I] > ESTUD[J]) então

X ESTUD [I] ESTUD [I] ESTUD [J] ESTUD [J] X

X ← ESTUD[I] ESTUD[I] ← ESTUD[J] ESTUD[J] ← X fim_se

I

fim_para

1, 20, 1

fim_para ESTUD[I]

para I de 1 até 20 o 1 faça escreva ESTUD[I]

Fim

Figura 6.1 - Diagrama de blocos para a ordenação dos nomes dos estudantes.

Aplicação Prática de Matrizes

fim_para fim

77

A Figura 6.1 ilustra o diagrama de blocos que representa a entrada dos nomes dos 20 estudantes, o armazenamento dos nomes no vetor, o processo de classificação crescente com trocas sucessivas e a apresentação dos nomes dos estudantes de forma ordenada. Observe que foi necessário usar o recurso de laços encadeados (ou aninhados) no trecho em que havia troca: para I de 1 até 19 o 1 faça

para J de I + 1 até 20 o 1 faça

se (ESTUDANTES[I] > ESTUDANTES[J]) então



X ← ESTUDANTES[I]



ESTUDANTES[I] ← ESTUDANTES[J]



ESTUDANTES[J] ← X



fim_se

fim_para

fim_para

Isso acontece porque precisamos efetuar, para cada elemento do vetor, as comparações e possíveis trocas com todos os elementos posteriores (laço interno). Esse processo é repetido para cada elemento do vetor (laço mais externo). No primeiro laço, foi utilizada uma variável auxiliar I para controlar o elemento do vetor usado como base de comparação. Observe que a variável I começa com o valor 1 (primeiro elemento do vetor) e termina com 19 (penúltimo elemento do vetor). Isso acontece porque o último elemento (de número 20) nunca será base de comparação, já que não há elemento após ele a ser comparado. Veja, também, que a variável J começa com o valor I + 1 porque o primeiro elemento a ser comparado será sempre o subsequente (I + 1) ao elemento utilizado como base de comparação naquela iteração. Dessa forma, se I = 1 (estamos falando do elemento A[1]), J terá de ser igual a I + 1; logo, compararemos A[I] com A[J] ou A[1] com A[2] e assim por diante. Ao longo da execução do algoritmo, a variável J tomará vários valores. Verifique a Tabela 6.2. Tabela 6.2 - Variação dos valores de I e J durante a execução do algoritmo de ordenação por troca Tabela de valores das variáveis I e J Quando I for

J será

1

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

2

3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

3

4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

4

5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

5

6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

[...]

78

Algoritmos - Técnicas de Programação

Tabela de valores das variáveis I e J Quando I for

J será

15

16, 17, 18, 19, 20

16

17, 18, 19, 20

17

18, 19, 20

18

19, 20

19

20

O valor de J sempre será subsequente ao de I e seguirá incrementado até atingir o valor 20, que corresponde ao índice do último elemento desse vetor de 20 posições, pois o problema considera 20 estudantes. Ao final de cada iteração do laço mais interno (controlado por J), o fluxo do programa volta ao laço externo (controlado por I) e acrescenta 1 ao valor de I, até chegar a 19, o que significa que o programa alcançou sua última iteração de processamento da ordenação. Um ponto importante a observar é o algoritmo de troca de valores (swap). Verifica-se, antes da troca, se o elemento comparado tem valor menor que o elemento-base. Se houver, a troca é realizada. Para efetuar a troca sem perder os valores, utiliza-se uma variável auxiliar (X) de mesmo tipo. Amplie seus conhecimentos Por que o termo inglês bug, que significa inseto, é empregado para representar um erro computacional? Acredita-se que o termo foi inicialmente usado em 1878, por Thomas Edson, quando um inseto causou problemas de leitura em seu fonógrafo. No entanto, foi Grace Murray Hopper (criadora da linguagem COBOL) que, em 1945, documentou um erro provocado por uma mariposa que teria ficado presa entre os relés do computador que ela usava. Para saber mais, consulte: . o em: 28 jan. 2014.

6.2 Pesquisa de elementos Ao utilizar matrizes, podemos ter dificuldade para encontrar, rapidamente, valores em sua estrutura. Perceba que a matriz pode gerar grandes tabelas, portanto a localização de determinado elemento nem sempre é simples, mesmo que o conjunto de dados esteja previamente ordenado. Para resolver problemas como esse, há técnicas de programação e algoritmos específicos para pesquisa de elementos em matrizes e outras estruturas de dados. Apresentaremos, a seguir, uma das técnicas mais simples de pesquisa: a busca sequencial. No método de pesquisa/busca sequencial, o dado desejado é procurado sequencialmente desde o primeiro elemento até chegar ao último. Se a pesquisa chegar ao final do conjunto e não localizar o dado, é porque ele não está armazenado na matriz. Vejamos um exemplo na Tabela 6.3.

Aplicação Prática de Matrizes

79

Tabela 6.3 - Exemplo de dados para pesquisa sequencial Índice

Nomes

1

Ludmila

2

João

3

Jefferson

4

Maria Luísa

5

Silvia Amélia

6

Clodis

7

Alexandre

A Tabela 6.3 representa uma matriz unidimensional (vetor) com sete elementos do tipo string (cadeia). Deseja-se pesquisar um dos seus elementos (efetuar uma busca). Essa busca pretende encontrar Jefferson que, no caso, está na posição de índice 3. A pesquisa sequencial é a mais simples e corriqueira. Verifica-se, elemento por elemento, se o valor armazenado corresponde à chave de busca (elemento que se procura). Isso é feito até que a pesquisa localize o elemento desejado ou chegue ao final do arquivo sem obter resultado. No exemplo da Tabela 6.3, o valor da chave de busca (Jefferson) foi comparado com o valor do primeiro elemento. Como eram diferentes, a comparação ou ao segundo elemento; também diferentes. A chave de busca foi comparada, então, com o próximo elemento, cujo valor era igual ao procurado. Assim, o algoritmo parou a pesquisa e informou que ela foi realizada com sucesso.

Exemplo Em uma aula de Biologia, o professor deseja que a classe descubra os nomes de determinados animais após descrever suas características. Cada grupo de alunos deve, portanto, tentar descobrir o nome de um animal procurando-o no computador. Se ele não for encontrado no conjunto de dados do programa, é porque o grupo escolheu o animal errado. Deve-se elaborar um programa que leia e armazene dez nomes de animais, além de permitir a busca e a apresentação do nome de certo animal utilizando o algoritmo de pesquisa sequencial.

Solução O algoritmo para este problema deve receber como entrada dez nomes de animais que possam ser solicitados como chaves de busca. Para realizar a pesquisa sequencial, será necessário um laço que efetue a busca enquanto o usuário desejar. Também deve ser solicitada a chave de busca (dado a ser pesquisado), que será comparada com cada um dos dez nomes de animais do conjunto. Além disso, o nome deve ser mostrado, quando encontrado. Caso ele não seja localizado, é preciso informar que o nome pesquisado não existe no conjunto.

80

Algoritmos - Técnicas de Programação

Exemplo Português estruturado programa PESQUISA var

ANIM : conjunto[1..10] de cadeia I : inteiro

PESQ, RESP : cadeia ACHA : lógico

início

para I de 1 até 10 o 1 faça leia ANIM[I]

fim_para

RESP ← "SIM" enquanto (RESP = "SIM") faça

escreva "Digite o nome do animal a ser pesquisado: " leia PESQ I ← 1 ACHA ← Falso enquanto (I <= 10) e (ACHA = Falso) faça se (PESQ = ANIM [I]) então ACHA ← Verdadeiro senão I ← I + 1 fim_se

fim_enquanto

se (ACHA = Verdadeiro) então

escreva PESQ, " foi localizado na posição ", I

senão

escreva PESQ, " não foi localizado no conjunto de dados"

fim_se

escreva "Deseja continuar? (SIM/NÃO): " leia RESP

fim_enquanto fim

Aplicação Prática de Matrizes

81

Exemplo Diagrama de blocos

RESP

‘‘SIM’’

N

RESP = ‘‘SIM’’ S PESQ

I 1 ACHA F

I <= 10 e ACHA = F

N

S N

S PESQ=ANIM[I]

I

ACHA

I+1

N

V

S ACHA = V PESQ ‘‘foi localizado na posição’’ I

PESQ ‘‘não foi localizado’’

RESP

Fim

Figura 6.2 - Diagrama de blocos para a pesquisa sequencial de nomes.

Anteriormente, foi montada a rotina de pesquisa com base em um contexto. Observe, a seguir, o trecho que executa a pesquisa com seus comentários:

82

Algoritmos - Técnicas de Programação

1 - leia PESQ 2 - I ← 1 3 - ACHA ← Falso 4 - enquanto (I <= 10) e (ACHA = Falso) faça 5 6 7 8 9 -

se (PESQ = ANIMAIS[I]) então ACHA ← Verdadeiro senão I ← I + 1 fim_se

10 - fim_enquanto 11 - se (ACHA = Verdadeiro) então 12 -

escreva PESQ, "foi localizado na posição", I

13 - senão 14 -

escreva PESQ, "não foi localizado no conjunto de dados"

15 - fim_se

A primeira linha solicita o nome do animal que servirá de chave de busca, o qual será atribuído à variável PESQ. Na segunda linha, o contador recebe o valor-base 1 para que possa atuar no loop; ele é incrementado até 10, que é o total de elementos do conjunto de dados (vetor). Na linha 3, a variável flag (bandeira - utilizada para indicar algo) ACHA é colocada como falsa; ela informa se o dado procurado foi encontrado no vetor. No começo, como o dado ainda não foi encontrado, seu valor inicial deve ser Falso. A linha 4 inicia o laço com a condição de verificar se ainda há dados a pesquisar; para isso, utiliza a variável I, comparando-a com a quantidade máxima de elementos (10); enquanto I <= 10 e o nome pesquisado não tiver sido encontrado (ACHA = falso), o laço continuará a ser executado (linhas 5 a 9). A partir da linha 5, a pesquisa é executada no vetor ANIMAIS, comparando a chave de busca (valor da variável PESQ) com cada elemento desse vetor. Se o nome procurado estiver na posição I do vetor, a flag ACHA será alterada para Verdadeiro; caso contrário, a variável de controle I será incrementada apenas para a próxima iteração. Isso acontecerá até que I atinja o valor 10 ou a flag tenha valor verdadeiro. Ao final do laço por um dos motivos mencionados, nas linhas 11 a 15 verificaremos o valor da flag. Se for Verdadeiro, significa que o nome do animal pesquisado existe no conjunto de dados; do contrário, será informado que o nome pesquisado não consta no conjunto de dados. Atente para a importância de uma variável flag como ACHA. No começo da execução do algoritmo, a bandeira fica “abaixada”, ou seja, indica falsidade. Quando o nome pesquisado é encontrado, ela a a ter valor verdadeiro, como se tivesse sido “levantada”.

Aplicação Prática de Matrizes

83

Vamos recapitular? Neste capítulo, estudamos algumas operações práticas para ordenação e pesquisa de elementos em matrizes. Com esse conhecimento você pode escrever algoritmos mais elaborados no paradigma de programação sequencial!

Agora é com você! 1)

84

Desenvolva os algoritmos em diagrama de blocos e a codificação em português estruturado dos seguintes exercícios: a)

Ler uma matriz de uma dimensão (vetor) com valores coletados em uma pesquisa de preços. Colocar os valores em ordem crescente e exibir a matriz reorganizada.

b)

Ler duas matrizes unidimensionais (vetores) de números inteiros A e B de cinco posições cada. Preencher uma terceira matriz SOMA, de mesma dimensão, com a soma das matrizes A e B (a primeira posição de A será somada à primeira posição de B; o resultado será atribuído à primeira posição da matriz SOMA). Por fim, apresentar a matriz SOMA em ordem crescente.

c)

Ler uma matriz 3 x 5 com valores coletados em uma pesquisa de preços por produto. São três produtos e cinco preços por produto. Apresentar os elementos da matriz C em ordem decrescente de preço (por produto). Em seguida, calcular e exibir o valor médio de cada produto.

d)

Um programa deve gerar um vetor V contendo os dez primeiros números inteiros múltiplos de 3, ler um valor inteiro N e, conforme o que você aprendeu sobre pesquisa em matrizes, verificar se existe algum elemento de V que seja igual a N.

e)

Ler duas matrizes do tipo vetor A com dez elementos e B com oito elementos. Ler um valor N do mesmo tipo das matrizes A e B. Construir uma matriz C, que será a junção das outras duas, e pesquisar se o valor N lido está armazenado na matriz C. A pesquisa deve retornar o valor e indicar a matriz que o originou, A ou B.

f)

Um programa deve ler um vetor com dez códigos alfanuméricos dos cursos técnicos ofertados por uma instituição e deixá-los em ordem crescente. Então, deve ler um código alfanumérico e, em seguida, pesquisar se ele está no vetor, indicando sua posição.

Algoritmos - Técnicas de Programação

7 Programação com Registros

Para começar Este capítulo mostra como efetuar o trabalho de estruturação de dados com base na criação de tipos de dados derivados. Assim sendo, serão apresentados os detalhes para definição, implementação e uso de registros e definição de novos tipos de dados com base nos dados básicos existentes.

7.1 Tipos de dados derivados Na programação e no desenvolvimento de sistemas para computador, utilizamos diversos tipos de dados básicos (também chamados de tipos primitivos). No Capítulo 2, estudamos os tipos primitivos utilizados (inteiro, real, caractere, cadeia e lógico) pelas linguagens de programação, bem como de suas aplicações e limitações. A maioria dos problemas computacionais pode ser resolvida utilizando os tipos primitivos, porém, em alguns casos, a tarefa de programar pode se tornar cansativa e tediosa, se não buscarmos outras formas de trabalhar com os dados. Com o objetivo de facilitar a programação, temos os tipos de dados derivados ou, como em algumas bibliografias, tipo composto de dados. Um tipo de dados derivado é construído baseando-se nos tipos de dados primitivos e são, em sua maioria, utilizados em necessidades específicas; por esse motivo, cada desenvolvedor cria a estrutura necessária para cada projeto a ser desenvolvido.

85

Um tipo de dados derivado, após a sua criação, será visto por todo o projeto e deve ser definido antes da criação de uma variável. Para a criação de novos tipos com base nos tipos primitivos, deve-se seguir a seguinte sintaxe: tipo =

Em que: »

Identificador: é a definição do nome do novo tipo a ser utilizado no sistema.

»

Tipo de dado primitivo: é um dos tipos de dados primitivos já existentes.

Partindo da definição de um novo tipo de dados, é possível criar uma variável baseada no tipo de dados que acaba de ser criado. Por exemplo: tipo

NOTA = real

var

NOTA_PROVA : NOTA

Veja que nota_prova é uma variável definida com base no tipo NOTA. Amplie seus conhecimentos Você sabia que o sítio The Language List apresenta informações básicas de 2500 linguagens de programação. Para saber mais, consulte o endereço Web: . o em: 21 nov. 2013.

7.2 Tipo de dado derivado: registro Estudamos no Capítulo 5 as variáveis compostas homogêneas, úteis quando se deseja armazenar grande quantidade de informações de um mesmo tipo de dados, porém, quando se tem uma estrutura semelhante a uma tabela, em que cada dado pertence a um conjunto de informações diferentes, o processo de programação pode se tornar muito mais complicado. Nesse caso, temos as variáveis compostas heterogêneas ou simplesmente registro. Um registro é um tipo de dado derivado dos dados primitivos (muitas vezes de diferentes tipos) e é uma estrutura customizada para atender às necessidade do projeto no qual se está trabalhando. A sintaxe para a formação de um registro é formada com base na seguinte definição: tipo

= registro <lista de campos e seus tipos> fim_registro

86

Algoritmos - Técnicas de Programação

Em que: »»

Identificador: é a definição do nome do registro a ser utilizado no sistema.

»»

Registro e fim registro: marca início e fim do bloco que contém as variáveis do registro.

»»

Lista de campos e seus tipos: são os campos e seus respectivos tipos de dados.

Observe a Figura 7.1, em que temos a imagem de uma ficha de acompanhamento acadêmico. A ficha é composta por Dados pessoais (nome do aluno, série, turma e disciplina) e por Evolução das notas/faltas (notas e faltas para os quatro bimestres). Observe que as informações a serem armazenadas em cada campo são diferentes. Por exemplo, o campo Aluno é uma cadeia de caracteres, já as Faltas sempre serão um número inteiro, porém uma Nota é composta por um número real. Por esse motivo, um registro é uma estrutura de dados também denominada heterogênea. Ficha acadêmica Dados pessoais Nome: Série:

Turma:

Disciplina:

Evolução das notas/faltas 1º bimestre Falta

Nota

2º bimestre Falta

Nota

3º bimestre Falta

Nota

4º bimestre Falta

Nota

Figura 7.1 - Exemplo de um registro.

Com o objetivo de facilitar a montagem do diagrama de bloco, do português estruturado e, por fim, da programação, devem ser tomados os devidos cuidados com relação à identificação dos campos e aos tipos de dados que serão armazenados. Na Tabela 7.1, temos um simples - porém muito útil quadro utilizado para documentar a estrutura de dados do projeto a ser desenvolvido. Para o preenchimento da Tabela 7.1, basta observar quais informações se deseja armazenar e processar pelo algoritmo que se está criando. Para cada registro a ser criado, devemos montar um quadro diferente, no qual em Nome do registro se coloca o nome do registro a ser utilizado, e nas partes Nome do campo e Tipo de dados, colocam-se, respectivamente, os nomes dos campos e o tipo de dado a ser usado para o campo mencionado. Na Tabela 7.2 temos o quadro de definição de registro já com as informações da ficha acadêmica preenchidos. Tabela 7.1 - Quadro de definição de uma estrutura de registro Nome do registro Nome do campo

Programação com Registros

Tipo de dados

87

Tabela 7.2 - Documentação da estrutura do registro FICHA_ACADEMICA FICHA_ACADEMICA Nome do campo

Tipo de dados

nome

cadeia

série

inteiro

turma

caractere

disciplina

cadeia

falta1

inteiro

nota1

real

falta2

inteiro

nota2

real

falta3

inteiro

nota3

real

falta4

inteiro

nota4

real

Vale lembrar que o correto preenchimento do quadro de definição de registros facilita a construção de todo algoritmo que processa os dados. Essa documentação dever estar ível a todos aqueles da equipe de desenvolvimento que estão envolvidos na criação do projeto. Com base na estrutura definida na Tabela 7.2, tem-se a codificação do seguinte português estruturado: tipo FICHA_ACADEMICA = registro : cadeia



NOME





SERIE



TURMA



DISCIPLINA : cadeia



FALTA1 : inteiro

: inteiro

NOTA1

: real

FALTA3 : inteiro

NOTA3

: real

FALTA2 : inteiro

NOTA2

: caractere

: real

FALTA4 : inteiro

NOTA4

: real

fim_registro var aluno : ficha_academica

88

Algoritmos - Técnicas de Programação

Fique de olho! Foi definido, primeiramente, o tipo de dados, isto é, a FICHA_ACADEMICA, para depois criar a variável aluno, definida como do tipo FICHA_ACADEMICA. Sendo assim, aluno seria uma variável como outra qualquer, se não fosse por uma diferença: é criada para um projeto específico; por esse motivo que recebe o nome de variável composta heterogênea. Observe que, dessa forma, podemos guardar em uma única estrutura vários tipos diferentes de dados.

Em todas as operações (leitura e escrita) que manipula, a variável aluno, é necessário utilizarmos um operador de escopo, já que ela é composta por diversos campos. A sintaxe geral de o é:

[nome da variável de registro].[nome do campo]

Observe o exemplo: Para ar o campo NOME do registro FICHA_ACADEMICA, utilizaremos: ALUNO.NOME

7.3 Estrutura de um registro com matriz Na FICHA_ACADEMICA, temos estruturas que se repetem, como é o caso de Faltas e Notas (observe que temos Falta1, Falta2, Falta3, Falta4 e Nota1, Nota2, Nota3, Nota4). Nesses casos, é mais interessante criar um vetor (ou matriz unidimensional) para gerenciar essas informações. Assim, é possível definir dois vetores, um para nota e outro para falta, em que cada um possui quatro índices. A Figura 7.2 mostra a ficha acadêmica com essa alteração. Ficha acadêmica Dados pessoais Nome: Turma:

Série:

Disciplina:

Evolução das notas/faltas 1 Nota

2

3

4

1

2

3

4

Falta

Figura 7.2 - Alteração do layout da FICHA_ACADEMICA considerando vetores e sua estrutura.

A documentação também deve ser ajustada para a nova configuração, pois temos, agora, a estrutura de dois vetores dentro da ficha acadêmica. Observe a documentação da estrutura proposta na Tabela 7.3 e sua descrição em português estruturado.

Programação com Registros

89

Tabela 7.3 - Nova estrutura para o registro FICHA_ACADEMICA FICHA_ACADEMICA Nome do campo

Tipo de dados

nome

cadeia

série

inteiro

turma

caractere

disciplina

cadeia

falta

conjunto[1..4] de inteiro

nota

conjunto[1..4] de real

tipo FICHA_ACADEMICA = registro : cadeia



NOME



SERIE



TURMA



DISCIPLINA : cadeia



FALTA

NOTA



: inteiro



: caractere

: conjunto[1..4] de inteiro : conjunto[1..4] de real



fim_registro

var aluno : ficha_academica

Note que a definição para a criação da variável não sofreu ajuste; houve alteração apenas na estrutura do registro.

7.4 Tipo de dado derivado: novo tipo No início deste capítulo, vimos que podemos criar e definir um novo tipo de dados com base nos tipos primitivos. A facilidade de criar novos tipos dá a liberdade aos desenvolvedores de abstrair informações em estruturas mais simples de ser entendidas do ponto de vista do desenvolvimento. Assim, imagine que queremos criar um tipo de dado denominado bimestre, que conterá dois vetores de quatro posições, um para as faltas para armazenar dados inteiros e outro para as notas, o qual é capaz de receber dados reais. Então, podemos criar o tipo BIMESTRE, conforme Tabela 7.4, e defini-lo dentro do registro FICHA_ACADEMICA (observe na Tabela 7.5) por meio da variável boletim.

90

Algoritmos - Técnicas de Programação

Tabela 7.4 - Definição do tipo BIMESTRE BIMESTRE Nome do campo

Tipo de dados

falta

conjunto[1..4] de inteiro

nota

conjunto[1..4] de real

Tabela 7.5 - Estrutura do registro FICHA_ACADEMICA com uso do tipo bimestre FICHA_ACADEMICA Nome do campo

Tipo de dados

nome

cadeia

série

inteiro

turma

caractere

disciplina

cadeia

boletim

bimestre

O português estruturado para a estrutura criada na Tabela 7.5 pode ser observado a seguir: tipo BIMESTRE = registro FALTA : conjunto[1..4] de inteiro NOTA : conjunto[1..4] de real fim_registro FICHA_ACADEMICA = registro



: cadeia



NOME





SERIE



TURMA



DISCIPLINA : cadeia



BOLETIM : bimestre

: inteiro

: caractere

fim_registro

var ALUNO : ficha_academica

Temos na especificação do registro FICHA_ACADEMICA a criação do campo boletim cujo tipo é BIMESTRE. Já o tipo BIMESTRE é formado por dois vetores (matriz unidimensional) predefinidos. Mais uma vez, observe que nada foi modificado na definição da variável aluno.

Programação com Registros

91

7.5 Matriz de registro Com o que aprendemos até agora, conseguimos criar estruturas para armazenar grande quantidade de dados heterogêneos, porém a estrutura de registro criada até então a armazenar somente os dados de um aluno por vez, o que nos remete ao mesmo problema trabalhado no Capítulo 5, quando vimos que, para armazenar mais de uma informação do mesmo tipo, podemos criar um vetor ou uma matriz com várias posições (índices), em que cada dado específico tem sido armazenado em uma posição. Aqui, em registros, podemos nos utilizar da mesma estrutura de vetores e matrizes, ou seja, criar um vetor de registros com várias posições; em cada posição (indexada por um índice), temos um conjunto de dados totalmente isolado. Note que, uma vez criada a estrutura do registro, conforme visto anteriormente, basta criarmos uma variável que seja definida como um vetor do tipo do registro. Vejamos o seguinte exemplo: Considere uma sala de aula com cinco alunos. tipo

BIMESTRE = registro

FALTA : conjunto[1..4] de inteiro

NOTA : conjunto[1..4] de real fim_registro

FICHA_ACADEMICA = registro NOME



SERIE



TURMA



var

: cadeia





: inteiro

: caractere

DISCIPLINA : cadeia

BOLETIM : bimestre

fim_registro

ALUNO : conjunto[1..5] de ficha_academica

Após o uso do comando var, é indicada a variável de registro aluno, formada por um conjunto (vetor) de cinco registros do tipo de dado derivado FICHA_ACADEMICA.

92

Algoritmos - Técnicas de Programação

Exemplo Crie um programa que efetue a leitura dos dados de uma FICHA-ACADEMICA - como já definida - para uma sala de aula com cinco alunos. Ao final, o sistema deve imprimir o nome de cada aluno, sua série, turma, disciplina, o total de faltas e a média aritmética.

Solução Uma vez definida a estrutura de dados que comportará os dados, deve-se efetuar a leitura de todos os dados e, em seguida (na fase de processamento), calcular e imprimir a soma de todas as faltas e as médias de cada aluno.

1

i

1, 5, 1

Diagrama de blocos total_faltas soma_notas

0 0

INÍCIO

I

j

1, 5, 1

ALUNO[I].NOME

total_faltas soma_notas

1, 4, 1

total_faltas + aluno[i].boletim.falta[j] soma_notas + aluno[i].boletim.nota[j]

ALUNO[I].SERIE

media

soma_notas/4

ALUNO[I].TURMA

aluno[i].nome

ALUNO[I].DISCIPLINA

J

1, 4, 1

aluno[i].serie

aluno[i].turma

aluno[i].disciplina ALUNO[I].BOLETIM.FALTA[J]

total_faltas ALUNO[I].BOLETIM.NOTA[J]

media

1

Fim

Figura 7.3a - Trecho responsável pela entrada de dados dos registros.

Figura 7.3b - Trecho responsável pelo processamento e pela saída de dados.

Programação com Registros

93

Português estruturado programa MEDIA_SALA_AULA tipo BIMESTRE = registro FALTA : conjunto[1..4] de inteiro NOTA : conjunto[1..4] de real fim_registro FICHA_ACADEMICA = registro NOME : cadeia SERIE : inteiro TURMA : caractere DISCIPLINA : cadeia BOLETIM : bimestre fim_registro var ALUNO : conjunto[1..5] de ficha_academica TOTAL_FALTAS : inteiro SOMA_NOTAS : real MEDIA : real início para I leia leia leia leia

de 1 até 5 o 1 faça ALUNO[I].NOME ALUNO[I].SERIE ALUNO[I].TURMA ALUNO[I].DISCIPLINA

para J de 1 até 4 o 1 faça leia ALUNO[I].BOLETIM.FALTA[J] leia ALUNO[I].BOLETIM.NOTA[J] fim_para fim_para para I de 1 até 5 o 1 faça TOTAL_FALTAS ← 0 SOMA_NOTAS ← 0 para J de 1 até 4 o 1 faça TOTAL_FALTAS ← TOTAL_FALTAS + ALUNO[I].BOLETIM.FALTA[J] SOMA_NOTAS ← SOMA_NOTAS + ALUNO[I].BOLETIM.NOTA[J] fim_para MEDIA ← SOMA_NOTAS / 4 escreva escreva escreva escreva escreva escreva fim_para

ALUNO[I].NOME ALUNO[I].SERIE ALUNO[I].TURMA ALUNO[I].DISCIPLINA TOTAL_FALTAS MEDIA

fim

94

Algoritmos - Técnicas de Programação

Vamos recapitular? Aprendemos neste capítulo como criar e definir uma variável heterogênea, ou seja, um registro. Vimos, também, como é possível trabalhar com vetores/matrizes com base em um registro.

Agora é com você! 1)

2)

Com base na estrutura definida na Tabela 7.5, crie o português estruturado de um programa de computador que, por meio de um menu de opção: a)

Cadastre os dez registros.

b)

Pesquise um registro de cada vez pelo campo nome.

c)

Imprima na tela os nomes dos alunos em ordem crescente.

d)

Imprima o nome do aluno com a maior e a menor média.

e)

Imprima o nome do aluno com a maior e a menor quantidade total de faltas.

f)

Imprima o nome do aluno com a maior e a menor nota.

g)

Saia do programa de cadastro.

Considere a seguinte ficha para uma escola de informática: Ficha cadastral Dados Nome: Série:

Turma:

Média:

Aprovado:

Sexo: Sim

M

F

Ano de nascimento:

Não

Construa um programa (definição do registro e português estruturado), que possa ler os dados para 20 alunos e responder, por meio de um menu de opções, as seguintes questões: a)

Qual a porcentagem de alunos aprovados e reprovados?

b)

Qual a porcentagem de alunos do sexo masculino e a do sexo feminino?

c)

Quais são os alunos com melhor nota de uma mesma série?

d)

Quantos alunos nasceram em um mesmo ano?

e)

Qual a listagem dos alunos por ordem alfabética separados por sexo?

Programação com Registros

95

3)

A tabela a seguir se refere ao cadastro dos distribuidores de uma determinada revista. Distribuidor Campo

Tipo

Descrição

DIS_Codigo

Inteiro

Código único

DIS_Nome

Cadeia

Razão Social do Distribuidor

DIS_Endereco

Cadeia

Endereço completo

DIS_Zona

Cadeia

Divisão de uma cidade. Ex.: Norte, Oeste, Leste e Sul

DIS_Cota

Inteiro

Número de exemplares recebidos

DIS_Cidade

Cadeia

Nome da Cidade

Elaborar um programa que armazene todos os dados do registro acima. O programa deve ser manipulado por meio de um menu que execute as seguintes etapas:

96

a)

Cadastrar 15 registros.

b)

O usuário deverá fornecer uma determinada cidade e o programa apresentar a Razão Social de todos os distribuidores daquela cidade.

c)

Apresentar um relatório que informe a quantidade de exemplares recebidos por cidade.

d)

Apresentar um relatório completo com todos os campos ordenado em ordem crescente de cota.

Algoritmos - Técnicas de Programação

8 Utilização de Sub-rotinas

Para começar Neste capítulo você aprenderá a utilizar sub-rotinas e técnicas de programação mais avançadas, como a técnica conhecida por “dividir para conquistar”. Com esse conhecimento, você poderá produzir códigos-fonte mais legíveis, fáceis de fazer manutenção e essencialmente mais modularizados. Com o uso adequado das técnicas avançadas de programação, você desenvolverá programas ainda mais profissionais.

8.1 Dividir para conquistar A atividade de programar requer conhecimentos lógico-conceituais e, principalmente, técnicos. Nesse sentido, o pleno domínio das principais técnicas de programação é fundamental para a elaboração de algoritmos e programas eficientes e de fácil manutenção. Em computação, algoritmos são considerados eficientes se conseguem resolver um determinado problema com o melhor desempenho possível. Uma das técnicas para projeto de algoritmos mais usuais e importantes da programação de computadores é conhecida por “dividir para conquistar”. Mais que uma técnica, dividir para conquistar tem sido considerado um paradigma, uma vez que inspira o desenvolvimento de diversas outras técnicas de programação e, também, de análise de sistemas. A técnica de dividir para conquistar consiste basicamente em três procedimentos:

97

1) Dividir: separar o problema em dois ou mais subproblemas menores similares ao original, pois solucionar vários pequenos problemas, em vez de um grande, é, do ponto de vista computacional, supostamente mais fácil; 2) Conquistar: resolver cada subproblema em separado utilizando o próprio algoritmo que está sendo projetado; 3) Combinar: obter uma solução para o problema original a partir da combinação das soluções dos subproblemas. Cada um desses procedimentos pode ser implementado de modo diferente, de acordo com o algoritmo que projetamos e com as necessidades do nosso problema. Por exemplo, para dividir o problema original, podemos usar divisão binária (dividir o problema em dois subproblemas) ou divisão n-ária (dividir o problema em n partes), conforme mostra a Figura 8.1.

Divisão

Subproblema 2

Subproblema 3

Solução 1

Solução 2

Solução 3

Combinação

Subproblema 1

Conquista

Problema original

...

Subproblema N

Solução N

Solução do problema original

Figura 8.1 - Macroprocesso de divisão e conquista.

Os processos de divisão em subproblemas e combinação das soluções são fundamentais para o desenvolvimento de algoritmos eficientes. Essa técnica tem sido utilizada na resolução de vários problemas da computação, como problemas de ordenação (Quicksort e Mergesort), problemas de busca (pesquisa binária), problemas geométricos (algoritmo do par mais próximo e convex hull), entre outros. Para mais informações sobre esses e outros algoritmos com uso da técnica de divisão e conquista, veja Cormen et al. (2002) e Feofiloff (2008). Em ambiente de desenvolvimento de software, é comum ouvir-se o termo “instância de problema”. Instância de um problema computacional são casos específicos de um determinado problema. Ao se projetar um algoritmo utilizando a divisão e conquista, o programador gera quantas instâncias do problema original forem necessárias. Essas instâncias são reduzidas em termos de dados, o que temos chamado de subproblema, de modo que a solução de cada instância tenha um custo de

98

Algoritmos - Técnicas de Programação

processamento muito baixo. Por exemplo, digamos que o nosso problema original seja pesquisar pela palavra “incondicional” em um glossário com 1000 verbetes. Se utilizarmos um algoritmo que divide o problema em dois subproblemas, podemos ter duas instâncias de 500 verbetes cada. Para ficar mais fácil de entender, imaginemos uma situação na qual precisemos computar a soma de n números x0 a xn-1. Considerando que n > 0, podemos, então, dividir o problema em pelo menos dois subproblemas: »»

soma dos n/2 primeiros números do conjunto;

»»

soma dos n/2 últimos números do conjunto.

Na prática, houve um desmembramento dos dados de entrada. Dividimos o conjunto de dados em dois. Logo, surgiram dois subproblemas menores, mas similares ao problema original: computar a soma. O próximo o é, portanto, resolver os dois subproblemas. Uma vez resolvidos, a combinação das soluções nos garante a solução do problema original: Sx(0,n-1) = (x0 + ... + x(n/2)-1) + (xn/2 + ... + xn-1) Note que esse é um problema simples que poderíamos resolver de uma forma igualmente simples, pela força bruta, sem uso de técnicas sofisticadas. Inclusive, não há ganho de eficiência se resolvermos esse algoritmo por meio de um único laço, considerando de uma só vez todo o conjunto de dados. Isso mostra que nem todos os problemas são melhorados por meio da técnica de divisão e conquista. Essa premissa é verdadeira até mesmo para outras técnicas de programação. Eis, então, a responsabilidade do programador em escolher a técnica mais adequada para o seu problema. Então, quando devo aplicar a técnica de divisão e conquista? Basicamente quando: »»

o seu problema puder ser particionado em problemas similares menores, o que chamamos de resolução por indução;

»»

os subproblemas gerados possam ser solucionados independentemente uns dos outros;

»»

for possível combinar as soluções dos subproblemas de modo eficiente.

Vejamos agora outro exemplo, um pouco mais complexo. Digamos que desejamos efetuar uma busca em um vetor ordenado. O modo mais trivial de solucionar esse problema é por meio da pesquisa sequencial, estudada no Capítulo 6. Todavia, em um conjunto de dados muito grande, a pesquisa sequencial é pouco eficiente. Nesse caso, a divisão e conquista am a ser uma estratégia interessante se o conjunto de dados estiver ordenado. Um dos algoritmos de busca por divisão e conquista mais utilizados é a pesquisa binária. A pesquisa binária consiste em dividir o conjunto de dados (com n elementos) em duas partes, por isso o adjetivo “binário”. Logo, o problema também é reduzido a dois subproblemas menores. Se o conjunto tiver apenas um valor (n = 1) e o elemento procurado for a1, então o valor procurado foi encontrado; caso contrário, esse valor não está no conjunto. Se n > 1, então verificaremos se a chave de busca está na posição do meio (n/2), ou seja, se k = an/2. Se estiver, o valor procurado foi encontrado; caso contrário, será necessário continuar a busca. Como o conjunto está ordenado, é simples saber se o valor procurado, caso exista, está na primeira ou na segunda parte do conjunto.

Utilização de Sub-rotinas

99

Dividimos, portanto, o problema em dois a depender do valor da chave de busca: »»

busca binária nos elementos a1 até a(n/2)-1 do vetor;

»»

busca binária nos elementos a(n/2)+1 até an do vetor.

O processo de divisão e conquista se repete até que, então, o valor procurado seja encontrado ou descubra-se que o valor não está no vetor. Note que o processo de divisão é realizado quantas vezes for necessário. Perceba também que nesse algoritmo, os processos de dividir e de conquistar são iterativos e incrementais, ou seja, ocorrem várias vezes, e a cada vez que ocorrem, o algoritmo está mais próximo de encontrar a chave de busca1 (ou de informar que ela não consta no conjunto de dados). Note que esse método é semelhante ao que realizamos ao procurar uma palavra (nossa chave de busca) em um dicionário. Vejamos um exemplo da aplicação desse algoritmo. Encontrar o número 4 no vetor ordenado V = {1, 3, 4, 9, 10, 11, 15}. Antes de resolver, saiba que o vetor V possui 7 elementos, logo n = 7. A primeira decisão é aplicada: 4 está na posição n/2, ou seja, na posição 3? Não, pois nessa posição está o valor 9. Então, dividiremos o vetor em dois subconjuntos: »»

valores abaixo da posição 3: V1 = {1, 3, 4};

»»

valores acima da posição 3: V2 = {10, 11, 15}.

Como 4 é menor que 9, então o conjunto representado pelo vetor V2 será descartado e, mais uma vez, o algoritmo de busca binária será executado, dessa vez sobre o vetor V1. Neste subproblema, a primeira decisão será similar à utilizada no problema original: 4 é menor que o elemento do meio? A reposta é não. O elemento do meio (posição 1) é 3. Então, o vetor será novamente dividido em dois novos subconjuntos: »»

valor abaixo da posição 1: V11 = {1};

»»

valor acima da posição 1: V12 = {4}.

Como 4 é maior que 3, o conjunto de valores abaixo de 3 (vetor V11) será descartado. Sobre o vetor V12 será aplicado novamente o algoritmo de busca binária. Verifique que o V12 possui apenas um elemento. Logo, se o valor procurado for diferente do valor desse elemento, o algoritmo deve informar que o valor procurado não se encontra no conjunto de dados. Nesse caso, o valor procurado (4) é igual ao elemento único de V12, logo, o valor procurado foi encontrado, conforme se observa na Figura 8.2.

1

3

1

1

1

3

3

4

9 10 11 15

9

4

10 11 15

4

4

Figura 8.2 - Visualização da execução do algoritmo de busca binária.

Chave de busca é o valor procurado no conjunto de dados.

100

Algoritmos - Técnicas de Programação

Veja, a seguir, o algoritmo em português estruturado e em diagrama de blocos.

Diagrama de blocos

Português estruturado programa BUSCA_BINARIA

INÍCIO

var I

V : conjunto[1..20] de inteiro

1, 20, 1

X, N, MEIO, ESQUERDA, DIREITA, I: inteiro

início

para I de 1 até 20 o 1 faça

V [I]

leia V [I]

fim_para N 20 ESQUERDA DIREITA N

0

N ← 20 ESQUERDA ← 0 DIREITA ← N

X

leia X N ESQUERDA <= DIREITA

enquanto (ESQUERDA <= DIREITA) faça MEIO ← (ESQUERDA + DIREITA) DIV 2

S MEIO

se (V[MEIO] = X) então

(ESQUERDA + DIREITA) DIV 2

escreva MEIO

N

senão

S

se (V[MEIO] < X) então

V [MEIO] = X

N

DIREITA

V [MEIO] < X

MEIO - 1

S

ESQUERDA

ESQUERDA ← MEIO + 1

MEIO

senão DIREITA ← MEIO - 1

MEIO + 1

fim_se

fim_se

fim_enquanto

fim

FIM

Figura 8.3 - Diagrama de blocos para o algoritmo de busca binária.

Utilização de Sub-rotinas

101

8.2 Programação top-down e bottom-up Ao projetar um software, o programador e o projetista podem optar por desenvolvê-lo das estruturas mais gerais para as mais específicas (top-down) ou vice-versa (bottom-up). Se optar pelo método top-down, primeiro será desenvolvida a estrutura geral do software e definidos os componentes menores, mas estes serão desenvolvidos conforme o processo de desenvolvimento avançar. No método bottom-up, os módulos/componentes menores são desenvolvidos e testados, só então são agregados para formar o software projetado. Numa programação top-down o software é desenvolvido a partir de refinamentos sucessivos, ou seja, o projeto e a implementação do software evolui incrementalmente ao longo do processo de desenvolvimento. Essa abordagem também é conhecida como método incremental. Um das vantagens do método top-down é efetuar todas as etapas do processo de desenvolvimento em partes pequenas do software, logo, ações que só ocorreriam no final do processo são “adiantadas” e executadas várias vezes em pequenas porções do produto, como os testes unitários e testes com usuários. Para ser efetivo, é preciso que as etapas de refinamento sejam simples e bem definidas e, além disso, ao longo do desenvolvimento a estrutura basilar do projeto de software deve ser definida, o que facilita, inclusive, os testes. Por sua vez, a programação bottom-up também desenvolve o software em etapas. Todavia, nessa abordagem, uma proposta inicial do software é definida no início do processo de desenvolvimento. Essa proposta contém informações sobre todos os módulos/componentes que serão desenvolvidos. Em seguida, são desenvolvidos os módulos/componentes detalhados.

8.3 Procedimentos O programador deve sempre se lembrar de manter a legibilidade dos algoritmos e códigos-fonte dos seus programas. Para isso, é preciso utilizar-se de vários mecanismos. Um deles é a modularização do programa. Ao criar módulos de programas, o programador permite estabelecer ações pontuais para cada porção de código, deixando o programa mais limpo e, consequentemente, mais fácil de efetuar manutenção. Atualmente, há diversas formas de modularização. Neste capítulo, estudaremos duas formas: procedimentos e funções. Procedimentos são subprogramas (também conhecidas por sub-rotinas), ou seja, partes de um programa maior, com finalidade específica. Os procedimentos executam uma determinada tarefa com uso ou não de parâmetros de entrada, mas jamais retornam valores ao programa que o chamou. Os parâmetros são valores enviados pelo programa principal para correta execução dos procedimentos. Todo procedimento deve ter uma . A é composta pelo identificador do procedimento e seus parâmetros de entrada, caso tenha. Também pode ter espaço para declaração de variáveis. Essas variáveis só poderão ser utilizadas dentro do procedimento onde foram declaradas.

102

Algoritmos - Técnicas de Programação

Em português estruturado, podemos definir um procedimento desta forma: Procedimento <nome do procedimento>(<lista de parâmetros>) fim_procedimento

Vejamos um exemplo de uso de procedimento: procedimento Ordenacao_Vetor (VET: conjunto[1..N] de inteiro, N: inteiro)

var

I, J : inteiro X : cadeia

início

para I de 1 até 19 o 1 faça

para J de I + 1 até 20 o 1 faça se (VET [I] > VET [J]) então X ← VET [I] VET [I] ← VET [J] VET [J] ← X fim_se

fim_para

fim_para

fim_procedimento

Para que um procedimento seja executado, é necessário que o computador processe um comando de chamada. Esse comando, em geral, é formado pelo identificador do procedimento seguido dos parâmetros necessários, como no exemplo abaixo, em que o procedimento Ordenacao_ Vetor é chamado: programa LISTA_NOME_ORDENADA var

ESTUD : conjunto[1..20] de cadeia I: inteiro

início

para I de 1 até 20 o 1 faça leia ESTUD [I]

fim_para

Ordenacao_Vetor (ESTUD, 20) para I de 1 até 20 o 1 faça escreva ESTUD [I]

fim_para

fim

Utilização de Sub-rotinas

103

8.4 Funções Similar aos procedimentos, funções são subprogramas (também conhecidas por sub-rotinas), ou seja, partes de um programa maior. Uma das principais diferenças é que funções obrigatoriamente retornam valores ao programa ou subprograma que as chamaram. Esse retorno é conhecido como parâmetro de saída. Os parâmetros de saída, assim como os de entrada, devem ter um tipo de dado associado, tais como interiro, real, cadeia ou lógico. A execução de uma função pode se dar pela chamada da função, como no procedimento ou, ainda, por meio de avaliação de uma expressão que contenha a função, como no excerto: [...] se (SALARIO > Media_Anual(SALARIOS[], N)) então [...]

Nesse exemplo, a função Media_Anual será executada ao programa tentar validar a condição SALARIO > Media_Anual (VETOR, N). Para efetuar a comparação do salário com a média anual, será necessário executar a função Media_Anual. Essa função recebe o vetor com os salários de todos os meses como parâmetro de entrada e, ao final, retorna como parâmetro de saída o valor médio dos salários recebidos durante o ano. Toda função deve ter uma . A é composta pelos parâmetros de saída, o identificador da função e pelos parâmetros de entrada, caso tenha. No corpo da função pode ter espaço para declaração de variáveis, que só poderão ser utilizadas dentro da função onde foram declaradas. Em português estruturado, podemos definir uma função da seguinte forma: tipo_retorno Função <nome da função>(<lista de parâmetros>) fim_funcao

Vejamos um exemplo de uso de função: função Media_Anual(VET : conjunto de inteiro, N: inteiro) : real var

I, ACUMULADOR : inteiro

início

para I de 1 até N o 1 faça ACUMULADOR ← VET[I] fim_para retorne ACUMULADOR / 12

fim_função

Amplie seus conhecimentos Você sabia que o conceito de linguagem de programação advém da linguística? Os linguistas tentaram definir precisamente quais eram as sentenças válidas descritas em uma determinada linguagem, bem como definiram regras de escrita. O mesmo ocorre com as linguagens de programação. Muitos dos códigos-fonte escritos em linguagens de programação am por analisadores baseados em processos linguísticos de análise léxica, sintática e semântica. Para saber mais, consulte Price e Toscani (2008).

104

Algoritmos - Técnicas de Programação

8.5 Escopo de variáveis Como vimos ao longo do curso, variáveis podem ser declaradas no programa principal (fora de procedimentos e funções), como parâmetros em procedimentos e funções ou, ainda, no corpo dessas sub-rotinas. A variável atende a um determinado escopo, a depender do local onde foi declarada. Temos dois tipos diferentes de escopo de variáveis: global ou local. Variáveis globais devem ser declaradas fora de qualquer sub-rotina, isto é, devem ser declaradas no programa principal. Essas variáveis são inicializadas no começo da execução do programa e continuam a existir durante todo o processo. Variáveis locais são aquelas declaradas como parâmetro ou dentro de uma sub-rotina (procedimento ou função). Variáveis desse tipo só poderão ser utilizadas dentro pela função ou procedimento onde foi declarada, não sendo possível seu uso em outra parte em nenhuma hipótese. Diferente das variáveis globais, as locais são criadas somente quando a sub-rotina é executada e são destruídas ao final da execução da sub-rotina. Essa é uma das vantagens de se utilizar variáveis locais, uma vez que elas ficam em memória somente enquanto são necessárias. Variáveis de escopos diferentes podem ter o mesmo nome. Portanto, cuidado ao nomear variáveis locais para que não ocorra duplicidade de nomes entre as variáveis e isso prejudique a manutenção do software. Quando houver variável local com o mesmo nome de uma global, a sub-rotina considerará a variável local em detrimento da global. No exemplo a seguir, SALARIOS, SALARIO e QTDSAL são variáveis globais e VET, N, I e ACUMULADOR são variáveis locais. programa PAGAMENTO var

SALARIOS : conjunto[1..20] de real SALARIO, QTDSAL: inteiro

início

leia SALARIO QTDSAL ← 12 se (SALARIO < Media_Anual(SALARIOS, QTDSAL)) então

escreva "Este empregado tem direito à bonificação"

fim_se

função Media_Anual (VET: conjunto[1..N] de inteiro, N: inteiro) : real var

I, ACUMULADOR : inteiro

início

para I de 1 até N o 1 faça ACUMULADOR ← VET[I]

Utilização de Sub-rotinas

105

fim_para retorne ACUMULADOR / 12

fim_funcao fim

8.6 agem de parâmetros Ao criarmos funções e procedimentos, definimos parâmetros de entrada com tipos associados. Ao serem chamados, as funções e os procedimentos podem receber esses parâmetros por referência ou por valor. Na agem de parâmetros por referência, a sub-rotina recebe apenas a referência da variável, ou seja, o endereçamento de memória. O parâmetro ado por referência se comporta como uma variável global dentro do subprograma e todas as alterações realizadas nela afetarão diretamente a variável do programa principal ado como parâmetro. Isso porque o subprograma se encarrega de ir ao endereço ado e capturar o valor que lá está. Essa forma de agem de parâmetros também permite à sub-rotina alterar o valor da variável diretamente na memória. Na agem de parâmetros por valor, o parâmetro tem as características de uma variável local. Logo, alterações realizadas nessa variável ficam restritas ao escopo do subprograma, sem afetar o programa principal, como na função produto do exemplo a seguir. programa EXEMPLO__VALOR var

N: inteiro

RESULTADO : inteiro

início

leia N

escreva N procedimento cálculo (X : inteiro) : inteiro X ← X * X retorna X

fim_funcao

escreva N

fim

Nesse exemplo, considerando que foi lido o valor N = 10, será apresentada na tela a seguinte saída: 10 100 10

106

Algoritmos - Técnicas de Programação

O último valor refere-se à variável N, que, por ter sido ada por valor à função Cálculo, não foi alterado dentro dessa função. O valor inicial de N é 10 e se mantém o mesmo até o final da execução desse programa. Veja que a principal diferença entre as duas formas de agem de parâmetros é que na agem por valor o conteúdo da variável é “copiado” para o parâmetro da sub-rotina. Na agem por referência, o endereço de memória é atribuído ao parâmetro do subprograma. Com esse endereço, o subprograma pode fazer as alterações que desejar, e todas elas serão vistas em qualquer parte do programa, como neste exemplo: Em português estruturado, podemos definir uma função da seguinte forma: função <nome da função>(<lista de parâmetros>) : tipo_retorno

Vejamos um exemplo de uso de função: função Media_Anual(VET : conjunto[1..N] de inteiro, N : inteiro) : real var

I, ACUMULADOR : inteiro

início

para I de 1 até N o 1 faça ACUMULADOR ← ACUMULADOR + VET[I]

fim_para

Media_Anual← ACUMULADOR / 12

fim_função

Nesse exemplo, considerando que foi lido o valor N = 10, será apresentada na tela a seguinte saída: 10 100 100 O último valor refere-se à variável N, que, por ter sido ada por referência à função Cálculo, foi alterado dentro dessa função, diferente do que ocorreu no exemplo em que N foi ada por valor. Veja, também, que para ar valor por referência a uma função ou procedimento é necessário colocar a palavra “var” antes do nome do parâmetro na da sub-rotina.

Vamos recapitular? Neste capítulo, estudamos as características fundamentais das sub-rotinas ou subprogramas, os seus tipos (procedimentos e funções) e as características mais importantes, como agem de parâmetros por valor e por referência, escopo de variáveis e métodos top-down/bottom-up.

Utilização de Sub-rotinas

107

Agora é com você! 1)

Escreva uma sub-rotina que receba por parâmetro um número inteiro e imprima se ele é divisível por 7 ou não. Decida se usará procedimento ou função e explique o porquê da escolha.

2)

Escreva um procedimento que receba por parâmetro o código do grupo ao qual um determinado animal pertence e, em seguida, imprima o nome do grupo e a constante K para cálculo da taxa metabólica basal (TMB), conforme tabela a seguir: Código do grupo

3)

Nome do grupo

Constante (K)

1

eriformes

129

2

Não eriformes

78

3

Mamíferos Placentários

70

4

Marsupiais e Edentatas

49

5

Répteis

10

Escreva uma função que receba por parâmetro o peso metabólico (PM) de um animal (peso total do animal expresso em quilogramas) e o grupo ao qual esse animal pertence e calcule a taxa metabólica basal (TMB). A taxa metabólica basal é o peso metabólico elevado a 0,75 e multiplicado por uma constante K. O valor de K depende do grupo do animal, conforme tabela do exercício anterior. Fórmula de cálculo da taxa metabólica basal: TMB = (PM ↑ 0,75) * K

4)

Escreva um procedimento que receba por parâmetro o peso metabólico (PM) de um animal (peso total do animal expresso em quilogramas), o grupo ao qual esse animal pertence e uma letra (flag). Se a letra for B, o procedimento deve chamar uma função para calcular a taxa metabólica basal (TMB). Se a letra for E, o procedimento deve chamar uma função para calcular a taxa metabólica específica (TME). Para o cálculo da TME, usar a fórmula a seguir. O valor da constante K corresponde ao grupo do animal, sendo o mesmo tanto para o cálculo da TMB como da TME. Fórmula de cálculo da taxa metabólica específica: TME = (PM ↑ 0,25) * K

108

Algoritmos - Técnicas de Programação

Medidas de Complexidade de Algoritmos

9 Para começar

Neste capítulo, serão abordados de maneira introdutória e mais didática possível conceitos preliminares do uso de medidas de complexidade de algoritmos para estudantes iniciantes em programação de computadores.

9.1 Análise de algoritmos O que apresentamos aqui sobre análise de algoritmos e suas complexidades não é comum em um livro introdutório sobre lógica de programação de computadores para programadores iniciantes, como este. A disponibilidade de livros em português é pequena e o foco desse estudo é ministrado em cursos mais avançados de programação. Assim sendo, o tema ora abordado constitui-se em uma visão preliminar com o objetivo de indicar ao nosso estudante os próximos os a serem seguidos no estudo da lógica de programação e no aprofundamento desse estudo, que se estende com a aprendizagem de uma disciplina denominada Estrutura de Dados. A expressão Análise de Algoritmos, como é usada e como a conhecemos, foi idealizada por Donald E. Knuth quando publicou em 1968 o primeiro volume de uma série de sete livros intitulado The Art of Computer Programming (A Arte da Programação de Computadores) não tendo este trabalho tradução para o português.

109

A disciplina de Análise de Algoritmos tem por objetivo estudar os problemas computacionais que se apresentam de forma recorrente, que se mostram de diferentes formas (FEOFILOFF, 2013). Nesse sentido, podemos entender que essa disciplina visa, para um dado problema, nos mostrar: »»

a prova de que o algoritmo que estamos usando está correto.

»»

a estimativa da complexidade do tempo que a execução do algoritmo consome.

»»

a estimativa do espaço de memória usada para seu armazenamento.

Veja que, com base no exposto fica fácil concordar com as palavras de Almeida (2000, p. 3) que nos diz que um “algoritmo não é a solução de um problema, pois, se assim fosse, cada problema teria um único algoritmo”. Note que poderão existir para a solução de um problema vários caminhos, vários algoritmos. Assim sendo, um problema poderá ser resolvidos com o uso de vários algoritmos (PRESTES, 2011), Almeida (2000, p. 3) acrescenta ainda que “algoritmo é um caminho para a solução de um problema, e em geral, os caminhos que levam a uma solução são muitas”. Análise de Algoritmos é a forma com a qual poderemos medir qual algoritmo é o melhor para responder a certo problema, pois como afirma Prestes (2011) “o fato de um algoritmo resolver um dado problema não significa que seja aceitável na prática”. Se tivermos dois algoritmos para a solução de um mesmo problema, a ação prática da Análise de Algoritmos nos permitirá decidir dos dois algoritmos fornecidos, aquele que seja melhor eficiente (otimilidade de algoritmos). É fundamental sabermos que eficiência é a forma como um algoritmo realiza sua tarefa até atingir seu objetivo e que eficácia é o objetivo em si. Os algoritmos devem ser eficazes, devem atender seus objetivos, devem fornecer uma solução de boa qualidade a certo problema. Assim, a eficiência é o grau de satisfação de boa qualidade medido pela Análise de Algoritmos para saber qual dos algoritmos encontrados é o melhor para solucionar o problema existente. Para analisar a eficiência no uso de certo algoritmo, é necessário levar em consideração a existência de duas possibilidades de análise, como mostra Matos (2008, p. 13): »»

Pormenorizada: mais exata e direta, em geral menos útil, pois: é expressa em segundos; resultado da avaliação da eficiência (por exemplo, tempo gasto): único e dependente da velocidade e características do processador.

»»

Por meio de ordens de grandeza: ignora as constantes multiplicativas e é uma análise assintótica (método para medir o tempo total gasto por um algoritmo para realizar certa tarefa computacional), isto é: expressa em ordens de grandeza; resultado da avaliação da eficiência: paramétrico (uma função do comprimento dos dados) e independente da velocidade e características do processador.

Com base nessa explicação, podemos dizer que a Análise de Algoritmos é uma disciplina de Engenharia, de Matemática ou da Ciência da Computação, dependendo do enfoque que queira se dar, que procura prever o comportamento de um algoritmo antes mesmo que seja implementado

110

Algoritmos - Técnicas de Programação

e efetivamente colocado “em produção” (FEOFILOFF, 2013, p. 9). Este tipo de análise possibilita ganho econômico na produção de software. Amplie seus conhecimentos O estudo de análise e complexidade de algoritmos pode ser ampliado com base na consulta de diversos outros materiais publicados na grande rede mundial (Internet), em português, a partir dos seguintes sítios (o em: 19 dez. 2013): http://www.inf.ufrgs.br/~prestes/site/Welcome.html (slides); http://www.youtube.com/watch?v=j7BKN7phIeY (vídeo aula); http://www.ime.usp.br/~pf/analise_de_algoritmos/ (diversos materiais); http://www.ime.usp.br/~pf/livrinho-AA/AA-BOOKLET.pdf (minicurso de análise de algoritmos); http://www.decom.ufop.br/toffolo/ (diversos materiais de apoio); http://www.dcc.fc.up.pt/~ap/taa/1011/ (apostila com notas de aula).

9.2 Modelo de tempo e espaço: otimilidade de algoritmos Nós, programadores de computador, temos que sempre levar em consideração que todo projeto de programa pode vir a ser influenciado pelo estudo de seus comportamentos. Após um problema ser analisado e as decisões sobre o projeto serem tomadas, o algoritmo em si deve ser implementado na forma de um programa de computador. Nesse instante, devemos analisar as inúmeras alternativas que poderemos aplicar, devemos considerar os aspectos de tempo de execução e espaço de memória ocupado. As alternativas encontradas para o desenvolvimento desses algoritmos podem ser localizadas em outras disciplinas tais como: pesquisa operacional, otimização, teoria de grafos, estatísticas, probabilidades etc. (CLAUDINO, 2013). Knuth (apud CLAUDINO, 2013, p. 8) informa que “na área de estudo dos algoritmos, há dois tipos de problemas bem distintos” a serem considerados: a análise de um algoritmo particular e a análise de uma classe de algoritmos e assim os especifica: »

A análise de um algoritmo particular leva em conta o custo do uso de um dado algoritmo para equacionar um problema específico. Características importantes do algoritmo devem ser investigadas, geralmente uma análise do número de vezes que cada parte do algoritmo deve ser executada, seguida do estudo da quantidade de memória necessária a ser utilizada por certo computador.

»

A análise de uma classe de algoritmos visa identificar o algoritmo de menor custo possível para resolver um determinado problema particular. Toda uma família algoritmos para resolver um problema específico deve ser investigada com o objetivo de identificar o algoritmo que seja o melhor possível. Isso significa colocar limites para a complexidade computacional dos algoritmos pertencentes à classe. Por exemplo, é possível estimar o número mínimo de comparações necessárias para ordenar “n” números por meio de comparações sucessivas.

Medidas de Complexidade de Algoritmos

111

Quando determinamos o menor custo possível e usamos para resolver problemas de determinada ordem, como no caso das ordenações de valores ou dos padrões usados para estabelecer o processamento de uma pesquisa de dados em vetores, temos nestes a medida da dificuldade inerente para resolvê-los. Além disso, quando o custo de um algoritmo é igual ao menor custo possível, então podemos concluir que o algoritmo é ótimo para a medida de custo considerada (LOUREIRO, 2005; TOFFOLO, 2012). É com base nessas considerações que nós podemos medir o nível de otimilidade de um algoritmo. Em relação à otimilidade de algoritmos Potros (2013, p. 3) nos orienta que “para um determinado problema, pode existir várias resoluções algorítmicas, então se faz necessário escolher o melhor” e acrescenta que “se a mesma medida de custo é aplicada a diferentes algoritmos, então é possível compará-los e escolher o mais adequado para resolver o problema”. Entre as várias maneiras a qual se pode medir o custo de utilização de um algoritmo Ziviani (1999, p. 4) nos mostra que a ”forma mais adequada de se medir o custo de utilização de um algoritmo é através do uso de um modelo matemático”, acrescenta que “o conjunto de operações a serem executadas deve ser especificado, assim como o custo associado com a execução de cada operação”. Desta forma, o modelo matemático indicado para medir o custo de execução de certo algoritmo refere-se ao uso de uma função de complexidade denominada f(n). A função de complexidade f(n) pode ser utilizada para a obtenção da métrica de tempo (medida do tempo de execução consumida, dado um conjunto de entrada de dados, que certo algoritmo requer para produzir uma resposta) ou da métrica de espaço (medida da quantidade de memória de computador que o algoritmo necessita para sua execução). Se a função de complexidade f(n) for usada para medir a quantidade do tempo necessário para executar certo algoritmo de tamanho n, então f é considerada como função de complexidade de tempo do algoritmo. Caso a função de complexidade f(n) seja usada para medir a quantidade da memória de computador necessária para executar um algoritmo de tamanho n, então f é chamada função de complexidade de espaço do algoritmo (ZIVIANI, 1999, p. 4). Podemos considerar como relações funcionais os aspetos: »»

Temporal: função de complexidade de tempo que tem por finalidade relacionar o tamanho da entrada com o tempo de execução: t = f(n)

»»

Espacial: função de complexidade de espaço que tem por finalidade relacionar o tamanho da entrada com o espaço de memória necessário para o armazenamento requerido: e = f(n)

Em termos práticos o fator de medida mais usado é a função de complexidade de tempo: t = f(n). Isso significa que essa função é normalmente calculada em primeira instância, ficando, a função de complexidade de espaço: e = f(n) em segunda instância. A escolha da função de complexidade a ser usada dependerá do tipo de métrica que se deseja avaliar para escolher o algoritmo de melhor otimilidade.

112

Algoritmos - Técnicas de Programação

Quando se fala em medidas de otimilidade de algoritmos (temporal ou espacial), podem ocorrer duas possibilidades de resultados, sendo: »

Melhor caso: quando o teste de medição efetuado mostra o tempo mais rápido para a execução do algoritmo ou o menor consumo de espaço em memória;

»

Pior caso: quando o teste de medição efetuado mostra o tempo mais longo para a execução do algoritmo ou o maior consumo de espaço em memória.

É importante considerar que o fato de um algoritmo ser mais rápido em sua execução que outro algoritmo não guarda este relação direta com o fator de consumo de espaço em memória. Assim, poderá ocorrer de um primeiro algoritmo ser executado mais rápido que um segundo algoritmo ocupando este mais espaço de memória que o segundo algoritmo. A escolha do melhor fator de medição de otimilidade de algoritmos (espacial e temporal) depende de certa análise, pois se a escolha é pelo algoritmo mais rápido usa-se a função de complexidade de tempo, se for obter o menor consumo de espaço em memória usa-se a função de complexidade espacial. Normalmente leva-se em consideração o tempo de execução (os programas necessitam ser rápidos), daí o fato de ser a função de complexidade de tempo a mais usada, mas há momentos em que a rapidez de processamento é mais irrelevante (rotinas de programas menos críticas) proporcionando o uso da medida de complexidade de espaço. Em termos práticos é difícil encontrar um ponto de equilíbrio entre as funções temporal e espacial, prevalecendo na mediação uma delas. As métricas de tempo e espaço podem ser usadas de duas maneiras: na forma abstrata e na forma concreta. Na forma abstrata (forma mais comum) faz-se a análise da complexidade dos algoritmos em papel, considerando-se o grau de inteligência usada para a solução do problema. Na forma concreta faz-se a análise da complexidade dos algoritmos em um computador real, onde se pode aferir o desempenho do algoritmo em tempo de execução de máquina. No entanto, o uso dessas métricas na esfera real dependerá de alguns fatores a serem fortemente considerados, tais como: quantidade de memória utilizada e disponível na máquina, tipo de sistema operacional usado, resultados dependem do tipo de compilador de linguagem utilizado, dependência da configuração de hardware, entre outras variáveis que podem interferir nas medições realizadas.

Exemplo Como exemplo de métrica de tempo de execução (a mais comum) em nível abstrato considere o uso dos algoritmos de pesquisa sequencial e binária para localizar em um vetor A de 1000 posições classificados em ordem crescente determinado valor pesquisado. Os valores do vetor A são compostos por números reais múltiplos de 10 iniciando-se em 10. Assim sendo, A[1] = 10, A[2] = 20, A[3] = 30, A[4] = 40, ..., A[1000] = 10000.

Medidas de Complexidade de Algoritmos

113

Exemplo Situação-problema O estudo do método de pesquisa sequencial foi apresentado no Capítulo 6. Apesar de eficaz (se determinado valor existir no vetor este é apresentado) o método não é muito eficiente, uma vez que para localizar, por exemplo, o elemento 10000 (pior caso) que se encontra na última posição do vetor necessitará percorrer um a um cada um dos elementos anteriores, ocorrendo assim um alto custo do tempo de processamento. Se certo elemento pesquisado não existir o algoritmo sequencial percorrerá todas as posições do vetor. Este algoritmo é eficiente se o elemento a ser pesquisado estiver na primeira posição do vetor, caso não esteja o método se torna vagaroso à medida que avança a cada posição do vetor. Em uma situação média de busca o elemento pesquisado é encontrado após n/2 comparações. A função de complexidade para métrica de tempo para a situação-problema exposta configura-se como t = f(1000). De forma hipotética, imagine que o ciclo de processamento para cada verificação (comparação, localização ou não do elemento) no vetor pesquisado seja executada em um segundo. Assim, para localizar o elemento 10000 ou responder que não há o elemento pesquisado no vetor o tempo gasto na operação será de 1000 segundos (aproximadamente 16,6 minutos). Um algoritmo de pesquisa bem mais eficiente é o método binário, baseado na ideia de divisão e conquista (padrão logarítmico), desde que o vetor a ser pesquisado esteja previamente ordenado. Neste algoritmo, o vetor é dividido em duas partes, a parte central é então comparada com o elemento pesquisado, se o elemento que estiver na posição central for o elemento pesquisado a busca é encerrada, se não for é verificada se a possibilidade de encontrar o elemento está na parte de cima ou na parte de baixo do vetor (considerando um vetor vertical). Se a probabilidade de encontrar o elemento pesquisado for a parte de baixo, o início é movimentado para a primeira posição após o meio da tabela. Se for a parte de cima o final da tabela é movimentado para a posição que antecede o meio. A partir desta sequência, faz-se a repetição deste algoritmo até localizar ou não o elemento pesquisado. Considerando-se a estrutura do vetor A o tempo médio de pesquisa na pior situação é em torno de 10 segundos. A função de complexidade para métrica de tempo para a um algoritmo de pesquisa binária configura-se como t = f(log2 1000). Se cada comparação leva o tempo de 1 segundo para ser realizada a localização do elemento 10000 no vetor ocorrerá em torno de apenas 10 segundos, pois log2 1000 é aproximadamente 9.96 (praticamente os 10 segundos indicados). O valor 9,96 é obtido a partir do cálculo do log de 1000 sobre log de 2 (log 1000 / log 2). Ao observar os relatos de funcionamento dos algoritmos de pesquisa nota-se que o de pesquisa binária é em média mais rápido que o sequencial possibilitando menor custo de processamento no tempo de execução de um computador. Considerando para esta análise a situação mais crítica de uso dos dois algoritmos. Atente para o trecho de processamento de pesquisa binária do diagrama de blocos da Figura 9.1 e na sequência o código completo do programa em português estruturado, observando o trecho em negrito correspondente a imagem da Figura 9.1. A operação de pesquisa binária se assemelha ao mesmo tipo de ação que usamos quando consultamos uma palavra em um dicionário para descobrirmos o seu significado.

114

Algoritmos - Técnicas de Programação

Exemplo Diagrama de blocos RESP

''SIM''

N RESP = ''SIM''

S PESQ

COMEÇO 1 FINAL 1000 ACHA .F.

COMEÇO <= FINAL .e. ACHA = F

N

S MEIO

(COMEÇO + FINAL) DIV 2

N

S PESQ = A [MEIO]

ACHA N

.V.

S PESQ < A [MEIO]

COMEÇO

MEIO + 1

FINAL

MEIO - 1

N

S ACHA = .V.

PESQ, ''foi localizado na posição'', MEIO

PESQ, ''não foi localizado''

RESP

Figura 9.1 - Exemplo de um algoritmo de pesquisa binária.

Medidas de Complexidade de Algoritmos

115

Português estruturado programa PESQUISA_BINÁRIA var

A : conjunto[1..1000] de real

I, J, COMEÇO, FINAL, MEIO : inteiro RESP : cadeia PESQ : real

ACHA : lógico

Início

A[1] ← 10 para I de 2 até 1000 o 1 faça A[I] ← A[I - 1] + 10

fim_para

RESP ← "SIM"

enquanto (RESP = "SIM") faça

escreva "Entre valor a ser pesquisado: " leia PESQ

COMEÇO ← 1

FINAL ← 1000

ACHA ← .Falso.

enquanto (COMEÇO <= FINAL) .e. (ACHA = .Falso.) faça MEIO ← (COMEÇO + FINAL) div 2 se (PESQ = A[MEIO]) então ACHA ← .Verdadeiro.

senão

se (PESQ < A[MEIO]) então FINAL ← MEIO - 1

senão

COMEÇO ← MEIO + 1

fim_se

fim_se

fim_enquanto

se (ACHA = .Verdadeiro.) então

escreva PESQ, " foi localizado na posição ", MEIO

senão

escreva PESQ, " não foi localizado"

fim_se

escreva "Deseja continuar? (SIM/NÃO): " leia RESP

fim_enquanto fim

116

Algoritmos - Técnicas de Programação

Exemplo No trecho em negrito, que corresponde ao diagrama de blocos da Figura 9.1 observe a condição (COMEÇO <= FINAL) .e. (ACHA = .Falso.) referente ao segundo laço da imagem, este laço é responsável por verificar se a pesquisa continua ou não. Na execução da pesquisa é efetuado o processamento do cálculo MEIO ← (COMEÇO + FINAL) div 2 que tem por finalidade encontrar o valor do meio do vetor. Após ter o valor da variável MEIO a condição PESQ = A[MEIO] verifica se o valor pesquisado (variável PESQ) está na posição A[MEIO] se a condição for verdadeira a variável ACHA é atribuída ao valor .Verdadeiro. e a pesquisa é encerrada. Caso a condição seja falsa o programa é desviado para a segunda decisão com a condição PESQ < A[MEIO] que faz a operação de divisão e conquista para a definição da pesquisa binária. Se a condição for verdadeira, ou seja, o valor pesquisado está acima da posição A[MEIO] o fim do vetor identificado pela variável FINAL é atualizado com o valor da variável MEIO menos 1. Se o resultado lógico da segunda condição for falso, ou seja, o valor pesquisado está abaixo da posição central, a variável COMEÇO será atribuída com o valor da variável MEIO mais 1. Uma curiosidade em relação à medida de otimilidade deste exemplo é que o método de pesquisa binário é sem dúvida, em média, mais rápido que o método de pesquisa sequencial em virtude da possibilidade que o método de pesquisa binária possui de evitar a percorrer uma parte desnecessária do vetor e por esta razão ele é mais eficiente. No sentido de agilizar as ações de pesquisa em um sistema deve o método de pesquisa binária ser mais utilizado. No entanto o custo de espaço em memória para gerenciá-lo é maior em razão da quantidade de variáveis em uso. O método de pesquisa sequencial usa as variáveis de apoio PESQ, RESP e ACHA, além das variáveis que representam o vetor e o o a cada posição do vetor. O método de pesquisa binária além das variáveis que representam o vetor e o o a posição de cada elemento no vetor e das variáveis PESQ, RESP e ACHA usa as variáveis COMEÇO, FINAL e MEIO consumindo, assim, mais memória de máquina. Note que, nesse caso, escolher o algoritmo pela quantidade de memória usada não é uma boa opção.

9.3 Busca de padrões em cadeias de caracteres O tratamento e manipulação de cadeias de caracteres (strings) é uma tarefa operacional muito requisitada nos sistemas computacionais. Tanto é verdade, que é muito comum as linguagens de programação formais para computadores fornecerem para seus programadores um extenso conjunto de funções com a finalidade de efetuar o tratamento dessa estrutura de dados. Um dos problemas mais comuns na manipulação de cadeias de caracteres é o de efetuar a busca de padrões de caracteres em determinada sequência de caracteres. A essa ação se dá o nome de busca de padrões em cadeias de caracteres. Para realizar o tratamento de strings, principalmente as operações de busca de padrões existem diversos algoritmos a disposição para este tipo de ação, destacando-se: Knuth-Morris-Pratt (KPM), Boyer-Moore, Rabin-Karp, Harrison, Força Bruta, entre outros.

Medidas de Complexidade de Algoritmos

117

Veremos, neste tópico, o método de busca de padrões em cadeias de caracteres por força bruta. O método por força bruta recebe essa denominação por usar a “força” de processamento dos computadores, em vez da inteligência do programador. Caracteriza-se por ser a forma mais simples de efetuar a ação pretendida e a forma mais trabalhosa de fazê-lo, não sendo o mais eficiente dos métodos existentes, mas adequado para a operação em sequências de caracteres pequenas (MOREIRA, 2012). O método de força bruta, também conhecido como método intuitivo tem por objetivo fazer uma operação de busca de um conjunto de caracteres (que chamamos de janela) dentro de uma sequência de caracteres definida (que chamamos de sentença). A busca inicia-se, preferivelmente, junto ao primeiro caractere da sentença e avança até o último caractere da sentença. Se a janela pesquisada existir este pode ser impresso à medida que é encontrado na sentença. Se a janela pesquisada não for encontrado nada deverá ser apresentado. A janela de pesquisa poderá ser formada por um ou mais caracteres a serem pesquisados em uma sentença. Para fazer uso deste algoritmo é necessário conhecer algumas definições operacionais: »»

o conjunto de caracteres, a sentença chamaremos de S que tem seu início na posição 1 e estendendo-se até o limite n, sendo representada pelo vetor S[1..n];

»»

a definição do conjunto de caracteres, a janela chamaremos de J iniciando-se na posição 1 e estendendo-se até o limite m, sendo representada pelo vetor J[1..m];

»»

o algoritmo de força bruta para ser operado deve considerar o fato do valor limite m ser menor ou igual ao valor do limite n.

Para fazermos a demonstração neste tópico do uso da ação de busca de padrões de caracteres precisamos levar em consideração um detalhe muito importante, a linguagem de projeto de programação, português estruturado, não possui internamente um conjunto de funções para realizar tarefas específicas, como é o caso da manipulação de certa sequência de caracteres. Assim sendo, essas operações devem ser definidas logicamente e para não ficar em uma esfera abstrata vamos construir manualmente a lógica de toda ação do programa que será exemplificado. Para realizar as operação nas estruturas S[1..n] e J[1..n] necessitaremos de uma função que efetue o cálculo do tamanho dessas sequências de caracteres. Todas as linguagens de programação possuem uma função do tipo length (comprimento) que retorna o tamanho em caracteres de um string (cadeia de caracteres). A linguagem português estruturado não possui essa e outras funções internas pelo fato de ser uma linguagem de documentação de código, mas nada impede de que façamos a implementação desta funcionalidade desde que tenhamos o cuidado de usar nas sequências de caracteres manipuladas pela função tamanho() um caractere de finalização, neste caso, será usado um ponto final para que o algoritmo de cálculo de tamanho do string saiba o ponto onde parar a execução do programa. Assim, para a linguagem de programação português estruturado fica definida a função do tipo interna tamanho() que retornará a quantidade de caracteres de uma sequência de caracteres finalizada com um ponto final fornecida como seu parâmetro. Para tanto, observe a Figura 9.2 que mostra o diagrama de blocos da função e seu código em português estruturado definidos a seguir.

118

Algoritmos - Técnicas de Programação

Diagrama de blocos

Português estruturado função TAMANHO(TEXTO : cadeia) : inteiro

Tamanho (texto)

var I

I : inteiro

1

T : cadeia

T

início

Texto + ''.''

I ← 1 T ← TEXTO + "."

N T[I] <> ''.''

I

enquanto (T[I] <> ".") faça

S

I ← I + 1

I+1

fim_enquanto TAMANHO ← I - 1

Tamanho

fim

I-1

Retorna tamanho

Figura 9.2 - Função interna tamanho().

A partir da definição da função tamanho() para a linguagem português estruturado fica fácil implementar um programa que localize certa janela de caracteres em uma sentença definida pelo método de força bruta.

Exemplo Como exemplo de busca de padrões em uma sequência de caracteres considere um programa que efetue a busca de uma janela em uma sentença pelo método da força bruta e retorne como resultado de sua operação as posições iniciais onde os padrões de caracteres ocorrem na sentença. A sentença será “YCTABWATAB” e a janela a ser pesquisada será “AB”. Observe a seguir a disposição do conteúdo da sentença em cada uma das posições do vetor que faz parte com certa sequência de caracteres. Sentença 1

2

3

4

5

6

7

8

9

10

Y

C

T

A

B

W

A

T

A

B

A seguir, é mostrada a janela com a sequência de caracteres a ser pesquisada. Janela A

Medidas de Complexidade de Algoritmos

B

119

Ao fazer vista no conteúdo da janela podemos perceber que a sequência AB se encontra a partir das posições 4 e 9 do vetor onde a sentença se encontra definida. O programa em questão deverá testar a janela fornecida em todas as posições da sentença, posição por posição a partir do início da sentença. Assim sendo, tentaremos “casar” o conteúdo da janela dentro da extensão da sentença, Caso os caracteres indicados na janela sejam iguais aos que estão na sentença ocorrerá a apresentação a partir de que posição os caracteres da janela se encontram na sentença. Se os caracteres da janela forem diferentes dos caracteres da sentença, paramos a comparação e deslocamos a frente da janela para a próxima posição da sentença e é iniciada a ação de busca novamente até que se chegue ao fim da sentença. Observe a seguir a Figura 9.3 com o algoritmo de força bruta implementado e seu respectivo código em português estruturado.

Diagrama de blocos

Português estruturado programa FORÇA_BRUTA

INÍCIO

FRASE JANELA

N M

var

FRASE, JANELA : cadeia

''YCTABWATAB'' ''AB''

N, M, I, J : inteiro

início

TAMANHO (FRASE) TAMANHO (JANELA)

FRASE ← "YCTABWATAB" I

JANELA ← "AB"

1, N - M + 1, 1

J

N ← tamanho(FRASE)

O

M ← tamanho(JANELA) J<M .E. FRASE [I + J] = JANELA [I + 1]

N

para I de 1 até N – M + 1 o 1 faça J ← 0

J

enquanto (J < M) .e. (FRASE[I + J] = JANELA [I + 1]) faça

J+1

N

J ← J + 1

fim_enquanto

S J=M

se (J = M) então escreva I

I

fim_se

fim_para FIM

Figura 9.3 - Diagrama para busca de padrões de caracteres.

120

fim

Algoritmos - Técnicas de Programação

As instruções N ← tamanho(FRASE) e M ← tamanho(JANELA) fazem uso da função tamanho() definida na Figura 9.2. Ao ser verificada a execução do programa por meio de um teste de mesa obter-se-á como resultado da ação da execução da instrução escreva I a apresentação dos valores 4 e 9 referentes às posições iniciais onde a janela AB ocorre na sentença FRASE.

9.4 Fundamentos de retrocesso Um algoritmo de retrocesso (backtraking) é um mecanismo de ação em profundidade que visa verificar de maneira exaustiva todas as possibilidades de solução de certo problema. Um mecanismo de backtraking bem popular e comum é o uso de funções recursivas. Uma função recursiva é uma função que faz chamadas a si mesma. O uso de recursividade proporciona a escrita de um código mais elegante com alto grau de abstração.

Exemplo Como exemplo de recursividade considere uma função que calcule o valor do fatorial de um número inteiro qualquer N.

Diagrama de blocos FATORIAL (N)

Início

N

S N <= 1

LIMITE

FATORIAL

FATORIAL (N - 1)

X

N

FATORIAL

1

FATORIAL (LIMITE)

Fim

RETORNA FATORIAL

Figura 9.4 - Diagramas de blocos com função FATORIAL recursiva.

Medidas de Complexidade de Algoritmos

121

Português estruturado programa CALC_FAT função FATORIAL(N : inteiro) : inteiro início

se (N <= 1) então FATORIAL ← 1 senão FATORIAL ← FATORIAL(N - 1) * N fim_se

fim var

LIMITE : inteiro

início

escreva "Qual fatorial: " leia LIMITE escreva FATORIAL(LIMITE)

fim

Ao observar a função recursiva FATORIAL() do algoritmo de programa CALC_FAT, nota-se dentro do bloco adjacente para condição N <= 1 (falsa) a operação de cálculo matemático FATORIAL ← fatorial(N − 1) * N, em que FATORIAL é atribuído pelo resultado da operação FATORIAL(N − 1) * N. O parâmetro N determina o número de vezes que a operação deve ser efetuada e fatorial(N − 1) é uma nova instância de chamada da função a si mesma com o valor do parâmetro N menos 1. Imagine a função recursiva FATORIAL() receber como agem de parâmetro por valor o 5. Neste caso, o resultado dessa operação será 120. Para chegar a esse resultado, são necessários os seguintes os: 1)

Ao ar o conteúdo 5 para a função recursiva FATORIAL() e pelo fato de esse valor não ser menor ou igual a 1, será efetuada a operação FATORIAL ← FATORIAL(N − 1) * N. Neste caso, FATORIAL ← FATORIAL(4) * 5, sendo o valor 5 armazenado na pilha de memória.

2)

Em seguida, o conteúdo 4 obtido a partir de 5 − 1, não sendo um valor menor ou igual a 1, é ado à função recursiva FATORIAL() que efetua a operação FATORIAL ← FATORIAL(N − 1) * N. Neste caso, FATORIAL ← FATORIAL(3) * 4, sendo o valor 4 armazenado na pilha de memória.

122

Algoritmos - Técnicas de Programação

3)

O conteúdo 3 obtido a partir de 4 − 1, não sendo um valor menor ou igual a 1, é ado à função recursiva FATORIAL() que efetua a operação FATORIAL ← FATORIAL(N − 1) * N. Neste caso, FATORIAL ← FATORIAL(2) * 3, sendo o valor 3 armazenado na pilha de memória.

4)

Depois, o conteúdo 2 obtido a partir de 3 − 1, não sendo um valor menor ou igual a 1, é ado à função recursiva FATORIAL() que efetua a operação FATORIAL ← FATORIAL(N − 1) * N. Neste caso, FATORIAL ← FATORIAL(1) * 2, sendo o valor 2 armazenado na pilha de memória.

5)

Por último, o conteúdo 1 obtido a partir de 2 − 1 é menor ou igual a 1 e, por esta razão, é atribuído à variável FATORIAL o valor 1. Neste caso, a função recursiva FATORIAL() retorna o valor 1 e multiplica-o pelo valor 2 armazenado na pilha, obtendo o resultado 2 que é então retornado pela própria função recursiva FATORIAL(). Neste caso o valor 1 é destruído na memória, permanecendo em memória apenas o valor 2.

6)

Na sequência, o valor 2 retornado é multiplicado pelo valor empilhado 3, obtendo o valor 6 que é então retornado pela função recursiva FATORIAL() e o valor 2 é destruído da memória, permanecendo em memória apenas o valor 6.

7)

Após o retorno, o valor 6 é multiplicado pelo valor empilhado 4, obtendo o valor 24 que é então retornado pela função recursiva FATORIAL() e o valor 6 é destruído da memória, permanecendo em memória apenas o valor 24.

8)

Por último, o valor 24 é multiplicado pelo valor empilhado 5, obtendo o valor 120 que é então retornado pela função recursiva FATORIAL() e o valor 24 é destruído da memória, permanecendo em memória apenas o valor 120.

Após a obtenção do valor 120, chega-se à quinta e última etapa do empilhamento dos valores calculados, em virtude da agem de parâmetro de valor do conteúdo 5 para a função FATORIAL(5). Neste caso, ocorre o encerramento da função e o retorno do valor 120 para o trecho do programa que efetuou a chamada da função. A Figura 9.5 demonstra graficamente a lógica de funcionalidade e de ação e mostra como funciona uma função recursiva (backtraking). Cada instância de chamada da função recursiva FATORIAL() ocorre de forma a empilhar cada uma das instâncias da função em operação para depois, no retorno, efetuar a multiplicação sucessiva típica do valor retornado com o valor armazenado na pilha, a fim de calcular a fatorial solicitada.

Medidas de Complexidade de Algoritmos

FATORIAL (5) FATORIAL (5 - 1) * 5 FATORIAL (4 - 1) * 4 FATORIAL (3 - 1) * 3 FATORIAL (2 - 1) * 2 FATORIAL (1 - 1) * 1

FATORIAL

1

RETORNA 1 RETORNA 2 * 1 RETORNA 3 * 2 RETORNA 4 * 6 RETORNA 5 * 24 RETORNA 120

Figura 9.5 - Esquema lógico de funcionalidade e ação de função recursiva. (MANZANO; FIGUEIREDO, 2012)

123

A Figura 9.6 apresenta outra perspectiva do processamento da função recursiva FATORIAL(). 5! FATORIAL

FATORIAL (N - 1) * N

4! * 5 FATORIAL

24 * 5

120

6*4

24

2*3

6

1*2

2

1*1

1

FATORIAL (N - 1) * N

3! * 4 FATORIAL

FATORIAL (N - 1) * N

2! * 3 FATORIAL

FATORIAL (N - 1) * N

1! * 2 FATORIAL

FATORIAL (N - 1) * N

0! * 1

Valores retornados da ação recursiva. Ação de desempilhamento.

Processamento de execuções recursivas. Ação de empilhamento.

FATORIAL (N)

Figura 9.6 - Perspectiva de função recursiva. (MANZANO; FIGUEIREDO, 2012)

O processo de recursividade (backtraking) é considerado elegante, pois facilita a abstração e a modularidade na criação de funções que podem ser complexas. No entanto, devido ao efeito de empilhamento, essa estratégia pode consumir grande espaço de memória.

Amplie seus conhecimentos Sobre ações de uso de backtraking pesquise os algoritmos relacionados aos problemas: da mochila, do labirinto, das oito rainhas e do eio do cavalo.

Vamos recapitular? São descritas no capítulo as ações conceituais do uso da análise e complexidade de algoritmos. Foram apresentados em linhas gerais e de forma teórica, sem aprofundamento técnico, temas sobre: análise de algoritmos, otimalidade de algoritmos - métricas de tempo e de espaço -, algoritmos de busca de padrões em cadeias de caracteres e algoritmos de retrocesso (backtracking).

Agora é com você!

124

1)

Qual é o objetivo da disciplina Análise de Algoritmos?

2)

O que deve ser analisado pelo programador de computador após um problema ser examinado e as decisões sobre o projeto serem tomadas?

3)

Em que consiste a busca de padrões em cadeias de caracteres?

4)

O que é uma função recursiva?

Algoritmos - Técnicas de Programação

Bibliografia ALCALDE, E.; GARCIA, M.; PENUELAS, S. Informática básica. São Paulo: Makron, 1991. ALMEIDA, C. Técnicas de Linguagem de Programação. Portugal: Escola Secundária de Emídio Navarro, 2000. Disponível em: . o em: 19 dez. 2013. ALVAREZ, B.; ESMERALDA, M. Organização, Sistemas e Métodos. São Paulo: Makron, 1991. AZEREDO, P. A. Métodos de Classificação de Dados e Análise de suas Complexidades. Rio de Janeiro: Campus, 1996. BATISTA, L. Elementos de Programação. São Paulo: Edgard Blücher, 1983. BELLIS, M. Fortran: The First Successful High Level Programming Language. About.com Inventors, Disponível em: . o em: 12 nov. 2013. BERG, A. C.; FIGUEIRÓ, J. P. Lógica de Programação. Editora ULBRA, Rio Grande do Sul: Editora ULBRA, 1998. BIO. Ada Augusta. Bio. True History. Disponível em: . o em: 12 nov. 2013 BOUTE, R. T. The Euclidean definition of the functions div and mod. ACM Transactions on Programming Languages and Systems (TOPLAS). v. 14, p. 127-144, 2 abr. 1992. CAINE, S.; GORDON, K. PDL: A Tool for Software Design. Proc. National Computer Conference, AFIPS Press, 1975. CHAPIN, N. A New Format for Flowcharts. Software - Practice and Experience, v. 4, n. 4, 1974. CLAUDINO, R. Análise de Algoritmos. Minas Gerais: Universidade Federal de Itajubá, 2013. Disponível em: < https://sites.google.com/site/analgorit/ccf140-12>. o em: 19 dez. 2013. CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L.; STEIN, C. Algoritmos: teoria e prática. Tradução da segunda edição americana. Tradutor: Vandenberg D. de Souza. Rio de Janeiro: Elsevier, 2002. DAHL, O. J.; et al. Structured Programming. Academic Press, 1972. DIVERIO, T. A.; MENEZES, P. B. Teoria da computação: máquinas universais e computabilidade. 3. ed. Porto Alegre: Bookman, 2011. v. 5. (Série Livros Didáticos - Instituto de Informática UFRGS). FARRER, H. Algoritmos Estruturados. Guanabara, 1986. FEOFILOFF, P. Algoritmos em linguagem C. Rio de Janeiro: Elsevier, 2008. FEOFILOFF, P. Minicurso de Análise de Algoritmos. São Paulo: Universidade de São Paulo, 2013. Disponível em: . o em: 19 dez. 2013.

Bibliografia

125

FORBELLONE, A. L. V.; EBERSPÄCHER, H. F. Lógica de programação: A construção de Algoritmos e Estruturas de Dados. São Paulo: Makron, 2000. GUIMARÃES, A. M.; LAGES, N. A. C. Algoritmos e Estruturas de Dados. Rio de Janeiro: LTC, 1994. HOUAISS, A. Dicionário Eletrônico Houaiss da Língua Portuguesa: Versão 2.0a. Brasil: Instituto Antônio Houaiss/Editora Objetiva, 2007. KNUTH, D. E. The Art of Computer Programming: Fundamental Algorithms. Massachusetts: Addison-Wesley, vol 1, 1972. LEIJEN, D. Division and Modulus for Computer Scientists. 2001. Disponível em: . o em: 6 dez. 2013. LOUREIRO, A. A. F. Algoritmos e Estruturas de Dados II – Introdução. Belo Horizonte: Universidade Federal de Minas Gerais, 2005. Disponível em: . o em: 19 dez. 2013. MANZANO, J. A. N. G.; FIGUEIREDO, J. Algoritmos: Lógica para Desenvolvimento de Programação de Computadores. São Paulo: Érica, 2012. MARTIN, J. Técnicas Estruturadas e Case. São Paulo: Makron, 1991. MATOS, A. Tópicos Avançados de Algoritmos. Portugal: Universidade do Porto, 2008. Disponível em: . o em: 18 dez. 2013. MOREIRA, G de A. Algoritmos para Busca de Padrões: uma análise empírica. São Paulo: Faculdade de Tecnologia de São Paulo, 2012. Disponível em: . o em: 22 de dez. de 2013. NASSI, I.; SHNEIDERMAN, B. Flowchart Techiques for Structured Programming. SIGPLAN Notices, ACM, 1973. PACIEVITCH, Y. Lógica de Programação. Nov. 2013. Disponível em: . o em: 11 nov. 2013. POTROS, J. de P. Medida do Tempo de Execução. Minas Gerais: IF Sudeste de MG, 2013. Disponível em: . o em: 20 dez. 2013. PRESSMAN, R. S. Engenharia de Software. São Paulo: Makron, 1995. PRESTES, E. Complexidade de Algoritmos. Rio Grande do Sul: Universidade Federal do Rio Grande do Sul, 2011. Disponível em: o em: 18 dez. 2013. PRICE, A. M. A.; TOSCANI, S. S. Implementação de Linguagens de Programação: compiladores. 3. ed. Porto Alegre: Bookman, 2008. PRINCETON. ALGOL. Princeton University. Disponível em: . o em: 12 nov. 2013

126

Algoritmos - Técnicas de Programação

SALIBA, W. L. C. Técnica de Programação: Uma Abordagem Estruturada. São Paulo: Makron, 1993. SCIENCE MUSEUM. The Babbage Engine. Computer History Museum. Disponível em: . o em: 12 nov. 2013. SEBESTA, R. W. Conceitos de Linguagens de Programação. 5. ed. Rio Grande do Sul: Bookman, 2003. SIMCSIK, T. OMIS: Organização, Métodos, Informação, Sistemas. São Paulo: Makron, 1992. SZWARCFITER, J. L.; MARKENZON, L. Estruturas de Dados e seus Algoritmos. Editora LTC, Rio de Janeiro: Editora LTC, 1994. TOFFOLO, T. Análise de Algoritmos. Minas Gerais: universidade Federal de Ouro Preto, 2012. Disponível em: . o em: 19 dez. 2013. VENANCIO, C. F. Desenvolvimento de Algoritmos: Uma Nova Abordagem. São Paulo: Érica, 1998. VERZELLO, R. J. Processamento de Dados. São Paulo: McGraw-Hill, 1984. WEBER, R. F. Fundamentos de Arquitetura de Computadores. 3. ed. Porto Alegre: Instituto de Informática UFRGS: Editora Sagra Luzzato, 2004. WIRTH, N. Algoritmos e Estruturas de Dados. São Paulo: Prentice-Hall, 1989. ZIVIANI, N. Projeto de Algoritmos com Implementação em Pascal e C. 4. ed. São Paulo: Pioneira, 1999.

Bibliografia

127

Marcas Registradas Todos os nomes registrados, marcas registradas ou direitos de uso citados neste livro pertencem aos seus respectivos proprietários.

128

Algoritmos - Técnicas de Programação