1-Algoritmos e o Computador

Prévia do material em texto

27/01/2015
1
Algoritmos e o Computador
Algoritmos Computacionais
Livro de Texto
 FORBELLONE, A. Lógica de programação: a construção 
de algoritmos e estrutura de dados. São Paulo: Pearson, 
2005.
27/01/2015
2
Procedimento de Avaliação
 AP1: 10% Programa. 90% Prova.
 AP2: 10% Programa. 90% Prova.
 AP3: 100% Prova.
 AP1 + AP2 é 60% da nota
 AP3 é 40% da nota
 Nota mínima para passar: 5,0.
Academus
 Em Academus está toda a informação sobre a disciplina. 
 Ementa
 Objetivos
 Conteúdo
 Cronograma
 Data
 Assunto
 Objetivo
 Conteúdo
 Estudo Independente
 Avaliação
 Material de apoio
 Fórum
27/01/2015
3
Programação em C
 Compilador: Dev-C++
 Site: http://orwelldevcpp.blogspot.com.br/
Algoritmos
 Um algoritmo pode ser definido como uma sequencia de 
passos que visam a atingir um objetivo bem definido. 
 Para poder desenvolver um algoritmo precisamos utilizar 
lógica.
 Exemplos de algoritmos comuns no cotidiano:
 Uma receita de bolo,
 A solução de uma equação do 2º grau.
 Buscar um livro na biblioteca.
 Orientação para se chegar em algum endereço
27/01/2015
4
Propriedades de Algoritmos
 Ações simples e bem definidas (não ambíguas)
 Sequencias ordenadas de ações
 Sequencia finita de passos.
Exemplos
 Trocar uma lâmpada
 Seqüenciação
Algoritmo 1.1:
1. pegar uma escada;
2. posicionar a escada embaixo da lâmpada;
3. buscar uma lâmpada nova;
4. subir na escada;
5. retirar lâmpada velha;
6. colocar lâmpada nova.
27/01/2015
5
Exemplos
 Trocar uma lâmpada SE estiver queimada
 Seleção (Decisão)
Algoritmo 1.2:
1. pegar uma escada;
2. posicionar a escada embaixo da lâmpada;
3. buscar uma lâmpada nova;
4. acionar o interruptor;
5. se a lâmpada não acender, então
6. subir na escada;
7. retirar lâmpada queimada;
8. colocar lâmpada nova.
Exemplos
 Trocar uma lâmpada SE estiver queimada (v. 2)
 Seleção (Decisão)
Algoritmo 1.3: Evita buscar a escada e lâmpada
1. acionar o interruptor;
2. se a lâmpada não acender, então
3. pegar uma escada;
4. posicionar a escada embaixo da lâmpada;
5. buscar uma lâmpada nova;
6. subir na escada;
7. retirar lâmpada queimada;
8. colocar lâmpada nova.
27/01/2015
6
Exemplos
 Trocar uma lâmpada SE estiver queimada (v. 3)
 Seleção (Decisão)
Algoritmo 1.4: Re-teste depois da troca
1. acionar o interruptor;
2. se a lâmpada não acender, então
3. pegar uma escada;
4. posicionar a escada embaixo da lâmpada;
5. buscar uma lâmpada nova;
6. acionar o interruptor;
7. subir na escada;
8. retirar lâmpada queimada;
9. colocar lâmpada nova;
10. se a lâmpada não acender, então
11. retirar lâmpada queimada;
12. colocar lâmpada nova;
13. se a lâmpada não acender, então
. . .
Exemplos
 Trocar uma lâmpada SE estiver queimada (v. 4)
 Repetição
Algoritmo 1.5: Re-teste depois da troca (por repetição)
1. acionar o interruptor;
2. se a lâmpada não acender, então
3. pegar uma escada;
4. posicionar a escada embaixo da lâmpada;
5. buscar uma lâmpada nova;
6. acionar o interruptor;
7. subir na escada;
8. retirar lâmpada queimada;
9. colocar lâmpada nova;
10. enquanto a lâmpada não acender, faça
11. retirar lâmpada queimada;
12. colocar lâmpada nova;
27/01/2015
7
Exemplos
 Trocar 10 lâmpadas SE estiverem queimadas
 Repetição
Algoritmo 1.6: Escrever 10 vezes
1. acionar o interruptor do primeiro soquete;
2. se a lâmpada não acender, então
3. pegar uma escada;
4. posicionar a escada embaixo da lâmpada;
5. buscar uma lâmpada nova;
6. acionar o interruptor;
7. subir na escada;
8. retirar lâmpada queimada;
9. colocar lâmpada nova;
10. enquanto a lâmpada não acender, faça
11. retirar lâmpada queimada;
12. colocar lâmpada nova;
13. acionar o interruptor do segundo soquete;
14. . . .
Exemplos
 Trocar 10 lâmpadas SE estiverem queimadas (v. 2)
 Repetição
Algoritmo 1.7: Contagem de trocas
1. ir até o interrupto do primeiro soquete;
2. enquanto a quantidade de soquetes testados for menor que 10, faça
3. acionar o interruptor;
4. se a lâmpada não acender então
5. pegar uma escada;
6. posicionar a escada embaixo da lâmpada;
7. buscar uma lâmpada nova;
8. acionar o interruptor;
9. subir na escada;
10. retirar lâmpada queimada;
11. colocar lâmpada nova;
12. enquanto a lâmpada não acender, faça
13. retirar lâmpada queimada;
14. colocar lâmpada nova;
15. ir até o interruptor do próximo soquete;
. . .
27/01/2015
8
Formas de Representação de Algoritmos
 Gráficas (Fluxograma e Chapin)
 Vantagens
 Maior clareza no fluxo de execução
 Linguagem visual
 Desvantagens
 Requer conhecimento de convenções gráficas
 Mais trabalhoso em decorrência de seus desenhos
 Dificuldade para fazer correções
 Textuais (Pseudocódigo, Português Estruturado)
 Apresenta mais vantagens, desde que se tomem alguns cuidados:
 Riqueza gramatical de nossa língua pode levar a ambiguidades
 Para resolver, utilizaremos um conjunto restrito de regras, conhecido como 
Português Estruturado
Formas de Representação
 Algoritmo 1.7 em Chapin
ir para o primeiro soquete
soquetes testados < 10
acionar o interruptor
F
pegar uma escada
colocar a escada embaixo do soquete
buscar lâmpada nova
acionar o interruptor
subir na escada
retirar lâmpada queimada
colocar lâmpada nova
lâmpada não acendeu
retirar lâmpada queimada
colocar lâmpada nova
ir para o próximo soquete
lâmpada não acendeu 
27/01/2015
9
Formas de Representação
 Algoritmo 1.7 em Fluxograma
início
ir para o primeiro soquete
soquetes
restantes < 10
acionar o interruptor
pegar uma escada
posicionar escada
buscar lâmpada nova
acionar o interruptor
não
acendeu?
subir na escada
retirar a lâmpada queimada
colocar lâmpada nova
acionar o interruptor
não
acendeu?
retirar a lâmpada queimada
colocar lâmpada nova
ir ao próximo soquete
fim
F
F
F
V
V
V
Algoritmo: Receita de Bolo Comum de Ovos
 Passo 1: Receber os ingredientes
 2 xícaras de açúcar;
 3 ovos;
 250g de margarina;
 3 xícaras de farinha de trigo;
 1 e ½ colher de fermento;
 1 xícara de leite.
 Passo 2: Aqueça o forno a 180 graus;
 Passo 3: Bata as claras em neve e reserve;
 Passo 4: Em uma travessa, bata o açúcar, a manteiga e as gemas;
 Passo 5: Misture a farinha e o leite;
 Passo 6: Bata bem, até ficar bem homogêneo;
 Passo 7: Com a ajuda de uma colher, acrescente o fermento;
 Passo 8: Por último, adicione as claras em neve e mexa cuidadosamente;
 Passo 9: Coloque em uma forma untada com manteiga e farinha de trigo e leve ao forno 
médio para assar por aproximadamente 35 minutos ou até que, ao espetar um palito, esse saia 
seco;
 Passo 10: Após assado, desligue o forno e deixe o bolo esfriar;
 Passo 11: Desenforme e saboreie.
27/01/2015
10
Algoritmo: Torre de Hanói
 Mover os três discos de uma haste para outra, 
considerando as seguintes regras: 
 pode-se mover apenas um disco de cada vez;
 nunca pode ser colocado um disco maior sobre um menor
Solução à Torre de Hanói
27/01/2015
11
Solução escrita do Algoritmo
 Nomeamos as hastes como A, B e C, e os discos como 1, 
2, e 3. Considera-se que inicialmente os discos estão na 
haste A.
 Passos
1. Mover o disco 1 de A para C
2. Mover o disco 2 de A para B
3. Mover o disco 1 de C para B
4. Mover o disco 3 de A para C
5. Mover o disco 1 de B para A
6. Mover o disco 2 de B para C
7. Mover o disco 1 de A para C 
Atividade: Problema 1.5
 Considere que uma calculadora comum, de quatro 
operações, está com as teclas de divisão e multiplicação 
inoperantes. Escreva algoritmos que resolvam as 
expressões matemáticas a seguir usando apenas as 
operações de adição e subtração.
 12 x 4
 10	÷ 2
27/01/2015
12
Algoritmo de Multiplicação
 multiplicando x multiplicador = resultado
 Algoritmo:
1. Digite o multiplicando na calculadora
2. Some o multiplicando o (multiplicador – 1) número de 
vezes.
3. O resultado será o número mostrado na calculadora.
Algoritmo de divisão
 dividendo ÷ divisor = quociente + resto
 Algoritmo
1. Digite o dividendo na calculadora.
2. Conte quantas vezes pode subtrair o divisor do número 
mostrado na calculadora.3. O quociente é a conta do passo anterior
4. O resto é o número mostrado na calculadora.
27/01/2015
13
Desenvolvimento de Algoritmos
 Para escrever um algoritmo devemos escrever instruções 
que o executor (pessoa ou máquina) possa entender 
claramente sem ambiguidades.
 Nesta disciplina vamos a escrever algoritmos para ser 
executados no computador.
 Instruções como bater as claras de ovos ou subir a 
escada, não faz sentido para um PC.
 A primeira coisa que temos que aprender antes de 
escrever um algoritmo para o computador é entender a 
linguagem que um computador entende.
Organização Básica de um Computador
 Unidade de entrada
 Teclado
 Mouse
 Unidade de saída
 Monitor de vídeo
 Impressora
 Unidade de processamento central (CPU)
 Nela são realizadas as operações aritmética, lógicas, e de controle.
 Unidade de memória
 RAM
 Armazenamento temporário.
 Armazena dados de informações que serão utilizados no 
processamento.
 Armazena o programa em execução.
 Tem dois componentes, o endereço e o conteúdo.
27/01/2015
14
Informação no computador
 Toda a informação no computador é em números 
binários (0 e 1). 
 A única coisa que o computador entende são números 
binários.
 Toda interação com o computador, já seja programas ou dados 
devem ser convertidos a números binários.
 Números: 10012 = 910
 Letras ou Caráteres (ASCII) : a = 01100001
Linguagens de programação de baixo nível
 Instruções na linguagem de máquina.
 Difícil de programar e modificar.
 Instruções na linguagem assembly
 Uma relação de instruções de um-para-um com a linguagem de 
máquina.
 Ainda difícil de programar.
 Precisa de um tradutor (assembler)
27/01/2015
15
Linguagens de programação de alto nível
 Uma relação de instruções de um-para-várias com a linguagem de 
máquina.
 Precisa de um compilador ou interpretador para converter a 
representação a números binários.
 Linguagens procedimentais.
 C, Pascal, Java, etc.
 Linguagens declarativas.
 Funcionais
 LISP
 Lógicas
 PROLOG
 Muito diferente a programação com linguagens procedimentais 
em relação com linguagens declarativas. 
 Nesta disciplina vamos a escrever algoritmos para programar 
em linguagens procedimentais (C, Java, Pascal)
Fases de um algoritmo.
 A maioria dos algoritmos tem três fases fundamentais
 Dados de entrada
 Processamento
 Dados processados ou de saída.
 Os dados são colocados na memória.
 Que tipos de dados podemos colocar na memória?
 Tipos básicos: 
 Numéricos (inteiros ou reais)
 Caracteres
 Lógicos
 Tipos compostos
 Registros
 Listas
 Vetores
 Matrizes
27/01/2015
16
Como podemos escrever um algoritmo.
 Usando Fluxograma
 São formas de representação , através de figuras geométricas, interligada 
por setas que indicam o caminho a ser seguido
 Usando Diagramas de Chapin
 As estruturas lógicas são apresentadas por figuras retangulares, 
colocando uma após a outra, de cima para baixo.
 Pseudocódigo
 Usado em lugar de uma linguagem de programação especifica.
 Apresenta os passos de maneira informal.
 Alguns detalhes não são definidos.
 Português Estruturado
 Uma linguagem completa parecida a uma linguagem de programação.
 Mais detalhada do que Pseudocódigo.
 Menos detalhada do que uma linguagem de programação
 Linguagem de Programação.
 Pascal, C, Java, etc.
Fases na solução de problemas
 Entendimento do problema
 Criação de uma sequencia de operações (ou ações) que 
quando executadas, produzem a solução para o problema
 Execução desta sequencia de operações.
 Verificação de adequação da solução.
27/01/2015
17
Diretrizes para a elaboração de Algoritmos
 Identificação do problema
 determinar o que se quer resolver ou qual objetivo a ser atingido.
 Identificação do resultado (saída) do algoritmo
 as informações a serem geradas como resultado.
 Identificação das “entradas de dados”
 informações fornecidas, a partir das quais se desenvolverão os 
cálculos para produzir o resultado do algoritmo.
 Identificação das regras e limitações do problema ou das 
limitações do agente executante.
 Determinação do que deve ser feito para transformar as 
“entradas” em “saídas”.
 Construção do algoritmo, utilizando uma das formas de 
representação do algoritmos
 Teste da solução
Exemplo de um algoritmo
 Calcular a média final para esta disciplina. Os alunos 
realizarão três provas: AP1, AP2, e AP3.
 Para montar o algoritmos proposto, faremos três 
perguntas:
 Quais é o resultado (saída) do problema?
 O dado de saída será a média final
 Quais são os dados de entrada?
 Os dados de entrada são os resultados do AP1, AP2 e AP3
 Qual será o processamento a ser utilizado?
 O procedimento será somar todos os dados de entrada e dividi-los 
por 3.
27/01/2015
18
Algoritmo para a média da disciplina.
início 
//declaração de variáveis
real: AP1, AP2, AP3, Média;
//entrada de dados
leia (AP1, AP2, AP3); 
//processamento
Média ←	(AP1+AP2+AP3)/3;
//saída de dados
escreva (Média)
fim.