From: Khang
Subject: Help! cannibal and missionary problem in LISP or C++
Date:
Message-ID: <6g3b99$d3p$1@nntp.epix.net>
I'm looking for an algorithm or complete program (if possible) to solve the
cannibal and missionary problem in Lisp or C++ for an initial configuration
of (m m m c c c) on the left bank and 3 things can be taken in the boat at
once, please help.
Here is the complete problem:
Three missionaries and three cannibals are on one side of a river. They have
a boat that can carry three people. At least one missionary is needed in the
boat to row. They need to cross the river. The difficulty is that at no time
is it safe to allow the cannibals to outnumber the missionaries on either
side of the river or in the boat. If outnumbered,the missionaries would be
eaten by the cannibals. How should they proceed to cross the river in a
safe manner?
Thanks
Khang
"Khang" <··········@hotmail.com> writes:
> Three missionaries and three cannibals are on one side of a river. They have
> a boat that can carry three people. At least one missionary is needed in the
> boat to row. They need to cross the river. The difficulty is that at no time
> is it safe to allow the cannibals to outnumber the missionaries on either
> side of the river or in the boat. If outnumbered,the missionaries would be
> eaten by the cannibals. How should they proceed to cross the river in a
> safe manner?
I'd suggest tying the cannibals up, building a raft out of them (cf.
Monty Python), and towing them behind the boat. To implement this
solution in Lisp, you'll need to learn about bindings, constructors,
and floats.
--
Robert St. Amant Email: xxxxxxxxxxxxxx
Computer Science Department Voice: (919) 515-7938
North Carolina State University Fax: (919) 515-7925
········@ncsu.edu wrote in message ...
>"Khang" <··········@hotmail.com> writes:
>> Three missionaries and three cannibals are on one side of a river. They
have
>> a boat that can carry three people. At least one missionary is needed in
the
>> boat to row. They need to cross the river. The difficulty is that at no
time
>> is it safe to allow the cannibals to outnumber the missionaries on either
>> side of the river or in the boat. If outnumbered,the missionaries would
be
>> eaten by the cannibals. How should they proceed to cross the river in a
>> safe manner?
>
>I'd suggest tying the cannibals up, building a raft out of them (cf.
>Monty Python), and towing them behind the boat. To implement this
>solution in Lisp, you'll need to learn about bindings, constructors,
>and floats.
Although your solution WAS elegant, I think it was a bit too complex for the
questioner. I believe that the SIMPLEST solution would be to let the
cannibals eat the missionaries who obviously tranferred into divinty school
after being too lazy to do their own computer science homework.
--
Frank A. Adrian
First DataBank
············@firstdatabank.com (W)
······@europa.com (H)
This message does not necessarily reflect those of my employer,
its parent company, or any of the co-subsidiaries of the parent
company.
From: Thomas A. Russ
Subject: Re: Help! cannibal and missionary problem in LISP or C++
Date:
Message-ID: <ymi1zvea7vm.fsf@sevak.isi.edu>
OK, here's the algorithm:
(1) Describe the state of the problem in a suitable representation.
(2) Describe the effect of various operators such as getting in the
boat, crossing the river, etc.
(3) Pick a node in your state space that hasn't been processed.
Test it:
(3a) If everyone is across the river, then you are done. Print
the record of operators that got you to this point.
(3b) If it violates the constraints (cannibals outnumber missionaries)
mark the node as a failure.
(3c) If it is neither a success or a failure, generate a set of
children by applying your operators to the current state.
This will in general create a set of new states. Record
the operator used in creating each new state so that you
will be able to reconstruct the solution.
Mark the node as having been processed.
(4) Return to step (3)
A key step is figuring out a good way to pick the node in step (3).
Hint: Depth-first search is unlikely to be a good choice for this
problem.
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu
From: Christopher Browne
Subject: Re: Help! cannibal and missionary problem in LISP or C++
Date:
Message-ID: <6g404q$ts5$12@blue.hex.net>
On Fri, 3 Apr 1998 14:00:05 -0500, Khang <··········@hotmail.com> wrote:
>I'm looking for an algorithm or complete program (if possible) to solve the
>cannibal and missionary problem in Lisp or C++ for an initial configuration
>of (m m m c c c) on the left bank and 3 things can be taken in the boat at
>once, please help.
This sounds very much like a standard textbook problem which suggests
that you may be trying to get "the Internet" to do homework for you.
Depending on the context, this might be either legitimate or potentially
a serious academic offense.
You might want to check with a professor or teaching assistant to verify
the rules in effect at your institution.
If you can tell us when any an assignment might be due, we can make sure
that we avoid providing illegal or otherwise "offensive" academic
assistance.
We wouldn't want to become part of an academic offense, would we?
--
"The reality of the software business today is that if you find
something that can make you ridiculously rich, then that's something
that Microsoft is going to take away from you." -- Max Metral
········@hex.net - <http://www.hex.net/~cbbrowne/lsf.html>