03 - Formalização de um Algoritmo

Prévia do material em texto

Introdução à Ciência da Computação
Departamento de Computação
Universidade Federal de Sergipe
Formalização de um Algoritmo
Prof. Kalil Araujo Bispo
Junho/2013
 
Objetivo da Aula
● Apresentar regras de sintaxe e algumas formas de 
resolução de problemas, seguindo essas regras
 
Introdução
● Utilização de convenções
● Por que formalizar a descrição de um algoritmo?
● Regras sintáticas
● Regras semânticas
 
Sintaxe
● Que comandos podem ser utilizados?
● Como escrever expressões?
● Como manipular dados?
– Variáveis
– Constantes
● Funções e procedimentos predefinidos
 
Exemplo de Sintaxe
● Área de um triângulo
– Especificar um algoritmo para calcular e exibir na tela 
a área de um triângulo de base b e altura h em que os 
valores b e h são fornecidos pelo usuário via teclado.
 
Exemplo de Sintaxe
● Passos para resolver um algoritmo
– Entender o Problema! (Muito Importante)
– Extrair informações (dados e operações)
– Relacionar com o conhecimento que se tem sobre o 
assunto
 
Exemplo de Sintaxe
Inicio
Pedir para o usuário digitar os valores de b e h
Calcular a área s usando s = (b*h)/2
Exibir o valor de s na tela
Fim
 
Exemplo de Sintaxe
● Utilizando uma 
representação 
mais formal
 
Exemplo de Sintaxe
● Utilizando outra representação mais formal
– Área do triângulo em portugol
Inicio
Leia (b, h);
S ← (b*h)/2;
Exiba (s);
Fim
 
Semântica
● Regras para interpretação dos símbolos usados na 
descrição
● Evitar ambiguidades
● Impedir a criação de símbolos ou comandos 
desnecessários
● Aproximação com as regras de linguagens de 
programação
 
Como resolver problemas
● A criação de um algoritmo consiste em
– A partir de um enunciado de um problema, obter um 
algoritmo que o resolva
● Pode-se dizer que a tarefa de resolver algoritmos é a 
tarefa de resolver problemas
● A solução de um problema envolve duas fases
– Análise
– Síntese
 
Análise de um problema
● Entender o problema
● Quais as dados necessários?
● Quais as condições para resolvê-lo?
● Os dados e condições são necessários? Suficientes? 
Redundantes? Contraditórios?
 
Análise de um problema
● Elaboração de um plano de ação
● Pode-se usar a experiência obtida em outros problemas
● Pode ser necessário utilizar problemas auxiliares
 
Análise do Problema
● Execução do plano definido na fase de análise
● Representação dos passos por meio de um algoritmo
● Verificação da solução através da execução do algoritmo
● Caso haja alguma discrepância, deve-se procurar a 
causa e repetir o ciclo de verificação
 
Exemplo
● Problema das Canetas
– Foram compradas 30 canetas iguais
– Foram pagas com uma nota de R$ 100,00, obtendo 
R$ 67,00 de troco
– Quanto custou cada caneta?
 
Exemplo
● Qual o problema? Os dados são suficientes? 
Redundantes? Contraditórios?
● O custo total das canetas é a diferença entre o valor que 
paguei e o troco que recebi
● Para encontrar o custo individual de cada caneta basta 
dividir o valor encontrado pelo número de canetas
 
Exemplo
● Solução
– Se eu tinha R$100,00 e recebi como troco R$67,00, o 
custo do total de canetas é a diferença entre os 
R$100,00 que eu tinha e os R$67,00 do troco
– Isto vale R$33,00. Portanto, esse valor foi o total pago 
pelas canetas
– Para saber quanto custou cada caneta, basta dividir 
os R$33,00 por 30, resultando no preço de cada 
caneta
– Assim, cada caneta custou o equivalente a R$1,10
 
Exemplo
● Matematicamente (síntese)
– Seja x o custo de cada caneta, então, 
– quantogastei = 30x. Como quantogastei + troco = 
R$100,00$, tem-se:
● 30x + 67 = 100
● 30x = 100 – 67
● 30x = 33
● X = 33 / 30
● X = 1,1
 
Exemplo
● Algoritmicamente (síntese)
● Início
Pegar os valores 30, 100 e 67
Subtrair 100 de 67 e dividir o resultado por 30
Mostrar o resultado final
● Fim
 
Exemplo
● E se quiséssemos o problema geral das canetas?
● Compraram-se N canetas iguais, que foram pagas com 
uma nota de Z reais, obtendo-se Y reais de troco. 
Quanto custou cada caneta?
 
Exemplo
● Podemos utilizar a experiência obtida no problema 
particular e generalizá-la
● Basta que sejam lidos os valores das variáveis N, Y e Z 
que o restante da solução é a mesma
 
Exemplo
Inicio
Ler os valores de N, Y e Z;
Subtrair Y de Z e dividir o resultado por N;
Mostrar o resultado final
Fim
 
Exemplo
● O que acontece se alguém tentar comprar zero canetas?
● Ou -3 canetas?
● E se os valores forem: N = 10, Z = 10 e Y = 15?
● É preciso levar em consideração as condições 
(implícitas) do problema.
 
Exemplo
Inicio
Ler os valores de N, Y e Z;
se Z > Y e N > 0 e Y ≥ 0 e Z > 0 então
● Subtrair Y de Z e dividir o resultado por N;
● Mostrar o resultado final;
senão
● Exibir a mensagem: “ERRO! Os valores são 
inconsistentes”
Fim
 
Exemplo
 
Exercícios para resolver
● Exercício 1
– Descreva como descobrir a moeda falsa em um grupo 
de cinco moedas, fazendo uso de uma balança 
analítica (sabe-se que a moeda falsa é mais leve que 
as outras), com o menor número de pesagens 
possível. Lembre-se de que sua descrição deve 
resolver o problema para qualquer situação.
– Dica: Pode-se resolver o problema em duas 
passagens
 
Exercícios para resolver
● Exercício 2
– Idem ao anterior, porém, só se sabe que a moeda 
falsa tem massa diferente. Para descobrir se ela é 
mais leve ou mais pesada que as outras, muda-se 
alguma coisa?
 
Exercício para resolver
● Exercício 3
– Idem ao Exercício 1.1, porém com nove moedas.
 
Exercícios para resolver
● Exercício 4
– Têm-se três garrafas, com formatos diferentes, uma 
cheia até a boca, com capacidade de oito litros e as 
outras duas vazias com capacidades de cinco e três 
litros respectivamente. Deseja-se separar o conteúdo 
da primeira garrafa em duas quantidades iguais. 
Elabore uma rotina que consiga realizar a tarefa, sem 
que se possa fazer medidas.
 
Exercícios para resolver
● Exercício 5
– Um caramujo está na parede de um poço a cinco 
metros de sua borda. Tentando sair do poço, ele sobe 
três metros durante o dia, porém desce escorregando 
dois metros durante a noite. Quantos dias levará para 
o caramujo conseguir sair do poço?
 
Introdução à Ciência da Computação
Departamento de Computação
Universidade Federal de Sergipe
Formalização de um Algoritmo
Prof. Kalil Araujo Bispo
Junho/2013
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31