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