Aula anterior...
• Formulação do problema
– Salientando a forma como o computador será utilizado
(e.g. ler do teclado ... calcular ... e escrever no écran ...)
• Especificação
– Identificação/caracterização dos dados de entrada
– Identificação/caracterização dos dados de saída
– Identificação do método ou solução para chegar dos
dados de entrada aos de saída
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
Aula anterior... (cont.)
• Definição do algoritmo
(aquilo que realmente interessa)
– Usando vocabulário e sintaxe próximas do Pascal
– Decompor o método ou solução que se pretende seguir
numa sequência de passos
• Escrita do Programa
– Se o algoritmo estiver bem definido e detalhado esta
parte poderá resumir-se a uma simples tradução
daquele para Pascal
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
Esta Aula ...
• Definição do algoritmo
(continuação)
– Método de decomposição hierárquica utilizando níveis
crescentes de detalhe (abordagem top-down)
– Primeira noção de encapsulamento de operações
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
Decomposição hierárquica
Nível 1
nome: asdzxc
begin
passo 1
passo 2
passo 3
end.
nome: passo 1
begin
passo 1.1
passo 1.2
passo 1.3
end
nome: passo 3
begin
passo 3.1
passo 3.2
passo 3.3
passo 3.4
end
Nível 2
nome: passo 2
begin
passo 2.1
passo 2.2
end
...
Nível 3
nome: passo 3.2
begin
passo 3.2.1
passo 3.2.2
end
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
Conversão de distâncias (milhas para quilómetros)
Sua formulação para resolução no computador: Dada uma distância, expressa em
milhas, que é lida do teclado, convertê-la para quilómetros e escrevê-la no écran do
monitor vídeo.
Variável de entrada: MILHAS (distância expressa em milhas)
valor numérico positivo ou nulo
Variável de saída: KILOMETROS (distância expressa em quilómetros)
valor numérico representado com 3 casas decimais
Solução: KILOMETROS = 1.609 * MILHAS
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
Conversão de distâncias (milhas para quilómetros)
(Decomposição ao nível 1)
Algoritmo:
nome: Conversão de distâncias (milhas para quilómetros)
begin
leitura com validação de uma distância expressa em milhas (MILHAS);
conversão da distância de milhas para quilómetros (MILHAS, KILOMETROS);
impressão da distância expressa em quilómetros (KILOMETROS)
end
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
Conversão de distâncias (milhas para quilómetros)
(Decomposição ao nível 2)
nome: Leitura com validação de uma distância expressa em milhas
begin
repetir
escrita no écran do monitor vídeo da mensagem ‘Distância em milhas? ‘;
leitura do valor introduzido pelo teclado (MILHAS)
até que MILHAS >= 0.0
end
nome: Conversão da distância de milhas para quilómetros
begin
KILOMETROS = 1.609 * MILHAS
end
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
Conversão de distâncias (milhas para quilómetros)
(Decomposição ao nível 2)
nome: Escrita no écran do monitor vídeo da distância expressa em quilómetros
begin
escrita no écran do monitor vídeo da mensagem ‘Distância em quilómetros é ‘;
escrita no écran do monitor vídeo do valor de KILOMETROS com 3 casas decimais;
mudança de linha
end
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
Conversão de distâncias (milhas para quilómetros)
program conv_dist;
const Km_por_milha= 1.609;
var Km, milhas: real;
begin
repeat
write(‘Escreva uma distância em milhas: ‘);
readln(milhas);
until milhas >= 0.0;
Km:= Km_por_milha * milhas;
writeln(‘A distância em Kilómetros é: ‘,Km:0:3);
end
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
Resolução da equação de 2º grau
Sua formulação para resolução no computador: Dados os parâmetros A, B e C, que
são lidos do teclado, determinar as raízes da equação de 2º grau, Ax2+Bx+C=0, e
escrevê-las no écran do monitor vídeo.
Variáveis de entrada: A, B, C (parâmetros da equação)
A é um valor numérico não nulo, B e C são valores
numéricos quaisquer
Variáveis de saída: X1R, X1I, X2R, X2I (raízes da equação)
valores numéricos representados em notação científica,
com 4 algarismos significativos na mantissa
Solução:
 = B2 - 4  A  C
  0  X1R =
-B+ 
2 A
  0  X1R =
-B
2 A
X1I = 0
X2R =
-B - 
2 A
-
2 A
X2R =
-B
2 A
X1I =
X2I = 0
X2I = -
-
2 A
(raizes reais)
(raizes complexas conjugadas)
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
Resolução da equação de 2º grau
Algoritmo:
(Decomposição ao nível 1)
nome: Resolução da equação de 2º grau Ax2+Bx+C = 0
begin
leitura com validação dos coeficientes da equação (A, B, C);
determinação das raízes da equação por aplicação da fórmula resolvente
(A, B, C, X1R, X1I, X2R, X2I);
impressão das raízes (X1R, X1I, X2R, X2I)
end
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
Resolução da equação de 2º grau
(Decomposição ao nível 2)
nome: Leitura com validação dos coeficientes da equação
begin
escrita mais ou menos centrada no écran da mensagem
‘Resolução da equação de 2º grau Ax^2+Bx+C = 0‘;
mudança de linha;
repetir
escrita no écran da mensagem ‘A = ‘;
leitura do valor introduzido pelo teclado (A)
até que A <> 0.0;
escrita no écran da mensagem ‘B = ‘;
leitura do valor introduzido pelo teclado (B);
escrita no écran da mensagem ‘C = ‘;
leitura do valor introduzido pelo teclado (C)
end
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
Resolução da equação de 2º grau
(Decomposição ao nível 2)
nome: Determinação das raízes da equação por aplicação da fórmula resolvente
begin
DELTA := B2 - 4AC;
se DELTA >= 0.0 então
begin (* raízes reais *)
X1R := (-B + (DELTA)) / 2A;
X1I := 0.0;
X2R := (-B - (DELTA)) / 2A;
X2I := 0.0
end
ou então
begin (* raízes complexas conjugadas *)
X1R := -B / 2A;
X1I := (-DELTA) / 2A;
X2R := X1R;
X2I := -X1I
end
end
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
Resolução da equação de 2º grau
nome: Impressão das raízes
(Decomposição ao nível 2)
begin
(* os valores relativos às raízes deverão ser escritos em notação científica, com 4
algarismos significativos na mantissa *)
escrita no écran da mensagem ‘X1 = ‘; (* X1 = (X1R) + i (X1I) *)
seguida do valor de X1R,
seguido da mensagem ‘ + i‘;
seguida do valor de X1I;
mudança de linha;
escrita no écran da mensagem ‘X2 = ‘;
seguida do valor de X2R,
seguido da mensagem ‘ + i‘;
seguida do valor de X2I;
mudança de linha;
end
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
Mudança da roda de um automóvel que tem um pneu furado
Formulação:
Dados um automóvel que tem um pneu furado, uma roda suplente, uma
chave de cruz e um macaco, descrever as operações necessárias à
mudança da roda com o pneu furado.
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
Mudança da roda de um automóvel que tem um pneu furado
Algoritmo:
(Decomposição ao nível 1)
nome: Mudança da roda de um automóvel que tem um pneu furado
begin
se há tampão então
tirar o tampão;
soltar as porcas;
posicionar o macaco e levantar o carro;
desapertar e retirar as porcas;
trocar as rodas;
colocar e apertar as porcas;
baixar o carro e retirar o macaco;
dar um aperto forte às porcas;
se há tampão então
colocar o tampão
end
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
Mudança da roda de um automóvel que tem um pneu furado
(Exemplo de decomposição ao nível 2)
nome: Soltar as porcas
begin
para todas as porcas (1 de cada vez) fazer
begin
posicionar a chave de cruz sobre a porca;
repetir
aplicar o binário à chave no sentido do desaperto;
até a chave rodar;
retirar a chave da porca;
end
end
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
Mudança da roda de um automóvel que tem um pneu furado
(Exemplo de decomposição ao nível 2)
nome: Posicionar o macaco e levantar o carro;
begin
enquanto não se encontrar o encaixe do macaco fazer
begin
procurar encaixe;
end
colocar macaco no encaixe;
repetir
rodar uma volta no macaco;
até que roda furada esteja no ar;
end
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
Mudança da roda de um automóvel que tem um pneu furado
(Exemplo de decomposição ao nível 2)
nome: Desapertar e retirar as porcas
begin
para todas as porcas (1 de cada vez) fazer
begin
posicionar a chave de cruz sobre a porca;
repetir
aplicar o binário à chave no sentido do desaperto;
até soltar porca do parafuso;
retirar a chave e a porca;
end
end
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
Programar um Micro-Rato
• Problema: Programar o robot para ir da
posição de partida (P) para a posição de
chegada (C) desviando-se dos obstáculos que
encontrar pelo caminho.
P
Comandos reconhecidos pelo robot (instruções):
Virar à direita/esquerda
Andar em frente/parar
Possui sensores (variáveis de entrada):
de obstáculos (dir/fre/esq/nenhum)
de chegada (dir/fre/esq/baixo)
C
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
Programar um Micro-Rato
nome: micro-rato
Nível 1
P
begin
C
enquanto não estiver na Chegada fazer
begin
orientar-se para a chegada
andar em frente
Comandos reconhecidos pelo robot:
se encontra obstáculo
Virar à direita/esquerda
então desviar-se de obstáculo
Andar em frente/parar
end
Possui sensores:
Não existem no
parar
de obstáculos (dir/fre/esq/ne)
vocabulário básico!
end
de chegada (dir/fre/esq/cima)
É necessário prosseguir
a decomposição...
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
Programar um Micro-Rato
Nível 2
P
nome: orientar-se para a chegada
C
begin
repetir
se Chegada à direita então
virar à direita
Comandos reconhecidos pelo robot:
ou então
Virar à direita/esquerda
se Chegada à esquerda então
Andar em frente/parar
virar à esquerda
Possui sensores:
até que Chegada em frente
de obstáculos (dir/fre/esq)
end
de chegada (dir/fre/esq/cima)
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
Programar um Micro-Rato
Nível 2
nome: desviar-se de obstáculo
begin
repetir
se obstáculo à direita então
virar à esquerda
se obstáculo à esquerda então
virar à direita
se obstáculo em frente então
virar à esquerda
até que nenhum obstáculo
andar em frente
end
P
C
Comandos reconhecidos pelo robot:
Virar à direita/esquerda
Andar em frente/parar
Possui sensores:
de obstáculos (dir/fre/esq)
de chegada (dir/fre/esq/cima)
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
O robot Francisco
Apresentação: O Francisco é um robot formado por uma base móvel, que possibilita a
sua deslocação linear, para a esquerda e para a direita, por uma câmara vídeo, que
lhe permite a detecção rudimentar de objectos, presentes no cenário visualizado, e a
determinação da cor de objectos particulares, e por um braço articulado, terminado
numa pinça, que pode ser usado para pegar em objectos de pequenas dimensões.
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
O robot Francisco
Operações que o Francisco executa:
deslocar-se para a posição (X)
- dada uma coordenada linear de posição, o Francisco acciona o motor da sua base
móvel e desloca-se para a posição indicada;
pegar num objecto
- o Francisco usa a pinça do seu braço articulado para pegar num objecto que ele
detectou no cenário visualizado;
pousar um objecto
- o Francisco move o seu braço articulado para pousar, no centro da área visualizada,
o objecto que segura na pinça;
detecção de objectos
- com a sua câmara vídeo, o Francisco pode determinar se existem ou não objectos
no cenário que visualiza (função booleana);
cor do objecto
- igualmente com a sua câmara vídeo, o Francisco pode ainda determinar a cor do
objecto que segura na pinça (função que devolve o nome de uma cor).
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
Separação dos berlindes
Sua formulação: Dados três vasos cilíndricos, A, B, C, colocados sobre uma mesa,
que contêm berlindes de vidro de três cores diferentes, ensinar o Francisco a separálos, de modo a que os berlindes verdes fiquem no vaso A, os berlindes azuis no vaso
B e os berlindes rosa no vaso C.
A
B
C
Variáveis de entrada:
A, B, C
(coordenadas lineares de posição dos vasos A, B, C)
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
Separação dos berlindes
Solução: Para resolver o problema, é necessário o recurso a um vaso auxiliar, onde os
berlindes são despejados, antes de se iniciar o processo de separação. A separação,
propriamente dita, vai consistir num processo repetitivo, em que cada berlinde é
retirado do vaso auxiliar e, de acordo com a cor que apresenta, é colocado no vaso
de destino.
A
B
C
A
U
X
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
Separação dos berlindes
Algoritmo:
(Decomposição ao nível 1)
nome: Separação dos berlindes
begin
deslocar todos os berlindes do vaso de partida para o vaso de destino (A, AUX);
deslocar todos os berlindes do vaso de partida para o vaso de destino (B, AUX);
deslocar todos os berlindes do vaso de partida para o vaso de destino (C, AUX);
while há berlindes no vaso (AUX) do
retirar um berlinde do vaso e arrumá-lo no vaso de destino correspondente (A, B, C)
end
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
Separação dos berlindes
(Decomposição ao nível 2)
nome: Deslocar todos os berlindes do vaso de partida para o vaso de destino
procedimento
variáveis de entrada: X - vaso de partida
Y - vaso de destino
begin
while há berlindes no vaso (X) do
begin
pegar num objecto;
colocar berlinde no vaso (Y)
end
end
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
Separação dos berlindes
(Decomposição ao nível 2)
nome: Há berlindes no vaso
função booleana
retorna TRUE, se existir pelo menos um berlinde no vaso
FALSE, em caso contrário
variável de entrada: X - vaso em análise
begin
deslocar-se para a posição (X);
TESTE := detecção de objectos;
retornar o valor de TESTE
end
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
Separação dos berlindes
(Decomposição ao nível 2)
nome: Retirar um berlinde do vaso e arrumá-lo no vaso de destino correspondente
begin
pegar num objecto;
COR := cor do objecto;
case COR of
VERDE: colocar berlinde no vaso (A);
AZUL: colocar berlinde no vaso (B);
ROSA: colocar berlinde no vaso (C)
end
end
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
Separação dos berlindes
(Decomposição ao nível 3)
nome: Colocar berlinde no vaso
procedimento
variável de entrada: Y - vaso de destino
begin
deslocar-se para a posição (Y);
pousar um objecto
end
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
Separação dos berlindes
Observações
O problema, tal como foi formulado, não tem variáveis de saída, porque o Francisco é
um computador muito especial. Embora, como a generalidade dos computadores e dos
seres humanos, o Francisco processe informação, os resultados por ele obtidos traduzemse em acções concretas.
Contudo, se estivéssemos interessados numa solução que pudesse ser executada num
computador convencional, as três variáveis de entrada anteriores seriam substituídas por
nove variáveis de entrada / saída (variáveis de estado), do tipo N (vaso, cor), relativas ao
n.º de berlindes de cor cor, existentes no vaso vaso.
A intenção expressa de implementar algumas das operações anteriores, através de
mecanismos de encapsulamento de informação, permitiu aumentar o vocabulário do
Francisco. Agora, além das cinco operações base, ele conhece mais três: deslocar todos
os berlindes de um vaso de partida para um vaso de destino, existência de berlindes num
vaso e colocar um berlinde num vaso.
Este mecanismo é extremamente importante, porque permite dar concisão, clareza e
robustez às descrições das soluções de problemas complexos.
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro
Charada com berlindes
Sua formulação: Considere de novo três vasos cilíndricos, A, B, C, colocados sobre
uma mesa, que contêm berlindes de vidro de duas cores diferentes, rosa e azul, e
procure descobrir em que situação ficam os vasos, após a realização das operações
seguintes:
1) Se o vaso C contiver berlindes, desloque-os todos para o vaso A;
2) Se o vaso A contiver, pelo menos, um berlinde rosa, desloque um berlinde rosa do
vaso A para o vaso C;
3) Se o vaso B contiver, pelo menos, um berlinde azul, desloque um berlinde azul do
vaso B para o vaso A;
4) Se o vaso B, ou o vaso C, contiver berlindes azuis, regresse ao passo 2.
Descreva a seguir uma solução do problema que possa ser realizada pelo Francisco!
Departamento de Electrónica e Telecomunicações - Universidade de Aveiro