Livro Algoritmo - Universidade Positivo - Ciência da computação, Manuais, Projetos, Pesquisas de Matemática

Baixe Livro Algoritmo - Universidade Positivo - Ciência da computação e outras Manuais, Projetos, Pesquisas em PDF para Matemática, somente na Docsity! Pedro Kantek Algoritmos UP Jul/07, dez/07 Curitiba 1versão de 23 de janeiro de 2009 ©88-09, Pedro Kantek ©88-09, Pedro Kantek versão de 23 de janeiro de 20092 Caṕıtulo 1 Contrato Pedagógico Regras da disciplina Uma aula dupla tem 100 minutos, que serão – em prinćıpio – assim divididos: 10 minutos para os bons dias, 30 minutos de teoria, 30 de apresentação do exerćıcio prático e mais 30 minutos para os alunos fazerem o seu exerćıcio. Cada aluno vai receber um exerćıcio individual e único. O exerćıcio deverá ser devolvido feito até a data escrita na própria folha do exerćıcio. Se entregue atrasado pagará 50% da nota de multa. Em outras palavras, a nota do exerćıcio será dividida por 2. Não haverá segunda chamada de exerćıcios perdidos. Não serão aceitos xerox, fax ou e-mail de exerćıcios. Apenas o exerćıcio original que contiver o nome do aluno será aceito. Se o aluno quiser (alguns querem), tire cópia xerox do exerćıcio para guardar a coleção deles. Entretanto, todo exerćıcio entregue ao professor será corrigido e devolvido ao aluno. A nota bimestral será obtida fazendo a média aritmética dos exerćıcios do bimestre, com peso de 60% e a prova bimestral, esta com peso 40%. As provas também são individuais e diferentes para cada aluno. Bibliografia para Algoritmos SKI97 SKIENA, Steven S. - The Algorithm Design Manual. New York, Springer. 1997. 486p. (Localizador UP: 005.12 S628a) SKI03 SKIENA, Steven S e REVILLA, Miguel A. Programming Challenges. New York, Springer. 2003. 361p. (Localizador UP: 005.1 S628p) FOR05 FORBELLONE, A. L. V. e EBERSPÄCHER, H. F. - Lógica de Programação. São Paulo. 2005. 214p. FAR85 FARRER, Harry et all. Algoritmos estruturados. Rio de Janeiro, Guanabara, 1985. 241p. (Programação estruturada de computadores). FOR72 FORSYTHE, Alexandra I. et all. Ciência de Computadores - 1. curso. Volume 1. Rio de Janeiro, Ao Livro Técnico. 1972. 234p. FOR72b FORSYTHE, Alexandra I. et all. Ciência de Computadores - 1. curso. Vo- lume 2. Rio de Janeiro, Ao Livro Técnico. 1972. 560p. GUI75 GUIMARÃES, Ângelo de Moura & LAGES, Newton Alberto de Castilho. Al- goritmos e estruturas de dados. Rio de Janeiro, LTC, 1975. 216p. 5 CAPÍTULO 1. CONTRATO PEDAGÓGICO KNU71 KNUTH, Donald E. The Art of Computer Programming. Volumes 1 e 2. Reading, Massachussets, Addison Wesley Publishing Company, 1971, 624p. SIL90 SILVA PINTO, Wilson. Introdução ao desenvolvimento de algoritmos e estru- turas de dados. São Paulo, ÉRICA, 1990, 201p. WIR89 WIRTH, Niklaus. Algoritmos e estruturas de dados. Rio de Janeiro, Prentice- Hall do Brasil, 1989, 245p. Kao08 KAO, Ming-Yang. (ed.) Encyclopedia of Algorithms. Springer. 2008. New York. 1200p. ©88-09, Pedro Kantek versão de 23 de janeiro de 20096 CAPÍTULO 1. CONTRATO PEDAGÓGICO O autor, pelo autor Meu nome é Pedro Luis Kantek Garcia Navarro, conhecido como Kantek, ou Pedro Kantek. Nasci em Curitiba há mais de 50 anos. Sou portanto brasileiro, curitibano e coxa-branca com muito orgulho, mas sendo filho de espanhóis (meus 7 irmãos nasceram lá), tenho também a nacionalidade espanhola. Aprendi a falar em castellano, o portu- guês é portanto meu segundo idioma. Estudei no Colégio Bom Jesus e quando chegou a hora de escolher a profissão, lá por 1972, fui para a engenharia civil, mas sem muita convicção. Durante a copa do mundo de futebol de 1974 na Alemanha, ao folhear a Gazeta do Povo, achei um pequeno anúncio sobre um estágio na área de processamento de dados (os nomes informática e computação ainda não existiam). Lá fui eu para um estágio na CELEPAR, que hoje, mais de 30 anos após, ainda não acabou. Na CELE- PAR já fui de tudo: programador, analista, suporte a BD (banco de dados), suporte a TP (teleprocessamento), coordenador de auto-serviço, coordenador de atendimento, ... Atualmente estou na área de governo eletrônico. Desde cedo encasquetei que uma boa maneira de me obrigar a continuar estudando a vida toda era virar professor. Comecei essa desafiante carreira em 1976, dando aula num lugar chamado UUTT, que não existe mais. Passei por FAE, PUC e cheguei às Faculdades Positivo em 1988. Sou o decano do curso de informática e um dos mais antigos professores da casa. Na década de 80, virei instrutor itinerante de uma empresa chamada CTIS de Braśılia, e dei um monte de cursos por este Brasil afora (Manaus, Recife, Braśılia, Rio, São Paulo, Fortaleza, Floripa, ...). Em 90, resolvi voltar a estudar e fui fazer o mestrado em informática in- dustrial no CEFET. Ainda peguei a última leva dos professores franceses que iniciaram o curso. Em 93 virei mestre, e a minha dissertação foi publicada em livro pela editora Campus (Downsizing de sistemas de Informação. Rio de Janeiro: Campus, 1994. 240p, ISBN:85-7001-926-2). O primeiro cheque dos direitos autorais me manteve um mês em Nova Iorque, estudando inglês. Aliás, foi o quarto livro de minha carreira de escritor, antes já havia 3 outros (MS WORD - Guia do Usuário Brasileiro. Rio de Janeiro: Cam- pus, 1987. 250p, ISBN:85-7001-507-0, Centro de Informações. Rio de Janeiro: Campus, 1985. 103p, ISBN:85-7001-383-3 e APL - Uma linguagem de programação. Curitiba. CELEPAR, 1982. 222p). Depois vieram outros. Terminando o mestrado, rapidamente para não perder o fôlego, engatei o doutorado em engenharia elétrica. Ele se iniciou em 1994 na UFSC em Florianópolis. Só terminou em 2000, foram 6 anos inesquećıveis, até porque nesse meio tive que aprender o francês - mais um mês em Paris aprendendo-o. Finalmente virei engenheiro, 25 anos depois de ter iniciado a engenharia civil. Esqueci de dizer que no meio do curso de Civil desist́ı (cá pra nós o assunto era meio chato...) em favor de algo muito mais emocionante: matemática. Nessa época ainda não havia cursos superiores de informática. Formei-me em matemática na PUC/Pr em 1981. Em 2003, habilitei-me a avaliador de cursos para o MEC. Para minha surpresa, fui selecionado e virei delegado do INEP (Instituto Nacional de Pesquisas Educacionais) do Governo Brasileiro. De novo, visitei lugares deste Brasilzão que sequer imaginava existirem (por exemplo, Rondonópolis, Luiziânia, Rio Grande, entre outros), sempre avaliando os cur- sos na área de informática: sistemas de informação, engenharia e ciência da computação. Atualmente estou licenciado da PUC e na UP respondo por 4 cadeiras: Algoritmos (1. ano de sistemas de informação), Estrutura de Dados (2.ano, idem) e Tópicos Avançados em Sistemas de Informação (4.ano, idem), além de Inteligência Artificial (último ano de Engenharia da Computação). Já fiz um bocado de coisas na vida, mas acho que um dos meus sonhos é um dia ser professor de matemática para crianças: tentar despertá-las para este mundo fantástico, do qual – lastimavelmente – boa parte delas nunca chega sequer perto ao longo de sua vida. 7versão de 23 de janeiro de 2009 ©88-09, Pedro Kantek CAPÍTULO 2. CIÊNCIA DA COMPUTAÇÃO 5. Com a fala, os dois sujeitos tem que estar tête-à-tête. A seguir, surge a escrita. Agora a comunicação é posśıvel na modalidade um-muitos (Antes era um-um) e mesmo um cérebro morto pode se comunicar pela escrita. 6. Enquanto a escrita é manuscrita, está naturalmente limitada. A próxima novidade é a imprensa que ao automatizar a produção de textos, amplia significativamente o acesso e a disseminação de informações. 7. Finalmente, o último estágio da ampliação do conhecimento reside no software. Hoje, 23 milhões de brasileiros sabem declarar seu IR, sem precisar fazer um exaustivo aprendizado sobre as regras da declaração, graças a um... software. O nome é inteligência extrassomática. Durante o século XX a maior indústria foi a do petróleo. Depois, a do automóvel e finalmente no final do século, a indústria de computadores passou a ser a maior. A tendência para o futuro é de que ela suplante todas as demais. Hoje o homem mais rico do mundo construiu a sua fortuna vendendo um software. O computador nasce na cabeça de um cientista inglês (Alan Matheson Turing em 1937) e é constrúıdo para a guerra pelos ingleses em 1942. A seqüência de escopo do computador é guerra a idéia aqui é usar o computador como otimizador dos recursos bélicos, cripto- grafia, pesquisa operacional, tabelas baĺısticas...→ aritmética o computador se transforma em super-calculadora. A matemática passa a ser a linguagem da informática, por excelência. O FORTRAN é dessa época... → negócios em plena sociedade capitalista, os negócios passam a ser otimizados pelo computador. Dessa época é o COBOL a linguagem representante... → aldeia global Negócios, governos, universidades e organizações sociais passam a com- partilhar o ciberespaço. Surge e se robustece a Internet... → lazer o computador vira um eletrodoméstico. As casas de classe média passam a contar com um (ou mais de um) computador. Jogos, música, filmes, e-mule, mp3, ... → ... → realidade virtual Não se sabe direito o que virá por aqui. As técnicas de simulação levadas ao paroxismo permitirão criar realidades virtuais, com toda a contradição exposta no t́ıtulo. Talvez retornemos à dúvida de Platão (o universo existe ou é apenas uma sensação que eu tenho? ). O computador se diferencia de qualquer outra máquina pela sua generalidade. No texto original de Turing isto fica claro pela conceituação de uma máquina universal. Assim, diferentemente de um liquidificador (que só serve para picar comida e tem ape- nas um botão de liga-desliga), um computador precisa – antes de qualquer coisa – ser programado para fazer algo. De fato, se comprar um computador vazio e ligá-lo, ele não vai fazer nada. Tecnicamente, chama-se a parte f́ısica do computador de hardware significando ferragem, duro (hard), componente f́ısico, etc. Já a programação recebe o nome de software significando mole (soft em oposição a hard), componente lógico, não f́ısico, programa de computador. A fabricação de hardware é engenharia. Sua produção pode ser planejada e otimizada e isso de fato é feito. A fabricação de software, a despeito de ser chamada de engenharia, cá entre nós, não o é muito. Está mais para arte do que para engenharia. ©88-09, Pedro Kantek versão de 23 de janeiro de 200910 CAPÍTULO 2. CIÊNCIA DA COMPUTAÇÃO Talvez, como seres humanos, devamos dar graças aos céus por esta situação. Pois en- quanto a produção de hardware é (ou pode ser) em grande parte robotizada, a produção de software ainda exige um bom cérebro cinzento por trás. As restrições que ainda existem sobre o software e que talvez nunca deixem de existir, impedem a programação dos computadores em linguagem natural. Hoje ainda não é posśıvel dialogar com um computador como se fala com uma pessoa medianamente inteligente. Os computadores ainda não conseguem tal proeza. Para programar um computador necessitamos uma linguagem. O hardware só en- tende uma linguagem de pulsos elétricos (chamada de linguagem de máquina). Para facilitar a nossa vida (já que é muito dificil para o homem programar nela), criaram-se programas tradutores que recebem comandos e dados em uma linguagem artificial e a convertem em linguagem de máquina. A maioria desses tradutores recebeu o mesmo nome da linguagem que eles traduzem. Assim, temos o Java, o Cobol, Pascal, Apl, Clipper, Dbase, Basic, Natural, Fortran, C, Php, Lisp, Prolog, Modula, entre outras. Veja no śıtio www.tiobe.com o ı́ndice TPC que mensalmente lista as 100 linguagens mais usadas no mundo. Quando os primeiros computadores foram construidos, a única linguagem por eles entendida era a binária. Seqüências intermináveis de uns e zeros, algo assim como 0 0 1 0 1 0 0 0 1 0 1 0 1 0 1 1 1 0 1 0 1 1 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 1 0 1. Era um autêntico samba do crioulo doido. Chamou-se a isto, mais tarde, linguagem de primeira geração. A seguir, o primeiro melhoramento: o assembler (ou montador), programa que era capaz de entender instruções escritas em uma linguagem um pouco mais humana, e traduzir cada uma destas instruções em sua expressão binária equivalente. Junto com este programa criou-se a primeira linguagem digna deste nome: o assembler, até hoje usado, se bem que muito raramente. Programar em assembler ainda exige muito talento e paciência. A máquina precisa ser conhecida em inúmeros detalhes de construção, os programas são longos e dif́ıceis (principalmente sua manutenção). Entretanto esta é a linguagem mais eficiente do ponto de vista dos consumo dos recursos da máquina, isto é, ela gera programas velozes e pequenos. Depois, vieram as linguagens de terceira geração: a primeira foi o FORTRAN, de- pois COBOL, PL/I, PASCAL, C, C++, Java, LISP, Prolog e outras menos votadas: BASIC, ADA, APL. Há um distanciamento do programador em relação à máquina, e uma aproximação do mesmo em relação ao problema a resolver. Estas linguagens são mais fáceis de aprender e embora gerem programas maiores e mais lentos, aumentam em muito a produtividade humana de escrever código de programação. Um exemplo diferente para mostrar todos estes conceitos de linguagens poderia ser o seguinte: Suponha um engenheiro brasileiro, que só conhece o idioma português. Ele precisa transmitir certas ordens de fabricação para um colega soviético, que só conhece o idioma russo, com escrita ciŕılica. Os dois podem tentar conversar quanto quiserem, mas provavelmente não haver nenhum resultado prático útil. É necessária a presença de um tradutor, alguém que ouvindo o português consiga transformar as ordens em suas equivalentes russas. Finalmente, o engenheiro brasileiro verá se as ordens foram corretamente traduzidas e executadas analisando o resultado final do trabalho. Neste exemplo, o engenheiro brasileiro é o programador. O colega soviético é a máquina (que ao invés de russo, só entende a linguagem elétrica). O tradutor é a linguagem de programação. Podemos ainda estabelecer dois ńıveis para linguagens de programação: baixo e alto. Linguagem de baixo ńıvel é aquela que requer a especificação completa do problema nos seus mı́nimos detalhes. No nosso exemplo, equivaleria ao engenheiro brasileiro des- crevendo tin-tin por tin-tin todos os passos para montar uma engenhoca qualquer. Já as linguagens de alto ńıvel, pressupõe uma tradução ”inteligente”, o que libera o enge- 11versão de 23 de janeiro de 2009 ©88-09, Pedro Kantek CAPÍTULO 2. CIÊNCIA DA COMPUTAÇÃO nheiro brasileiro de informar todas as etapas. Ele diz o que deve ser feito, sem precisar estabelecer como isto vai ser realizado. Todas as linguagens compartilham uma estrutura parecida, já que rodam todas no mesmo computador que é constrúıdo usando a chamada Arquitetura de Von Neumann. Bem resumido, essa arquitetura prevê a existência da memória, de uma unidade aritmé- tico lógica, canais e o elemento ativo: a unidade de controle. Essa estrutura comporta os seguintes tipos de comandos (ordens): entrada-sáıda de dados, aritmética, movimen- tação em memória, condicional e desvio. Com apenas essas 5 ordens, são constrúıdos todos os programas que existem ou que existirão em nosso mundo usando este tipo de computador. Uma pergunta que se pode fazer aqui, é se é melhor aprender tudo de uma linguagem e se tornar um especialista nela, ou se é melhor conhecer várias, ainda que não chegando a muita profundidade em nenhuma. Não há resposta fácil, mas apostar todas as suas fichas em uma única pode ser perigoso. A tecnologia tem substitúıdo a linguagem “da vez” mais ou menos a cada 8, 10 anos. Pior, ao se fixar em uma linguagem, corre-se o risco de misturar questões do problema (do algoritmo) com questões do programa (da linguagem). Como na vida real, parece ser melhor buscar ser poliglota, ainda que obviamente haja uma linguagem preferida. Neste caso, todo o esforço deve ser no núcleo mais ou menos comum a todas as linguagens e deixar em segundo plano o aprendizado das idiossincrasias de cada uma. Exerćıcio 1 Lembrando que existe muita semelhança entre seguir um programa de computador e uma receita culinária, prepare um fluxograma da seguinte receita: Bolo de nozes da Dona Filustreca Ingredientes: 250g de chocolate em pó, 250g de passas, 3 x́ıcaras de açucar, meia x́ıcara de leite condensado, meia x́ıcara de óleo, 1 colher de chá de baunilha, 250g de manteiga e 1 colher de chá de sal. Modo de fazer: ponha o leite, o óleo, o açucar, o chocolate e o sal em uma panela e leve ao fogo, mexendo até a fervura. Reduza o fogo e continue a fervura até o ponto de caramelo. Retire do fogo e deixe esfriar por 10 min. Em seguida, bata com a manteiga e a baunilha até a mistura ficar homogênea. Distribua as passas no fundo de uma forma grande untada de manteiga. Derrame a massa sobre as passas. Deixe esfriar por 10 minutos, corte em pedaços e o bolo está pronto para ser comido. Exerćıcio 2 Seja agora um exemplo numérico. Eis aqui a seqüência de Fibonacci 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... Escreva um procedimento que informe a soma dos primeiros 1000 números da seqüência de Fibonacci. Fica claro por estes dois exemplos, que programar um computador é “emprestar in- teligência ao computador”. Ou seja, para programar a solução de um problema, há que saber resolver esse problema. E, não apenas resolver em tese, mas descrever detalhada- mente todas as etapas da solução. De fato, a programação é detalhista ao extremo. Como se disse acima, o computador surge em 1937, descrito em um artigo denominado “on a computable numbers”. Este artigo era tão inédito que quase não é publicado: faltavam revisores que o atestassem. O conceito matemático de computador está lá, quase 10 anos de existir algo f́ısico que lembrasse o conceito. ©88-09, Pedro Kantek versão de 23 de janeiro de 200912 CAPÍTULO 2. CIÊNCIA DA COMPUTAÇÃO Capricho Tenha sempre em mente que a principal função de um algoritmo é transmitir a solução de um problema a outrem. Desta maneira, um mı́nimo de capricho é indispensável a fim de não assustar o leitor. Letra clara, identação correta, nomes bem atribúıdos, tudo isto em papel limpo e sem borrões. Como o leitor já pode estar imaginando, esta caracteŕıstica é fundamental em provas, avaliações e trabalhos. A primeira conseqüência prática desta regra é: faça seus algoritmos a lápis. Documentação Nem sempre o texto que descreve o algoritmo é muito claro. Além do que, ele informa o que é feito, mas não porque é feito, ou quando é feito. Assim, o programador pode e deve lançar mão de comentários sempre que sentir necessidade de clarificar um ponto. “Bons comentários não podem melhorar uma má codificação, mas maus comentários podem comprometer seriamente uma boa codificação”. Jean Paul Tremblay. Correção (ou integridade ou ainda robustez) Um algoŕıtmo ı́ntegro é aquele onde os cálculos estão satisfatoriamente colocados, e atuam corretamente para todos os dados posśıveis de entrada. Não adianta um algoritmo sofisticado e cheio de estruturas de controle, se suas operações aritméticas elementares não estiverem corretas. É mais comum (e perigoso) o algoritmo que funciona em 95% dos casos, mas falha em 5% deles. Eficiência Esta caracteŕıstica tem a ver com economia de processamento, de memória, de comandos, de variáveis etc. Infelizmente, quase sempre é uma caracteŕıstica oposta à da clareza e da simplicidade, sendo estas mais importantes do que a efici- ência. Entretanto, em alguns casos, (principalmente na programação real - dentro das empresas), a eficiência pode ser fundamental. Neste caso, perde-se facilidade, para se ter economia. O bom programador é aquele que alia a simplicidade ao máximo de eficiência posśıvel. Generalidade Dentro do posśıvel, um algoritmo deve ser o mais genérico que puder. Isto significa que vale a pena um esforço no sentido de deixar nossos algoritmos ca- pazes de resolver não apenas o problema proposto, mas toda a classe de problemas semelhantes que aparecerem. Usualmente o esforço gasto para deixar um algoritmo genérico é pequeno em relação aos benef́ıcios que se obtém desta preocupação. Modularidade Algoritmos grandes dificilmente ficam bons se usarmos uma abordagem linear. É praticamente imposśıvel garantir clareza, impessoalidade, documentação etc, quando se resolve um algoritmo de cima a baixo. Uma conveniente divisão em módulos (isto é, em sub-algoritmos), para que cada um possa ser resolvido a seu tempo. Não podemos esquecer que a regra áurea da programação estruturada é “dividir para conquistar”. Comentários Permitem a agregação de informações destinadas ao leitor humano do algoritmo. Seu conteúdo não é levado em consideração na análise da integridade e correção do algoritmo. Tem finalidade apenas explicativa e informativa. Mas isso não significa que eles sejam despreźıveis. Pelo contrário, comentários são importantes em algoritmos de um modo geral. Os comentários são delimitados por um ”abre-chave”({) e um ”fecha-chave”(}). Eles podem ser colocados em qualquer ponto do algoritmo e tudo o que estiver entre chaves é desconsiderado no momento de seguir o algoritmo. Exemplo {Isto é um comentário} 15versão de 23 de janeiro de 2009 ©88-09, Pedro Kantek CAPÍTULO 2. CIÊNCIA DA COMPUTAÇÃO Há dois tipos de comentários aqui: aqueles encerrados entre chaves e aqueles coloca- dos depois de uma dupla barra. {Isto é um comentário, que só será encerrado quando se encontrar o fecha chave, ainda que ele ocupe mais de uma linha } // isto também é um comentário, desde a dupla barra até o fim da linha 2.2.2 Como se escreve um algoritmo A questão agora é: “como se escreve um algoritmo?” Usando uma ferramenta adequada para comunicar algum tipo de computação que o algoritmo execute. Qualquer linguagem poderia ser adequada, mas é melhor inventar uma sublinguagem derivada do português (ou do inglês em livros nesse idioma) que ajude a treinar o pensamento criativo em algoritmos. A idéia é que a ferramenta ajude a fazer a tarefa. Por analogia, experimente apara- fusar algo pequeno usando um pé de cabra. O nome da sublinguagem que usaremos é“português estruturado”, também conhecida como “portugol”. 2.3 Portugol Figura 2.1: Qual a melhor linguagem ? Figura 2.2: Como se entender com ele ? Como vimos, português estruturado é uma linguagem inventada aqui para simplificar a tarefa de aprender a construir, depurar e documentar algoritmos estruturados. Existem inúmeras versões, cada professor de lógica tem a sua. É importante salientar que a ©88-09, Pedro Kantek versão de 23 de janeiro de 200916 CAPÍTULO 2. CIÊNCIA DA COMPUTAÇÃO śıntaxe e a construção de português estruturado são arbitrados por alguém, segundo seus critérios, mas uma vez estabelecido um padrão, pele precisa ser seguido. Esta restrição tem duas vertentes. A primeira, é que há que haver um mı́nimo de concordância para que outras pessoas possam ler e entender o que escrevemos. A segunda, é que uma das principais caracteŕısticas do bom programador é a disciplina intelectual. Nada mais apropriado que começarmos a exercitar esta dif́ıcil qualidade desde já. Por que PORTUGOL e não PORTUGUÊS ? Português (como qualquer idioma natural) tem inúmeras desvantagens: ˆ Não é entendido pela máquina (exige tradução complex́ıssima) ˆ É amb́ıguo ˆ É muito extenso Vejamos por exemplo, uma orientação extráıda do manual de organização de uma Em- presa. ”O funcionário fará jus ao PRÊMIO PRODUTIVIDADE se estiver traba- lhando há mais de 6 meses da época de distribuição (fevereiro de cada ano), e trabalhar na área de vendas, ou então se tiver sido especialmente citado como tendo tido alta produtividade. Perdem o direito, funcionários que tive- rem mais de 2 faltas e mais de 5 atrasos, ou que tiverem fruido licença saúde do INSS no peŕıodo aquisitivo”. Parece claro, não é ? Agora tentemos responder: ˆ João tem 3 meses de casa e foi citado como de ”alta produtividade”. Ganha ou não? ˆ Maria teve 3 faltas. Perde ou não ? Outro exemplo, “minha tia tem uma gatinha e ela é muito bonita”. Quem é bonita, a tia ou a gatinha ? O linguajar acima, não é adequado para expressarmos algoritmos pois é inexato, dúbio, e deixa muita margem de interpretação, usa verbos e comandos proibidos, isto é, que o computador não saberá executar. Devemos lembrar sempre que a margem de interpretação do computador, qualquer computador, é sempre ZERO, e os computadores tem a péssima mania de fazer o que mandamos eles fazerem, e não o que queremos que eles façam. Por que PORTUGOL e não uma linguagem qualquer como Java? ou qualquer outra linguagem de programação? Uma linguagem de programação, ainda que de alto ńıvel, caso do Java, exige um conhecimento da máquina que ainda não temos. Também é importante salientar que idealmente falando, não é boa poĺıtica enfrentar dois problemas interligados ao mesmo tempo. Isto é, não convém misturar dificuldades de lógica, (advindas do problema que se quer resolver) com dificuldades da linguagem (advindas do ambiente tecnológico onde o programa vai rodar), pois ambas somadas podem ser demais para a cabeça do autor. Já dizia Dijkstra “deve-se reconhecer que tem-se uma cabeça pequena, e que é melhor tratar de conviver com ela e respeitar suas limitações”. Aproveitando a citação, mais de uma do mesmo autor: ”A regra áurea da programação estruturada é dividir para reinar”. 17versão de 23 de janeiro de 2009 ©88-09, Pedro Kantek CAPÍTULO 2. CIÊNCIA DA COMPUTAÇÃO existente. Entretanto este re-uso dificilmente é imediato. Sempre há que estudar e eventualmente modificar um algoritmo já existente, a menos que quando este foi feito seu autor já tinha a preocupação com o reuso. ˆ transcrever em LP. É hora de escolher um computador, um ambiente operacional e sobretudo uma linguagem de programação que esteja dispońıvel e seja conhe- cida. Dessas 3 opções (computador, ambiente e linguagem) surge a plataforma definitiva: agora é posśıvel escrever, testar, depurar e implementar o programa de computador. ˆ depurar. Usualmente há uma seqüência de testes: – compilação correta: nenhum erro apresentado pelo compilador – testes imediatos sem erro: testes ad hoc para este programa (e só para ele) dão os resultados esperados. – teste alfa: um esforço completo de testes, inclusive integrando este programa aos seus antecessores e sucessores. Usualmente o teste é feito pelo(s) autor(es) do programa. – teste beta: um teste completo feito por terceiros. Há uma regra aqui de que quem faz (programador) não deve ser quem testa (testador). ˆ implementar e rodar. Com o programa testado e liberado é hora de rodá-lo em produção. Nesta hora ocorre o que tem sido chamado de deploy (dizem as más ĺınguas que sempre associado a seu irmão gêmeo, o delay). Dependendo do porte da instalação e do sistema, às vezes esta passagem é complexa e trabalhosa. ˆ manutenção. Seria muito bom se a história acabasse na etapa anterior. Não é o que ocorre, já que o mundo muda e os programas precisam mudar com ele. Se a manutenção é pequena, usualmente pode-se fazê-la sem muito transtorno, mas caso não seja, este ciclo recomeça. Note-se que após algumas manutenções grandes o programa começa a dar mostrar de instabilidade –a popular colcha de retalhos – e é hora de começar tudo de novo, na nova versão do programa. Como se aprende algoritmos? Não é fácil aprender algoritmos. No que têm de engenharia, é mais fácil. Há fórmulas, procedimentos, práticas consagradas prontas a serem usadas. Mas, no que são arte, tais receitas desaparecem. É mais ou menos como tentar ensinar alguém a desenhar (outra arte) ou a compor música (outra ainda). Olhando como se aprende a desenhar, é posśıvel ter alguns insights. Aprendizes de desenho copiam desenhos e partes de desenho extensivamente. Pode-se tentar algo parecido aqui. Em resumo, estas seriam as indicações ˆ Estudando algoritmos prontos. Pegue bons livros de algoritmos, e estude as im- plementações que lá aparecem. Transcreva tais algoritmos em um simulador (tipo visualg) ou mesmo em uma linguagem de programação. Execute os algoritmos. Busque entender o que cada parte do mesmo faz. Sugira hipóteses sobre o funci- onamento e provoque pequenas mudanças no código para confirmar (ou rejeitar) suas hipóteses. ˆ Tenha intimidade com algum ambiente de compilação e testes. Esta proposta é importante para poder testar algoritmos. Se ficar embatucado diante de uma simples implementação, você terá grandes dificuldades de escrever algoritmos. ©88-09, Pedro Kantek versão de 23 de janeiro de 200920 CAPÍTULO 2. CIÊNCIA DA COMPUTAÇÃO ˆ Escreva pequenos algoritmos. Tente fazer os exerćıcios (começando sempre pelos mais simples) de qualquer bom livro de algoritmos. ˆ Treine a interpretação dos enunciados. Enquanto não entender o que deve ser feito, não adianta olhar para o algoritmo, pois o motivador das ações que ele toma estará ausente. Nunca se deve começar a estudar ou a construir um algoritmo se não houver um claro entendimento do que o algoritmo deve fazer. 2.4 Programação Estruturada O termo programação estruturada veio à luz pela primeira vez, nos fins da década de 60, quando Edsger Dijkstra (Lê-se como Dikster) escreveu um artigo, publicado em Communications of the ACM, cujo t́ıtulo é “O comando GO TO é prejudicial”. Viv́ıamos a época de ouro do COBOL, e o comando GO TO é a instrução de desvio desta linguagem. Dijkstra observou que a qualidade dos programadores decai em função do número de GO TOs usados em seus programas. Segundo ele,“Comandos GO TO tendem a criar caminhos de lógica confusos e programas pouco claros”. A sua recomendação foi de que o comando em questão fosse banido das linguagens de alto ńıvel. Nessa época também (1966) dois professores italianos, Giuseppi Jacopini e Corrado Bohm, provaram matematicamente que qualquer lógica de programação poderia ser de- rivada de três tipos básicos de procedimentos, a saber: seqüência, alternativa e repetição. Chegou-se então ao âmago da programação estruturada, que é trocar a instrução de desvio pelas instruções de repetição. Ao fazer isto, todos os componentes de um programa passam a ter uma entrada e sáıda únicas. Atente-se que ao usar uma instrução de desvio, essa regra de uma entrada e uma sáıda é violada: o conjunto passa a ter no mı́nimo duas sáıdas. Seqüência simples Trata-se de um conjunto de comandos simples, que seguem um ao outro e que são executados na ordem em que aparecem. Exemplo A ← 10 B ← A + 5 X ← 1 + 2 Dentro de uma seqüência simples de comandos a entrada sempre é pelo primeiro co- mando e a sáıda sempre é pelo último. Graças ao prinćıpio da programação estruturada (uma entrada e uma sáıda), uma seqüência simples pode ser substitúıda por um bloco com entrada e sáıda únicas. Alternativa É um comando que permite dois caminhos alternativos, dáı o nome, a depender de alguma condição. Na matemática convencional isto já existe, por exemplo na fórmula de Bhaskhara. No momento de calcular a raiz quadrada de ∇, há que se tomar uma decisão. Se ∇ < 0 os cálculos cessam e a resposta de ráızes imaginárias deve ser dada. Se ∇ ≥ 0, a raiz pode ser extráıda e um ou dois valores de ráızes emergem. O ponto importante aqui é que em algum lugar os dois ramos se juntam novamente, e a regra de ouro da programação estruturada (entrada única e sáıda única também) continua verdadeira. Tal como na seqüência, um comando alternativo, por mais complexo que seja, pode ser substitúıdo por única caixa. 21versão de 23 de janeiro de 2009 ©88-09, Pedro Kantek CAPÍTULO 2. CIÊNCIA DA COMPUTAÇÃO Repetição O terceiro bloco da programação estruturada é a resposta à necessidade de usar o comando de desvio. Perceba-se que aqui existe um desvio impĺıcito, já que ao se terminar o bloco, há que se desviar para o ińıcio do mesmo, que é o que caracteriza uma repetição. A restrição a obedecer não é a ausência de desvio – de resto, imposśıvel de obedecer – mas sim a regra da entrada e sáıda únicas. Em outras palavras não é proibido usar o desvio, desde que ele esteja contido em limites bem determinados. Tal como na seqüência e na alternativa, um comando de repetição, por maior ou mais complexo que seja, pode ser substitúıdo por única caixa. A importância desta descoberta para o software teve tanto impacto quanto a de que qualquer forma lógica de hardware pode ser construida pelas combinações de portas AND, OR e NOT. A grande vantagem dos três elementos da programação estruturada é que possuem a caracteŕıstica de pacote ou caixa preta, uma vez que todos tem uma única entrada e uma única sáıda. Isto significa que partes de programas construidos com estas estruturas podem ser também considerados pacotes, sempre com entradas e saidas únicas. Esta é a melhor qualidade da programação estruturada, e é por esta caracteŕıstica que o GOTO deve ser desprezado na construção de bons algoritmos. Tanto isto é verdadeiro, que as linguagens mais modernas, não tem mais a instrução de desvio, banida por perniciosa e desnecessária. 2.5 A máquina de Turing Embora a humanidade use o conceito de algoritmo há milênios (O de MDC é devido a Euclides), e o próprio nome algoritmo derive do autor árabe de um tratado de álgebra escrito por volta de 800 dC, a definição precisa do que seja um algoritmo geral é apenas de 1930. Ela é devida a Turing, através do seu conceito de Máquina de Turing. Esta não é uma máquina real, sendo apenas uma abstração matemática, dáı o seu poder de encanto. Em 1900, o matemático alemão Hilbert apresentou em um congresso uma lista de problemas que segundo ele estariam ocupando as mentes matemáticas no século que ora se iniciava. O décimo problema de Hilbert, dizia: ...haverá algum procedimento mecânico geral que possa em prinćıpio resolver todos os problemas da ma- temática ? 1 Em 1937, Turing respondeu a esta pergunta através do conceito de Máquina de Turing. Ela é composta por um número finito de estados, ainda que possa ser muito grande. Deve tratar um input infinito. Tem um espaço exterior de armazenagem também infinito. Turing imaginou o espaço exterior para dados e armazenamento como sendo uma fita, que pode mover-se para frente e para trás. Além disso a máquina pode ler e escrever nesta fita. A fita está composta por quadrados (ou seja, o nosso ambiente é discreto). Apenas 2 śımbolos podem ser escritos nos quadrados da fita, digamos 0 significando quadrado em branco e 1 (quadrado preenchido), ou vice-versa. Isto posto, lembremos que: 1. os estados internos do aparelho são finitos em número 2. o comportamento da máquina é totalmente determinado pelo seu estado interior e pelo input. 1Eis o problema original, como proposto por Hilbert: Determination of the solvability of a diophan- tine equation: Given a diophantine equation with any number of unkown quantities and with rational numerical coefficients: to devise a process according to which it can be determined by a finite number of operations whether the equation is solvable in rational integers ©88-09, Pedro Kantek versão de 23 de janeiro de 200922 CAPÍTULO 2. CIÊNCIA DA COMPUTAÇÃO INT 21H PUSH AX ;DEPOIS VOU DAR POR EXTENSO MOV BX,10 MOV DI,OFFSET DIA MOV AH,0 MOV AL,DL DIV BL OR AX,3030H STOSW MOV AL," " STOSB MOV AH,0 MOV AL,DH PUSH AX ;DEPOIS VOU DAR POR EXTENSO DIV BL OR AX,3030H STOSW MOV AL," " STOSB 2.6.2 Fortran Fortran é uma linguagem muito antiga, originalmente sugerida pela IBM na década de 50. Seu texto se assemelha a uma descrição matemática e de fato, FORTRAN significa 25versão de 23 de janeiro de 2009 ©88-09, Pedro Kantek CAPÍTULO 2. CIÊNCIA DA COMPUTAÇÃO FORmula TRANslation. É, ou pelo menos era, uma linguagem franciscana de tão pobre em recursos. Foi a única linguagem ensinada em escolas de engenharia até a década de 80. O primeiro compilador de FORTRAN foi desenvolvido para o IBM 704 em 1954-57 por uma equipe da IBM chefiada por John W. Backus. A inclusão de um tipo de dados de número complexo na linguagem tornou a lingua- gem Fortran particularmente apta para a computação cient́ıfica. As principais revisão são a Fortran 66, 77, 90 e 95. A mais famosa e usada é a Fortran 90. Sua principal vantagem é a eficiência em calculo numérico pesado. A seguir, um exemplo de FORTRAN C 1 2 3 4 5 6 C2345678901234567890123456789012345678901234567890123456789012345 PROGRAM BASKHARA C REAL A,B,C, DELTA, X1,X2, RE, IM C PRINT *, "Este programa resolve uma equaç~ao de 2o.grau" PRINT *, "do tipo: a*x**2 + b*x + c = 0" C PRINT 10, "Digite a,b,c: " 10 FORMAT(A,1X,$) 20 READ(*,*,ERR=20) A,B,C C DELTA=B*B-4.*A*C C IF (DELTA.GT.0) THEN ! (DUAS RAIZES REAIS) X1=(-B-SQRT(DELTA))/(2.*A) X2=(-B+SQRT(DELTA))/(2.*A) PRINT *, "RAIZES: X1=",X1 PRINT *, " X2=",X2 ELSE IF (DELTA.EQ.0) THEN ! (DUAS RAIZES REAIS IGUAIS) X1=-B/(2.*A) X2=X1 PRINT *, "RAIZES: X1=X2=",X1 ELSE ! (DUAS RAIZES COMPLEXAS) RE=-B/(2.*A) IM=SQRT(-DELTA)/(2.*A) PRINT *, "RAIZES COMPLEXAS: X1=",RE," -",IM,"i" PRINT *, " X2=",RE," +",IM,"i" ENDIF C END 2.6.3 Lisp LISP é a segunda linguagem de alto nivel mais antiga. O LISP nasce como filho da comunidade de Inteligência Artificial. Na origem, 4 grupos de pessoas se inseriram na comunidade de IA: os lingüistas (na busca de um tradutor universal), os psicólogos (na tentativa de entender e estudar processos cerebrais humanos), matemáticos (a mecanização de aspectos da matemática, por exemplo a demonstração de teoremas) e os informáticos (que buscavam expandir os limites da ciência). ©88-09, Pedro Kantek versão de 23 de janeiro de 200926 CAPÍTULO 2. CIÊNCIA DA COMPUTAÇÃO O marco inicial é o encontro no Dartmouth College em 1956, que trouxe duas con- seqüências importantes: a atribuição do nome IA e a possibilidade dos diferentes pes- quisadores se conhecerem e terem suas pesquisas beneficiadas por uma interfecundação intelectual. A primeira constatação foi a de que linguagens existentes privilegiavam dados numé- ricos na forma de arrays. Assim, a busca foi a criação de ambientes que processassem śımbolos na forma de listas. A primeira proposta foi IPL (Information Processing Lan- guage I, por Newel e Simon em 1956). Era um assemblão com suporte a listas. A IBM engajou-se no esforço, mas tendo gasto muito no projeto FORTRAN decidiu agregar-lhe capacidade de listas, ao invés de criar nova linguagem. Nasceu a FLPL (Fortran List Processing Language). Em 1958, McCarthy começou a pesquisar requisitos para uma linguagem simbólica. Foram eles: recursão, expressões condicionais, alocação dinâmica de listas, desalocação automática. O FORTRAN não tinha a menor possibilidade de atendê-las e assim Mc- Carthy junto com M. Minsky desenvolveu o LISP. Buscava-se uma função Lisp Universal (como uma máquina de Turing Universal). A primeira versão (chamada LISP pura) era completamente funcional. Mais tarde, LISP foi sofrendo modificações e melhoramentos visando eliminar ineficiências e dificuldades de uso. Acabou por se tornar uma lingua- gem 100% adequada a qualquer tipo de resolução de problema. Por exemplo, o editor EMACS que é um padrão no mundo UNIX está feito em LISP. Inúmeros dialetos LISP apareceram, cada um queria apresentar a sua versão como sendo a melhor. Por exemplo, FranzLisp, ZetaLisp, LeLisp, MacLisp, Interlisp, Scheme, T, Nil, Xlisp, Autolisp etc. Finalmente, como maneira de facilitar a comunicação entre todos estes (e outros) ambientes, trabalhou-se na criação de um padrão que foi denomi- nado Common Lisp. Como resultado o Common Lisp ficou grande e um tanto quanto heterogêneo, mas ele herda as melhores práticas de cada um de seus antecessores. Seja agora um exemplo de uma função lisp: > (defun li (L1 L2) ; pergunta se duas listas s~ao iguais (cond ((null L1) (null L2)) ((null L2) nil) ((not (eql (car L1) (car L2))) nil) (t (li (cdr L1) (cdr L2))))) LI 2.6.4 Prolog O nome Prolog para a linguagem concreta foi escolhido por Philippe Roussel como uma abreviação de PROgrammation LOGique. Foi criada em meados de 1972 por Alain Col- merauer e Philippe Roussel, baseados no conceito de Robert Kowalski da interpretação procedimental das cláusulas de Horn. A motivação para isso veio em parte da von- tade de reconciliar o uso da lógica como uma linguagem declarativa de representação do conhecimento com a representação procedimental do conhecimento. *Histórico ˆ Precursores: Newell, Shaw e Simon, com sua Logic Theory Machine, que buscava a prova automática de teoremas, em 1956. ˆ Robinson, 65, no artigo A machine oriented logic based on the resolution princi- ple. Propunha o uso da fórmula clausal, do uso de resolução e principalmente do algoritmo de unificação. 27versão de 23 de janeiro de 2009 ©88-09, Pedro Kantek CAPÍTULO 2. CIÊNCIA DA COMPUTAÇÃO será. Idem para matrizes e até arrays-nd. Em algumas versões de APL este n chega a 256 dimensões. Este é um comando EDIT (troca algo, de... para...) 2.6.7 Basic A linguagem BASIC (acrônimo para Beginners All-purpose Symbolic Instruction Code), foi criada, com fins didáticos, pelos professores John G. Kemeny e T. Kurtz em 1963 no Dartmouth College. BASIC também é o nome genérico dado a uma grande famı́lia de linguagens de programação derivadas do Basic original. Provavelmente existem mais variações de Basic do que de qualquer outra linguagem de programação. Basic é uma linguagem imperativa de alto ńıvel, pertencente à terceira geração, que é normalmente interpretada e, originalmente, não estruturada, por ter sido fortemente baseada em FORTRAN II. Um programa em Basic tradicional tem suas linhas numeradas, sendo que é quase que padrão usar números de 10 em 10 (o que facilita a colocação de linhas intermediárias). Os comandos são poucos, simples e facilmente compreenśıveis na ĺıngua inglesa (LET, IF, ...). Um programa em Basic, que calcula a fórmula de Bhaskara ficaria como: 10 REM RESOLVE EQUACAO DO SEGUNDO GRAU 20 READ A,B,C 25 IF A=0 THEN GOTO 410 30 LET D=B*B-4*A*C 40 IF D<0 THEN GOTO 430 50 PRINT "SOLUCAO" 60 IF D=0 THEN GOTO 100 70 PRINT "PRIMEIRA SOLUCAO",(-B+SQR(D))/(2*A) 80 PRINT "SEGUNDA SOLUCAO",(-B-SQR(D))/(2*A) 90 GOTO 20 100 PRINT "SOLUCAO UNICA",(-B)/(2*A) 200 GOTO 20 410 PRINT "A DEVE SER DIFERENTE DE ZERO" 420 GOTO 20 430 PRINT "NAO HA SOLUCOES REAIS" 440 GOTO 20 490 DATA 10,20,1241,123,22,-1 500 END O programa demonstra a falta de estruturação da linguagem original, pois o IF funciona como um GOTO condicional, o que favorece o código espaguete. ©88-09, Pedro Kantek versão de 23 de janeiro de 200930 CAPÍTULO 2. CIÊNCIA DA COMPUTAÇÃO 2.6.8 Clipper Tudo começou com o dbase, que foi o precursor de bancos de dados para micros. Por volta de 83, 84 surgiu o dbase 2 (nunca houve o 1) para micros de 8 bits com memórias t́ıpicas de 64Kb e um ou dois disquetes de 8 polegadas e cerca de 512 KB de capacidade em cada um. O dbase já era um gerenciador de dados, dentro da visão relacional, com mı́nima redundância de dados e com todas as garantias de acesso e uma linguagem estruturada, no melhor padrão, de uso geral, capaz de garantir um aumento na produtividade na programação. A história do dBASE começa em 74, no Jet Propulsion Laboratory, conhecido como JPL, e instalado em Pasadena, Califórnia. Nesta instalação da NASA trabalhava Jeb Long, pesquisador que lidava com dados obtidos nas pesquisas espaciais através de naves não tripuladas. Estes, por serem em grande número, começaram a trazer problemas e dissabores a Jeb Long, que desenvolveu, então, um programa de computador capaz de gerenciar tais informações. Este programa com nome de JPLDIS, foi conclúıdo e alcançou razoável sucesso tendo sido bastante comentado pelo pessoal técnico. Foi o que bastou para que um analista de sistemas (Wayne Ratliff) começasse a desenvolver um programa gerenciador de dados, genérico, mas tendo como modelo o JPLDIS. Rapidamente o novo trabalho tornou-se melhor do que o original, e Ratliff desenvolveu- o cada vez mais. Em 79, Ratliff achou que o programa já estava maduro e pronto para enfrentar o mercado, e ele foi anunciado com o nome de VULCAN. Foi, entretanto, um fracasso: não se chegou a vender sequer 50 cópias. Alguns meses depois, um grande distribuidor de programas de micros, George Tate, tomou conhecimento do dBASE. Testou-o e ficou entusiasmado. Achou que o que faltava a Ratliff era suporte comercial, uma vez que seu trabalho era muito bom. Rapidamente providenciaram-se algumas mudanças cosméticas no pro- grama, seu nome foi mudado para dBASE II (nunca houve o dBASE I, tratava-se de estratégia comercial, para apresentar o produto como um melhoramento), e uma nova empresa (ASHTON TATE) foi criada para vender este produto. Em pouco tempo, dBASE tornou-se um marco na história de softwares para micro- computadores. A grande vantagem de um banco de dados é retirar a amarração entre programas e dados. A explicação desta vantagem é que dados são muito mais estáveis do que os proce- dimentos (=programas). Separando-os garante-se que longevidade aos dados, que em geral são os mais custosos para adquirir. O dbase como linguagem era interpretado, o que trazia desempenho ṕıfio nas apli- cações, além da eventual falta de segurança (qualquer um podia alterar os dados). Para corrigir estas duas deficiências, logo surgiram inúmeros compiladores, dos quais o mais famoso foi o CLIPPER. Eis um programa em CLIPPER, por acaso um trecho do programa que emite provas aleatórias e diferentes: w_nomq = space(8) w_file = "LIXO " @ 08,45 say "Nome Arquivo: " get w_file pict "@!" @ 09,5 say "Qual a turma ? " get w_turm pict "@!" @ 09,40 say "OU arquivo de nomes " get w_nomq pict "@!" oba := 1 do while oba == 1 31versão de 23 de janeiro de 2009 ©88-09, Pedro Kantek CAPÍTULO 2. CIÊNCIA DA COMPUTAÇÃO oba := 0 W_mess := " " @ 11,15 say "Questao 1:" @ 12,20 say "Topico: " get w_top1 @ 12,50 say "Grupo: " get w_gru1 pict "99" 2.6.9 Natural NATURAL é uma linguagem de quarta geração que pode ser utilizada, indistintamente por usuários finais trabalhando em auto-serviço, ou por programadores profissionais em suas atividades normais no CPD. Embora possa ler arquivos seqüenciais, o Natural é mais indicado para ler bancos de dados ADABAS, que a partir da década de 90 foi o padrão de bancos de dados em nosso páıs e em boa parte do mundo. Eis um exemplo de programa em Natural: 0010 AT TOP OF PAGE 0020 DO 0030 WRITE 20T "INFORMACOES SALARIAIS PARA SANTA CATARINA" 0040 SKIP 1 0050 DOEND 0060 FIND PESSOAL WITH ESTADO = "SC" 0070 SORTED BY CIDADE 0080 AT BREAK OF CIDADE 0090 DISPLAY NOTITLE "NOME DA/CIDADE" OLD(CIDADE) 0100 "TOTAL/SALARIOS" SUM(SALARIO) (EM=ZZZ,ZZZ,ZZZ) 0110 "SALARIO/MEDIO" AVER(SALARIO) 0120 "SALARIO/MAXIMO" MAX(SALARIO) 0130 "NUMERO/PESSOAS" COUNT(CIDADE) (EM=ZZ99) 0140 AT END OF DATA 0150 DO 0160 SKIP 1 0170 WRITE "TOTAL DE TODOS OS SALARIOS" TOTAL(SALARIO) 0180 DOEND 0190 END 2.6.10 Pascal É uma linguagem de programação estruturada que recebeu este nome em homenagem ao matemático Blaise Pascal. Foi criada em 1970 pelo súıço Niklaus Wirth, tendo em mente encorajar o uso de código estruturado. Segundo o autor, Pascal foi criada simultaneamente para ensinar programação estru- turada e para ser utilizada em sua fábrica de software. A linguagem reflete a liberação pessoal de Wirth após seu envolvimento com a especificação de ALGOL 68, e sua su- gestão para essa especificação, o ALGOL W. A linguagem é extremamente bem estruturada e muito adequada para ensino de linguagens de programação. É provavelmente uma das linguagens mais bem resolvidas entre as linguagens estruturadas, e certamente um dos exemplos de como uma linguagem especificada por uma pessoa pode ser bem melhor do que uma linguagem especificada por um comitê. Pascal originou uma enorme gama de dialetos, podendo também ser considerada uma famı́lia de linguagens de programação. Grande parte de seu sucesso se deve a criação, na ©88-09, Pedro Kantek versão de 23 de janeiro de 200932 CAPÍTULO 2. CIÊNCIA DA COMPUTAÇÃO public class Gato extends Animal { public void fazerBarulho() { System.out.println("Miau!"); } } 2.6.13 PHP PHP (um acrônimo recursivo para “PHP: Hypertext Preprocessor”) uma linguagem de programação de computadores interpretada, livre e muito utilizada para gerar conteúdo dinâmico na Web. A linguagem surgiu por volta de 1994, como um subconjunto de scripts Perl criados por Rasmus Lerdof, com o nome Personal Home Page Tools. Mais tarde, em 1997, foi lançado o novo pacote da linguagem com o nome de PHP/FI, trazendo a ferramenta Forms Interpreter, que era na verdade um interpretador de comandos SQL. Trata-se de uma linguagem modularizada, o que a torna ideal para instalação e uso em servidores web. Diversos módulos são criados no repositório de extensões PECL (PHP Extension Community Library) e alguns destes módulos são introduzidos como padrão em novas versões da linguagem. Muito parecida, em tipos de dados, sintaxe e mesmo funções, com a linguagem C e com a C++. Pode ser, dependendo da configuração do servidor, embutida no código HTML. Existem versões do PHP dispońıveis para os seguintes sistemas operacionais: Windows, Linux, FreeBSD, Mac OS, OS/2, AS/400, Novell Netware, RISC OS, IRIX e Solaris Construir uma página dinâmica baseada em bases de dados é simples, com PHP. Este provê suporte a um grande número de bases de dados: Oracle, Sybase, PostgreSQL, InterBase, MySQL, SQLite, MSSQL, Firebird etc, podendo abstrair o banco com a biblioteca ADOdb, entre outras. PHP tem suporte aos protocolos: IMAP, SNMP, NNTP, POP3, HTTP, LDAP, XML- RPC, SOAP. É posśıvel abrir sockets e interagir com outros protocolos. E as bibliotecas de terceiros expandem ainda mais estas funcionalidades. Veja um exemplo de PHP <? ... $tipss =mysql_result($result,0,’SSERVTIPSS’); $porss =mysql_result($result,0,’SSERVPORSS’); $daali =mysql_result($result,0,’SSERVDAALI’); $anexo =mysql_result($result,0,’SSERVANEXO’); $query = "select * from ANDAM where ANDAMNSERV =’$nserv1’ " ; $result = mysql_query($query); $quantos = mysql_num_rows($result); $quantos++; ?> <table > <tr> <td>Numero da solicitacao de servico<td><? echo $nserv ?><tr> <td>autor<td><? echo $nomeu ?><tr> <td>cliente<td><? echo $clien ?><tr> <td>CA responsavel<td><? echo $cares ?><tr> <td>interlocutor no cliente<td><? echo $intcl ?><tr> <td>fone<td><? echo $fonic ?><tr> <td>email<td><? echo $emaic ?><tr> 35versão de 23 de janeiro de 2009 ©88-09, Pedro Kantek CAPÍTULO 2. CIÊNCIA DA COMPUTAÇÃO 2.6.14 J Para os que acharam APL uma linguagem meio sem pés nem cabeça, eis aqui J. Olhando para o J, o APL passa a ser tão comportada quanto um COBOL da década de 70. Para entender o J, precisamos estudar a vida do cara que inventou o APL, o cana- dense Ken Iverson. Na minha opinião, o sujeito foi um gênio. Coloco-o sem nenhum medo de errar na galeria dos grandes matemáticos da humanidade, talvez o primeiro (junto com Mandelbroot) que tenha realmente conseguido casar com sucesso a matemá- tica e a computação. Depois de propor o APL como uma notação matemática (década de 50), de liderar o grupo que converteu o APL em linguagem de programação (década de 60 na IBM) e de liderar a popularização da linguagem (anos 70 e começos dos 80), em meados dos 80, ele chegou a algumas conclusões: ˆ o uso de um alfabeto não usual (para ser educado), restringia o uso do APL (lembremos que ainda não havia o windows e portanto para usar APL havia que comprar hardware especializado - e caro). ˆ o desenvolvimento continuado por 30 anos da linguagem apontou algumas incon- sistências teóricas no modelo. Não esqueçamos que o Iverson era um matemático da pesada ˆ o custo que o APL sempre teve inviabilizava seu uso pelos menos aquinhoados Dessas elocubrações nasceu a linguagem J. O nome não tem explicação, exceto a dada por um de seus autores (”Why ’J’? It is easy to type.”). Há quem diga que J segue ”I”no alfabeto, sendo este ”I”a notação Iverson. Seja como for, J não tem nada a ver com Java. Para maiores detalhes veja www.jsoftware.com. Eis a seguir um programa J: gerasima =: 3 : 0 r=.(2$y)$(1+?200$2 2 2 2 2 3 3 3 4 4 4 5 6)*2+-<.1.5*?200$2 1 1 1 2 1 2 xx=.(y?(<.y*1.6)) z=.+/|:r*($r)$xx r,.((y,1)$z),.(y,1)$xx ) Equivale ao programa gerasima do workspace vivo128, que gera um sistema de n incóg- nitas e n equações, depois o resolve para obter os termos independentes e possibilitar propor ao aluno que descubra as incógnitas. 2.6.15 Lua Lua é inteiramente projetada, implementada e desenvolvida no Brasil, por uma equipe na PUC-Rio (Pontif́ıcia Universidade Católica do Rio de Janeiro). Lua nasceu e cresceu no Tecgraf, o Grupo de Tecnologia em Computação Gráfica da PUC-Rio. Atualmente, Lua é desenvolvida no laboratório Lablua. Tanto o Tecgraf quanto Lablua são laboratórios do Departamento de Informática da PUC-Rio. O projeto e a evolução de Lua foram apresentados em junho de 2007 na HOPL III, a 3a Conferência da ACM sobre a História das Linguagens de Programação. Essa conferência ocorre a cada 15 anos (a primeira foi em 1978 e a segunda em 1993) e somente poucas linguagens são apresentadas a cada vez. A escolha de Lua para a HOPL III é um importante reconhecimento do seu impacto mundial. Lua é a única linguagem de programação de impacto desenvolvida fora do primeiro mundo, estando atualmente ©88-09, Pedro Kantek versão de 23 de janeiro de 200936 CAPÍTULO 2. CIÊNCIA DA COMPUTAÇÃO entre as 20 linguagens mais populares na Internet (segundo o ı́ndice TIOBE). (Dados obtidos em www.lua.org) Eis um exemplo de lua function fatorial(n) if n < 2 then return 1 else return n * fatorial(n-1) end end function exemplo() print("Ola mundo\n\n") print("Fatorial de seis: " .. fatorial(6) .. "\n") print("Tchau......\n") end -- execuç~ao da funç~ao exemplo() 37versão de 23 de janeiro de 2009 ©88-09, Pedro Kantek CAPÍTULO 3. ESCREVENDO ALGORITMOS Dentro deste diagrama, (e nos próximos que tiverem este formato) qualquer caminho seguido, levar a identificadores válidos. Consideram-se ”letra”, as 26 letras do alfabeto latino maiúsculas, e ”d́ıgito”, os 10 d́ıgitos de 0 a 9. Deve-se atentar que o branco não faz parte do rol de caracteres válidos, o que faz com que o identificador não possa ser constitúıdo de mais de uma palavra. Pode-se usar neste caso o separador ( ), chamado ”sublinha”. Atente-se para a importância dos nomes criados pelo programador serem escritos em maiúscula. Exemplos válidos NOME SOM_TERMOS RAIZ1 SALDO08 SALDO_09 Exemplos não válidos nome (usa-se letras minúsculas) Saldo Devedor (usa-se duas palavras) SaldoDevedor (mistura-se letras maiúsculas e minúsculas) 123SALDO (começa por um dı́gito numérico) Embora a maioria dos livros de lógica não façam distinção entre o uso de maiúsculas e minúsculas para efeito de estabelecimento de identificadores, aqui vai-se padronizar nossos identificadores sempre EM LETRAS MAIÚSCULAS. Isto pode incomodar um pouco no ińıcio, mas se revelará uma grande vantagem na análise de algoritmos feitos por terceiros, ou mesmo fde autoria própria, mas feitos há tempos. O autor do algoritmo tem total autoridade para nomear seus identificadores como queira. Entretanto, há uma regra de bom senso impĺıcita. Cada identificador deve ter um nome o mais próximo posśıvel de sua função. Exemplo: Se precisarmos um identificador para representar uma somatória, poderemos chamá-lo de SOMA, SOMAT, SM, etc, mas nunca de ABC, ou XYZ, ou ainda AKLJHJKH. Quanto ao tamanho do identificador, também só há uma regra: BOM SENSO. Nem tão pequeno que fique quase imposśıvel identificá-lo pelo nome, nem tão longo que seja cansativo escrevê-lo. Exemplo. Ao gerar um identificador para conter a quanti- dade total de horas trabalhadas deve-se chamá-lo como QTHT, ou QTDHORAS, ou HORTRAB, ou similar, mas seria um exagero chamar o identificador de QUANTI- DADE DE HORAS TRABALHADAS NO MES. Finalmente, deve-se discutir se as palavras que compõe o algoritmo devem ou não ser acentuadas. Parece uma discussão bizantina, mas não o é necessariamente. Se o leitor do algoritmo for um ser humano, pode-se acentuá-lo sem nenhum problema. Entretanto, se o algoritmo for – no futuro – processado por algum programa, há que se ter em mente, que em geral, para qualquer programa “á” é diferente de “a” e esta regra vale para todas as letras. Também “ç” é diferente de “c”. ©88-09, Pedro Kantek versão de 23 de janeiro de 200940 CAPÍTULO 3. ESCREVENDO ALGORITMOS 3.2 Variáveis Ao identificador atribui-se um valor, que será usado nas computações futuras. Quando este valor pode variar ao longo do processamento, diz-se que o identificador representa uma variável. (No contrário, dir-se-ia que o identificador representa uma constante). Outra definição para variável é: ”Um lugar onde se guarda uma valor”. Por norma do português estruturado, todas as variáveis devem ser declaradas antes de poderem ser utilizadas. Chama-se à atenção, pois esta não é uma regra obrigatória. Inúmeras linguagens de programação, permitem que se defina uma variável no instante em que ela passa a ser necessária e em qualquer ponto do programa. (Exemplo: BASIC, dbase, APL etc) Em portugol (e em Pascal, Cobol, Fortran, C, Java etc), isto não é posśıvel. Assim, nossos programas terão dois blocos: O primeiro é o de definição de variáveis, e o segundo é o de procedimentos, sempre nesta ordem. 3.2.1 Tipos de variáveis Existem cinco tipos de variáveis básicas em portugol: inteiro, real, caracter, lógico e cadeia. Inteiro É uma variável que pode conter números inteiros (positivos ou negativos, não importa). Exemplos: 5, 1009, -6730 etc. O conceito de inteiro é familiar a nós. Qualquer operação de contagem, pode ser estabelecida a partir do conjunto dos valores inteiros. Uma quantidade discreta 1(i.é. enumerável) sempre pode ser processada com base nos inteiros. Embora possam ter uma definição formal, para nós é suficiente a seguinte descrição: Uma variável inteira é a que pode armazenar qualquer um dos números do conjunto: −∞, ...− (n + 1),−n, ...,−2,−1, 0, 1, 2, ..., n, n + 1, ..., +∞ Real É outra variável numérica que pode conter qualquer número real, isto é, inteiro ou fracionário. Ex.: 1.5, -0.99, 1700,78 etc. Claramente salta aos olhos que armazenar uma variável real é mais ”caro”(em tempo e em recursos) do que processar uma variável inteira. Aliás, esta é uma das razões porque existem variáveis inteiras. Outra é a caracteŕıstica da enumerabilidade que não está presente no conjunto dos números reais. Caracter Uma variável que pode conter um único caracter, como uma letra, ou um único d́ıgito. O real conteúdo de uma variável caracter depende do código básico que está em uso. Mas, por enquanto, pode-se simplificar esta questão dizendo que qualquer caracter que esteja no teclado do computador pode ser colocado em uma variável caracter. Cadeia ou string É um tipo de variável formado por um ou mais de um caracteres. Por exemplo, um nome: ”JOSE”, ou uma cidade como ”CURITIBA”etc. Ou seja, a diferença entre uma variável caracter e uma variável cadeia é que a primeira tem tamnho 1 (um único caracter) e a segunda tem tamanho maior que um, ou seja, vários caracteres. 1discreta = quantia que exprime valores inteiros, objetos, coisas, enfim grandezas não cont́ınuas 41versão de 23 de janeiro de 2009 ©88-09, Pedro Kantek CAPÍTULO 3. ESCREVENDO ALGORITMOS Lógico ou booleano O nome booleando vem de George Boole, um matemático. É uma variável que pode conter apenas 2 valores, conhecidos pelas palavras: VERDADEIRO e FALSO. Algumas linguagens não têm este tipo (C ou APL, por exemplo) usando artif́ıcios para simular o conceito. O tipo cadeia traz consigo uma pequena dificuldade, que é a necessidade de esta- belecer - quando da definição da variável - qual o seu tamanho máximo, em número de caracteres. Esta atitude é necessária para informar a quem lê o algoritmo (seja um homem ou um computador) quanto de espaço reservar para conter esta variável. Esta dificuldade não existe nas variáveis numéricas nem nas lógicas que tem tamanhos predeterminados e principalmente fixos. Existe uma caracteŕıstica das linguagens de programação conhecida como“tipagem”. Há linguagens de tipagem forte (por exemplo Pascal) e as há de tipagem fraca (por exemplo C). Este conceito tem a ver com restrições e verificações que a linguagem deter- mina ou executa a cada comando. A tipagem forte torna as linguagens um pouco mais demoradas, mas evita erros cometidos pelo programador ao não verificar as operações que comandou. Este tipo de erro, de resto muitas vezes é dif́ıcil de localizar e corrigir, pois o sintoma que surge frequentemente é intermitente e nem sempre tem muito a ver com o real local onde o erro está acontecendo. Outra vertente de linguagens fracamente tipadas é quando a linguagem tem regras de conversão entre tipos diversos e elas são aplicadas antes de qualquer comando. 3.2.2 Código de caracteres No momento de representar caracteres, aparece um problema: “Qual sua lei de formação e representação ?”. Tal problema não aparece nos números: a matemática ajuda. Entre- tanto, não há uma aritmética para caracteres, e portanto precisa-se construir uma série de propriedades e relações entre os caracteres. Para não criar um novo conceito, vai-se aproveitar o código de representação padrão em uso nos computadores atuais. Trata-se do código ASCII (American standard Code for Information Interchange). A seguir, uma parte do próprio: Código de caracteres Existem diversos códigos usados no mundo da computação. O mais usual é o código ASCII (American Standard Code for Intrechange of Informations), embora se usem também o BCD, EBCDIC e mais recentemente haja uma tendência no uso do UNICODE. Como exemplo, eis uma parte do código ASCII. ©88-09, Pedro Kantek versão de 23 de janeiro de 200942 CAPÍTULO 3. ESCREVENDO ALGORITMOS 3.3 Comando de atribuição Comando de atribuição é aquele que permite colocar/alterar valores de conteúdo em variáveis. Para tanto usaremos o śımbolo ←. 2 Quando dizemos expressão, podemos estar querendo dizer “valor” (que é a forma mais simples de expressão), ou simplesmente um conjunto de valores e operadores (que é a definição de expressão). Exemplos: A ← 1 (aqui, a expressão é apenas um valor) B ← 1 + 2 (neste caso, a expressão é um conjunto de 2 valores e uma operação, no caso, a adição) É importante notar, que a expressão que se encontra do lado direito da flecha de atribuição (←) deve ser compat́ıvel com o tipo de variável que foi definida. Em outras palavras, no comando A ← 1+1, a expressão 1+1 tem que ser compat́ıvel com a variável A, ou seja A deverá ter sido definida como inteira ou real, mas não como caracter, cadeia ou lógica. Na atribuição de variáveis do tipo inteira, a expressão deverá ser uma expressão inteira, isto é, sem parte fracionária. Para variáveis do tipo real, a expressão deverá ser numérica sem nenhuma outra restrição. Esta é a única exceção à regra acima, pois podemos colocar um valor inteiro em uma variável real. Na atribuição de variáveis cadeia, o valor deverá estar envolvido entre aspas simples (’). Ele não deverá ter um tamanho maior do que aquele estabelecido para a variável. Se isto acontecer, o valor será truncado. Entretanto, não é boa norma de programação usar esta facilidade (ou caracteŕıstica) pois ela dificulta a compreensão do algoritmo. Finalmente, nas variáveis lógicas, deveremos usar as palavras VERDADEIRO e FALSO, ou quando não houver risco de confusão, podemos usar as abreviaturas F ou V. Exemplos de atribuições: variáveis inteiras X ← 1 XAC ← 1 + 1 + 1 DEV ← 2000 × 23 N ← -1 variáveis reais B ← 1.89 XAD ← 1 ÷ 3 N ← -1.0009 ALF ← 1000900 X ← 1 variáveis cadeia NOME ← ’ALFREDO’ COD ← ’ABCDEabcde’ ALFA ← ’abcde12345’ variáveis lógicas SIM ← VERDADEIRO NÃO ← FALSO VARLOG ← V VARLOG2 ← F 2A questão do śımbolo da atribuição é bem complicada. Poucos ambientes (como o APL) dispõe do śımbolo nativo ←. Os outros improvisam, com os śımbolos := do Pascal, ou simplesmente = do C e Java. No primeiro caso, são 2 śımbolos, ao invés de um único, e no segundo surge a confusão entre A=1 (significando A recebe 1) e A=1 (significando a pergunta: A é igual a 1 ?). Dáı o C e o Java fazerem a pergunta com ==. Não há uma sáıda fácil. 45versão de 23 de janeiro de 2009 ©88-09, Pedro Kantek CAPÍTULO 3. ESCREVENDO ALGORITMOS variáveis caracter NOME ← ’A’ XUNXO ← ’X’ NUM ← ’1’ AST ← ’*’ Duas perguntas a responder: ˆ A ← ’1’ A é variável numérica ou caracter ? ˆ B ← ’V’ B é variável lógica ou cadeia ? Como regra geral, sempre que houver mistura entre elementos inteiros e reais, nas operações +, − e × o resultado será real. Exemplos de uso de operadores em expressões numéricas A ← 1 × 1,78 ÷ 3 B ← trunc(3.1416) C ← abs (-6 + trunc (3.4)) D ← 1 + 10 + 100 - 1000 etc Uma observação final e bem importante é que dentro de um mesmo algoritmo uma variável pode ter diversos (isto é, mais de um) comandos de assinalamento. Isto não é erro, e ao contrário é bem freqüente. Nestes casos, a variável terá o valor que foi nela colocado por último. Por exemplo, em 1: A ← 1 2: ... 3: A ← 10 4: ... 5: escreva (A) 6: ... Se nos comandos representados com ... não houver nenhuma alteração na variável A, o resultado impresso ao final será 10 (e não 1). 3.4 Expressões Expressões são conjuntos de variáveis, valores, operações e eventualmente parênteses, que demandam algum tipo de computação determinada na expressão e produzem um resultado. As expressões se classificam em geral devido ao tipo de operações que existem dentro da expressão, podendo ser aritméticas, condicionais, lógicas e de caracteres. 3.4.1 Aritméticas As expressões aritméticas são aquelas que envolvem variáveis numéricas, valores idem e as operações aritméticas, dando como resultado um número (que obviamente pode ser real ou inteiro). Notação Exponencial Para os casos em que seja necessário representar números muito grandes ou muito pequenos, pode-se lançar mão da notação exponencial, que será escrita de acordo com a seguinte regra: A primeira parte do número será escrita como um número convencional, podendo ter o ponto decimal (constante ponto flutuante) ou não (constante inteira). Depois, vem a letra maiúscula ”E”, indicando ”elevado a”. Um segundo número inteiro, positivo ou negativo indicando a potência de 10 à qual a primeira parte do número está elevada. ©88-09, Pedro Kantek versão de 23 de janeiro de 200946 CAPÍTULO 3. ESCREVENDO ALGORITMOS Por exemplo: o número deve ser entendido como 3E4 3× 104 ou 3× 10000 ou 30000 6.3E-2 6.3× 10−2 ou 6.3× 0.01 ou 0.063 -4.22E6 −4.22× 106 ou −4.22× 1000000 ou -4220000 Operações usuais Função Formato Objetivo Tipos - ope- randos Tipo do re- sultado Exemplo Adição A + B Adicionar A e B inteiro ou real Se A e B são intei- ros, A+B é inteiro. Se pelo menos um dos dois é real, o resultado é real 3 + 7 é 10 Subtração A - B Subtrair B de A inteiro ou real idem ao an- terior 5 - 2 é 3 MultiplicaçãoA × B O produto de A e B inteiro ou real idem ao an- terior 3×12 é 36 Divisão real A ÷ B O quociente de A por B inteiro ou real real 10÷2 é 5 Potência A B A elevado à B inteiro ou real real 25 é 32 Absoluto abs(A) O valor absoluto de A inteiro ou real O mesmo tipo de A abs(4) é 4 Seno Sin(A) seno de A radia- nos inteiro ou real real sin(3.14...) é 1 Cosseno cos(A) cosseno de A ra- dianos inteiro ou real real cos(3.14...) é 0 Inteiro trunc(A) A parte inteira de A real inteiro trunc(2.5)é 2 Fracionário frac(A) A parte fracio- nária de A real real frac(2.5) é .5 Exponencial exp(A) E (2.718...) ele- vado a A inteiro ou real real exp(1) é 2.718 Log Natural log(A) Logaritmo natu- ral de A inteiro ou real real log(1) é 0 Arredondamentoround(A)Arredonda A para o inteiro mais próximo real inteiro round(3.6) é 4 Raiz qua- drada sqrt(A) Raiz quadrada de A inteiro ou real, mas A ( 0 real sqrt(4) é 2 Quadrado sqr(A) O quadrado de A inteiro ou real O mesmo de A sqr(4) é 16 Somar 1 A++ A variável A é incrementada de 1 unidade inteira ou real O mesmo de A Se A é 10, A++ coloca 11 em A. 47versão de 23 de janeiro de 2009 ©88-09, Pedro Kantek CAPÍTULO 3. ESCREVENDO ALGORITMOS suc, pred, ord e chr Para os tipos ordinais pré-definidos (caracter, inteiro e lógico), existem algumas funções que podem ser usadas. Para cada tipo de operandos os universos são: inteiros neste caso, a seqüência de ordenação é aquela dos números inteiros da mate- mática: ... ∞, ..., -2, -1, 0, 1, 2, ... +∞. caracteres aqui a seqüência é dada pelo código nativo do ambiente, no caso o ASCII. booleanos a seqüência é FALSO, VERDADEIRO. Ord A Função ord devolve o ordinal do operando dentro do seu universo original. Assim, a ord de um operando caracter, devolve o ordinal dentro do código ASCII. A ord de um lógico, considera o universo de 2 valores (V e F). e a ord de um número inteiro, é o próprio número inteiro. Embora atue sobre os 3 tipos acima, na verdade ela se aplica verdadeiramente aos caracteres. Por exemplo: ORD(-3) é -3. ord(’a’) é 97. ord(FALSO) é 0. ord(’7’) é 55, ord(’W’) é 87, ord(’z’) é 122, No caso dos caracteres, a resposta à função ord se encontra na tabela vista anteri- ormente. Consultamos o operando de ord na coluna referente a ASCII, e a resposta de ord é o número decimal que estiver na mesma linha. Chr A função chr é a função inversa da função ord, porém só funciona para carac- teres. Dado um número inteiro entre 0 e 255, para o código ASCII e 0 e 64536 para o código UNICODE, a função chr deste número devolve o caractere correspondente a ele. Para simular como o portugol faz isto, dado um número, procura-se na tabela em qual linha ele ocorre sob a coluna decimal, e a seguir responde-se com o caractere ASCII correspondente à mesma linha. Exemplo, CHR(97) é ”a”, etc. Suc Trata-se da função sucessora, que nos devolve o próximo valor ao do operando considerado o seu universo original. Esta função só se aplica a operandos ordinais pré- definidos (inteiro, caracter e lógico). Se o operando for inteiro, a resposta também será. Se o operando for lógico, a resposta também será. Da mesma maneira se o operando for caracter. suc(’a’) é ”b” suc(FALSO) é VERDADEIRO suc(23) é 24, e assim por diante suc(’1’) é ’2’, CUIDADO ====> succ(’9’) é ’:’ e succ(9) é 10. Uma aplicação interessante para esta função é a substituição do incremento de va- riáveis. Por exemplo, em vez de fazer: I ← I + 1; podemos fazer I ← suc(I); ©88-09, Pedro Kantek versão de 23 de janeiro de 200950 CAPÍTULO 3. ESCREVENDO ALGORITMOS Pred Esta função devolve o predecessor, e também só se aplica a ordinais pré-definidos. Também (tal como no suc) o tipo da resposta é o mesmo tipo do operando. Exemplos: pred(’b’) é ”a” pred(FALSO) é VERDADEIRO pred(23) é 22, e assim por diante. 3.4.2 Relacionais As expressões relacionais são as que envolvem os operadores =, 6=, >, ≥, < e ≤. Este operadores visam a estabelecer se uma dada proposição é falsa ou verdadeira. É co- mum em qualquer linguagem de programação, comparar-se 2 valores, perguntando, por exemplo, se o primeiro é maior do que o segundo. A resposta, na forma lógica, dirá se a afirmação é ou não é verdade. São eles: igual (=), diferente (6=), maior (>), maior ou igual (≥), menor (<) e menor ou igual (≤). Estes operadores sempre relacionam duas variáveis ou constantes de tipos compat́ı- veis. Por exemplo ao perguntar 3 > 5?, a resposta será “falso”. Note que não é permitido (ou seja gera-se um erro), misturar valores de tipos distin- tos. Então, a comparação ’A’ 6= 3, embora logicamente pudesse estar correta (ou seja a letra A não é igual ao número 3), dá erro em qualquer linguagem de programação e portanto está proibida de ser usada na construção de algoritmos. A exceção à regra acima é quando se comparam dois números, sendo um deles do tipo inteiro e outro do tipo real. Embora de tipos diferentes (inteiro e real), a matemática permite fazer essa comparação, já que ambos são números. Tem-se então que os operandos poderão ser de qualquer tipo, desde que compat́ıveis, mas a resposta sempre será do tipo lógico. Função Formato Objetivo Operando Resultado Exemplo Igual A = B Comparar o conteúdo de A e de B ambos intei- ros, reals ou alfanuméri- cos .V. se A = B e .F. se A 6= B. 3 = 4 é .F., 66.0 = 66 é .V., ”AB”= ”ab”́e .F. Diferente A 6= B igual ao anterior igual ao an- terior .V. se A 6= B e .F. se A = B. 3 6= 4 é .V., 66.0 6= 66 é .F. ”AB”6= ”AB”́e .F. Maior A > B igual ao anterior ambos intei- ros ou reais .V. se A > B e .F. se A ≤ B. 5 > 2 é .V. 2 > 5 é .F. Maior ou igual A ≥ B igual ao anterior igual ao an- terior .V. se A ≥ B e .F. se A < B. 5 ≥ 2 é .V. 2 ≥ 2 é .V. Menor A < B igual ao anterior igual ao an- terior .V. se A < B e .F. se A ≥ B. 5 < 2 é .F. 2 < 5 é .V. Menor ou igual A ≤ B igual ao anterior igual ao an- terior .V. se A ≤ B e .F. se A > B. 2 ≤ 5 é .V. 2 ≤ 2 é .V. 3.4.3 Lógicas As expressões lógicas envolvem valores lógicos (verdadeiro e falso) conectados por ope- radores lógicos, que são 3: “E” (∧), “OU” (∨) e “NÃO” (¬ ou ∼). Estes operadores 51versão de 23 de janeiro de 2009 ©88-09, Pedro Kantek CAPÍTULO 3. ESCREVENDO ALGORITMOS destinam-se as operações lógicas entre operandos. Eles atuam sobre os valores V (ver- dade) e F (falso). Acompanhe a seguir as tabelas verdade: Em termos verbais a expressão A ∧ B será verdadeira quando A e B forem verdadeiros e será falsa senão. Vendo na tabela a seguir: ∧ verdadeiro falso verdadeiro verdadeiro falso falso falso falso A expressão A ∨ B será verdadeira quando A for verdadeiro ou B for verdadeiro ou ainda quando ambos forem verdadeiros. A expressão só será falsa quando A e B forem falsos. Veja: ∨ verdadeiro falso verdadeiro verdadeiro verdadeiro falso verdadeiro falso Finalmente, a expressão ∼ A (lida como NÃO A), devolve o valor lógico oposto ao de A. Então ∼ verdadeiro é falso e ∼ falso é verdadeiro. ∼ ou ¬ verdadeiro falso falso verdadeiro Função Formato Objetivo Operando Resultado Exemplo E-lógico A ∧ B Realizar a ope- ração E-lógico ambos lógi- cos .V. se A e B são .V., .F. em caso con- trário .V. ∧ .V. é .V. .V. ∧ .F. é .F. .F. ∧ .V. é .F. .F. ∧ .F. é .F. OU- lógico A ∨ B Realizar a ope- ração OU-lógico ambos lógi- cos .V. se A ou B são .V., .F. em caso con- trário .V. ∨ .V. é .V. .V. ∨ .F. é .V. .F. ∨ .V. é .V. .F. ∨ .F. é .F. NÃO- lógico ∼ A ou ¬ A Nega logica- mente A lógico .V. se A é .F. .F. se A é .V. ∼ .F. é .V. ∼ .V. é .F. As palavras “verdadeiro” e “falso” bem como os śımbolos ”V”e ”F” podem ser consi- derados constantes lógicas também chamadas booleanas e podem ser empregados livre- mente na construção dos algoritmos. As duas constantes, formam um conjunto ordenado, e podemos dizer que o F (falso) precede o V (verdadeiro). Como uma ajuda, podemos associar o Falso ao zero, e o Verdadeiro ao 1. Com isto todas as relações numéricas entre 0 e 1 continuam verdadeiras entre FALSO e VERDADEIRO. A grande importância dos valores lógicos em portugol, decorre do fato de que qual- quer comparação usando os operadores relacionais sempre devolve um lógico. A importância das expressões lógicas é que elas permitem conectar duas ou mais expressões relacionais, formando uma nova e maior expressão relacional. Veja-se nos exemplos: ©88-09, Pedro Kantek versão de 23 de janeiro de 200952 CAPÍTULO 3. ESCREVENDO ALGORITMOS Exerćıcio 17 Quanto é 400 mod 51 30 mod 7 (5 mod 4) + (22 div 10) + (3 mod 2) 4376 mod 10 4376 mod 100 4376 mod 1000 4376 mod 10000 10 mod 4 10 div 4 cos (9 div 11) trunc (abs (round (6 div 6))) (1 + 5) mod 3 1 + (5 mod 3) (2 × 4) mod 2 2 × (4 mod 2) 10000 mod 1 5 div 0 Exerćıcio 18 Informe qual o valor final para VAR3 VAR3 ← (3 ≥ 2) ∨ (1 = 3) VAR3 ← (1 + 1) = (3 - 1) VAR3 ← (trunc(1.5 × 4) > 6) ∧ (1 6= 2) Exerćıcio 19 Informe qual o valor da variável VAR2 VAR2 ← VERDADEIRO VAR2 ← ∼ FALSO VAR2 ← ∼ ∼ VERDADEIRO (”...Eu não disse que nunca viajaria...”) VAR2 ← FALSO ∨ FALSO VAR2 ← VERDADEIRO ∧ (∼ VERDADEIRO) VAR2 ← (∼ FALSO) ∨ (∼ VERDADEIRO) VAR2 ← (FALSO OU VERDADEIRO) ∧ (∼ VERDADEIRO) VAR2 ← FALSO ∧ FALSO VAR2 ← FALSO ∨ FALSO VAR2 ← VERDADEIRO ∧ (∼ VERDADEIRO) VAR2 ← VERDADEIRO ∧ VERDADEIRO Exerćıcio 20 Informe qual o valor para a variável VAR4. VAR4 ← ((frac(0.999) - 1) > 0 VAR4 ← 1 = 2 VAR4 ← 1 + 2 = 2 VAR4 ← 0.5 ≥ 2.5 - trunc(2.9000) VAR4 ← 3 > 1 + 1 VAR4 ← 1 + 3 × 4 VAR4 ← 2 × sqr(3 × 2 + 1) VAR4 ← 1 × 2 × 3 × 4 × 0 + 1 VAR4 ← ((2 × 2) + 2) × 3 VAR4 ← 33 > (32 + trunc(2.45) - frac(0.5)) VAR4 ← 0.20 - 0.5 VAR4 ← 2 × 3 × 4 + 2 × 3 × 4 VAR4 ← (4 × (2 ÷ 2 × 2) ≥ 3.5) ∧ (1 = 3 × 0) VAR4 ← (trunc (sen (3.14/2)) = 1) ∧ VERDADEIRO VAR4 ← FALSO ∨ ((1 + 2) > (6 div 3)) 55versão de 23 de janeiro de 2009 ©88-09, Pedro Kantek CAPÍTULO 3. ESCREVENDO ALGORITMOS VAR4 ← (5 div 2) > (trunc (3.5) + frac(3.5)) VAR4 ← 7 ÷ 2 + 2 > 0 VAR4 ← 5 + 5 - 5 VAR4 ← (10 + frac(0) + trunc(0) - 10) > 5 VAR4 ← 5 > 6 div 3 + 2 mod 1 + 0 mod 6 VAR4 ← 2 × 8 ÷ 4 ÷ 2 VAR4 ← (1 + trunc (13.5) × 2) × (1 ÷ (2 + 1)) ©88-09, Pedro Kantek versão de 23 de janeiro de 200956 Caṕıtulo 4 Comandos 4.1 Visão Top down e Bottom up Estes termos, consagrados no jargão da informática, significam maneiras de atacar e resolver um problema em computador. A maneira top down, que pode ser traduzido como ”de cima para baixo”, pressupõe estudar o problema como um todo, e depois ir realizando a montagem do esquema completo, através da execução das partes, mas sem nunca esquecer o modelo completo. A visão bottom up, parte da construção individual de todos os elementos, que poste- riormente são juntados e testados. É posśıvel fazer sistemas de computador usando as duas técnicas. Fazendo uma analogia (meio mambembe, mas vá lá) com a montagem de um carro, na visão top down a primeira coisa a fazer seria juntar a carroceria e as rodas, de maneira que o carro conseguisse se mover. Depois, os diversos sistemas e componentes iriam sendo instalados peça a peça no carro e a cada etapa o carro continuaria a andar em suas próprias rodas. A montagem terminaria quando o carro andasse sozinho. Já na visão bottom up cada um dos sistemas (motor, bancos, instrumentação, ...) seria montado isoladamente, testado e em caso de sucesso levado aonde o carro está sendo constrúıdo e áı posto em conexão com os outros sistemas do carro. O processo também termina quando o carro sair andando. O exemplo não é dos melhores, porque um carro é diferente de um programa de com- putador. Lá se lida com coisas f́ısicas que ocupam espaço e pesam para ser carregadas. Aqui se fala de entidades abstratas (dados e programas). Outro exemplo, este talvez algo melhor é a proposta de escrever um livro. Antes de tudo há que se ter o plano completo da obra, mas depois é posśıvel visualizar a construção top down e a construção bottom up. 4.2 Seqüência de execução Vale lembrar que a menos que o comando em questão determine outro caminho, os comandos dentro de um algoritmo vão sendo executado seqüencialmente, começando no primeiro e terminando no último, e sempre esperando terminar este para começar o próximo. Diz-se nestes casos que o fluxo cai por decantação. Assim, por exemplo, na seqüência 1: A ← 1 2: B ← 2 + A 57 CAPÍTULO 4. COMANDOS 1: se condição então 2: c1 3: c2 4: ... 5: senão 6: c10 7: c11 8: ... 9: fimse ińıcio v condição c1 c2 ... c10 c11 ... fim 4.4.2 Alternativa composta É uma extensão da alternativa simples. Neste caso podemos determinar o que fazer se a condição verdadeira, e o que fazer se a condição for falsa. O formato deste comando é (à esquerda em linguagem algoŕıtmica, portugol, e à direita em fluxograma. Se a condição estabelecida é verdadeira, são executados os comandos c1, c2, ... e não são executados os comandos c10, c11.... Se a condição é falsa, são executados os comandos c10, c11, ..., mas não os primeiros. Neste caso a identação também é importante. Os comandos “se”, “senão” e “fimse” começam na margem corrente. Todos os demais comandos internos a este deixam uma identação de 3 caracteres. Exemplo: 1: DELTA ← 4 × A × C - sqr(B) 2: se DELTA < 0 então 3: escreva (”raizes imaginárias”) 4: senão 5: X ← sqrt(DELTA) 6: fimse ińıcio DELTA ← 4 × A × C - sqr(B) v DELTA < 0 escreva (”raizes imaginárias”) X ← sqrt(DELTA) fim 4.4.3 Alternativas aninhadas Nada impede que exista uma condição dentro de outra, (regra da programação estru- turada) e assim por diante. Nestes momentos a identação é mais importante ainda. Repare no exemplo a seguir: Para ver a vantagem da identação analisar-se-á exatamente o mesmo código, porém escrito sem este recurso: ©88-09, Pedro Kantek versão de 23 de janeiro de 200960 CAPÍTULO 4. COMANDOS 1: se A 6= 0 então 2: B ← 0 3: se C 6= 0 então 4: D ← 0 5: F ← 3 6: fimse 7: G ← 77 8: fimse ińıcio v A 6= 0 B ← 0 v C 6= 0 D ← 0 F ← 3 G ← 77 fim 1: se A 6= 0 2: B ← 0 3: C 6= 0 4: D ← 0 5: F ← 3 6: fimse 7: G ← 77 8: fimse Exerćıcio 21 Reescreva as condições acima usando a condição de igual. Cada se tem que ter um fimse correspondente. Ao percorrer o fluxo, encontrando um fimse encerra-se o último se aberto. Esta regra é importante para determinar o fim de SE’s aninhados. Ao examinar um comando se, deve-se agir da seguinte forma: Se a condição que acompanha o se for verdadeira, os comandos internos ao se devem ser executados. Se, ao contrário, a condição não for verdadeira, então, todos os comandos seguintes devem ser pulados até ser encontrado o comando fimse correspondente. Agora é hora de voltar um pouco na teoria e relembrar o conceito das operações com operadores lógicos (VERDADEIRO e FALSO). Tais operações eram: ∧, ∨ e ∼. Usando-as, em conjunto com o comando se simples ou composto, podemos criar trechos de algoritmo muito ricos. Veja-se alguns exemplos: Definir se um valor esta compreendido entre 10 e 35, inclusive: 1: se VALOR > 9 ∧ VALOR < 36 então 61versão de 23 de janeiro de 2009 ©88-09, Pedro Kantek CAPÍTULO 4. COMANDOS 2: ... valor OK ... 3: senão 4: ... valor ERRADO ... 5: fimse Definir se um valor numérico representativo de um mês, está correto 1: se MES > 0 ∧ MES < 13 então 2: ... mes OK ... 3: senão 4: ... mes ERRADO ... 5: fimse Um certo código pode assumir os seguintes valores: 10, 15, 17, 18 e 30. Testar se ele está ou não correto. 1: se COD = 10 ∨ COD = 15 ∨ COD = 17 ∨ COD = 18 ∨ COD = 30 então 2: ... código OK ... 3: senão 4: ... código ERRADO ... 5: fimse As vezes é mais fácil organizar a sáıda correta através do SENÃO e não do ENTÃO, o que inverte o comando. Vejamos um exemplo. Um indicador estar errado, se assumir os valores: 1, 4, 5, 6, 7, ou 9. Organizar o comando: 1: se IND = 1 ∨ IND = 4 ∨ IND = 5 ∨ IND = 6 ∨ IND = 7 ∨ IND = 9 então 2: ... indicador ERRADO ... 3: senão 4: ... indicador CERTO ... 5: fimse Se entretanto, quiséssemos não inverter as saidas, precisaŕıamos negar as condições. Atente-se a que a negação de um conjunto de OUs é um conjunto de Es. 1: se IND 6= 1 ∧ IND 6= 4 ∧ IND 6= 5 ∧ IND 6= 6 ∧ IND 6= 7 ∧ IND 6= 9 então 2: ... indicador CERTO ... 3: senão 4: ... indicador ERRADO ... 5: fimse Outra maneira de escrever o comando acima, seria: 1: se (IND = 1) ∨ (IND > 3 ∧ IND < 8) ∨ (IND = 9) então 2: ... indicador ERRADO ... 3: senão 4: ... indicador CERTO ... 5: fimse Finalmente, se quiséssemos manter as saidas sem inversão: 1: se (IND 6= 1) ∧ (IND ≤ 3 ou IND ≥ 8) ∧ (IND 6= 9) então 2: ... indicador CERTO ... 3: senão 4: ... indicador ERRADO ... 5: fimse ©88-09, Pedro Kantek versão de 23 de janeiro de 200962 CAPÍTULO 4. COMANDOS Exerćıcio 25 Escrever um algoritmo portugol que receba (não importa como) três valores numéricos (chamados A,B e C), e devolva a informação ”OK”quando se satisfizerem as seguintes condições: (A deve ser maior que 10 e menor do que 100) OU (B deve ser diferente de C E C deve ser maior que 50). Se a condição não for satisfeita, o algoritmo deve devolver a mensagem ”ERRO” 4.5 Estruturas de repetição Para obedecer à terceira estrutura da programação estruturada e visando o reaprovei- tamento de código, ver-se-ão agora as possibilidades de repetir partes do algoritmo. Estas estruturas contém impĺıcito um comando de desvio (go to) e nas linguagens mais modernas é o único desvio que é aceito. Os trechos de programas que são repetidos ao se usar as estruturas de repetição são conhecidos genericamente com o nome de loops ou em português “laços”. Assim, um erro de programação bastante comum é o chamado loop infinito, quando inadvertidamente a condição de sáıda é tal, que nunca é alcançada. 4.5.1 Repetição com condição no ińıcio: enquanto Parece razoável que um algoritmo deve ser criado para a execução de um único conjunto de valores fornecidos como entrada. Por exemplo, ao escrever o algoritmo de aprovação de alunos na cadeira de algoritmos da UP, o programador só precisa se preocupar com um único aluno, pois a regra de um vale para todos. Não teria sentido descrever os mesmos procedimentos para todos os alunos, isto seria interminável, além de deixar o algoritmo espećıfico para um determinado número de alunos. Falando em termos mais genéricos, ao escrever um programa de computador que calcule o salário de um empregado, deve-se imaginar apenas um empregado e não os milhares que o computador processará. A chave para este problema está no reaproveitamento de instruções do algoritmo. Em outras palavras, uma vez escrito o caminho principal do algoritmo (o chamado caminho das pedras), nós vamos fazer todos os funcionários (ou alunos) passarem por este caminho. Uma das chaves para este procedimento é o comando chamado ENQUANTO. Seu formato: enquanto <condiç~ao> faça c1 c2 ... fimenquanto Este comando deve ser assim interpretado. A condição é avaliada. Se ela for falsa, o algoritmo deve saltar todos os comandos subordinados e continuar a execução após o comando fimenquanto. Entretanto, se a condição for verdadeira, os comandos subor- dinados são executados, até se encontrar o comando fimenquanto. Neste momento, há um desvio na seqüência de processamento e um retorno ao comando enquanto. A condição é novamente avaliada. Se falsa, pulam-se os comandos subordinados. Se verdadeira, os comandos são novamente executados, e assim por diante. Se a condição for uma ”verdade eterna”, isto é, algo como 1 = 1, tem-se um laço infinito, pois os comandos nunca deixarão de ser executados. Por outro lado se a con- dição for uma tautologia (sempre falsa), então os comandos subordinados nunca serão executados. Exemplo Calcular a soma dos números inteiros até 100. 65versão de 23 de janeiro de 2009 ©88-09, Pedro Kantek CAPÍTULO 4. COMANDOS 1: SOMA:real 2: NUMERO:inteiro 3: SOMA ← 0 4: NUMERO ← 1 5: enquanto NUMERO < 101 faça 6: SOMA ← SOMA + NUMERO 7: NUMERO ← NUMERO + 1 8: fimenquanto 9: escreva (SOMA) ińıcio SOMA:real NUMERO:inteiro SOMA ← 0 NUMERO ← 1 v NUMERO < 101 SOMA ← SOMA + NUMERO NUMERO ← NUMERO + 1 vNUMERO < 101 escreva (SOMA) fim Comandos internos ao comando“enquanto”devem estar identados de 3 espaços, para clareza. enquanto <condiç~ao> faça <comando-1> <comando-2> ... fimenquanto Por exemplo: 1: leia A 2: enquanto A < 11 faça 3: escreva A 4: A ← A + 1 5: fimenquanto 4.5.2 Repetição com variável de controle: para O segundo comando que se usa para controlar laços, atende pelo nome de para. Ele pressupõe a existência de uma variável de controle que irá (como o nome diz) controlar o ińıcio e o fim do laço. O formato do comando para é para variável DE valor-1 ATÉ valor-2 [PASSO valor-3] faça comando 1 comando 2 ©88-09, Pedro Kantek versão de 23 de janeiro de 200966 CAPÍTULO 4. COMANDOS ... comando n fimpara A regra de funcionamento do para é: ˆ Antes de começar o trecho inclúıdo no para, a variável mencionada no comando é inicializada com o valor-1. ˆ Se este valor for menor ou igual ao valor-2 o trecho subalterno é executado. ˆ Ao chegar ao final dos comandos, a variável é incrementada com o valor-3 (ou com 1 se nada for referenciado) ˆ Há um desvio incondicional, ao ińıcio do comando para, e o teste definido no passo <2> acima é refeito, com idênticas sáıdas. ˆ Dentro dos comandos subalternos ao para, a variável de controle não pode ser alterada pelos comandos escritos pelo usuário. ˆ Os valores 1, 2 e 3 podem ser valores auto-declarados (caso mais comum) ou podem ser quaisquer variáveis numéricas. Neste caso, elas também não podem ser alteradas dentro do para. ˆ Por convenção, quando o valor do passo for 1, toda a cláusula pode ser omitida. Exemplo: o comando PARA K DE 1 ATE 10 equivale ao comando PARA K DE 1 ATE 10 PASSO 1. Uma especial observação deve ser feita quando o valor-3 (o incremento) for negativo. Nestes casos há várias inversões no comando, a saber: ˆ O valor 1 deve ser maior do que o valor 2, já que a variável de controle vai diminuir ao invés de aumentar. ˆ O teste de saida é para maior ou igual, por idêntica razão. Veja-se dois exemplos para ajudar a entender e a guardar estas questões: 1: para J de 1 até 9 passo 2 faça 2: escreva J 3: fimpara Aqui serão impressos os valores 1, 3, 5, 7 e 9. Já em 1: para J de 9 até 1 passo -2 faça 2: escreva J 3: fimpara Serão impressos os valores 9, 7, 5, 3 e 1. Devemos lembrar que todo comando para pode ser convertido em seu equivalente enquanto. Dá mais trabalho (são 3 comandos) mas sempre é posśıvel. Já a rećıproca nem sempre é verdadeira. Só é posśıvel transformar um enquanto em um para equi- valente, quando se souber o número exato de iterações que o enquanto faria. Quando isto for desconhecido a conversão não é posśıvel. Exemplos: usando para equivalente usando enquanto para I de 1 até 10 passo 2 I ← 1 escreva I enquanto (I ≤ 10) fimpara escreva I I ← I + 2 fimenquanto 67versão de 23 de janeiro de 2009 ©88-09, Pedro Kantek CAPÍTULO 4. COMANDOS 2. foram pares; 3. foram inteiros; 4. foram negativos; Exerćıcio Resolvido 1 Escreva um algoritmo que leia uma série de notas (que se encerram quando for lido um número negativo) e ao final escreva as duas maiores notas que apareceram. Por exemplo, se as notas lidas forem 8, 3, 2, 1, 10, 7, 8, 9, 5, 4 e 3, o algoritmo deve imprimir 10, 9 Como o exerćıcio é um pouco mais complexo, vamos ver diversas estratégias para a sua solução: 1. primeira estratégia 1: enquanto ... faça 2: leia(N) 3: se N > P então 4: P ← N 5: fimse 6: se N > S então 7: S ← N 8: fimse 9: fimenquanto DEFEITO: ao final, P e S terão o mesmo valor (o maior) 2. segunda abordagem 1: enquanto ... faça 2: leia(N) 3: se N > P então 4: P ← N 5: fimse 6: se N > S então 7: se N 6= P então 8: S ← N 9: fimse 10: fimse 11: fimenquanto DEFEITO: Com a série 1, 10, 2, 8, 5 → funciona Com a série 1, 8, 7, 2, 9 → não funciona 3. terceira abordagem 1: inteiro NUM, NOT, PNU, PNO, SNU, SNO, X 2: X ← 1 3: PNO ← 0 4: SNO ← 0 5: enquanto X < 100 faça 6: leia (NUM, NOT) 7: se NOT > PNO então 8: se PNO > SNO então 9: SNO ← PNO 10: SNU ← PNU ©88-09, Pedro Kantek versão de 23 de janeiro de 200970 CAPÍTULO 4. COMANDOS 11: fimse 12: PNO ← NOT 13: SNO ← NUM 14: fimse 15: se NOT > SNO então 16: se NOT 6= PNO então 17: SNO ← NOT 18: SNU ← NUM 19: fimse 20: fimse 21: fimenquanto 22: escreva (PNO,PNU) 23: escreva (SNO,SNU) Eis a lista de variáveis usada acima NUM = número do aluno atual NOT = nota do aluno atual PNU = número do aluno com a melhor nota até agora PNO = melhor nota até agora SNU = número do aluno com a segunda melhor nota até agora SNO = segunda melhor nota até agora X = contador até 100 Exerćıcio 31 Definir algoritmo capaz de jogar com o operador o“JOGO DO PALITO”, e de vencer, sempre que posśıvel. Este jogo tem a seguinte regra. ˆ São dois jogadores, a quem chamaremos: máquina (programa) e humano. ˆ O humano escolhe um número de palitos qualquer entre 20 e 30. ˆ A máquina retira 1, 2 ou 3 palitos. ˆ O humano também retira 1, 2 ou 3 palitos, e a seqüência prossegue, até que reste apenas um palito. ˆ Quem tirar o último palito perde. ˆ O programa deve atentar para impedir retiradas diferentes de 1 2 ou 3. Dica: Estratégia vencedora: deixar o adversário sempre com 1, 5, 9, 13, 17, 21, 25 ou 29 Exerćıcio 32 Defina algoritmo que calcule e escreva o somatório expresso pela seguinte série: S = 500 2 + 480 3 + 460 4 + ... + 20 26 Exerćıcio 33 Escreva um algoritmo que leia uma seqüência de números positivos (a condição de fim é a leitura do número -1) e escreva ao final, qual o número mais próximo de 100 que foi lido. DESAFIO: escreva o número par mais próximo a 100. Exerćıcio 34 Escreva um algoritmo que leia uma seqüência de números positivos (a condição de fim é a leitura do número -1) e escreva ao final, qual o último número que foi lido. DESAFIO: escreva o ante-penúltimo, ou -1 se não houver ante-penúltimo 71versão de 23 de janeiro de 2009 ©88-09, Pedro Kantek CAPÍTULO 4. COMANDOS Exerćıcio 35 Dados o seguinte trecho de lógica escritos usando o enquanto, escrever trecho equivalente usando o repita 1: Z ← 10 2: enquanto Z > 0 faça 3: Z ← Z - 3 4: escreva (Z) 5: fimenquanto Exerćıcio 36 Dado o seguinte algoritmo que utiliza o comando repita escrever coman- dos equivalentes usando o comando enquanto. 1: GH ← 5 2: repita 3: escreva (ABC) 4: até GH 6= 5 Exerćıcio 37 Escreva o trecho a seguir, usando 1. o comando Enquanto e 2. o comando Repita 1: para J de 2 até -10 passo -3 faça 2: K ← sqr(J) 3: escreva K 4: fimpara Exerćıcio 38 Escrever um algoritmo que leia um único número (que por definição é maior que 3), e escreva ”PRIMO”se ele for primo, ou ”NÃO PRIMO”se ele for diviśıvel. Por exemplo, se for lido 10, o programa dever dizer ”NÃO PRIMO”, e se for lido 11, dever dizer ”PRIMO”. Exerćıcio 39 Definir algoritmo que leia uma seqüência de valores numéricos inteiros e determine, ao final se eles estavam em ordem ascendente ou não. Se estiverem, deve imprimir ”EM ORDEM”, e se não estiverem, deve imprimir ”FORA DE ORDEM”. Exerćıcio 40 Defina algoritmo que calcule e escreva o somatório expresso pela seguinte série. O número de termos deve ser lido a priori. S = 1 1 2 + 2 1 3 + 3 1 4 + ... + n 1 n + 1 Exerćıcio 41 Escreva o algoritmo que leia N e escreva S, onde S = 1 2 + 2 3 + 3 4 + ... + N N + 1 Exerćıcio 42 Dados o seguinte trecho de lógica escritos usando o enquanto, escrever trecho equivalente usando o repita. 1: A ← 10 2: B ← 20 3: enquanto (A + B) < 50 faça 4: A ← A + 5 5: B ← B + 10 6: escreva (A+B) ©88-09, Pedro Kantek versão de 23 de janeiro de 200972 CAPÍTULO 4. COMANDOS Exerćıcio 54 Escrever um algoritmo, que receba conjuntos de 3 notas de um aluno. O primeiro valor corresponde a média do primeiro semestre. O segundo valor é média do segundo semestre, e o terceiro valor correspondendo a nota final. Existe uma variável no algoritmo (pré-definida) chamada QTD-APROV. Para cada aluno aprovado, o algoritmo deve somar 1 em QTD-APROV. Regra de aprovação: (N1 × 3 + N2 × 3 + N3 × 4)÷ 10 ≥ 7 Os dados terminam quando o primeiro valor da série for negativo. Por exemplo, se QTD- APROV tiver o valor 0, e forem lidas as triplas (5,7,2), (8,8,6), (1,10,5) e (-1,0,0) o resultado final de QTD-APROV será 1. Exerćıcio 55 Definir um algoritmo que leia uma série de pares de valores inteiros que representam COMPRIMENTO e LARGURA de um retângulo. Calcular e imprimir a área do retângulo se o peŕımetro do mesmo for superior a 25. Os dados se encerram quando for lida a dupla zero,zero. Por exemplo, se forem lidas as duplas (2,2), (10,8), (10,1) e (0,0) só será impressa a área 80, equivalente à dupla (10,8). Exerćıcio Resolvido 2 Imagine um relógio analógico de ponteiros. Não existe o ponteiro de segundos, e os ponteiros realizam movimentos discretos, isto é, eles só se movem a cada 60 segundos. Escreva um algoritmo que leia diversos conjuntos de hora e minuto, e para cada conjunto lido, informe qual o menor ângulo que os dois ponteiros fazem entre si ao representar a hora informada. O algoritmo termina quando for lida a dupla 0,0. Os valores permitidos para hora estão entre 0 e 11 e para minuto os valores válidos estão entre 0 e 59. A sáıda do resultado pode ser em graus e décimos de grau, ou se o aluno preferir em graus e minutos. 1: algoritmo ponteiro 2: inteiro h m 3: real ah am qtm angulo 4: leia (h,m) 5: enquanto h 6= 99 faça 6: qtm ← (h * 60) + m 7: ah ← qtm * 0,5 8: am ← qtm * 6 9: enquanto ah ≥ 360 faça 10: ah ← ah - 360 11: fimenquanto 12: enquanto am ≥ 360 faça 13: am ← am - 360 14: fimenquanto 15: se se ah > am então 16: angulo ← ah - am 17: senão 18: angulo ← am - ah 19: fimse 20: se se angulo > 180 então 21: angulo ← 360 - angulo 22: fimse 23: escreva (angulo) 24: leia(h,m) 25: fimenquanto 26: fim{algoritmo} 75versão de 23 de janeiro de 2009 ©88-09, Pedro Kantek CAPÍTULO 4. COMANDOS Exerćıcio 56 Interprete o seguinte trecho de algoritmo, informando (em português) o que faz ou para que serve o algoritmo analisado. Estude e informe a condição de fim. Se necessário, realize um ”chinês”sobre os dados. 1: inteiro CA,CE 2: leia(CA,CE) 3: enquanto CA 6= CE faça 4: se CA < CE então 5: escreva(CA) 6: fimse 7: escreva(CE) 8: leia(CA,CE) 9: fimenquanto Exerćıcio 57 Interprete o seguinte trecho de algoritmo, informando o que faz ou para que serve o algoritmo analisado. Estude e informe a condição de fim. Se necessário, realize um ”chinês”sobre os dados. 1: inteiro A,B,C 2: real X 3: {A é } 4: {B é } 5: {C é } 6: {X é } 7: leia(A) 8: B ← 0 9: enquanto A 6= 0 faça 10: se A < B então 11: B ← A 12: fimse 13: leia(A) 14: fimenquanto 15: escreva (B/2) Exerćıcio 58 Interprete o seguinte trecho de algoritmo, informando o que faz ou para que serve o algoritmo analisado. Estude e informe a condição de fim. Se necessário, realize um ”chinês”sobre os dados. 1: real PI,R,C 2: {R é } 3: {C é } 4: PI ← 3.141592 5: leia(R,C) 6: enquanto (R 6= 0) ∨ (C 6= 0) faça 7: se R = 0 então 8: C ← 2 × PI × R 9: senão 10: R ← C ÷ (2 × PI) 11: fimse 12: escreva(R,C) 13: leia(R,C) 14: fimenquanto Exerćıcio 59 Siga o seguinte algoritmo, e informe quais os valores de A, B, C e D que são impressos ao final. ©88-09, Pedro Kantek versão de 23 de janeiro de 200976 CAPÍTULO 4. COMANDOS 1: inteiro A, B, C, D 2: A ← 0 3: B ← 10 4: C ← B × 3 5: D ← B + C + A 6: enquanto D < 0 faça 7: A ← A + 1 8: D ← D + 1 9: fimenquanto 10: se A > 0 então 11: D ← D × 2 12: senão 13: B ← B × 2 14: fimse 15: escreva (A,B,C,D) A:__________ B:__________ C:__________ D:__________ Exerćıcio 60 Brinquedos“PIRRALHOS ENDIABRADOS”é um grande distribuidor de presentes em todo o páıs. Recentemente, a empresa teve a oportunidade de comprar 15.000 pequenos brinquedos, todos embalados em caixas retangulares. O objetivo da compra, foi colocar cada brinquedo em uma esfera colorida, para revendê-los como surpresa, mais ou menos como o Kinder ovo. Existem esferas de raios 10, 20 e 30 cm. Cada brinquedo, tem um número de ordem, e as suas 3 dimensões A, B e C, medidas em cent́ımetros. Definir um algoritmo que leia 15.000 quádruplas (ordem,A,B,C) e para cada uma delas escreva a ordem do brinquedo e o raio da esfera necessário. Todos os brinquedos caberão em uma das esferas. Exerćıcio 61 Supondo um trecho de código escrito em pseudo-código: 1: para I de 1 até 100 faça 2: para J de 3 até 11 passo 2 faça 3: para K de 5 até 25 passo 5 faça 4: escreva (I,J,K) 5: fimpara 6: fimpara 7: fimpara Imagine que você precisa re-escrever este código e a sua nova linguagem não é estruturada, o que significa que não existem as estruturas para ... fimpara, enquanto ... fimenquanto e nem repita ... até. Você só conta com labels, testes e desvios. Eis como ficaria: 1: algoritmo qualquer 2: I ← 1 3: J ← 3 4: K ← (*1) 5: L1: se (I > 100) 6: vápara FIM 7: senão 8: se (J > 11) 9: vápara L2 10: senão 11: se (K > (*2)) 12: vapara L3 77versão de 23 de janeiro de 2009 ©88-09, Pedro Kantek CAPÍTULO 4. COMANDOS 1: A ← 0 2: enquanto A 6= 3 faça 3: A ← A + 1 4: escreva (A) 5: fimenquanto Exerćıcio 63 Dado o seguinte algoritmo que utiliza o comando repita escrever coman- dos equivalentes usando o comando enquanto. 1: A ← 10 2: repita 3: A ← A + 1 4: até A > 10 Exerćıcio 64 Dado o trecho a seguir, escrito usando o comando para, reescreve-lo usando o comando enquanto 1: para J de 1 até 20 faça 2: X ← J ÷ 3 3: escreva (X) 4: fimpara Exerćıcio 65 Dado o trecho a seguir, escrito usando o comando para, reescreve-lo usando o comando enquanto 1: para SEMENTE de 0 até 100 passo 2 faça 2: SEM1 ← SEMENTE × 2 3: SEM2 ← SEMENTE + 1.5 × ABC 4: MEDIA ← (SEM1 + SEM2) ÷ 2 5: escreva MEDIA 6: fimpara Exerćıcio 66 Escreva o trecho a seguir, usando 1. o comando Enquanto e 2. o comando Repita 1: para K de 5 até 25 passo 3 faça 2: escreva K+1 3: fimpara Exerćıcio Resolvido 3 Dois números são considerados ”amigos”quando um nú- mero é igual a soma dos fatores do outro número. Por exemplo, 220 e 284 são ”amigos”, pois 220 é igual a soma dos fatores de 284 (142,71,4,2,1) e 284 é a soma dos fatores de 220 (110 55 44 22 20 11 10 5 4 2 1). Definir algoritmo que escreva os pares de números amigos existentes entre 1 e 500. 1: inteiro i,j,k,l,m,n 2: inteiro função somf (inteiro a) 3: inteiro var ind,som 4: som ← 0 5: para ind ← 1 to a-1 faça 6: se a mod ind = 0 então 7: som ← som + i 8: fimse 9: fimpara ©88-09, Pedro Kantek versão de 23 de janeiro de 200980 CAPÍTULO 4. COMANDOS 10: retorne som 11: fim{função} 12: para i ← 1 to 500 faça 13: escreva i 14: para j← i to 500 faça 15: m ← somf(i) 16: n ← somf(j) 17: se (m = j) ∧ (n = i) então 18: escreva (i,j) 19: fimse 20: fimpara 21: fimpara Exerćıcio Resolvido 4 Escreva uma função que receba um número inteiro positivo k, calcule e devolva o próximo número primo x, onde k ≤ x. Solução Para resolver este exerćıcio, consideraremos definida e operante a função EPRIMO, com o seguinte cabeçalho lógico funç~ao EPRIMO (inteiro x), que devolve VERDA- DEIRO quando x é primo e FALSO senão. Eis a resposta 1: inteiro função PROXPRIM (inteiro K) 2: enquanto 1=1 faça 3: se EPRIMO(K) então 4: retorne K 5: abandone 6: fimse 7: K++ 8: fimenquanto 9: fimfunção Atente para a condição terminadora do enquanto. Já que a sáıda se dará através do abandone, qualquer condição sempre verdadeira pode ser colocada áı. Exerćıcio Resolvido 5 Você tem uma coleção seqüencial de 10.000.000 de apos- tas na sena. Para cada apostador, existem os 6 números em que ele jogou e mais o número da aposta, que posteriormente identificará o apostador. Suponha uma função lógico ganhou (inteiro a1, a2, a3, a4, a5, a6) que devolve VERDADEIRO se esta aposta é vencedora e FALSO senão. Suponha também que a condição de fim de dados é a leitura de a1 negativo. Solução Para resolver este exerćıcio, duas hipóteses podem ser consideradas: a primeira faz uma dupla leitura (uma fora e outra dentro do loop). 1: algoritmo SENA 2: inteiro a1, a2, a3, a4, a5, a6, apostador 3: leia (a1, a2, a3, a4, a5, a6, apostador) 4: enquanto a1 > 0 faça 5: se ganhou (a1, a2, a3, a4, a5, a6) então 6: escreva apostador 7: fimse 8: leia (a1, a2, a3, a4, a5, a6, apostador) 9: fimenquanto 10: fim{algoritmo} 81versão de 23 de janeiro de 2009 ©88-09, Pedro Kantek CAPÍTULO 4. COMANDOS A segunda abordagem, faz apenas uma leitura, mas a função é nitidamente menos limpa e clara: 1: algoritmo SENA2 2: inteiro a1, a2, a3, a4, a5, a6, apostador 3: a1 ← 1 {poderia ser qualquer valor maior que zero} 4: enquanto a1 > 0 faça 5: leia (a1, a2, a3, a4, a5, a6, apostador) 6: se a1 > 0 então {pode ter chegado o negativo} 7: se ganhou (a1, a2, a3, a4, a5, a6) então 8: escreva apostador 9: fimse 10: fimse 11: fimenquanto 12: fim{algoritmo} Exerćıcio Resolvido 6 Seja agora a tarefa, muito comum em programação, de obter números constrúıdos segundo uma certa lei de formação, a prinćıpio desconhecida. Só se conhecem os primeiros números de uma seqüência deles, e o que é pedido, é o resto dos números. Por exemplo, se a seqüência for 1,2,3,4,5,6 e for pedido o próximo número, a resposta é 7, por que a lei de formação é a dos números naturais. Entretanto, outras seqüências podem ser menos evidentes e conseqüentemente mais trabalhosas. Vejamos alguns exemplos: 5 7 9 11 13 15 17 ... 19 1 4 9 16 25 36 49 ... 64 4 7 12 19 28 39 52 ... 67 8 14 24 38 56 78 104 ... 134 5 8 13 20 29 40 53 ... 68 4 11 30 67 128 219 346 ... 515 16 25 36 49 64 81 100 ... 121 512 729 1000 1331 1728 2197 2744 ... 3375 36 144 324 576 900 1296 1764 ... 2304 8 64 216 512 1000 1728 2744 ... 4096 Uma estratégia é pesquisar os posśıveis valores de x, y e z, usando intuição, pistas, experiências passadas, ao estilo de Sherlock Holmes. Uma segunda estratégia é usar da informação de que 2 ≥ x, y, z,≤ 7 e adotar a força bruta, fazendo 1: para X de 2 até 7 faça 2: para Y de 2 até 7 faça 3: para Z de 2 até 7 faça 4: para I de 1 até 10 faça 5: escreva ... 6: fimpara 7: escreva ... 8: fimpara 9: fimpara 10: fimpara Exerćıcio 67 Escrever um algoritmo que leia uma série indeterminada de números positivos. A leitura deve prosseguir até ser lido o número 1203, quando o programa dar a mensagem “1203 ENCONTRADO” e terminar o processamento. Se este número não for encontrado, ao final dos dados (quando for lido um número negativo) o programa deve ©88-09, Pedro Kantek versão de 23 de janeiro de 200982 CAPÍTULO 4. COMANDOS Definir algoritmo que receba uma série de vendas no formato (valor, estado) e para cada uma informe a quantidade de bônus de direito. Os dados terminam quando for lido um estado igual a ’XX’ ou um valor de vendas negativo. Exerćıcio 80 Definir um algoritmo que leia uma série de números inteiros e positivos (condição de fim: leitura de um negativo). O algoritmo deve calcular e imprimir a média dos números lidos EXCLÚIDOS os zeros. Exerćıcio 81 Existe um conjunto de muitos números inteiros e positivos, agrupados três a três. Deve-se escrever um algoritmo capaz de: ˆ Ler os três números ˆ Identificar o maior deles, e rejeitá-lo ˆ Calcular a média entre os dois números restantes ˆ Imprimir os dois números selecionados e a média. A pesquisa termina quando o primeiro número dos três lidos, for negativo. Exerćıcio 82 Dados conjunto de 20 pares de números, realizar sobre eles o seguinte processamento: ˆ Se ambos forem pares, eles devem ser somados ˆ Se ambos forem ı́mpares, devem ser multiplicados ˆ Se um for par e outro ı́mpar, deve-se imprimir zero. Para cada conjunto lido, deve-se imprimir os dois números e o resultado obtido segundo as regras acima. Exerćıcio 83 Uma eleição é anulada se a somatória de votos brancos e nulos é superior à metade dos votos totais. Suponha que numa eleição existem 3 candidatos e para apurá-la, deveremos ler um conjunto indeterminado de votos (números inteiros), usando a regra: ˆ 1 = voto no candidato número 1 ˆ 2 = voto no candidato número 2 ˆ 3 = voto no candidato número 3 ˆ 8 = voto em branco ˆ 9 = voto nulo. A entrada de dados termina quando for lido um voto igual a zero. Caso ocorra um empate, dever ser vencedor o candidato mais velho. As idades são: 1=55 anos, 2=58 anos e 3=47 anos. Escrever um algoritmo que: 1. Verifique se a eleição foi válida 2. Se foi, quem a venceu. Exerćıcio 84 Escreva um algoritmo que leia uma sequëncia de números positivos (a leitura é um depois do outro, por restrição do problema não se pode usar um vetor) com condição de fim igual a leitura de um número negativo e escreva o último número lidos que tenha sido maior que 100. 85versão de 23 de janeiro de 2009 ©88-09, Pedro Kantek CAPÍTULO 4. COMANDOS Exerćıcio 85 Calcular a soma total e o produto total de uma série de números inteiros e positivos que serão fornecidos. A série termina quando for lido o número -1. Exerćıcio 86 Escreva um algoritmo capaz de move atribúıdas a atletas de ginástica oĺımpica. Tal como na prática, este algoritmo deve eliminar a maior e a menor notas, e a seguir calcular e imprimir a média entre as duas notas restantes. ©88-09, Pedro Kantek versão de 23 de janeiro de 200986 Caṕıtulo 5 Nassi-Schneiderman Fluxos e Nassi-Schneiderman Além da maneira pela qual descreveremos nossos algoritmos (que é através do Portugol), existem outras formas de representar algoritmos. Falaremos de mais duas: a primeira é a linguagem dos fluxogramas. Tem importância histórica na informática, pois foi a primeira (e durante muito tempo única) representação de programas e similares. A seguir uma lista dos principais śımbolos usados em fluxogramas Iniciador/terminador Processo Alternativa Conector Entrada/saída Fluxo de processamento Fluxogramas perderam sua condição de únicas ferramentas, entre outras razões, pelas a seguir expostas: ˆ Prestam-se mal à programação estruturada, pois permitem a construção de algo- ritmos não estruturados. ˆ Exigem capricho, dando muito trabalho para serem feitos e mantidos. ˆ São necessárias quantidades enormes de papel, pois há um overhead muito grande, isto é, só se escreve dentro dos quadrinhos, e boa parte do papel se perde. ˆ Embora hoje já existam programas para fazer e guardar fluxos em computador (como por exemplo o FLOWCHART e o AUTOFLOW), eles não são muito prá- ticos para este trabalho. Assim para seguir a tendência moderna (que é guardar matriz da documentação em computador e não em papel) o fluxograma resulta incômodo. 87 CAPÍTULO 5. NASSI-SCHNEIDERMAN raciocinar, a ponta da lapiseira fica sobre o ponto de interrupção. A tabela de valores das variáveis vai sendo lida (consultada) e escrita (alterada) durante o chines Decisão Quando o algoritmo e o chines terminam, um resultado é obtido. Então, ele é comparado com o resultado esperado, acima calculado. Se for diferente, um erro aconteceu. Raras vezes é no processo manual de obtenção do resultado, mas quando isso ocorre o algoritmo pode estar certo e é o resultado obtido que está errado. Mas, na maioria das vezes, é o algoritmo que está errado. É hora de procurar o erro e refazer todo o ciclo. Se ambos são iguais, o algoritmo funcionou para este caso de teste. Quanto deste funcionamento adequado pode ser generalizado para qualquer caso de testes fica em aberto. Exerćıcio 87 Faça um chines com o algoritmo a seguir: 1: inteiro função CALCU (inteiro A, B) 2: se A ≥ B então 3: devolva A 4: senão 5: devolva B 6: fimse ©88-09, Pedro Kantek versão de 23 de janeiro de 200990 Caṕıtulo 6 Visualg O VISUALG é um programa que auxilia o aprendizado de algoritmos na medida em que permite a entrada e execução de um algoritmo escrito em portugol, conforme aqui descrito. Escrito pela empresa Apoio, pode ser obtido em www.apoioinformatica.com.br. 6.1 Regras de Visualg Em visualg, valem as regras: ˆ cada comando de visualg deve estar em uma linha ˆ não há separadores (;), nem blocos (como { e {) nem goto ˆ todas as palavras reservadas não tem acentos ou cedilha ˆ não há separação entre maiúsculas e minúsculas nos comandos ou variáveis ˆ o limite de variáveis é de 500 (cada item de vetor conta como 1 variável) ˆ o ponto decimal é o ponto ˆ valores caractere estão entre aspas duplas ˆ O śımbolo de atribuição é <-. Na verdade são dois śımbolos ˆ Existe recursividade Algoritmo É a unidade básica de escrita de algoritmos. formato 1: algoritmo <nome> 2: var 3: variáveis 4: — se houver, a função entra aqui 5: inicio 6: comandos 7: fimalgoritmo exemplo 1: algoritmo ”teste” 2: var 3: N : inteiro 4: inicio 5: leia (N) 6: escreva (N * 2) 7: fimalgoritmo Comentários são caracterizados por começar por \\. 91 CAPÍTULO 6. VISUALG Função A função é uma unidade não autônoma de programação. Ela sempre precisa receber seus dados (através de uma lista de parâmetros) e devolver um resultado a quem a chamou. Em Visualg são colocadas imediatamente antes da palavra inicio do bloco a que se referem. Formato 1: funcao <nome>( <parametros>) : <tipo-resultado> 2: var 3: variáveis locais 4: inicio 5: comandos 6: ... retorne ... 7: fimfuncao Exemplo 1: funcao ”teste”(N : inteiro; A, B:real) : inteiro 2: var 3: inicio 4: retorne (N * 2) 5: fimfuncao O <nome-de-função> obedece as mesmas regras de nomenclatura das variáveis. Por outro lado, a <seqüência-de-declarações-de-parâmetros> é uma seqüência de [var] <seqüência-de-parâmetros>: <tipo-de-dado> separadas por ponto e v́ırgula. A presença (opcional) da palavra-chave var indica pas- sagem de parâmetros por referência; caso contrário, a passagem será por valor. Por exemplo, eis alguns cabeçalhos de funções 1: funcao CALC22 (A, B : inteiro; C : real) : real Definiu-se uma função de nome CALC22, que recebe 3 parâmetros, sendo os dois primeiros inteiros e o terceiro real. A função devolve um resultado real. 1: funcao EQA6 (X : inteiro) : inteiro Definiu-se uma função de nome EQA6, que recebe um único número inteiro e devolve outro número inteiro. 1: funcao EXA (var X : inteiro) A função EXA recebe um parâmetro inteiro. A presença da palavra var implica em que a passagem é por referência, ou seja o que a função modificar na variável X permanecerá modificado após o retorno da função EXA. Nomes Ao construir algoritmos é necessário dar nomes a muitas coisas. A regra de construção de nomes é ˆ Uma única palavra ˆ Composta de letras e números ˆ Começando com uma letra ˆ Escrita em maiúsculo Tipos Os tipos posśıveis são 4: inteiro, real, lógico, caracter. ©88-09, Pedro Kantek versão de 23 de janeiro de 200992 CAPÍTULO 6. VISUALG Expressão Lógica Qualquer combinação compat́ıvel de expressões relacionais e/ou lógicas que acabem gerando um único resultado lógico. Formato O que faz Exemplo E Em A E B, devolve VERDADEIRO se A e B são verdadeiros e devolve FALSO senão VERDADEIRO E VERDA- DEIRO é VERDADEIRO Todas as outras combinações dão FALSO Ou Em A OU B, devolve VERDADEIRO se A ou B ou ambos são VERDA- DEIRO e devolve FALSO senão FALSO OU FALSO é FALSO To- das as outras combinações dão VERDADEIRO Não (NAO) Inverte o valor lógico do operando NAO VERDADEIRO é FALSO e NAO FALSO é VERDADEIRO Se Este comando é denominado alternativo, pois permite escolher caminhos da pro- gramação dependendo de uma condição (expressão lógica). Note que o trecho entre sen~ao e o comando imediatamente anterior a fimse são opcionais, razão pela qual no formato eles aparecem entre colchetes. Os comandos entre ent~ao e sen~ao ou fimse (se não houver senão) serão executados apenas se a condição do comando for verdadeira. Se houver comandos entre sen~ao e fimse os mesmos serão executados apenas se a condição for falsa. formato se <condição> entao comando1 comando2 ... senao comando11 comando12 fimse exemplo se A >= 4 entao B < − B + 1 C < − C + D + A X < − 0 senao escreva (N * 2) Y < − 0 fimse Enquanto Este comando permite a realização de laços (loops) dentro de programas. Começando o comando, a condição é avaliada. Se ela for falsa, há um desvio para o comando seguinte ao fimenquanto. Se a condição for verdadeira os comando internos ao enquanto são executados. Ao se encontrar o fimenquanto há um desvio incondicional ao ińıcio do enquanto e a condição inicial é reavaliada. formato enquanto < condição > faca comando1 comando2 ... fimenquanto exemplo A < − 5 enquanto A <= 9 faca escreva (A) A < − A + 3 fimenquanto serão impressos os valores 5 e 8. Repita Este comando também permite a realização de laços (loops) dentro de progra- mas. 95versão de 23 de janeiro de 2009 ©88-09, Pedro Kantek CAPÍTULO 6. VISUALG formato repita comando1 comando2 ... ate < condição > exemplo A < − 5 repita escreva (A) A < − A + 3 ate A > 9 serão impressos os valores 5 e 8. Para Este comando também permite a realização de laços (loops) dentro de programas. No ińıcio a variável citada no comando é inicializada com <constante1>. Depois é feita a condição. Se o passo está ausente ou é positivo, a variavel é testada para ≤ <constante2>. (Se o passo é negativo, o teste é com≥). Se o resultado é VERDADEIRO os comandos internos são executados. Ao final deles, a variável é incrementada (ou decrementada se o passo é negativo) e depois há um retorno ao teste inicial. Quando o passo não é explicito, ele vale 1. formato para <var> de <constante1> ate <constante2> [passo <constante3>] faça comando1 comando2 ... fimpara exemplo para K de 3 ate 8 passo 2 faca escreva (A) fimpara serão impressos os valores 3, 5 e 7. Retorne Usado exclusivamente dentro de funções, tem a finalidade de devolver um resultado a quem chamou esta função. Ao contrário do ”C”, não necessariamente encerra a execução da função. formato retorne < expressão compat́ıvel > exemplo se A > 5 entao retorne A fimpara Outros Comandos aleatorio arquivo <nome-de-arquivo> algoritmo ”lendo do arquivo”arquivo ”teste.txt” timer on / timer off pausa debug eco cronômetro 6.2 Exemplos de Visualg Exemplo 1 algoritmo "primos" var J,K,R: inteiro ©88-09, Pedro Kantek versão de 23 de janeiro de 200996 CAPÍTULO 6. VISUALG funcao QP(N: inteiro): inteiro var A,B:inteiro inicio A <- 2 B <- 1 enquanto B <= N faca se EPRIMO(A) entao B <- B + 1 fimse A <- A + 1 fimenquanto retorne A - 1 fimfuncao funcao EPRIMO(M: inteiro): logico var QT,DI:inteiro inicio QT <- 0 DI <- 2 enquanto DI < M faca se M % DI = 0 entao QT<- QT + 1 fimse DI <- DI + 1 fimenquanto retorne QT = 0 fimfuncao inicio leia (J,K) R <- QP(K)-QP(J) escreva (R) escreva (QP(K)) escreva (QP(J)) fimalgoritmo Exemplo 2 algoritmo "palito" var N,SEQ,J,TV:inteiro inicio N<-0 enquanto ((N<20) ou (N>30)) faca escreval ("com quanto comecamos ?") leia (N) fimenquanto enquanto (N>0) faca SEQ <- 1 enquanto ((N-SEQ)>=0) faca 97versão de 23 de janeiro de 2009 ©88-09, Pedro Kantek