Algorítmos Material Completo

Embed Size (px)

Citation preview

  • Algoritmos

    Metodologia de desenvolvimento

    Verso: Fevereiro de 2008(Primeira Verso: Fevereiro de 2004)

    Prof. Camilo de Llis M. Pereira *

    * Prof. Camilo de Llis M. PereiraTrabalha com Informtica e Educao desde o incio dos anos 90. Tendo atuado como Desenvolvedor, Consultor, Professor e Coordenador em diversas Instituies e Universidades da regio. Atualmente Professor Titular do IFET SE MG.Mestre em Engenharia de Produo pela UFSC; Especialista em Docncia Superior; Graduado em Informtica e Licenciado em Matemtica.Material disponvel no site do autor: www.clmp.web44.net

  • ALGORITMOS

    Metodologia de desenvolvimento

    1. Metodologia de desenvolvimento de algoritmos1.1. Introduo Cincia da Computao1.2. O conceito de algoritmos1.3. Programao Estruturada1.4. Linguagens de programao1.5. Portugol

    1.5.1. Constantes e Variveis1.5.2. Clculos1.5.3. Entrada e sada1.5.4. Estruturas bsicas de controle: seqencial, condicional e repetio

    1.6. Metodologia de desenvolvimento de algoritmos1.7. Regras prticas para a construo de algoritmos legveis1.8. Exerccios1.9. Mximas de programao

    2. Programao em uma linguagem de alto nvel2.1. Introduo linguagem de programao Pascal2.2. O ambiente de desenvolvimento2.3. Tabela de converso de comandos2.4. Exerccios

    3. Tipos estruturados3.1. Agregados homogneos: vetores e matrizes3.2. Agregados heterogneos: registros3.3. Aplicaes e exerccios

    4. Noes de modularizao4.1. Introduo aos mdulos4.2. Procedimentos4.3. Funes4.4. Passagem de parmetros4.5. Recursividade4.6. Exerccios

    5. Noes de arquivo5.1. Organizao e armazenamento de dados em memria secundria5.2. Instrues utilizadas5.3. Aplicao exemplo

    6. Bibliografia

    2

  • 1. Metodologia de Desenvolvimento de Algoritmos

    Introduo Cincia da ComputaoEvoluo tecnolgica dos computadoresO ComputadorA estrutura de um computador digital / Memria / UCP / Perifricos

    Conceituao de algoritmoO conceito central da programao e da cincia da computao o algoritmo.

    Programar basicamente construir algoritmos. Wirth apresenta a programao estruturada como a arte ou tcnica de construir e formular algoritmos de uma forma sistemtica. Programas so segundo Wirth formulaes concretas de algoritmos abstratos, baseados em representaes e estruturas especficas de dados.

    Nesta definio aparece o outro aspecto fundamental da construo de programa: as estruturas de dados usadas no algoritmo para representar as informaes do problema a ser resolvido. De fato, no processo de construo de programas, a formulao do algoritmo e a definio das estruturas de dados a serem usadas esto intimamente ligadas.

    Um algoritmo a descrio de um padro de comportamento, expressado em termos de um repertrio bem definido e finito de aes primitivas, das quais damos por certo que elas podem ser executadas

    Programao EstruturadaBasicamente, a Programao Estruturada consiste numa metodologia de projeto

    de programas visando: Facilitar a escrita dos programas; Facilitar a leitura (o entendimento) dos programas; Permitir a verificao a priori dos programas; Facilitar a manuteno e modificao dos programas.

    Para Dijkstra, o indiscutvel iniciador da programao estruturada, a arte de programar consiste na arte de organizar e dominar a complexidade.

    A idia bsica da Programao Estruturada, que vai ao encontro da mencionada tarefa do programador, reduzir a complexidade, em trs nveis:

    a) Desenvolvimento do programa em diferentes fases por refinamento sucessivo (desenvolvimento top-down);

    b) Decomposio do programa total em mdulos funcionais, organizados de preferncia num sistema hierrquico;

    c) Usando dentro de cada mdulo s um nmero muito limitado de estruturas bsicas de fluxo de controle.

    Linguagens de programaoConceito / Exemplos / Compilador / Linguagem de mquina

    3

  • Portugol

    O Portugol uma pseudolinguagem de programao (simbiose do Portugus com o ALGOL e PASCAL). A idia permitir que com um conjunto bsico de primitivas seja possvel ao projetista pensar no problema e no na mquina que vai executar o algoritmo e, por outro lado, no fique muito distante da mesma mquina. Em outra perspectiva, que o projetista possa pensar na soluo do problema e que esta soluo seja facilmente implementada no computador.

    ConstantesUma constante um determinado valor fixo que no se modifica ao longo do

    tempo, durante a execuo de um programa.Uma constante pode ser numrica, lgica ou literal.

    VariveisSabe-se da Matemtica que uma varivel a representao simblica dos

    elementos de um certo conjunto.Nos algoritmos, destinados a resolver um problema no computador, a cada

    varivel corresponde uma posio de memria, cujo contedo pode variar ao longo do tempo durante a execuo de um programa. Embora uma varivel possa assumir diferentes valores, ela s pode armazenar um valor a cada instante.

    Toda Varivel identificada por um nome ou identificador.

    Declarao de variveis Tipos Bsicos Inteiro Real Caracter Lgico

    Operadores Lgicos e (conjuno)ou (disjuno no exclusiva)no (negao)

    Operadores relacionais=, , >, >=,

  • Exerccios Variveis e expresses lgicas

    1. Variveis - Assinale os tipos de dados abaixo, da seguinte maneira: (I) inteiro, (R) real, (C) caracter e (L) lgico.

    ( ) -678( ) 0,87( ) -9,12( ) Verdadeiro( ) 456( ) 99,8( ) Cinco( ) 45,8976( ) Falso( ) 1.56

    2. Nome de varivelO nome de uma varivel utilizado para sua identificao e posterior uso dentro de um programa, sendo assim, necessrio estabelecer algumas regras de utilizao das mesmas:

    1. Nomes de variveis podero ser atribudos com um ou mais caracteres;2. O primeiro caracter do nome de uma varivel no poder ser em hiptese alguma, um nmero,

    sempre dever ser uma letra;3. O nome de uma varivel no poder possuir espaos em branco;4. No poder ser nome de uma varivel, uma palavra reservada a uma instruo de programa

    constante da linguagem em uso;5. No podem ser utilizados outros caracteres a no ser letras (sem acento) e nmeros, com exceo

    do smbolo underline.

    Assinale com um X os nomes vlidos para uma varivel.( ) ENDEREO( ) 21BRASIL( ) FONE$COM( ) NOMEUSURIO( ) NOME_USUARIO( ) NOME*USURIO( ) END*A-6( ) CIDADE3( ) #CABEC

    3. Expresses lgicas Determine o resultado lgico das expresses abaixo, assinalando se so verdadeiras ou falsas. Considere para as respostas os seguintes valores: X=1, A=3, B=5, C=8 e D=7.

    Verdadeiro Falsoa) no (X>3)b) (XD)c) no (D5)d) no (X>3) ou (CB) ou (C>B)f) (X>=2)g) (X=D)h) (D5)i) no (D>3) ou no (BB) ou no (C>B)

    5

  • Entrada e Sada

    Entrada / Sada

    leia (v1, v2, v3, .., vn);

    imprima (v1, v2, .., vn);

    imprima (O valor :, valor);

    Exemplos:1. Elaborar um algoritmo que leia um nome e o imprima na tela.2. Leia nome e sobrenome e os imprima juntos.3. Leia dois nmeros inteiros.4. Leia trs nmeros reais e os imprima na tela

    Clculos

    Comando de atribuio ( )Soma a + b;

    Operadores Aritmticos+ adio- subtrao* multiplicao/ divisoraiz(x) raiz

    Funes Matemticas: sen(x), cos(x), tg(x), arctg(x), abs(x), int(x), ...

    A m mod i (A recebe o resto da diviso inteira de m por i )A m div i ( A recebe o quociente da diviso inteira de m por i)

    Exemplos:1. Elaborar um algoritmo que leia dois ns e imprima a sua soma.2. Leia trs nmeros, calcule e imprima a sua mdia aritmtica.3. Leia dois ns e imprima a sua soma, diferena, produto e quociente.4. Calcule a rea de um tringulo.

    6

  • Estruturas de Controle

    Deve-se usar, tanto quanto possvel, somente algumas estruturas bsicas de fluxo de controle: a seqncia simples, a alternativa e a repetio, que correspondem a formas de raciocnio intuitivamente bvias.

    Seqncia simples

    C1;C2;...Cn;

    Alternativa (simples) Alternativa (composta)

    se ()ento

    C1;C2;...Cn;

    fim-se;

    se ()ento

    C1;C2;...Cn;

    seno C1; C2; ... Cn; fim-se;

    Repetio

    enquanto () faaC1;C2;...Cn;

    fim-enquanto;

    Exemplos:1. Elaborar um algoritmo que leia dois ns e informe o maior.2. Leia trs ns e informe o maior.3. Leia a nota de um aluno e informe aprovado (nota>=60) ou reprovado

    (nota

  • Metodologia de desenvolvimento de algoritmos

    Passo 1: Leia cuidadosamente a especificao do problema at o final.(fazer anotaes)

    Passo 2: Repetir o passo 1 at entender completamente a especificao.

    Passo 3: Levantar e analisar todas as sadas.

    Passo 4: Levantar e analisar todas as entradas.

    Passo 5: Verificar se preciso gerar valores internamente ao algoritmo e levantar as variveis necessrias e os valores iniciais de cada uma.

    Passo 6: Levantar e analisar todas as transformaes necessrias para, dadas as entradas e valores gerados internamente, produzir as sadas especificadas.

    Passo 7: Testar cada passo do algoritmo, verificando se as transformaes intermedirias executadas esto conduzindo aos objetivos desejados. Utilizar, sempre que possvel, valores de teste que permitam prever os resultados a priori.

    Passo 8: Fazer uma reavaliao geral, elaborando o algoritmo atravs da integrao das partes.

    Regras prticas para a construo de algoritmos legveis

    1. Procure incorporar comentrios no algoritmo. Em Portugol comentrios podem ocorrer em qualquer parte do algoritmo, encerrados entre {...} ou entre (*...*).Mnimo: objetivo, autor, data e local.

    2. Escolha nomes de variveis que sejam significativos, isto , que traduzam o tipo de informao a ser armazenada na varivel.

    3. Grife todas as palavras-chave (escritas com letras minsculas) do algoritmo, destacando as estruturas de controle.

    4. Procure alinhar os comandos de acordo com o nvel a que pertenam, isto , destaque a estrutura na qual esto contidos.

    8

  • Exerccios Diversos

    1. Elaborar um algoritmo que calcule a rea de um trapzio, suas dimenses so fornecidas pelo teclado.

    2. Construir um algoritmo para calcular e imprimir a mdia aritmtica de diversos valores naturais fornecidos pelo teclado, o flag -1.

    3. Elaborar um algoritmo para contar quantas vezes possvel subtrair 3 de 1000 (considere os nmeros naturais).

    4. Um determinado material radioativo perde metade de sua massa a cada 50 segundos. Dada a massa inicial em gramas (atravs do teclado), pede-se elaborar um algoritmo que determine o tempo necessrio para que essa massa se torne menor que 0,5 gramas. Devero ser impressas a massa inicial, a massa final e o tempo calculado em horas, minutos e segundos.

    5. Elaborar um algoritmo que determine o maior e o menor nmero de uma srie de nmeros inteiros positivos fornecidos pelo teclado. Considere que existe pelo menos um nmero e -1 o flag.

    6. Construir um algoritmo para calcular as razes de uma equao do 2 grau, sendo que os coeficientes a,b e c so fornecidos pelo teclado.

    7. Escrever um algoritmo para calcular o fatorial de um nmero N, cujo valor fornecido pelo teclado.

    8. Supondo que a populao de um pas A seja da ordem de 90 milhes de habitantes com uma taxa anual de crescimento de 3% e que a populao de um pas B seja aproximadamente de 200 milhes de habitantes com uma taxa anual de crescimento de 1,5%, elaborar um algoritmo que calcule e imprima o nmero de anos necessrios para que a populao do pas A ultrapasse ou se iguale a populao do pas B. (mantidas essas taxas de crescimento)

    9. Elaborar um algoritmo que leia o nome e o sexo de uma pessoa, informando o nome seguido da palavra homem (sexo = masculino) ou mulher (sexo = feminino).

    9

  • Exerccios Alternativas e deciso

    1. Dia da semana - Elaborar um algoritmo que l um nmero de 1 a 7 e informa o dia da semana correspondente, sendo domingo o dia de nmero 1. Se o nmero no corresponder a um dia da semana, mostrada uma mensagem de erro.

    2. Tringulo - Em um tringulo, cada lado menor do que a soma dos outros dois. Escreva um programa que l trs valores e informa se estes no podem constituir um tringulo ou, caso contrrio, se o tringulo formado equiltero (trs lados iguais), issceles (dois lados iguais) ou escaleno (lados diferentes).

    3. Faixa etria - Fazer um algoritmo que leia nome e idade de uma pessoa e determine se esta pessoa criana (at 12 anos), adolescente (de 12 at 21 anos), adulto (de 21 at 60 anos) e idoso (acima de 60 anos).

    4. Menu Principal - Faa um programa de menu que mostra na tela, sob o ttulo de "Menu Principal", trs opes: "1 - Fim", "2 - Cadastro" e "3 - Consulta", l do teclado a opo desejada pelo usurio e mostra uma mensagem confirmando a opo escolhida ou uma mensagem de erro, se a opo for invlida.

    5. Mltipla Escolha - Elaborar uma questo de mltipla escolha, de uma disciplina que esteja cursando ou um tema de interesse, com um enunciado e cinco alternativas, sendo uma correta ou incorreta. Escrever um programa que mostra a questo na tela, pede a resposta correta e informa ao usurio se este acertou ou errou.

    6. Senha - Elabore um programa que l uma senha de at 8 caracteres, verifica se a senha est correta ou no, comparando-a com uma senha predefinida, e informa "Acesso autorizado" ou "Acesso negado", conforme o caso.

    7. Desconto - Uma loja de departamentos possui a seguinte poltica de descontos para com seus clientes:5 % de desconto no preo total para compras com valores inferiores ou iguais a R$ 50,0010 % de desconto no preo total para compras com valores entre R$ 50,00 e R$ 100,0015 % de desconto no preo total para compras com valores superiores ou iguais a R$ 100,00

    Elaborar um algoritmo para automatizar a situao.

    8. Geometria - Para facilitar a tarefa dos alunos de uma escola, um professor de matemtica necessita de um programa para calcular a rea de certas figuras planas. O usurio deve escolher qual figura que se deseja calcular a rea (quadrado, retngulo, tringulo e circunferncia). Devem ser fornecidos os valores para clculo da rea. Ao final o programa deve imprimir o nome da figura escolhida, bem como sua rea.

    9. Salrio - Elaborar um algoritmo que efetue o clculo do reajuste de salrio de um funcionrio. Considere que o funcionrio dever receber um reajuste de salrio de 15% caso seu salrio seja menor que 500. Se o salrio for maior ou igual a 500 e menor ou igual a 1000, seu reajuste ser de 10%; e caso maior que 1000, o reajuste dever ser de 5%.

    1

  • Exerccios Repetio

    1. Egocentrismo Elaborar um algoritmo que mostra seu nome na tela dez vezes.

    2. mpares - Apresentar todos os nmeros mpares situados na faixa de 0 a 50.

    3. Pares - Apresentar todos os nmeros pares situados na faixa de 0 a 50.

    4. Soma dos cem Calcular e apresentar a soma dos nmeros inteiros de 1 a 100 (1+2+3+...+98+99+100).

    5. Divisibilidade por 5 Elaborar um algoritmo que fornea como sada os nmeros divisveis por 5, situados na faixa de 1 a 100.

    6. Temperatura - A converso de graus Farenheit para Celsius obtida por C = 5/9*(F 32). Faa um algoritmo que calcule e escreva uma tabela de centgrados em funo de graus Farenheit, cujos graus variam de 50 a 150 de 1 em 1.

    7. Aplicao - Faa um programa que receba o salrio de um funcionrio chamado Jos. Sabe-se que o funcionrio Manoel tem um salrio equivalente a um tero do salrio de Jos. Jos aplicar seu salrio integralmente na caderneta de poupana, que est rendendo 1% ao ms e Manoel aplicar seu salrio integralmente no fundo de renda fixa, que est rendendo 3% ao ms. Calcule e mostre a quantidade de meses necessrios para que o valor pertencente a Manoel iguale ou ultrapasse o valor pertencente a Jos.

    8. Valores - Faa um programa que leia um conjunto no determinado de valores, um de cada vez, e escreva uma tabela com cabealho, que deve ser repetido a cada 20 linhas. A tabela dever conter o valor lido, seu quadrado, seu cubo e sua raiz quadrada. Finalizar a entrada de dados com um valor negativo ou zero.

    9. Fibonacci - Construir um algoritmo para escrever os termos da seqncia de Fibonacci (1, 1, 2, 3, 5, 8, 13, 21, ...) inferiores a um valor L.

    10. Tabuada - Elaborar um algoritmo que leia um nmero inteiro de 1 a 9, e fornea como sada a sua tabuada de multiplicao.

    11. Asteriscos - Elaborar um algoritmo que receba a nota de 10 alunos e a cada nota recebida imprima um grfico da seguinte maneira:

    nota = 4, Aluno 1 ****nota = 7, Aluno 2 *******...

    12. Cidades - Uma turma de Sistemas de Informao, possui alunos oriundos de diversas cidades. Sendo as principais: Juiz de Fora, Leopoldina, Rio Pomba e Cataguases. Elaborar um algoritmo que leia o nome e a respectiva cidade de origem de seus 50 alunos. Ao final imprima o total de alunos por cidade.

    1

  • Mximas de programao

    1. Algoritmos devem ser feitos para serem lidos por seres humanos.2. Escreva comentrios no momento em que estiver escrevendo o algoritmo.3. Os comentrios devem, acrescentar alguma coisa.4. Use comentrios no prlogo (cabealho: o que algoritmo faz e instrues para o

    seu uso).5. Utilize espaos em branco para melhorar a legibilidade.6. Escolha nomes representativos para suas variveis.7. Um comando por linha sufuciente.8. Em expresses matemticas utilize parnteses para aumentar a legibilidade e

    prevenir-se contra erros.9. Utilize identao para mostrar a estrutura lgica do algoritmo.10. Lembre-se: toda vez que for feita uma modificao no algoritmo, os comentrios

    associados devem ser alterados, e no apenas os comandos. Antes no comentar do que deixar algum comentrio errado.

    Exerccio: A telemar est interessada em saber qual foi o maior n de impulsos no ms e quantos assinantes atingiram este valor. Sabe-se que os valores dos pulsos sero fornecidos pelo teclado, sendo uma entrada por assinante. A ltima entrada contm o valor 1 e no deve ser considerada. Os resultados devem fornecer o maior n de impulsos do ms e o n de assinantes que atingiram este valor.

    1

  • 2. Programao em uma linguagem de alto nvel

    Linguagem Pascal

    A primeira implementao da linguagem foi desenvolvida por Niklaus Wirth no Instituto de Informtica da ETH em Zurique na Sua, onde era professor.

    O professor Wirth, especificou e sistematizou a linguagem como uma evoluo do Algol (Algoritmic Language) e o nome Pascal foi uma homenagem ao matemtico e filsofo francs Blaise Pascal (1623-1662), criador da primeira calculadora mecnica.

    A primeira especificao foi definida em 1968 e sofreu modificaes no incio da dcada de 70.

    A linguagem Pascal uma linguagem com caractersticas voltadas programao estruturada.

    uma linguagem extremamente simples e poderosa e, no sendo voltada para nenhuma aplicao especfica, permite a sua implementao em atividades comerciais, cientficas, domsticas e principalmente em atividades educacionais, pois vrios educadores defendem a linguagem para promover o primeiro contato entre alunos que tenham interesse na programao.

    O ambiente de desenvolvimento

    Para trabalhar com a linguagem Pascal voc vai precisar de um compilador, um linkeditor e um editor de textos.

    Para facilitar o processo de programao foram criados os ambientes de desenvolvimento, que unem estas caractersticas, alm de oferecer outros recursos.

    Em nossas aulas utilizaremos o ambiente de desenvolvimento Pascal Zim, disponvel para download em http://pascalzim.tripod.com/index.html. Que une algumas vantagens, entre elas: possuir interface grfica e no apresentar custo.

    ExemplosRealizar a converso utilizando a tabela e o ambiente de desenvolvimento.

    ExercciosPraticar a converso dos algoritmos construdos anteriormente.

    1

  • Tabela de conversoPortugol Pascal Java

    Estruturaincio

    fim.

    program nome;var begin

    end.

    public class Ex1 { public static void main(String[ ] args) {

    }}

    Variveisinteiro: x,y,z;

    var x, y, z : integer;

    inteiro = integerreal = reallgico = Boolean (true, false) caracter = stringchar = string de apenas uma posiobyte = n inteiros de 0 at 255

    inteiro = int ou shortreal = double ou floatlgico = booleancaracter = Stringcharbyte

    Operadores Aritmticos + , - , * , /, div, mod +, -, *, (double) /, /, %Operadores Lgicos >, =, , =,

  • 3. Tipos estruturados3.1. Agregados homogneos: vetores e matrizes3.2. Agregados heterogneos: registros3.3. Aplicaes e exerccios

    Agregados homogneos: vetores e matrizes (Arrays)Vetores (uma dimenso)Matrizes (duas ou mais dimenses)

    Comandos Extrasrepita C1; C2; ...at (Condio);

    para v de i at f faa (passo p) C1; C2; ...fim-para;

    Definio de novos tipostipo V = array [Li1..Lsl, Li2 .. Ls2, ... ] tipo bsico;V: VETOR;

    Exemplo (Vetor)tipo V = array [1..80] real;V : NOTAS;

    1 2 3 ... 805.0 3.0 6.5 ... 9.8

    Nmero de elementosO nmero de elementos de um vetor ser dado por: Ls - Li + 1.

    Percorrendo o vetortipo V = array [1 .. 80] real;V: NOTAS;inteiro: I;

    para I de 1 at 80 faa leia(NOTAS[I]);fim-para;

    1

  • Exerccios - Vetores e Matrizes

    ***VETORES

    1. Um professor tem uma turma de 80 alunos e deseja calcular e imprimir a nota de cada aluno seguida da mdia da turma. As notas sero fornecidas pelo teclado. Elaborar um algoritmo para automatizar a situao.

    2. Elaborar um algoritmo que defina e leia dois vetores A e B com 20 elementos inteiros cada, calcule e imprima o vetor SOMA.

    3. Fornecer o nmero de elementos de cada uma das estruturas abaixo:a) VET [-5 .. +5] b) NOME [0 .. 10] c) OC [1..10] d) ARR [O .. N]

    4. Dado o vetor VET, definido por:tipo V = array [1 .. 100] inteiro; V: VET;

    a) preench-lo com o valor inteiro 30; b) preench-lo com o nmeros inteiros 1, 2, 3, ..., 100;c) preencher VET[i] com 1, se i quadrado perfeito, e com O, nos demais casos.

    5. Escreva um algoritmo que: a) Leia um conjunto A de 100 elementos reais;b) construa e imprima um outro conjunto B formado da seguinte maneira:

    i) os elementos de ordem par so os correspondentes de A divididos por 2. ii) os elementos de ordem mpar so os correspondentes de A multiplicados por

    3.

    6. Elaborar um algoritmo para calcular e imprimir o nmero de alunos que tiraram nota acima da nota mdia da turma. Preencher o vetor com valores aleatrios (funo RANDOM), a turma tem 40 alunos.

    ***MATRIZES

    7. (EXEMPLO) Escreva um algoritmo que leia duas matrizes reais de dimenso 3x5, calcule e imprima a soma das matrizes.

    8. Dada uma matriz M de 5x3 elementos literais (fornecida pelo teclado), faa um algoritmo para:a) Percorrer a matriz linha por linha (fixe a linha, varie a coluna).b) Percorrer a matriz coluna por coluna (fixe a coluna, varie a linha).

    9. Dada uma matriz MAT de 4x5 elementos (fornecida pelo teclado), faa um algoritmo para somar os elementos de cada linha gerando o vetor SOMALINHA. Em seguida, somar os elementos do vetor SOMALINHA na varivel TOTAL que deve ser impressa ao final.

    1

  • ***EXTRAS

    10. (MTODO DA BOLHA) Elaborar um algoritmo que leia um vetor A de 20 elementos inteiros e o classifique em ordem crescente.

    11. (BUSCA SEQENCIAL E BUSCA BINRIA) Dado um vetor A de 128 elementos inteiros, verificar se existe um elemento igual K (chave) no vetor. Se existir, imprimir a posio onde foi encontrada a chave; se no, imprimir: 'chave K no encontrada'. O vetor A e a chave K so fornecidos pelo teclado.

    *PESQUISA: Exerccios 10 e 11Referncia: GUIMARES, Lajes. Algoritmos e Estruturas de Dados. LTC Editora.

    12. (PROJETO) Codificar um programa capaz de verificar em um vetor de 1000 elementos inteiros qual o maior e menor nmero, a mdia aritmtica dos nmeros e a quantidade de nmeros pares e impares. O programa dever inicialmente preencher o vetor com nmeros aleatrios entre 0 e 1000, para isso sugiro a utilizao da funo random.

    13. (MEGASENA) Elaborar um aplicativo capaz de sortear palpites para a Megasena. O programa deve receber como entrada o nmero de cartes e o nmero de palpites por carto, fornecendo como sada os palpites sorteados.

    1

  • Agregados heterogneos: registrosO registro uma estrutura de dados agregada, assim com o vetor, mas difere no fato de cada componente poder ser de um tipo diferente.O registro a abstrao de uma estrutura real muito conhecida, a ficha de cadastro.

    Observe:Ficha cadastral

    Nome (caracter)Salrio (real)Idade (inteiro)Sexo (lgico)

    Assim definimos um registro como um conjunto de campos, que podem ser de tipos diferentes.

    Definio do computador:

    tipo R = registro caracter[30]: NOME; real: SALARIO; inteiro: IDADE; lgico: SEXO;fim-registro;R: REG;

    Memria:REGNOMESALARIOIDADESEXO

    Acesso e atribuio de valoresA atribuio de valores s variveis que compem um registro pode ser qualificada da seguinte maneira:

    REG.NOMEFulano de Tal;REG.SALARIO800,00;REG.IDADE30;REG.SEXOverdadeiro;

    Arquivo

    1

    Nome ______(1)Salrio________Idade__ Sexo__

  • Um registro sozinho no faz muito sentido, da surge o conceito de arquivo. Um arquivo um conjunto de registros. O que tambm uma abstrao da realidade.

    Exemplo:Elaborar um algoritmo que receba: nome, nota e situao(aprov. ou reprov.) dos 15 alunos de uma turma. Armazene os dados em um arquivo(vetor de registros). Ao final imprima a lista completa.

    inicio{Definies}

    tipo reg=registrocaracter: nome;real: nota;lgico: situacao;

    fim-registro;tipo vet=vetor[1..15] reg;vet: turma;inteiro: i;

    {Entrada}para i de 1 at 15 faa

    leia(turma[i].nome);leia(turma[i].nota);se (turma[i].nota>=60)

    ento turma[i].situacaoverdadeiroseno turma[i].situacaofalso

    fim-se;fim-para;

    {Sada}para i de 1 at 15 faa

    imprima(turma[i].nome);imprima(turma[i].nota);se (turma[i].situao=verdadeiro)

    ento imprima(Aprovado)seno imprima(Reprovado)

    fim-se;fim-para;

    fim.

    Exerccios Registros

    1. Defina o registro para cada uma das situaes abaixo:a) Coleo de livros.b) Coleo de CDs.c) Clientes de uma empresa.d) Setores de uma empresa.

    2. Elaborar um algoritmo que permita o cadastro do nome, idade, sexo e cidade dos alunos de sua turma. Ao final imprima a lista completa dos alunos cuja cidade Juiz de Fora.

    3. (PROJETO) Elaborar um algoritmo que permita o controle dos dados de seus amigos(mximo 100), atravs de um arquivo (vetor de registros). Implemente as operaes de cadastro, consulta e alterao.

    1

    12...

    15

    ...

    Turma

    Nome

    Nota

    Situacao

    Reg

  • 4. Noes de modularizao4.1. Introduo aos mdulos4.2. Procedimentos4.3. Funes4.4. Passagem de parmetros4.5. Recursividade4.6. Exerccios

    Introduo aos mdulosModularizar um programa dividi-lo em pequenos mdulos (sub-rotinas, rotinas,

    blocos) cuja caracterstica principal a de que cada mdulo deve possuir uma funo especfica.

    Vantagens: eliminao de trechos de um ou mais programas com funes redundantes, facilita a codificao e a manuteno.

    Os mdulos so representados pelos PROCEDIMENTOS (PROCEDURES) ou FUNES (FUNCTION).

    ProcedimentosProcedure (parmetros);var ;begin

    ;End;

    FunesA nica diferena real entre funes e procedures que as funes tem um valor

    de retorno, enquanto os procedimentos no retornam um valor, por isso no cabealho da funo temos que definir o tipo do resultado da funo. Isto feito ao se adicionar dois pontos e um tipo ao cabealho.

    function (parmetros) : ;var ;begin

    ;End;

    2

  • ExemploProgram SubP1;// Variveis Globaisvar N: Integer;

    // Mdulosprocedure Fatorial(X: Integer);// Variveis Locaisvar I, F: Integer;begin F := 1; for I := 1 to X do begin F := F * I; end; writeln(F);end;

    // Programa Principalbegin readln(N); Fatorial(N);End.

    Program SubP2;// Variveis Globaisvar N: Integer;

    // Mdulosfunction Fatorial(X: Integer) : integer;// Variveis Locaisvar I, F: Integer;begin F := 1; for I := 1 to X do begin F := F * I; end; Fatorial:=F;end;

    // Programa Principalbegin readln(N); writeln(Fatorial(N));end.

    Escopo de variveis de um programaO escopo de uma varivel define a parte do programa em que a varivel

    acessvel. O importante saber que uma varivel significativa somente dentro de seu escopo, ou seja, somente dentro do bloco em que ela declarada. Voc no pode usar uma varivel fora do seu escopo.

    Diz-se que um bloco externo a outro, quando o segundo faz parte do primeiro. Nesse sentido, uma varivel declarada em um bloco global para todos os blocos internos e local para o prprio bloco.

    Variveis Globais: So declaradas no mbito (escopo) do programa principal, valendo, portanto, para todo o programa.

    Variveis locais: Existem somente enquanto a sub-rotina est sendo executada. Ao terminar a sub-rotina, a mesma retirada da memria, levando consigo suas variveis locais, deixando seus valores perdidos.

    Passagem de ParmetrosTanto os procedimentos (procedures) como as funes (functions) podem receber

    valores ou variveis quando da ativao das mesmas. Estes elementos so chamados de parmetros.

    Os parmetros so declarados no cabealho da procedure atravs de uma lista de parmetros. Os parmetros usados na codificao da procedure devem coincidir em nmero, ordem e tipo com os descritos na chamada da procedure. Podemos ter passagem de parmetros por valor ou por referncia.

    Passagem de Parmetros por Valor: Quando a passagem feita por valor, o procedimento ou funo trabalha com uma cpia local dos parmetros passados, qualquer alterao do seu valor no interior do procedimento ou funo no pode ser devolvido referida fonte.

    * Resolver exerccio no. 1

    2

  • Passagem de Parmetros por Referncia: A passagem de parmetros por referncia indica ao procedimento ou funo o endereo da varivel e, por consequncia, todas as alteraes efetuadas no interior do procedimento ou funo sero devolvidadas referida fonte. Os parmetros a serem passados por referncia devero ter na definio da sub-rotina na frente do nome do parmetro a palavra VAR.

    Exemplo//Passagem de parmetros por valor

    Program SubP3;var N: Integer;

    procedure Fatorial(X: Integer);var I, F: Integer;begin F := 1; for I := 1 to X do begin F := F * I; end; writeln(F);end;

    begin readln(N); Fatorial(N);end.

    //Passagem de parmetros por referncia

    Program SubP4;var N, FAT: Integer;

    procedure Fatorial2(X: Integer; var F: integer);var I: Integer;begin F := 1; for I := 1 to X do begin F := F * I; end;end;

    begin readln(N); Fatorial2(N, FAT); writeln(FAT);end.

    2

  • RecursividadeDiz-se que uma FUNCTION ou uma PROCEDURE recursiva, quando ela

    chama a si prpria. Esta caracterstica pode, a princpio parecer estranha, ou at mesmo desnecessria devido ao nvel de programas o qual estamos trabalhando, mas o uso da recursividade muitas vezes, a nica forma de resolver problemas complexos. No nvel que ser dado este curso, bastar saber o conceito e o funcionamento de uma sub-rotina recursiva.

    Exemplo// Recursividade

    Program SubP5;var N: Integer;

    function Fatorial(X : integer) : integer;beginif (X

  • 5. Noes de arquivo5.1. Organizao e armazenamento de dados em memria secundria5.2. Instrues utilizadas5.3. Aplicao exemplo

    ARQUIVOS

    Um arquivo de suma importncia nos programas computacionais, desde o tempo em que o primeiro computador surgiu, pois, para que um programa faa algum tipo de operao, o mesmo precisa ser alimentado com informaes fornecidas pelo teclado, o que em muitos casos torna-se invivel, ou so fornecidos atravs de um arquivo.

    O PASCAL, possui dois tipos de arquivos, os quais so:

    Arquivos FILE Arquivos TEXTFILE

    ARQUIVO FILE

    Um arquivo do tipo FILE, tambm conhecido por arquivo randmico, ou de acesso aleatrio, caracterizado pelo fato de ser possvel buscar uma determinada informao em qualquer posio que a mesma se encontre, sem haver a necessidade de se percorrer todo o arquivo at se alcanar a informao desejada. O acesso a informao direto.

    A sintaxe geral para definir uma varivel com esse tipo de estrutura :

    Type Arquivo = File of ;

    Var a : Arquivo;

    Para tanto, existem diversos comandos para executar tais operaes e que passaremos a examinar agora.

    AssignFile: Este comando tem a finalidade de atribuir um nome lgico ao arquivo fsico, ou seja, ao nome do arquivo em disco.

    Sintaxe: Assign( Varivel_tipo_file, Nome_arquivo);

    Type Arquivo = File Of Integer;

    Var Arq : Arquivo;Begin Assign(Arq,'A:EXEMPLO.DTA');

    2

  • A partir desse instante, todas as operaes de escrita ou leitura que forem realizadas com a varivel Arq, ser automaticamente feitas no arquivo EXEMPLO.DTA no drive A.

    Rewrite: Cria e abre para Entrada\Sada um arquivo. Caso o arquivo no exista, o mesmo ser criado. Caso o arquivo j exista, todos os dados existentes nele sero apagados.

    Type Arquivo = File Of Integer;Var Arq : Arquivo;Begin Assign(Arq,'A:EXEMPLO.DTA'); Rewrite(Arq);

    Reset: Este comando abre o arquivo em disco associado varivel Arq para leitura ou escrita. Esta procedure parte do princpio que o arquivo exista em disco, caso ele no exista, haver erro.

    Type Arquivo = File Of Integer;Var Arq : Arquivo;Begin Assign(Arq,'A:EXEMPLO.DTA'); Reset(Arq);

    Write: Este comando utilizado para escrever dados em um arquivo. Os dados so gravados sequencialmente no arquivo, ou seja, um aps o outro. Para tanto a linguagem Pascal mantm um apontador de registro de arquivo que aponta sempre para o nmero do registro, onde ser gravado ou lido um dado.

    Type Arquivo = File Of Integer; Var Arq : Arquivo; I: Integer; Begin Assign(Arq,'A:EXEMPLO.DTA'); Rewrite(Arq); For I:=1 to 100 do Write(Arq,I);

    Seek: Como j dissemos anteriormente, a linguagem Pascal mantm um apontador de registro que indica o prximo registro que ser lido ou escrito, e toda vez que fazemos uma leitura ou escrita num registro, o apontador incrementado de um, isto

    2

    Aps estas declaraes, teremos um novo arquivo no drive A com o nome EXEMPLO.DTA, aberto e pronto para as operaes de entrada e sada.

    Aps estas declaraes, o arquivo no drive A com o nome 'EXEMPLO.DTA' est aberto e pronto para as operaes de entrada e sada.

    Grava no arquivo A:EXEMPLO.DTA os nmeros de 1 a 100.

  • automtico. No entanto, dispomos de um comando que nos permite alterar o valor desse apontador e portanto, nos permite acessar qualquer registro que quisermos. Esse comando chama-se Seek. A proprsito, o nmero do primeiro registro zero. A sintaxe deste comando :

    Seek(Arq,nmero_do_registro);

    Read: Comando para ler dados do arquivo, cuja sintaxe Read(Arq,varivel).

    Type Arquivo = File Of Integer; Var Arq: Arquivo; I: Integer; Begin Assign(Arq,'A:EXEMPLO.DTA'); Rewrite(Arq); For I:=1 to 100 do Write(Arq,I); Seek(Arq,0); (posiciona o apontador de registro no registro nmero 0)

    Read(Arq,I); (a varivel I fica igual ao contedo do registro nmero 0 que no presente exemplo valeria 1,a proprsito, o apontador de registro j est valendo 1)

    Read(Arq,I); (I agora est valendo 2)

    Observao: Aps cada operao READ/WRITE no arquivo, o endereo do registro corrente no arquivo incrementado em uma unidade. Assim por Exemplo, se o endereo do registro corrente igual a 10, aps uma operao de READ/WRITE, o registro corrente passar a ser o nmero 11.

    Close: Fecha um arquivo que tenha sido aberto com RESET\REWRITE, cuja sintaxe Close(Arq).

    Eof: Funo que retorna o valor TRUE quando for encontrado o fim do arquivo.

    While not eof(arquivo) do begin x:=x+1; Seek (arquivo,x); end;

    FilePos: Funo que retorna o nmero do registro corrente. Lembramos novamente, que o primeiro registro recebe o nmero zero. Sintaxe: FilePos(Arquivo).

    FileSize: Funo que retorna o nmero de registros de um determinado arquivo. Retorna zero se o arquivo estiver vazio. Esta funo em conjunto com o comando Seek,

    2

  • nos permite colocar o apontador de registros para o final do arquivo. Isto muito til quando desejamos adicionar mais registros num arquivo. Para tanto, basta declarar a seguinte instruo: Seek(Arquivo,FileSize(Arquivo));

    Erase: Elimina o arquivo do disco. importante notar que o arquivo a ser eliminado no pode estar aberto.

    Rename: Renomeia um arquivo. Sintaxe: Rename( Arq : File , Novo_Nome)

    ExerccioCodificar um programa para manipular informaes de um arquivo de registros, onde cada registro possui dois campos: nome e nota. O programa permitir somente duas operaes: Incluso e Consulta. A Consulta dever mostrar todos os registros.

    ARQUIVO TEXTFILE

    Um arquivo do tipo TEXTFILE, tambm conhecido por arquivo seqencial, um tipo especial de arquivo que, ao contrrio do arquivo FILE, pode ser editado normalmente atravs de um editor de textos qualquer. Ele dito seqencial porque a leitura tem que ser feita seqencialmente do incio ao fim do arquivo, no podendo desta forma, como feito no arquivo FILE atravs do comando SEEK, posicionar de forma direta, o ponteiro de arquivo em um registro em particular.

    Nos arquivos do tipo TEXTFILE, todas as informaes l armazenadas so texto (String's), mesmo assim, possvel escrever no arquivo informaes de qualquer tipo de dado simples (INTEGER, REAL, STRING, BYTE, etc) as quais , ao serem fisicamente armazenadas no arquivo, sero automaticamente convertidas do seu tipo original para o tipo STRING. A leitura se processa de forma inversa, ou seja, quando lida uma informao em um arquivo TEXT, a mesma ser automaticamente convertida para o tipo da varivel que ir armazenar a informao, isto , do tipo STRING para o tipo da varivel receptora da informao lida.

    Existem uma grande quantidades de comandos especialmente para manipular arquivos TEXTFILE, alguns dos quais j foram vistos (Assign, Rewrite, Reset, Close, Write, Writeln, Read, Readln, etc). Portanto veremos a seguir outros comandos:

    Append: Abre um arquivo para incluso de novas informaes do tipo Write-Only ( somente para escrita). Caso o arquivo no exista ocorrer um erro de execuo e o programa ser abortado. importante notar que as incluses se processam sempre no final do arquivo.

    Write ou Writeln: Ao ser usado o comando WRITE, todas as informaes sero escritas no arquivo na mesma linha. Ao ser usado o comando WRITELN, todas as informaes sero colocadas uma em cada linha

    Read ou ReadLn: Ao ser usado o comando READ, a leitura ser feita sempre na mesma linha , como acontece quando se usa este comando para ler informaes pelo

    2

  • teclado. Por outro lado, ao ser usado o comando READLN, as leituras sero feitas linha a linha, como acontece quando se usa este comando para leitura pelo teclado.

    Exerccios

    1. Codificar um programa capaz de solicitar ao usurio a digitao de uma frase. Cada frase digitada pelo usurio dever ser gravada em uma linha de um arquivo.

    2. Codificar um programa capaz fazer o inverso do projeto anterior. Cada linha do arquivo dever ser lida e mostrada para o usurio.

    2

  • 6. BibliografiaGUIMARES, Lajes. Algoritmos e Estruturas de Dados. LTC Editora.FARRER, Harry et al. Algoritmos Estruturados. Ed. Guanabara.AVILLANO, I. C. Algoritmos e Pascal. Cincia Moderna.MANZANO, Jos Augusto N. G.; MENDES, Sandro S. Vicca. Estudo Dirigido, Delphi. So Paulo: Ed. rica, 2001.

    2

    1. Metodologia de Desenvolvimento de AlgoritmosLinguagens de programaoPortugolConstantesVariveis

    Declarao de variveis Tipos BsicosEntrada / SadaSeqncia simples seno

    RepetioRegras prticas para a construo de algoritmos legveisExerccios DiversosMximas de programaoLinguagem PascalO ambiente de desenvolvimentoExemplosRealizar a converso utilizando a tabela e o ambiente de desenvolvimento.Exerccios

    Tabela de conversoPortugolPascalJavaEstrutura

    fim.var

    end.Variveisinteiro = int ou short

    Operadores Aritmticos+, -, *, (double) /, /, %Operadores LgicosExpresses de AtribuioComentrios// ...Entrada e SadaRepetio (1)Condio (1)Repetio (2)for (int I=0; I