Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forums/c/)
-   -   Humans & Cannibals Problem (http://www.go4expert.com/forums/humans-cannibals-problem-t543/)

rai_gandalf 28Dec2005 16:10

Humans & Cannibals Problem
 
Was wondering how to code this in C :

There are 'H' Humans and 'C' Cannibals on the bank of
a river. They are to be transported from the left bank
of a river to the right bank ,using a boat.
The boat can take maximum of 2 persons.
At no point of time, a situation may arise, wherein:
No. Of Humans<No. Of Cannibals.
i.e., H=0 OR H>=C.



Obviously, it must involve Recursion, but I am not able to figure out how.
Its probably pretty simple, but none-the-less, give it a try.

Also, if possible, tell me is there any way to code it non-recursively.

Ciao,
Rajiv :)

shabbir 28Dec2005 19:48

Re: Humans & Cannibals Problem
 
It was posted in the wrong forum and I have moved it to the correct forum.

Regarding your problem there is a standard algo for such a solution to the problem. http://www.cse.unsw.edu.au/~billw/cs...ndc/mandc.html will help you get the idea about the algo.

Quote:

Originally Posted by rai_gandalf
Also, if possible, tell me is there any way to code it non-recursively.

If not all almost every recursive problem has a non recursive solution specially standard algos.

rai_gandalf 28Dec2005 21:23

Re: Humans & Cannibals Problem
 
Thx a lot, Shabbir.

shabbir 28Dec2005 23:30

Re: Humans & Cannibals Problem
 
Quote:

Originally Posted by rai_gandalf
Thx a lot, Shabbir.

My pleasure

rai_gandalf 30Dec2005 00:14

A simple, yet consistent implementation
 
1 Attachment(s)
There's this friend of mine, who has coded this problem in 'C' (His net is down temporarily - so I got a soft copy of the prog), without adopting the above mentioned approach, infact he has used a very simple approach. Yet, it works.

If 'h' r the no. of Humans & 'c' the no. of cannibals entered as I/P (provided h>c, at the time of I/P), the program consistently gives the Solution in : 'h+c-1' steps.

can u xamine the code & tell me, is this also a valid implementation.

Ciao,
Rajiv :)

coderzone 30Dec2005 07:32

Re: Humans & Cannibals Problem
 
The logic used in the problem is quite simple and effective one. He has defined two functions
Code:

void bank(int hu,int ca)
and
Code:

void bank1(int hu,int ca)
which are recursively used for initial condition of Humans & Cannibals are equal or not.

Then it recursivly decrease (Movement from one bank to other) the humans and cannibals depending on the case as to who in what number on the bank.

Enjoy coding.


All times are GMT +5.5. The time now is 05:12.