Question

Problema do lobo, da ovelha e da couve. um lobo, uma ovelha e uma couve estao na mesma margem de um rio, juntamente com um barqueiro que os pretende transferir para outra margem. porem, como o barco (alem do barqueiro) so pode transportar um de cada vez, sabendo que o lobo gosta de comer ovelhas e que as ovelhas gostam de comer couves, o trasporte tem de serfeito de modo que na mesma margem nao fiquem a ovelha e o lobo ou a ovelha e a couve, em ambos os casos, sem a presenca do barqueiro. o problema consiste em propor ao barqueiro um plano eficinte para trasnportar o lobo, a ovelha e a couve saos e salvos para a outra margem. com este objectivo, desenhe um grafo cusjos vertices correspondem a situacoes admissiveis(por exemplo, a ovelha numa margem e o lobo ea couve na outra) e no qual dois vertices sao adjacentes se e so se as respectivas situacoes se podem transformar uma na outra com uma viagem entremargens. de que modo pode utilizar este grafo para resolver o problema?

Answer 1

Resposta:

primeiro você leva a ovelha para outra margem.

volta sem nada e pega o lobo e leva para outra margem e voltando trás a ovelha.

deixando a ovelha, pega o couve e leva pra outra margem.

volta sem nada, pega a ovelha novamente e leva ela para margem esquerda.

assim todos ficarão felizes.

espero ter ajudado!