Unidade 3 - Introdução a Algoritmos

3.1 - Noções de Lógica

·         Algumas definições:

o   "a lógica é a arte de bem pensar"

o   "a lógica é a ciência das formas do pensamento"

o   "a lógica nos ensina a colocar ordem no pensamento"

·         Exemplo:

o   Todo mamífero é um animal.

o   O homem é um mamífero.

o   Portanto, o homem é um animal.

·         A lógica no dia-a-dia

o   Quando queremos escrever, falar ou agir corretamente, precisamos colocar ordem no pensamento, isto é, utilizar a lógica.

o   Exemplo:

§  A gaveta está fechada.

§  A caneta está dentro da gaveta.

§  Então, precisamos abrir a gaveta para depois pegar a caneta.

·         A lógica de programação

o   Em que consiste?

A lógica de programação consiste no uso correto das leis do pensamento, da dedução, de processos de raciocínio e de simbolização formal na programação de computadores.

o   Qual o objetivo?

Permitir a resolução de problemas específicos com soluções de boa qualidade.

o   O raciocínio lógico pode ser expresso através de várias linguagens:

§  no contexto humano - utiliza-se a palavra escrita/falada que, por sua vez, se baseia num determinado idioma, mas, independente do idioma, tem-se o mesmo raciocínio. Há linguagens concretas (português) ou abstratas (matemática).

§  no contexto computacional - utilizam-se as linguagens de programação

o   Vamos utilizar uma linguagem computacional abstrata (livre de detalhes computacionais) e que traduza mais fielmente o raciocínio da lógica de programação: ALGORITMOS

o   Então ...

O objetivo da lógica de programação é a construção de algoritmos corretos e válidos.

 

3.2 - Sobre Algoritmos

·         Definição: um algoritmo consiste numa seqüência de passos lógicos, ordenados e finitos 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 a lógica.

·         Algoritmos são comuns no nosso cotidiano. Exemplo: uma receita de bolo - nela está escrita uma série de ingredientes necessários e uma seqüência de diversos passos (modo de preparar) que devem ser fielmente cumpridos para realizar a tarefa.

·         IMPORTANTE!!

Os algoritmos fixam um padrão de comportamento a ser seguido; uma norma de execução a ser trilhada, visando alcançar, como resultado final, a solução de um problema

·         Por que usar algoritmos?

1.    abstração - todo o esforço é concentrado na resolução do problema e não em detalhes computacionais que podem ser acrescentados posteriormente

2.    portabilidade - uma solução algorítmica pode ser traduzida para qualquer linguagem de programação

·         Vejamos um outro exemplo... Deseja-se escrever um algoritmo, usando português coloquial, para resolver um problema bastante simples, qual seja: trocar uma lâmpada queimada por uma lâmpada nova não queimada.

·          

UMA RECEITA:

Bolo de arroz cru

Ingredientes

·  2 copos de arroz cru, colocado de molho por 12 horas

·  3 ovos inteiros

·  1 copo de óleo

·  1 copo de açúcar

·  1 copo de queijo ralado

·  2 colheres de fermento em pó

·  1 copo de leite

Modo de Preparo

  1. Coloque o arroz em uma peneira e deixe escorrer
  2. Reserve
  3. No liquidificador coloque o óleo, o leite, o açúcar, os ovos e bata bem
  4. Coloque o arroz aos poucos até colocar tudo, deixe bater por uns 5 a 10 minutos (ou até ficar bem cremoso)
  5. Coloque o queijo e o fermento e bata somente para misturar na massa
  6. Coloque em uma forma untada com óleo
  7. Leve ao fogo por aproximadamente uns 40 minutos ou até dourar

 

 


Algoritmo 1 - Trocar uma lâmpada queimada

·         pegar uma escada;

·         posicionar a escada debaixo da lâmpada;

·         buscar uma lâmpada nova;

·         subir na escada;

·         retirar a lâmpada queimada;

·         colocar lâmpada nova;

 


Reexaminando o algoritmo 1, notamos que ele tem um objetivo bem definido: trocar uma lâmpada queimada. Porém o algoritmo não atingirá seu objetivo se a lâmpada nova estiver queimada. Para tal, acrescentamos um teste condicional (estrutura seletiva).

 


Algoritmo 2 - Trocar uma lâmpada queimada (uso de teste condicional)

·         pegar uma escada;

·         posicionar a escada debaixo da lâmpada;

·         buscar uma lâmpada nova;

·         subir na escada;

·         retirar a lâmpada queimada;

·         colocar lâmpada nova;

·         se a lâmpada nova não acender, então:

o   retirar a lâmpada queimada;

o   colocar lâmpada nova;

o   se a lâmpada nova não acender, então:

§  retirar a lâmpada queimada;

§  colocar a lâmpada nova;

§  se a lâmpada nova não acender, então:

o  retirar a lâmpada queimada;

o  colocar a lâmpada nova;

. . . 

até quando????

 


O Algoritmo 2 não está terminado. As ações cessarão quando conseguirmos colocar uma lâmpada que acenda (objetivo do algoritmo). Ao invés 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 re-executadas quantas vezes forem necessárias. Precisamos expressar essa repetição (estrutura de repetição) garantindo uma condição de parada.

 


Algoritmo 3 - Trocar uma lâmpada queimada (uso de estruturas de repetiçã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 lâmpada nova;

·         enquanto lâmpada nova não acender, faça

§  retirar a lâmpada queimada;

§  colocar lâmpada nova;

 


·         Um exemplo mais envolvendo processamento de dados (tipo de problema que realmente nos interessa!): Deseja-se elaborar um algoritmo que escreva os termos da série de Fibonacci inferiores a L.

A série de Fibonacci: 1 1 2 3 5 8 13 ...

 


Algoritmo 4 - Calcular a série de Fibonacci

·         pegar o valor L;

·         atribuir o valor 1 ao primeiro termo;

·         se o primeiro termo for menor do que L, então

o  escreva-o;

·         atribuir o valor 1 ao segundo termo;

·         se o segundo termo for menor do que L, então

o  escreva-o;

·         calcular novo termo somando os dois anteriores;

·         enquanto novo termo for menor do que L, faça:

o   escreva-o;

o   atualiza os termos anteriores;

o   calcule novo termo somando os dois anteriores;

 


·         Quando o nosso algoritmo estará completo?

o   Um algoritmo é considerado completo quando seus comandos (ações/instruções) forem do entendimento do destinatário.

o   Se um comando não estiver claro, este deve ser desdobrado em novos comandos, que constituirão um refinamento do comando inicial. Em alguns casos, devem ser feitos refinamentos sucessivos do algoritmo.

o   No algoritmo 4, dependendo do tipo de destinatário, poderia ser necessário detalhar algumas  ações, como por exemplo, a ação atualiza os termos anteriores. Nesse caso, teríamos:

...

§  primeiro termo passa a ter o valor do segundo termo;

§  segundo termo passa a ter o valor do novo termo;

...

·         Como representar algoritmos?

·         Vamos  continuar a utilizar a nossa linguagem natural, o português, para descrever algoritmos, procurando restringir o vocabulário e as estruturas sintáticas para evitar ambigüidade e obter precisão e clareza. (= pseudo-código)

·         É interessante ressaltar que, a idéia de usar um pseudo-código para facilitar a descrição dos algoritmos muito se aproxima da maneira pela qual as linguagens de programação reais (como FORTRAN, C e Pascal) realizam os algoritmos que serão executados pelo computador.

 

3.3 -  Itens Fundamentais dos Algoritmos

·         Tipos de Dados:

o   Constantes:

§  São os dados que não sofrem modificação durante a execução do algoritmo.

§  Exemplos: 123, 12.34, "Campina Grande", VERDADE.

o   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 dado e cuja identificação e dada através de um nome.

§  A área de uma círculo é processada pela fórmula descrita abaixo:

área = pi * raio 2

área = 3,14 * raio * raio

área e raio representam variáveis, uma vez que seus valores dependem de qual círculo estamos considerando; 3,14 é um valor constante utilizado para calcular a área de qualquer círculo.

§  No ambiente computacional cada variável corresponde a uma porção (parte ou pedaço) de memória (memória principal), 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 denominações das posições de memória (endereços de memória) que armazenam os dados. No exemplo anterior, área e raio são os identificadores (nomes) das variáveis que armazenam respectivamente a área e o raio do círculo.

§  Declarações de variáveis: criação de variáveis, atribuindo-lhes identificadores e definindo o tipo de dado que elas podem armazenar:

Formato:

variáveis <tipo>: <lista de identificadores de variáveis>

Exemplo:

variáveis inteiras: idade, quantidade, número

o   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 / (soma, subtração, multiplicação e divisão) - a precedência entre os operadores é a mesma utilizada na álgebra comum, porém, parênteses podem mudar a precedência.

§  operandos: constantes, variáveis e expressões aritméticas.

o   Expressões lógicas

São expressões utilizadas para representar condições cujos resultados de suas avaliações são verdadeiro ou falso. As expressões lógicas são compostas de:

§  operadores: são os operadores lógicos: =, ¹, <, £, >, ³, não, e, ou - a precedência entre os operadores, da maior para a menor, é mostrada a seguir, porém, parênteses podem mudar a precedência.

o  não

o  =, ¹, <, £, >, ³

o  e, ou

§  operandos: constantes, variáveis e expressões.

o   Comentários:

§  São informações adicionais acrescentadas ao algoritmo para aumentar seu entendimento - não influencia na execução do algoritmo.

§  Utilizaremos como comentário uma frase iniciada por /* e terminada por */.

§  Exemplo: área = 3,14 * raio * raio /* cálculo da área de um círculo */

·         Estrutura de um Algoritmo:

início

            declarações de variáveis

            . . .

            ações ou operações

            . . .

fim

 

3.4  - Entrada e Saída de Dados 

·         permite-nos fornecer os dados que "alimentam" os algoritmos e mostram os resultados processados pelos mesmos. Para os comandos de entrada e saída, utilizaremos palavras como: leia, informe, escreva, mostre, etc.

·         O comando leia, permite atribuir o dado lido (externo ao algoritmo) à variável identificada.

·         Exemplo: leia raio - atribui o valor lido à variável raio

·         O comando escreva, permite exibir o valor de constantes ou o conteúdo armazenado nas variáveis identificadas.

·         Exemplo: escreva "o valor do raio é", raio  - escreve a constante "o valor do raio é" seguido do valor armazenado na variável raio.

 


Algoritmo 3 - Cálculo da área de um círculo a partir de seu raio

início

    /* Calcular a área de um círculo a partir de seu raio */

    /* Declaração (criação) de variáveis */

    variáveis reais: raio, área

    /* Obtenção do raio */

    escreva "Informe o raio do círculo: "

    leia raio

    /* Cálculo da área do círculo */

    área = 3.14159 * raio * raio

    escreva "A área do círculo de raio “, raio,  “ é “, área

fim

 


<span style="mso-char-type: symbol; mso-symbol-font-family: Symbol; font-size: 16.0pt; mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Arial; mso-fareast-font-family: Times New Roman; mso-hansi-font-family: Arial; mso-bidi-font-family: Arial; mso-ansi-language: PT-BR; mso-fareast-language: PT-BR; mso-bidi-language: AR-SA">3.5  - Estruturas de Controle</span>

·         As estruturas de controle determinam a seqüência de execução (fluxo de execução) das ações dos algoritmos.

·         Existem três tipos de estruturas de controle: estrutura seqüencial, estrutura de seleção, estrutura de repetição. Vejamos um pouco mais sobre cada uma delas:

3.5.1 - Estrutura Seqüencial:

·         via de regra, as ações descritas num algoritmo serão executadas numa seqüência linear, isto é, da primeira à última, na ordem em que aparecem.

·         modelo geral de um algoritmo:

início

/* corpo do algoritmo */

ação1;

ação2;

...

açãoN;

fim

 


Algoritmo 4 - Cálculo da média aritmética de quatro valores de notas

início

    /* Declarações de variáveis */

    variáveis reais: nota1, nota2, nota3, nota4, média

    /* Obtenção da notas */

    escreva "Informe as quatro 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

 


3.5.2 - Estruturas de Seleção

·         permite a escolha de um conjunto de ações a serem executadas quando a condição for ou não satisfeita.

·         seleção simples - forma geral:

se <condição> então
            /* ações caso a condição seja verdadeira */

. . .
fim se

 

·         seleção composta - forma geral:

se <condição> então
            /* ações caso a condição seja verdadeira */

. . .

senão
            /* ações caso a condição seja falsa */

. . .

fim se

 

·         Exemplo: modificação do algoritmo 4 de modo que seja avaliado se o aluno obteve nota maior do que 7.0; deve-se informar sobre a aprovação ou não do aluno.

 


Algoritmo 4.1 – Verifica se um aluno foi ou não aprovado a partir do cálculo da média aritmética de quatro notas

Algoritmo

    /* Calcula a media de 4 notas de um aluno e emite mensagem dizendo se o aluno

        foi ou não aprovado */

    /* Declarações de variáveis */

    variáveis reais: nota1, nota2, nota3, nota4, média

    /* Obtenção da notas */

    escreva "Informe as quatro notas do aluno: "

    leia nota1, nota2, nota3, nota4

    /* Cálculo da média */

    média = (nota1 + nota2 + nota3 + nota4) / 4;

    /* Saída condicional */

    se média ³ 7 então

           escreva "O aluno foi aprovado com média ", média

    senão

           escreva "O aluno obteve média “, média, “e não foi aprovado!”

    fim se

fim algoritmo

 


·         é possível agruparmos várias seleções numa única estrutura denominada: seleção encadeada.

·         forma geral de uma seleção encadeada:

se <condição1> então

            /* ações caso a condição1 seja verdadeira */

senão se <condição2> então

            /* ações caso a condição2 seja verdadeira */

senão se <condição3> então

            /* ações caso a condição3 seja verdadeira */

. . .

senão se <condiçãoN> então

            /* ações caso a condiçãoN seja verdadeira */

senão

            /* ações caso todas as condições sejam falsas */

fim se

 

·         Exemplo: um algoritmo que determina se um conjunto de 3 valores (fornecidos pelo usuário) - lado1, lado2, lado3 - formam um triângulo e, se formarem, verificar se dão origem a um triângulo eqüilátero, isósceles ou escaleno. Informar também se não formaram um triângulo.

 


Algoritmo 5 - Verificar se três lados formam um triângulo e que tipo de triângulo

algoritmo

/* Declaração de variáveis */

variáveis reais: lado1, lado2, lado3

/* Obtenção dos dados */

leia lado1, lado2, lado3

/* Testa se é triângulo */

se (lado1 < lado2+lado3) e (lado2 < lado1+lado3) e

     (lado3 < lado2+lado1) então

escreva "Os valores fornecidos formam um triângulo ",

/* Testa se é eqüilátero */

se (lado1 = lado2) e (lado2 = lado3) então

escreva " eqüilátero."

/* Testa se é isósceles */

senão se (lado1 = lado2) ou (lado2 = lado3) ou (lado1 = lado3) então

escreva "isósceles"

      senão /* É escaleno */

escreva " escaleno"

senão

escreva "Os valores fornecidos não formam um triângulo",

fim se

fim algoritmo

 


·         Seleções encadeadas podem seguir um mesmo padrão lógico:

A - Padrão se-então-se:

·         Suponha um comando qualquer que deva ser executado apenas quando as condições, condição1 e condição2, forem verdadeiras. Então teremos a seguinte situação:

se <condição1> então

se <condição2> então

comando(s)

fim se

            fim se

·         Nesse caso é melhor utilizar:

se <condição1> e <condição2> então

comando(s)

            fim se

 

B - Padrão se-senão-se

·         Suponha que uma variável var só possa assumir os valores valor1 e valor2; e que existam comandos diferentes para cada valor armazenado em var. Então teremos a seguinte situação:

se var = valor1 então

        comando1

fim se

se var = valor2 então

        comando2

fim se

·         Melhorando o desempenho dessa estrutura (diminuindo a quantidade média de testes):

se var = valor1 então

        comando1

senão se var = valor2 então

comando2

fim se

3.5.3 - Estruturas de repetição

·         Quando um trecho de programa deve ser repetido ao longo do algoritmo, ao invés de reescrevê-lo várias vezes utilizam-se laços de repetição.

·         O número de execuções de um laço de repetição pode ser indeterminado, mas sempre será finito.

·         Tipos de laços:

o   Laço com número de repetições indeterminado

A condição de parada da repetição só ocorrerá conhecida num futuro imprevisível para o algoritmo – o número de repetições não pode ser previsto.

enquanto <condição> faça

comando(s) a repetir

fim equanto

 

Exemplo: calcular a média aritmética de quatro notas para um conjunto de alunos.

 


Algoritmo 6 - Calcular a média aritmética de 4 notas para vários alunos, perguntando a cada aluno se existe outra média a calcular

início

/* Declarações das variáveis */<span style="mso-char-type: symbol; mso-symbol-font-family: Symbol; font-size: 16.0pt; mso-bidi-font-size: 10.0pt; font-family: Symbol; mso-ascii-font-family: Arial; mso-fareast-font-family: Times New Roman; mso-hansi-font-family: Arial; mso-bidi-font-family: Arial; mso-ansi-language: PT-BR; mso-fareast-language: PT-BR; mso-bidi-language: AR-SA"></span>

variáveis cadeia de caracteres: resposta<span style="mso-char-type: symbol; mso-symbol-font-family: Symbol; font-size: 16.0pt; mso-bidi-font-size: 10.0pt; font-family: Symbol; mso-ascii-font-family: Arial; mso-fareast-font-family: Times New Roman; mso-hansi-font-family: Arial; mso-bidi-font-family: Arial; mso-ansi-language: PT-BR; mso-fareast-language: PT-BR; mso-bidi-language: AR-SA">

variáveis reais: nota1, nota2, nota3, nota4, média

/* Inicialização de resposta */

resposta<span style="mso-char-type: symbol; mso-symbol-font-family: Symbol; font-size: 16.0pt; mso-bidi-font-size: 10.0pt; font-family: Symbol; mso-ascii-font-family: Arial; mso-fareast-font-family: Times New Roman; mso-hansi-font-family: Arial; mso-bidi-font-family: Arial; mso-ansi-language: PT-BR; mso-fareast-language: PT-BR; mso-bidi-language: AR-SA"> = </span>"S";

enquanto (resposta = "S") faça

/* Obtenção das notas */

escreva "Informe as quatro 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

escreva "Deseja calcular outra média de aluno (S/N)?"

leia resposta

fim enquanto

fim

 

Exemplo: modificar o algoritmo 6, parando quando encontrar uma nota menor que zero.

 


Algoritmo 7 - Calcular a média aritmética de 4 notas para vários alunos e parar quando aparecer uma nota negativa

início

/* Declarações das variáveis */<span style="mso-char-type: symbol; mso-symbol-font-family: Symbol; font-size: 16.0pt; mso-bidi-font-size: 10.0pt; font-family: Symbol; mso-ascii-font-family: Arial; mso-fareast-font-family: Times New Roman; mso-hansi-font-family: Arial; mso-bidi-font-family: Arial; mso-ansi-language: PT-BR; mso-fareast-language: PT-BR; mso-bidi-language: AR-SA"></span>

variáveis reais: nota1, nota2, nota3, nota4, média

/* Obtenção das notas para o primeiro aluno */

escreva "Informe as quatro notas do aluno: "

leia nota1, nota2, nota3, nota4

enquanto (nota1 >= 0  e nota2 >= 0 e nota3 >= 0 e nota4 >= 0) faça

/* Cálculo da média */

média = (nota1 + nota2 + nota3 + nota4) / 4

escreva "Média calculada: ", média

/* Obtenção das notas para os demais alunos */

escreva "Informe as quatro notas do aluno: "

leia nota1, nota2, nota3, nota4

fim enquanto

fim

 


o   Laço com número de repetição determinado

A condição de parada da repetição pode ocorrerá num futuro previsível para o algoritmo – o número de repetições pode ser previamente calculado.

contador = valorInicial

enquanto contador <= valorLimite faça

comando(s) a repetir

contador = contador + valorDoIncremento

fim enquanto

 

Exemplo: modificar o algoritmo 6, considerando a quantidade de alunos igual a 50.

 


Algoritmo 8 - Calcular a média aritmética de 4 notas para 50 alunos

início

/* Declarações das variáveis */<span style="mso-char-type: symbol; mso-symbol-font-family: Symbol; font-size: 16.0pt; mso-bidi-font-size: 10.0pt; font-family: Symbol; mso-ascii-font-family: Arial; mso-fareast-font-family: Times New Roman; mso-hansi-font-family: Arial; mso-bidi-font-family: Arial; mso-ansi-language: PT-BR; mso-fareast-language: PT-BR; mso-bidi-language: AR-SA"></span>

variáveis reais: nota1, nota2, nota3, nota4, média

variáveis inteiras: numAlunos

numAlunos = 1  /* Inicialização do contador */

enquanto numAlunos < = 50 faça  /* verificação da continuidade */

/* Obtenção da notas */

escreva "Informe as quatro 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

numAlunos = numAlunos + 1  /* atualização do contador */

fim enquanto

fim

 

Exemplo: modificar o algoritmo 6, considerando uma determinada quantidade de alunos.

 


Algoritmo 9 - Calcular a média aritmética de 4 notas para um número determinado de alunos

início

/* Declarações das variáveis */<span style="mso-char-type: symbol; mso-symbol-font-family: Symbol; font-size: 16.0pt; mso-bidi-font-size: 10.0pt; font-family: Symbol; mso-ascii-font-family: Arial; mso-fareast-font-family: Times New Roman; mso-hansi-font-family: Arial; mso-bidi-font-family: Arial; mso-ansi-language: PT-BR; mso-fareast-language: PT-BR; mso-bidi-language: AR-SA"></span>

variáveis reais: nota1, nota2, nota3, nota4, média

variáveis inteiras: numAlunos, totalDeAlunos

/* Obtenção do número de alunos */<span style="mso-char-type: symbol; mso-symbol-font-family: Symbol; font-size: 16.0pt; mso-bidi-font-size: 10.0pt; font-family: Symbol; mso-ascii-font-family: Arial; mso-fareast-font-family: Times New Roman; mso-hansi-font-family: Arial; mso-bidi-font-family: Arial; mso-ansi-language: PT-BR; mso-fareast-language: PT-BR; mso-bidi-language: AR-SA"></span>

escreva "Informe o número total de alunos: "

leia totalDeAlunos

numAlunos = 1  /* inicialização do contador */

enquanto numAlunos < = totalDeAlunos faça  /* verificação da continuidade */

/* Obtenção da notas */

escreva "Informe as quatro 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

numAlunos = numAlunos + 1  /* atualização do contador */

fim enquanto

fim

 


Versão Word (.doc) do material acima.