Algoritimo

Prévia do material em texto

INTRODUÇÃO A ALGORITMOS
 
1.   - Noções de Lógica
 
-         Lógica:       
-         é a "arte de bem pensar";
-         é a "ciência das formas do pensamento"
-         "estuda a correção do raciocínio"
-         "ensina a colocar ordem no raciocínio"
 
Exemplo:
        Todo mamífero é um animal.
        Todo cavalo é um mamífero.
        Portanto, todo cavalo é um animal.
       
-         Lógica no dia-a-dia:
 
Quando queremos pensar, falar, escrever ou agir corretamente precisamos colocar "ordem no pensamento", isto é utilizar lógica.
 
Exemplo:
                A gaveta está fechada.
                A caneta está dentro da gaveta.
Precisamos primeiro abrir a gaveta para depois pegar a caneta.
 
-         Lógica de programação:
 
Significa o uso correto das leis do pensamento, da "ordem da razão" e de processos de raciocínio e simbolização formais na programação de computadores com o objetivo de resolver um problema específico.
 
O raciocínio é abstrato e o ser humano o expressa através de palavras faladas ou escritas seguindo padrões gramaticais de uma linguagem. O mesmo raciocínio pode ser expresso em qualquer idioma.
 
A lógica de programação pode ser representada em qualquer uma das inúmeras linguagens de programação existentes.
 
O objetivo do estudo da lógica de programação é a construção de algoritmos.
 
 
2.   - Introdução a Algoritmos
 
-         Definição:
 
Um algoritmo pode ser definido como uma seqüência de passos finitos e ordenados que visam atingir um objetivo bem definido.
 
Para especificar uma seqüência de passos , precisamos utilizar ordem, ou seja "pensar com ordem", portanto precisamos utilizar lógica.
 
Algoritmos são comuns no nosso cotidiano, como por exemplo uma receita de bolo. Nela está escrita uma série de ingredientes necessários e uma seqüência de diversos passos (ações/instruções) que devem ser fielmente cumprida para realizar a tarefa. Outro exemplo bastante comum é o conjunto de instruções para instalação e utilização de um eletrodoméstico.
 
 
-         Por que é importante construir um algoritmo?
 
Para representar mais fielmente o raciocínio envolvido na lógica de programação sem se preocupar com detalhes computacionais, que podem ser acrescentados mais tarde. Posteriormente o algoritmo poderá ser codificado em qualquer linguagem de programação.
 
-         Exemplo: Utilizando português coloquial escreveremos um algoritmo para uma atividade simples: trocar uma lâmpada queimada por uma lâmpada nova não queimada.
 
Algoritmo 1.1 Trocar uma lâmpada.
 
·       pegar uma escada;
·       posicionar a escada debaixo da lâmpada;
·       buscar uma lâmpada nova;
·       subir na escada;
·       retirar a lâmpada queimada;
·       colocar a lâmpada nova;
 
Reexaminando o algoritmo 1.1, notamos que ele tem um objetivo bem definido: trocar uma lâmpada. Porém se a lâmpada não estivesse queimada? A lâmpada seria trocada da mesma forma porque o algoritmo não previu essa possibilidade. Para tal acrescentamos um teste condicional (estrutura seletiva) .
 
Algoritmo 1.2 Trocar uma lâmpada.
·       pegar uma escada;
·       posicionar a escada debaixo da lâmpada;
·       buscar uma lâmpada nova;
·       acionar o interruptor;
·       se a lâmpada não acender, então
·       subir na escada;
·       retirar a lâmpada queimada;
·       colocar a lâmpada nova;
 
O algoritmo 1.2 pode ser melhorado uma vez que buscamos a lâmpada e a escada sem saber se de fato seriam necessárias.
 
Algoritmo 1.3 Trocar uma lâmpada.
·       acionar o interruptor;
·       se a lâmpada não acender, então
·       pegar uma escada;
·       posicionar a escada debaixo da lâmpada;
·       buscar uma lâmpada nova;
·       subir na escada;
·       retirar a lâmpada queimada;
·       colocar a lâmpada nova;
 
O algoritmo 1.3 não atingirá seu objetivo se a lâmpada nova estiver queimada. É necessário prevê essa possibilidade.
 
 Algoritmo 1.4 Trocar uma lâmpada.
·       acionar o interruptor;
·       se a lâmpada não acender, então
·       pegar uma escada;
·       posicionar a escada debaixo da lâmpada;
·       buscar uma lâmpada nova;
·       subir na escada;
·       retirar a lâmpada queimada;
·       colocar a lâmpada nova;
·       se a lâmpada não acender, então
·       retirar a lâmpada queimada;
·       colocar outra lâmpada nova;
·       se a lâmpada não acender, então
·       retirar a lâmpada queimada;
·       colocar outra lâmpada nova;
·       se a lâmpada não acender então
·       .
·       .
(Até quando?)
 
O Algoritmo 1.4 não está terminado. As ações cessarão quando conseguirmos colocar uma lâmpada que acenda, que é o objetivo do algoritmo. Em vez de reescrevermos várias vezes um conjunto de ações, podemos alterar o fluxo seqüencial de execução para permitir que ações sejam reexecutadas quantas vezes seja necessário. Precisamos expressar essa repetição (estrutura de repetição) garantindo uma condição de parada.
 
Algoritmo 1.5 Trocar uma lâmpada.
 
·       acionar um interruptor;
·       se a lâmpada não acender, então
·       pegar uma escada;
·       posicionar a escada debaixo da lâmpada;
·       buscar uma lâmpada nova;
·       subir na escada;
·       retirar a lâmpada queimada;
·       colocar a lâmpada nova;
·       enquanto a lâmpada não acender, faça
·       retirar a lâmpada queimada;
·       colocar outra lâmpada nova;
 
 
-         Refinamento de Algoritmos:
 
Um algoritmo é considerado completo se seus comandos (ações/instruções) forem do entendimento do destinatário. Um comando que não estiver claro, precisa ser desdobrado em novos comandos, que constituirão um refinamento do comando inicial. Se necessário, deve ser feito refinamentos sucessivos até que todos os comandos sejam entendidos pelo destinatário. No algoritmo exemplificado, dependendo do tipo de destinatário alvo, poderia ser necessário detalhar algumas ações, como por exemplo a ação retirar a lâmpada queimada.
 
-         Algoritmos voltados para processamento de dados:
 
Os algoritmos que exemplificaremos a partir de agora, são voltados para solucionar problemas de processamento de dados (problemas computáveis, ou seja, que podem ser resolvidos pelo computador). Portanto, apesar de usarmos o português coloquial, a linguagem será mais restrita, uma vez que o destinatário (o computador) entende poucos comandos (ações/instruções).
 
 
2.1 - Itens Fundamentais dos Algoritmos
 
-         Tipos de Dados:
·       Numérico: valores numéricos
·       Literal: dado composto por um conjunto de caracteres (letras, dígitos ou caracteres especiais)
·       Lógico (booleano): dado que pode assumir apenas os valores Verdadeiro ou Falso.  
 
-         Constantes:
São os dados que não sofrem modificação durante a execução do algoritmo.
Exemplos: 123, 12.34, ‘Campina Grande’, Verdadeiro.
 
-         Variáveis:
 
São os dados que sofrem modificação durante a execução do algoritmo. É um contêiner que pode armazenar um tipo determinado de e possui um nome .
 
Exemplo: A área de uma círculo é processada pela fórmula:
 
área = p . raio 2
                               área = 3,1416 * raio * raio
 
área e raio são variáveis uma vez que seus valores depende de qual círculo queremos calcular a área. 3,1416 é um valor constante para calcular a área de qualquer círculo.
 
Identificadores de Variáveis:
 
No exemplo anterior área e raio são os identificadores (nomes) das variáveis que armazenam respectivamente a área e o raio da circunferência.
 
Tipos de Variáveis:
 
A as variáveis possuem omendo tipo que o dado que ela pode armazenar.
 
Declaração de variáveis:
 
No ambiente computacional cada variável corresponde a uma porção (parte ou pedaço) de memória, cujo conteúdo pode variar durante a execução de um programa. Embora uma variável possa assumir vários valores, ela só pode armazenar um valor de cada vez. Os identificadores das variáveis representam as posições de memória(endereços de memória) que armazenam os dados. As alocações das variáveis são feitas na memória principal.
 
Na declaração associamos a variável ao tipo de dado a ser armazenado nela.
 
        Exemplos:
                        área, raio: numérico;
                        nome: literal;
 
-         Expressões Aritméticas:
 
São expressões cujos resultados de suas avaliações são valores numéricos. As expressões aritméticas são compostas de:
·       operadores: são os operadores aritméticos: +, -, * e /
·       operandos: constantes ou variáveis
 
-         Expressões Lógicas:
 
São expressões cujos resultados de suas avaliações são valores lógicos (Verdadeiro - V ou Falso - F). As expressões aritméticas são compostas de:
·       operadores: são os operadores relacionais (= ,> , <, >=, <=, <>) e os operadores lógicos (Não, E, Ou)
·       operandos: são relações ou variáveis ou constantes do tipo lógico
 
Os resultados dos operadores lógicos são avaliados de acordo com as tabelas lógicas que aparecem a seguir. Nestas tabelas, A e B representam um valor lógico (constante ou variável) ou expressões lógicas.
 
        Operação de Negação
	A
	Não A
	V
	F
	F
	V
 
        Operação de Conjunção
	A
	B
	A e B
	V
	V
	V
	V
	F
	F
	F
	V
	F
	F
	F
	F
 
        Operação de Disjunção
	A
	B
	A ou B
	V
	V
	V
	V
	F
	V
	F
	V
	V
	F
	F
	F
 
        Exemplos:
 
a)        2 < 5     e   15/3 = 5 
      V        e    5 = 5
      V        e       V
                V
 
b)        2 > 5     e   15/3 = 5 
      F        e    5 = 5
      F        e       V
                F
 
c)        não V    ou   15/3 <> 5 
      F        ou    5 <> 5
      F        ou        F
                 F
 
 
-         Comando de Atribuição:
 
Permite-nos fornecer um valor para uma variável (armazenamento na memória)
 
Exemplo:
    Nome: literal
    Salário: numérico
                        Nome ¬ 'Carlos'
                Salário ¬ 3000.00
 
-         Comandos de Entrada e Saída:
 
O comando leia permite atribuir o dado lido (exterior ao algoritmo) à variável identificada.
 
Exemplo: leia(raio);    {atribui o valor lido a variável raio}
 
O comando escreva permite exibir o valor de constantes ou o conteúdo armazenado nas variáveis identificadas.
 
Exemplo: escreva(´o raio é igual a ‘ , raio);
exibe a constante “o raio é igual a” seguida do valor armazenado na variável raio.
 
-         Comentário:
 
É qualquer texto que apareça no algoritmo entre chaves. Os comentários não fazem parte das ações (comandos) e tem como finalidade aumentar a clareza na leitura do algoritmo, ou seja, aumenta o grau de facilidade que as pessoas terão em compreender o que nele está escrito.
 
 
2.2 - Estruturas de Controle
 
As estruturas de controle determinam a seqüência de execução das ações dos algoritmos.
 
-         Estrutura Seqüencial:
 
Os comandos serão executados numa seqüência linear, isto é, do primeiro ao ultimo na ordem em que eles aparecem, se não houver indicação em contrário
 
Algoritmo
        d1
        d2
        . . .
        dn
        c1
        c2
        . . .
cn
fim algoritmo
 
onde:   d1, d2, . . ., dn são declarações, e
            c1, c2, . . ., cn são comandos.
 
Exemplo: Algoritmo que calcula a média aritmética entre 4 notas de um aluno.
 
Algoritmo
{declaração das variáveis}
Nota1, Nota2, Nota3, Nota4, Média: numérica;
{obtenção das notas}
escreva(‘Informe as notas do aluno:’)
leia(Nota1, Nota2, Nota3, Nota4);
{cálculo da média}
Média ← (Nota1 + Nota2 + Nota3 + Nota4 ) / 4;
escreva(‘Média Calculada = ’ , Média);
fim algoritmo.
 
 
-         Estrutura Condicional:
 
Permite a escolha do grupo de comandos a ser executado quando determinadas condições, representadas por expressões lógicas são ou não satisfeitas.
 
·       Seleção Simples:
       
se condição então
seqüência de comandos
fim se
 
 
·       Seleção Composta:
       
se condição então
seqüência de comandos 1
senão
seqüência de comandos 2
fim se
 
Exemplo: Algoritmo que calcula a média aritmética entre 4 notas de um aluno e informa se o aluno foi ou não aprovado.
 
Algoritmo
Nota1, Nota2, Nota3, Nota4, Média : numérico;
                escreva(‘Informe as notas do aluno:’);
leia(Nota1, Nota2, Nota3, Nota4);
Média ← (Nota1 + Nota2 + Nota3 + Nota4 ) / 4;
escreva( ‘Média Calculada = ’ , Média );
se (Média >= 7.0) então
                        escreva(‘ Aluno Aprovado’);
                        escreva(‘ Parabéns ! ‘)
                senão
escreva(‘ Aluno Reprovado’);
                        escreva(‘ Estude Mais ! ‘)
fim se
fim algoritmo.
 
Uma estrutura condicional também pode ser uma Seleção Encadeada (aninhada).
 
Exemplo: Algoritmo que dado 3 valores A, B e C, verifica se eles podem ser os lados de um triângulo (cada lado menor que a soma dos outros dois). Se forem verificar se é equilátero (lados iguais), isósceles (dois lados iguais e um diferente) ou escaleno (todos os lados diferentes).
 
Algoritmo
A, B, C: numérico;
                escreva(‘Informe os comprimentos dos lados’);
leia(A, B, C );
{verifica se os lados formam um triângulo}
     se ((A < B + C) e (B < A + C) e (C < A + B)) então
             se ((A = B) e (B = C)) então
escreva(‘ Triângulo Equilátero’);
senão
se ((A = B) ou (A = C) ou (B = C)) então
escreva(‘Triângulo Isósceles’)
                    senão
                            escreva(‘Triângulo Escaleno’);
fim se
             fim se
     senão
             escreva(‘Os valores não formam um triângulo’)
     fim se     
fim algoritmo.
 
 
-         Estruturas de Repetição:
 
Permite que uma seqüência de comandos seja executada repetidamente (laços de repetição) até que uma determinada condição de interrupção seja satisfeita. O número de repetições pode ser indeterminado, porém necessariamente finito.
 
Repetição com teste no início
 
Permite repetir diversas vezes um trecho do algoritmo, porém, sempre verificando antes de cada execução se é "permitido" executar o mesmo trecho.
 
                enquanto <condição> faça
                        c1;
c2;
                        .
                        .
                        cn;
                fim enquanto;
 
Exemplo1: Vamos fazer um algoritmo que calcula as médias aritméticas de vários alunos e para quando encontra uma primeira nota negativa (sinal de parada).
 
Algoritmo
Nota1, Nota2, Nota3, Nota4: numérico; {notas}
Média: numérico; {média}
escreva(‘Informe a primeira nota do aluno:’)
leia(Nota1); {lê a primeira nota do primeiro aluno}
enquanto (Nota1 >= 0) faça
escreva(‘Informe as demais notas do aluno:’)
leia(Nota2, Nota3, Nota4);
Média ← (Nota1 + Nota2 + Nota3 + Nota4 ) / 4;
        escreva(‘Média Calculada = ’ , Média);
        se (Média >= 7.0) então
                escreva(‘ Aluno Aprovado’);
                escreva(‘ Parabéns ! ‘)
        senão
escreva(‘ Aluno Reprovado’);
                escreva(‘ Estude Mais ! ‘)
fim se
escreva(‘Informe a primeira nota do aluno:’)
leia(Nota1); {lê a primeira nota do próximo aluno}
                fim enquanto
fim algoritmo.
 
Exemplo2: Um algoritmo para ler a média final de vários alunos, calcular a média aritmética da turma e parar quando encontrar uma média final de aluno negativa.
           
Algoritmo
        Contador, Acumulador, MédiaFinal, MédiaDaTurma: numérico;
        Contador ← 0;
Acumulador ← 0;
escreva(‘Informe a média final do aluno:’)
leia(MédiaFinal); {lê a a média final do primeiro aluno}
        enquanto (MédiaFinal >= 0) faça
Acumulador ← Acumulador + MédiaFinal;
Contador ← Contador + 1;             
escreva(‘Informe a média final do aluno:’)
leia(MédiaFinal); {lê a a média final do próximo aluno}
                fim enquanto
                MédiaDaTurma ← Acumulador / Contador;
                escreva('Média da Turma = ', MédiaDaTurma);
fim algoritmo.
 
Exemplo3:Algoritmo para encontrar o resto da divisão entre dois inteiros, com o dividendo maior que o divisor.
 
Algoritmo
Dividendo, Divisor, Resto: numérico;
escreva(‘Informe os valores do dividendo e do divisor:’)
leia(Dividendo e Divisor);
        Resto ← Dividendo;
enquanto (Resto >= Divisor) faça
        Resto ← Resto - Divisor;               
                fim enquanto
                escreva(‘O resto da divisão entre ’, Dividendo, ‘ e ’, Divisor, ‘ é ’,
Resto);
fim algoritmo.
 
Repetição com teste no final
 
Permite que uma seqüência de comandos seja repetido até que uma determinada condição seja verdadeira, isto é, repete enquanto a condição for falsa.
 
                repita
                        c1;
c2;
                        . . .
                        cn;
                até (<condição>);
 
Exemplo: Algoritmo que obtém o nome e a média final de cada aluno, calcula a média aritmética da turma e para após processar os dados do último aluno que tem o nome “Zózimo”.
 
Algoritmo
Contador, Total, MédiaFinal, MédiaDaTurma: numérico;
        Nome: literal;
        Contador ← 0;
Total ← 0;
        repita
                escreva(‘Informe o nome e a média final do aluno: ’);
                leia(Nome, MédiaFinal);
Total ← Total + MédiaFinal;           
Contador ← Contador + 1;
                até (Nome = ‘Zózimo’);
                MédiaDaTurma ← Total / Contador;
                escreva(‘Média da Turma = ’, MédiaDaTurma);
fim algoritmo.
 
Repetição com variável de controle ou com contagem
 
Permite que uma seqüência de comandos seja repetido um número definido de vezes. Esse número é definido e controlado pelo próprio comando através dos valores atribuídos a uma variável que é incrementada automaticamente a cada repetição dos comandos internos ao comando para.
 
                Para <variável> de <valorInicial> até <valorFinal> faça
c1;
c2;
. . .
cn;
                fim para;
 
onde:
<variável> é a variável de controle,
<valorInicial> é o valor inicial da <variável>,
<valorFinal> é o valor final que a <variável> deve atingir.
A cada repetição o valor de <variável> é incrementado de 1 automaticamente.
 
Exemplo: Fazer um algoritmo que lê a média final de 50 alunos e calcula a média aritmética da turma.
 
Algoritmo
Acumulador, MédiaFinal, MédiaDaTurma, Vezes: numérico;
        Acumulador ← 0;
        para Vezes de 1 até 50 faça
        escreva(‘Informe a média final do aluno: ’)
leia(MédiaFinal);
Acumulador ← Acumulador + MédiaFinal;              
                fim para;
                MédiaDaTurma ← Acumulador / 50;
                escreva('Média da Turma = ', MédiaDaTurma);
fim algoritmo.
 
 
3.   - Exercícios
 
3.1.      Construa um Algoritmo para calcular as raízes de uma equação do segundo grau (Ax2 + Bx + C) , sendo que os valores de A, B e C são fornecidos pelo usuário (considere que a equação possui duas raízes reais).
 
3.2.      Tendo como dados de entrada a altura e o sexo de uma pessoa, construa um algoritmo que calcule seu peso ideal , utilizando as seguintes fórmulas:
-         para homens: (72.7 * altura) - 58;
-         para mulheres: (62.1 * altura) - 44.7.
 
3.3.      Elabore um algoritmo que calcule N!, sendo que o valor inteiro de N é fornecido pelo usuário.
Sabendo que:
-         N! = 1 x 2 x 3 x ... x N;
-         0! = 1 por definição;
 
3.4.      A Série de Fibonacci é formada pela seqüência: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... Observe que os dois primeiros termos são iguais a 1, e os demais termos são iguais a soma dos dois anteriores. Elabore um algoritmo que gere a Série de Fibonacci até o vigésimo termo.
 
3.5.      Escreva um algoritmo que leia um conjunto de 20 números inteiros e mostre qual foi o maior e o menor valor fornecido.
 
 
4.   - Bibliografia
 
-         Lógica de Programação - A Construção de Algoritmos e Estrutura de Dados; André Luiz V. Forbellone e Henri Frederico Eberspacher; 2aEdição; 2000; Makron Books
-         Programação Estruturada de Computadores - Algoritmos Estruturados; Harry Farrer, Christiano Becker ; 1986; Guanabara Dois.