Introdução a Computação
Aula 01 – Resolução de Problemas Lógicos
Edirlei Soares de Lima
<elima@inf.puc-rio.br>
Desafio 1
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.
Desafio 1 - Solução
Qual o caminho para
a sua aldeia?
Desafio 2
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 2 – 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 3
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 3 – Solução 1
1
ª pesagem:
1
ª possibilidade: pesos iguais -
bola extra é a mais leve!
ª possibilidade: a bola mais
2
leve está no grupo mais leve -
descarta-se a bola extra e o
grupo mais pesado e realiza-se
nova pesagem.
2
3
ª pesagem:
descarta-se o grupo mais
pesado e realiza-se nova
pesagem.
ª pesagem:
Determina-se a bola mais leve!
Desafio 3 – Solução 2
1
ª pesagem:
1
a bola está no grupo extra - 6
bolas são descartadas e
ª possibilidade: pesos iguais -
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 3 – Solução
Como descrever passo a passo a solução do
Desafio 3?
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 3 – Solução
Como descrever passo a passo a solução do
Desafio 3?
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;
Desafio 4
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
enquanto dorme, escorrega 1 metro.
metros pela parede; mas à noite,
Depois de quantos dias ela consegue
chegar na saída do poço?
Desafio 4 - Solução
Dia Subida Descida Posição atual
(m)
(m)
(m)
1º
2º
3º
4º
5º
6º
7º
8º
9º
2
1
1
2
1
2
2
1
3
2
1
4
2
1
5
2
1
6
2
1
7
2
1
8
2
0
10
Desafio 4 - 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