Humans & Cannibals Problem

Discussion in 'C' started by rai_gandalf, Dec 28, 2005.

  1. rai_gandalf

    rai_gandalf New Member

    Joined:
    Nov 4, 2005
    Messages:
    46
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Final Year Comp Engg
    Location:
    Mumbai
    Home Page:
    http://mindpuncture.blogspot.com
    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 :)
     
  2. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    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/cs9414/notes/mandc/mandc.html will help you get the idea about the algo.

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

    rai_gandalf New Member

    Joined:
    Nov 4, 2005
    Messages:
    46
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Final Year Comp Engg
    Location:
    Mumbai
    Home Page:
    http://mindpuncture.blogspot.com
    Thx a lot, Shabbir.
     
  4. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    My pleasure
     
  5. rai_gandalf

    rai_gandalf New Member

    Joined:
    Nov 4, 2005
    Messages:
    46
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Final Year Comp Engg
    Location:
    Mumbai
    Home Page:
    http://mindpuncture.blogspot.com
    A simple, yet consistent implementation

    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 :)
     

    Attached Files:

  6. coderzone

    coderzone Super Moderator

    Joined:
    Jul 25, 2004
    Messages:
    736
    Likes Received:
    38
    Trophy Points:
    28
    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.
     
  7. Wilkyn Fernandes Taborda

    Wilkyn Fernandes Taborda New Member

    Joined:
    Oct 21, 2020
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    1
    Gender:
    Male
    Of course:
     

    Attached Files:

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice