INF 1005 – Programação I
Aula 01 – Resolução de Problemas Lógicos
Edirlei Soares de Lima
<elima@inf.puc-rio.br>
Desafio 1
•
•
•
Um senhor está em uma das margens de um
rio com uma raposa, uma galinha e um saco
de milho.
Ele pretende atravessar o rio com suas cargas
em um barco que só comporta ele e uma das
cargas.
Ele não pode deixar em uma das margens
sozinhos, a raposa e a galinha, nem a galinha
e o milho.
Desafio 1 - Solução
Desafio 1 - Solução
Desafio 1 - Solução
Desafio 1 - Solução
Desafio 1 - Solução
Desafio 1 - Solução
Desafio 1 - Solução
Desafio 1 - Solução
Desafio 1 - Solução
(
(
(
(
(
(
(
1) Atravessar a galinha.
2) Retornar sozinho.
3) Atravessar a raposa.
4) Retornar com a galinha.
5) Atravessar o milho.
6) Retornar sozinho.
7) Atravessar a galinha.
Desafio 2
•
•
Considere o seguinte ambiente:
–
1 balança (como a do desenho ao lado)
–
9 bolas - sendo que uma é mais leve do que as
demais.
Objetivo: Descobrir qual é a bola mais leve
com o menor número possível de pesagens.
Desafio 2 – Solução 1
•
1ª pesagem:
–
1ª possibilidade: pesos iguais - bola
extra é a mais leve!
–
2ª possibilidade: a bola mais leve está
no grupo mais leve - descarta-se a bola
extra e o grupo mais pesado e realiza-se
nova pesagem.
•
•
2ª pesagem:
–
descarta-se o grupo mais pesado e
realiza-se nova pesagem.
3ª pesagem:
–
Determina-se a bola mais leve!
Desafio 2 – Solução 2
•
•
1ª pesagem:
–
1ª possibilidade: pesos iguais - a bola
está no grupo extra - 6 bolas são
descartadas e realiza-se nova
pesagem.
–
2ª possibilidade: pesos diferentes -
bola mais leve está no grupo mais leve
-
6 bolas são descartadas e realiza-se
nova pesagem
2ª pesagem:
–
Determina-se a bola mais leve!
Desafio 2 – Solução
•
Como descrever passo a passo a solução do Desafio 2?
1
2
3
4
5
6
7
8
9
1
1
) Divida as bolas em 3 grupos;
) Escolha dois grupos para pesar e reserve o grupo extra;
) Coloque-os cada um em um lado da balança;
) Se os pesos forem iguais, descarte ambos os grupos;
) Senão, descarte o grupo mais pesado e o grupo extra;
) Divida as bolas em 3 grupos;
) Escolha dois grupos para pesar e reserve o grupo extra;
) Coloque-os cada um em um lado da balança;
) Se os pesos forem iguais descarte ambos os grupos;
0) Senão, descarte o grupo mais pesado e o grupo extra;
1) A bola que restou é a mais leve;
Desafio 2 – Solução
•
Como descrever passo a passo a solução do Desafio 2?
1
2
3
4
5
6
7
) Divida as bolas em 3 grupos;
) Escolha dois grupos para pesar e reserve o grupo extra;
) Coloque-os cada um em um lado da balança;
) Se os pesos forem iguais, descarte ambos os grupos;
) Senão, descarte o grupo mais pesado e o grupo extra;
) Repita os passos 1 a 5 até que reste apenas uma bola;
) A bola que restou é a mais leve;
afio 3
•
Premissas:
–
–
–
2 aldeias de índios:
• 1 canibal e 1 civilizada
O índio civilizado sempre diz a
verdade.
O índio canibal sempre mente.
•
Objetivo:
–
Ao chegar na encruzilhada fazer
uma única pergunta ao índio
para chegar à aldeia dos índios
civilizados.
De- Solução
Qual o caminho para a
sua aldeia?
Desafio 4
•
Torre de Hanói
–
–
–
Objetivo: mover os discos da haste
A para a haste C.
Restrições: Um disco NÃO pode
ficar sobre um disco menor que ele.
Qual a sequencia lógica para
resolver este problema?
Desafio 4 – Solução
Desafio 5
•
•
O pneu do seu carro furou...
Quais são os passos necessários para trocar o pneu
de um carro?
Desafio 5 - Solução
•
Algoritmo Textual Informal:
–
“Abra o porta-mala e verifique se todos acessórios estão
lá. Em caso negativo, feche o porta-malas e peça carona a
alguém. Em caso positivo, retire o triângulo, posicione-o a
cerca de 30 m do carro, e, depois, retire o estepe e o
macaco. Levante o carro...”
Desafio 5 - Solução
•
Algoritmo Gráfico Informal:
Desafio 5 - Solução
•
Algoritmo Textual Formal:
Abre(porta_malas)
Se acessorio_ok = FALSO Então
fecha(porta_malas)
espera_carona()
Senão
pega_triangulo()
.
.
.
Desafio 6
•
•
Uma lesma encontra-se no fundo de um poço seco de 10
metros de profundidade e quer sair de lá. Durante o dia,
ela consegue subir 2 metros pela parede; mas à noite,
enquanto dorme, escorrega 1 metro.
Depois de quantos dias ela consegue chegar na saída
do poço?
Desafio 6 - Solução
Dia
Subida (m) Descida (m)
Posição atual (m)
1º
2º
3º
4º
5º
6º
7º
8º
9º
2
2
2
2
2
2
2
2
2
1
1
1
1
1
1
1
1
0
1
2
3
4
5
6
7
8
10
Desafio 6 - Solução
Quantidade de dias = 1
Total percorrido = 2
Enquanto Total percorrido < 10 metros
Diminui 1 de Total percorrido (desceu na noite)
Soma 2 em Total percorrido (subiu no dia)
Incrementa 1 na quantidade de dias
Fim Enquanto
Mostrar a quantidade de dias
Exercícios
1
) Três gatos comem três ratos em três minutos.
Cem gatos comem cem ratos em quantos
minutos?
–
3 minutos
2
) O pai do padre é filho do meu pai. O que eu sou
do Padre?
–
Tio
3
) Se um bezerro pesa 75 kg mais meio bezerro,
quanto pesa um bezerro inteiro?
–
150 kg
Exercícios
4
) Qual o próximo número da sequência 7,8,10,13,17,?
–
22
5
) Qual o próximo número da sequência 25, 32, 37, 47,
8,?
5
–
71
6
) Um pai de 80kg e suas 2 filhas (40kg cada), precisam
sair de uma ilha com um barco. Porém a capacidade
do barco é de 80kg. Como farão para sair da ilha?
–
Vão as duas filhas. Uma delas volta. O pai sai. A outra
filha volta. As duas filhas saem juntas.