APC 01

Instituto Federal de Brasília
Núcleo Taguatinga
Disciplina: Algoritmo e Programação de Computadores

LISTA 01

BRASÍLIA 2015
Algoritmo e Programação de Computadores
Lista 1
1) O barquinho do camponês comporta apenas um item, além dele próprio. O barquinho pode lervar e trazer itens, respeitando as seguintes regras.
(A) O lobo devora a ovelha se os dois ficarem sozinhos;
(B) A ovelha come o repolho se ficar sozinho com ele.

O objetivo do camponês é atravessar o lobo, a ovelha e o repolho da margem esquerda do rio para a margem direita. Considere que o camponês (C), o lobo (L), a ovelha (O) e o repolho estejam todos na margem A do rio. Encontre uma sequência de movimento do barquinho, do camponês, dos animais e do repolho, de maneira que, ao final da sequência, todos estejam em segurança na margem B.

1. transportar "C" e "O" para o outro lado
2. "C" volta sozinho
3. Transportar "C" e "R"
4. "C" e "O" voltam
5. Transportar "C" e "L"
6. "C" volta
7. Transportar "C" e "O"
8. fim

2) Suponha que você tenha dois jarros, um de cinco litros e um de três litros. Suponha também que você tenha uma fonte inesgotável de água. Encontre uma sequência de movimentos de encher e esvaziar os jarros, de maneira que, ao final da sequência, você tenha quatro litros de água dentro do jarro de cinco litros.

1) Encher o jarro de 5L
2) Complete o de 3L deixando 2L no de 5L
3) Esvazie o de 3L
4) Coloque os 2L que estava no de 5L no de 3L
5) Encher o jarro de 5L
6) Complete o jarro de 3L com 1L de 5L
7) O jarro de 5L fica com 4L
8) Fim

3) Suponha que você tenha 1000 moedas e 10 caixas pretas vazias. Seu objetivo é distribuir as 1000 moedas nas caixas pedras, lacrá-las, rotulá-las com a informação de quantas moedas cada caixa contém, de maneira que seja possível obter qualquer valor de 1 até 1000 apenas, apenas combinando as caixas, sem alternar o seu conteúdo.

Caixa Moedas
1 1
2 2
3 4
4 8
5 16
6 32
7 64
8 128
9 256
10 489

1) Na 1ª caixa