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.
·
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
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
3.5
- Estruturas de Controle
·
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.