Baixe Algoritmo e Tecnicas de Programação e outras Notas de estudo em PDF para Algoritmos, somente na Docsity! FABRAI ALGORIMTOS E TÉCNICAS DE PROGRAMAÇÃO PROFa. Juliana Santiago Teixeira Índice ÍNDICE..............................................................................................................................................................2 1. O COMPUTADOR: HARDWARE/SOFTWARE.....................................................................................3 1.1. HARDWARE ..............................................................................................................................................3 1.1.1. Introdução .......................................................................................................................................3 1.1.2. Representação das Informações ......................................................................................................3 1.1.3. Componentes do Hardware .............................................................................................................4 1.2. SOFTWARE ...............................................................................................................................................7 1.2.1. Introdução .......................................................................................................................................7 1.2.2. Linguagens de Programação...........................................................................................................7 1.2.3. Categorias de Software ...................................................................................................................8 2. SISTEMAS DE NUMERAÇÃO ..................................................................................................................9 2.1. INTRODUÇÃO............................................................................................................................................9 2.2. O SISTEMA BINÁRIO DE NUMERAÇÃO......................................................................................................9 2.3. O SISTEMA HEXADECIMAL DE NUMERAÇÃO..........................................................................................10 3. DESENVOLVIMENTO DE PROGRAMAS............................................................................................11 3.1. FASES PARA A SOLUÇÃO DE UM PROBLEMA:...........................................................................................11 3.2. ALGORITMOS .........................................................................................................................................11 3.2.1. Definição de Algoritmos................................................................................................................11 3.2.2. Por que precisamos de algoritmos? ..............................................................................................12 3.2.3. Característica................................................................................................................................13 4. PORTUGOL................................................................................................................................................14 4.1. ESTRUTURA SEQÜENCIAL ......................................................................................................................14 4.2. CONSTANTES..........................................................................................................................................14 4.3. VARIÁVEIS .............................................................................................................................................14 4.3.1. Identificadores...............................................................................................................................15 4.3.2. Tipos de dados...............................................................................................................................15 4.3.3. Declaração de variáveis................................................................................................................16 4.3.4. Declaração de constantes..............................................................................................................16 4.4. OPERAÇÕES BÁSICAS .............................................................................................................................16 4.4.1. Operadores aritméticos .................................................................................................................17 4.4.2. Operadores relacionais .................................................................................................................18 4.4.3. Operadores relacionais .................................................................................................................18 4.4.3. Funções .........................................................................................................................................19 4.4.5. Prioridade de operadores..............................................................................................................19 4.5. COMANDOS DE ENTRADA E SAÍDA .........................................................................................................20 4.5.1. Comando de entrada de dados ......................................................................................................20 4.5.2. Comando de saída de dados ..........................................................................................................21 4.6. COMANDO DE ATRIBUIÇÃO ....................................................................................................................22 4.7. ESTRUTURA CONDICIONAL ....................................................................................................................22 4.7.1. Alternativa Simples........................................................................................................................23 4.7.2. Alternativa Composta ....................................................................................................................23 4.8. ESTRUTURA DE REPETIÇÃO ....................................................................................................................24 4.9. REGRAS PRÁTICAS PARA A CONSTRUÇÃO DE ALGORITMOS LEGÍVEIS ...................................................24 4.10. EXEMPLOS DE ALGORITMOS ................................................................................................................24 Algoritmos e Técnicas de Programação ______________________________________________________________________________________________________________ _________________________________________________________________________ 5 Memórias Conceitualmente, a memória é um componente muito simples: é um “depósito” onde são guardados certos elementos para serem usados quando desejado. A memória de um computador possui diferentes variedades: • de velocidade; • de capacidade de armazenamento; • de tecnologia de construção; • de utilidade dentro do sistema. Algoritmos e Técnicas de Programação ______________________________________________________________________________________________________________ _________________________________________________________________________ 6 Para o correto e eficaz funcionamento da manipulação das informações, verifica-se a necessidade de se ter em um mesmo computador diferentes tipos de memória. Periféricos Os periféricos são um conjunto de elementos “acessórios” ao fluxo de processamento de dados. Periféricos de Entrada • Teclado: permite entrada de códigos, caracteres numéricos e alfanuméricos na memória do computador. • Mouse: permite a integração visual entre o usuário e o equipamento; é representado por uma peça que possui uma esfera giratória na parte inferior que, quando em contato com uma superfície plana, reproduz o efeito no monitor de vídeo do equipamento. • Scanner: permite a digitalização de uma imagem pré-impressa; quando utilizado em conjunto com programas específicos chamados OCR (Optical Caracter Recognition), praticamente vem dispensar o trabalho de digitação de materiais já impressos. • Light Pen (Caneta Óptica): permite “apontar” com uma espécie de “caneta” o monitor de vídeo de um computador e assim realizar escolhas de opções predefinidas. • Leitores de Códigos de Barras: são dispositivos cujas características são estabelecidas com o propósito de atender às necessidades de leitura de códigos de barras. • Joystick: é atualmente rotulado como um periférico apenas para diversão. Algoritmos e Técnicas de Programação ______________________________________________________________________________________________________________ _________________________________________________________________________ 7 Periféricos de Saída • Monitor de Vídeo: permite visualizar as etapas do processamento de dados, desde a entrada dos dados até a saída das informações. • Impressora: a função desse periférico é perpetuar as informações obtidas pelo processamento por meio da impressão em folhas. • Plotter: conhecido também como traçador gráfico, é um periférico cujo objetivo se assemelha ao da impressora, porém é de uso mais específico: destina-se à confecção de trabalhos gráficos. 1.2. Software 1.2.1. Introdução Praticamente de nada adianta a existência apenas do hardware. O hardware tem de ser encarado com um potencial de recursos a serem extraídos na medida das necessidades de seu usuário. Para que seja possível usufruir desse potencial é necessária a parte lógica do computador: o software. O software é a parte lógica que dota o equipamento físico de capacidade para realizar todo tipo de trabalho. Por trás do software estão as linguagens de programação, que são regras básicas que permitem a melhor integração e buscam o ótimo relacionamento entre o software, o hardware e também o peopleware. 1.2.2. Linguagens de Programação Linguagem de Máquina • É a linguagem de programação mais próxima da máquina. • O computador consegue “entender” somente essa linguagem. • Essa linguagem é a única que consegue enviar instruções ao processados. Linguagem de Baixo Nível • É a linguagem de programação ainda bem próxima da máquina, porém com alguns artifícios que a torna mais acessível ao usuário. • O programador deve conhecer bem, tecnicamente o equipamento que estará programando para extrair dele o mais benefício possível. Linguagem de Alto Nível • São linguagens de programação mais acessíveis ao ser humano. • São constituídas de regras e códigos mais próximos da linguagem do ser humano. Algoritmos e Técnicas de Programação ______________________________________________________________________________________________________________ _________________________________________________________________________ 10 Conversão do sistema decimal para o sistema binário Para converter um número representado na base 10 para a base 2, tem-se que aplicar um processo para a parte inteira e outro para a parte fracionária. Para transformar um número inteiro na base 10 para a base 2 utiliza-se o método das divisões sucessivas, que consiste em dividir o número por 2, a seguir divide-se o quociente encontrado por 2 e assim o processo é repetido até que o último quociente seja igual a 1. O número binário será formado pela concatenação do último quociente com os restos das divisões lidos em sentido inverso ao que foram obtidos. Para transformar um número fracionário da base 10 para a base 2, utiliza- se o método das multiplicações sucessivas, que consistem em multiplicar o número fracionário por 2; deste resultado, a parte inteira será o primeiro dígito do número na base 2. O processo é repetido até que a parte fracionária do último produto seja igual a zero. 2.3. O Sistema Hexadecimal de Numeração O sistema hexadecimal possui 16 algarismos, sendo sua base igual a 16. Os algarismos são assim enumerados: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E e F. A letra A representa o algarismo A, que por sua vez representa a quantidade dez. A letra B representa o algarismo B que representa a quantidade onze, e assim sucede até a letra F que representa a quantidade quinze. Conversão do sistema hexadecimal para o sistema decimal Para convertermos um número hexadecimal em decimal, utilizaremos o conceito básico de formação de um número. Conversão do sistema decimal para o sistema binário O processo é análogo à conversão do sistema decimal para o sistema binário, somente que neste caso, utilizaremos a divisão por 16, pois sendo o sistema hexadecimal, sua base é igual a 16. Conversão do sistema hexadecimal para o sistema binário A regra consiste em transformar cada algarismo diretamente no correspondente em binário, respeitando-se o número padrão de bits do sistema, sendo o hexadecimal igual a 16 (24 = 16). Conversão do sistema binário para o sistema hexadecimal Neste caso, devemos separar o número em grupos de 4 bits a partir da direita. Em seguida, devemos efetuar a conversão de cada grupo de bits diretamente para o sistema hexadecimal. Algoritmos e Técnicas de Programação ______________________________________________________________________________________________________________ _________________________________________________________________________ 11 3. Desenvolvimento de Programas 3.1. Fases para a solução de um problema: 1. Definição do problema: É a descrição e a delimitação adequada do problema a ser resolvido, caracterizando-o de maneira clara e completa. 2. Desenvolvimento de um algoritmo: É a descrição, geralmente dividida em etapas, de diversas operações que devem ser realizadas pelo computador para resolver o problema e obter os resultados desejados. 3. Transcrição do algoritmo para uma linguagem de programação: É a codificação do algoritmo, obtendo-se um programa equivalente, de acordo com as regras e recursos oferecidos pela linguagem. 4. Processamento do programa pelo computador: Seguindo as instruções de um programa denominado compilador, o computador verifica a correção sintática do programa e o traduz para outra linguagem (linguagem de máquina) que, em seguida, passa a controlar o computador através de suas instruções, executando a resolução do problema e obtendo os resultados desejados. 5. Análise dos resultados: Os resultados obtidos pelas primeiras execuções de um programa devem ser analisados, pois podem estar comprometidos com erros de lógica. 3.2. Algoritmos 3.2.1. Definição de Algoritmos A palavra algoritmo, à primeira vista, parece-nos estranha. Embora possua designação desconhecida, fazemos uso constantemente de algoritmos em nosso cotidiano: a maneira como uma pessoa toma banho é um algoritmo. Definimos algoritmo como a seqüência de passos que visam atingir um objetivo bem definido. Os algoritmos são utilizados no dia-a-dia para a solução dos mais diversos problemas. Outros algoritmos freqüentemente encontrados são: • instruções para utilizar um aparelho eletrodoméstico; • uma receita para preparo de algum prato; • a maneira como as contas de água, luz e telefone são calculados mensalmente, etc. Algoritmos e Técnicas de Programação ______________________________________________________________________________________________________________ _________________________________________________________________________ 12 São vários os conceitos para algoritmo: “Um conjunto finito de regras que provê uma seqüência de operações para resolver um tipo de problema específico” [KNUTH] “Seqüência ordenada, e não ambígua, de passos que levam à solução de um dado problema” [TREMBLAY] “Processo de cálculo, ou de resolução de um grupo de problemas semelhantes, em que se estipulam, com generalidade e sem restrições, as regras formais para a obtenção do resultado ou da solução do problema” [AURÉLIO] Definição formal de algoritmo: é a descrição de um padrão de comportamento, representado por um repertório finito e bem definido de ações, das quais damos por certo que elas podem ser executadas. 3.2.2. Por que precisamos de algoritmos? Vejamos o que algumas pessoas importantes para a Ciência da Computação disseram a respeito de algoritmo: “A noção de algoritmo é básica para toda a programação de computadores”. [KNUTH - Professor da Universidade de Stanford, autor da coleção “The art of computer programming”] “O conceito central da programação e da ciência da computação é o conceito de algoritmo”. [WIRTH - Professor da Universidade de Zurique, autor de diversos livros na área e responsável pela criação de linguagens de programação como ALGOL, PASCAL e MODULA -2] A importância do algoritmo está no fato de termos que especificar uma seqüência de passos lógicos para que o computador possa executar uma tarefa qualquer, pois o mesmo por si só não tem vontade própria, faz apenas o que mandamos. Com uma ferramenta algorítmica, podemos conceber uma solução para um dado problema, independendo de uma linguagem específica e até mesmo do próprio computador. Algoritmos e Técnicas de Programação ______________________________________________________________________________________________________________ _________________________________________________________________________ 15 4.3.1. Identificadores Representam os nomes escolhidos para rotular as variáveis, constantes, novos tipos, procedimentos, funções e conjuntos. Tudo o que pode ser nomeado em um algoritmo deve obedecer às seguintes regras: 1)Devem possuir como 1º caractere uma letra ou sublinhado ( _ ); 2)Ter como demais caracteres letras, números ou sublinhado; 3)Os nomes devem ser formados por caracteres pertencentes ao seguinte conjunto: •As letras do alfabeto no padrão inglês maiúsculo e minúsculo: abcdefghijklmnopqrstuvxwyz abcdefghijklmnopqrstuvxwyz •Os dez algarismos: 0123456789 •O sublinhado (Underline): _ 4)Ter no máximo 127 caracteres; 5)Não possuir espaços em branco; 6)Os nomes escolhidos devem explicitar seu conteúdo. 7)O identificador não pode ser uma palavra reservada. (veremos adiante) 4.3.2. Tipos de dados A linguagem Portugol algoritmo possui 4 tipos básicos de dados: inteiro: qualquer número inteiro negativo, nulo ou positivo. (número sem casas decimais) Exemplos : -984563 , 1 , 5 , 0 , 321458 real: qualquer número real negativo, nulo ou positivo. (número pode ter casas decimais) Exemplos : -984563 , 1 , 5 , 0 , 321458 , -98,4588 , 45,789 caracter: qualquer conjunto de caracteres alfanuméricos. (letras e números e símbolos especiais) Exemplos : “Ana” , “João”, “Rua do ouro” , “123” , “#?*\!&” lógico: tipo especial de variável que armazena apenas os valores verdadeiro ou falso Algoritmos e Técnicas de Programação ______________________________________________________________________________________________________________ _________________________________________________________________________ 16 4.3.3. Declaração de variáveis Para que os programas manipulem valores, estes devem ser armazenados em variáveis e para isso, devemos declará-las de acordo com a sintaxe: tipo: identificador ; Exemplos : inteiro: Idade; caracter: Nome; real: salario; lógico: fumante; Se houver mais de uma variável do mesmo tipo deve-se definir de acordo com a sintaxe: tipo: identificador1, identificador2, ..., identificadorn ; Exemplos : inteiro: Idade, num_dependentes ; caracter: Nome, endereco, rg, estado_civil, nacionalidade ; real: salario, percentual ; lógico: fumante; Quando uma variável é declarada, o compilador cria um local na memória, rotulado com o nome simbólico da variável e determina o tipo de valores que ele pode conter. 4.3.4. Declaração de constantes Devemos declará-las de acordo com a sintaxe: const identificador = valor; Exemplo : const pi = 3.141592654; 4.4. Operações Básicas Na solução da grande maioria dos problemas é necessário que as variáveis tenham seus valores consultados ou alterados. Para isto, devemos definir um conjunto de operadores, sendo eles: aritméticos, lógicos e relacionais. Algoritmos e Técnicas de Programação ______________________________________________________________________________________________________________ _________________________________________________________________________ 17 4.4.1. Operadores aritméticos São usados para representar as operações matemáticas, e obedecem a mesma prioridade da matemática, ou seja, em um comando que aparecem várias operações básicas envolvidas, primeiro é resolvida a POTENCIAÇÃO , depois a MULTIPLICAÇÃO ou a DIVISÃO e por último a SOMA ou a SUBTRAÇÃO. Operador Ação + Adição * Multiplicação - Subtração ou inversor do sinal / Divisão ** Exponenciação Operadores Especiais div: Retorna o valor inteiro que resulta da divisão entre 2 números inteiros. mod: Retorna o resto da divisão entre 2 números inteiros. Exemplo: Linearização de Expressões Para a construção de algoritmos todas as expressões aritméticas devem ser linearizadas, ou seja, colocadas em linhas. É importante também ressalvar o uso dos operadores correspondentes da aritmética tradicional para a computacional. Exemplo: Expressão Matemática Tradicional Expressão Computacional Como pode ser observado no exemplo em expressões computacionais usamos somente parênteses “( )”. Em uma expressão computacional podemos ter parênteses dentro de parênteses. ( ) =+    −+ 135 3 2 (2/3+(5-3))+1= Algoritmos e Técnicas de Programação ______________________________________________________________________________________________________________ _________________________________________________________________________ 20 A maioria das linguagens de programação utiliza as seguintes prioridades de operadores: 1)Efetuar operações embutidas em parênteses "mais internos" 2)Efetuar funções 3)Efetuar exponenciação 4)Efetuar multiplicação e/ou divisão e/ou div e/ou mod 5)Efetuar adição e/ou subtração 6)Operadores relacionais 7)Operadores lógicos na ordem a seguir: 7.1) não 7.2). e 7.3) ou 4.5. Comandos de Entrada e Saída Em um algoritmo é preciso representar a troca de informações que ocorrerá entre o mundo da máquina e o nosso mundo, para isso, devemos utilizar comandos de entrada e saída, sendo que, em nível de algoritmo esses comandos representam apenas a entrada e a saída da informação, independe do dispositivo utilizado (teclado, discos, impressora, monitor,...), mas, sabemos que nas linguagens de programação essa independência não existe, ou seja, nas linguagens de programação temos comandos específicos para cada tipo de unidade de entrada/saída. 4.5.1. Comando de entrada de dados O comando de entrada de dados é utilizado para armazenar em uma variável um valor que se encontra em uma unidade de entrada de dados (usualmente o teclado). Existe apenas um comando simples para a entrada de dados, o comando leia: leia(variavel); onde: leia é uma palavra reservada variável representa a variável onde será armazenado o valor proveniente da unidade de entrada, qualquer que seja ela. Algoritmos e Técnicas de Programação ______________________________________________________________________________________________________________ _________________________________________________________________________ 21 Para ler e armazenar mais de um valor ao mesmo tempo deve-se usar o comando leia da seguinte forma: leia(variavel1, variavel2, ..., variaveln); Neste exemplo o primeiro valor digitado será armazenado na variavel1, o segundo valor digitado será armazenado na variavel2 e assim por diante. 4.5.2. Comando de saída de dados O comando de saída de dados é utilizado para exibir em uma unidade de saída (usualmente o monitor) uma mensagem e/ou dados do algoritmo. Existe apenas um comando simples para a exibição de resultados, o comando imprima. - Se quisermos que seja exibido o conteúdo de uma variável devemos usar o comando imprima da seguinte forma: imprima(variavel); onde: imprima é uma palavra reservada variavel representa a variável cujo conteúdo será exibido na unidade de saída. - Se houver mais de uma variável que queiramos exibir seu conteúdo devemos usar o comando imprima da seguinte forma: imprima(variavel1, variável2, ..., variáveln); onde: as variáveis deverão vir separadas por vírgula. - Se quisermos exibir um texto qualquer: imprima(“texto qualquer”); onde: o texto que será exibido sempre deve vir entre aspas. - Se quisermos exibir um texto e o conteúdo de uma variável juntos, devemos usar o comando imprima da seguinte forma: imprima(“texto” , variavel); - Se quisermos exibir o resultado do processamento de uma expressão lógica ou aritmética, devemos usar o comando imprima da seguinte forma: imprima(12,5 – 3); Algoritmos e Técnicas de Programação ______________________________________________________________________________________________________________ _________________________________________________________________________ 22 - Se quisermos exibir um texto, o conteúdo de uma variável e o resultado do processamento de uma expressão lógica juntos, devemos usar o comando imprima da seguinte forma: imprima(“texto” , variável , expressão); 4.6. Comando de Atribuição Esta instrução é um comando para “colocar” um valor na área de uma variável. E pode ocorrer das seguintes formas: - Atribuição de constante: variavel ← valor; onde: variavel é o nome da variável que receberá um dado valor, este valor deverá ser compatível ao tipo da variável. - Atribuição de variável: variavel1 ← variavel2; onde: variavel1 é o nome da variável que receberá o conteúdo da variavel2. As variáveis devem ser do mesmo tipo. - Atribuição de expressão: variavel ← expressao; onde: variavel é o nome da variável que receberá um valor através de: uma expressão aritmética (envolvendo um cálculo), expressão lógica (envolvendo uma comparação) ou expressão literal (envolvendo um processamento de texto). Após a expressão ser avaliada ou “calculada”, o valor obtido é atribuído à variável. 4.7. Estrutura Condicional Uma das tarefas fundamentais de qualquer algoritmo é decidir o que deve ser executado a seguir. A estrutura condicional permite determinar qual é a ação a ser tomada com base no resultado de um teste lógico. A estrutura condicional pode ser formada por uma alternativa simples ou composta.