need help with c++ recursion

Discussion in 'OT Technology' started by hurleyint1386, Apr 14, 2005.

  1. hurleyint1386

    hurleyint1386 Someone has sand in their vagina

    Joined:
    Jan 6, 2005
    Messages:
    3,687
    Likes Received:
    0
    Location:
    Rochester, NY
    ok, i have this small lab that i need to do, and it seems fairly simple, but i cant get it. i think i need to use loops in my function, but im not sure. here's the problem:

    Forming Committees.
    Let comm(n, k) represent the number of different committees of k people that can be formed if you have n people available. For example, comm(4, 3) = 4, since of four people, A, B, C, and D, there are four possible three-person committees: ABC, ABD, ACD, and BCD. In general, comm(n, k) = comm(n-1, k) + comm(n-1, k-1). Write and test arecursive C++ function to compute comm(n, k) for n>=1, k>=1.


    that's the problem, and i know how to do it in my head, but i can't think of how to put it into code. can anyone help me? :dunno:
     
  2. hurleyint1386

    hurleyint1386 Someone has sand in their vagina

    Joined:
    Jan 6, 2005
    Messages:
    3,687
    Likes Received:
    0
    Location:
    Rochester, NY
    *bump*
    anyone?
     
  3. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    In any recursive algorithm, ask yourself what the base case or cases are.
    In your problem, I think there are 3 base cases you need to handle.
    1) what do you return if n == k?
    2) what do you return if k == 1?
    3) what do you return if k > n?
    If you arguments don't match any of the base cases, just call the function recursively.
     
  4. hurleyint1386

    hurleyint1386 Someone has sand in their vagina

    Joined:
    Jan 6, 2005
    Messages:
    3,687
    Likes Received:
    0
    Location:
    Rochester, NY
    ok, that makes sense. i understand that part now. what would be the parameters of the function when it's called recursively? would it be comm(n-1, k) or is there more to it than that?
     
  5. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    Read your problem statement again:

    comm(n-1, k) + comm(n-1, k-1)

    It's not really a single recursive call.
     
  6. hurleyint1386

    hurleyint1386 Someone has sand in their vagina

    Joined:
    Jan 6, 2005
    Messages:
    3,687
    Likes Received:
    0
    Location:
    Rochester, NY
    so how do i do a double recursive call? i dont remember my teacher mentioning how it, unless i didnt notice. would it be something like:

    comm(n-1, k);
    comm(n-1, k-1);

    because i has to be more than that.
     
  7. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    Code:
     
    int comm(int n, int k)
     
     
    
    
    {[indent]if (parameters match a base case)
    
     
     
     
    
    
    {[indent]return ???;
    
     
     
    
    [/indent]}
    
     // otherwise...
    return comm(n-1, k) + comm(n-1, k-1);
     
    
    [/indent]}
     
  8. hurleyint1386

    hurleyint1386 Someone has sand in their vagina

    Joined:
    Jan 6, 2005
    Messages:
    3,687
    Likes Received:
    0
    Location:
    Rochester, NY
    i tried this, and it's compiling, however it's not giving me correct answers. if k == n, it doesnt give me 1, but if k > n, then it returns 0 correctly ....


     
  9. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    It works for me. Check your input values.
     
  10. hurleyint1386

    hurleyint1386 Someone has sand in their vagina

    Joined:
    Jan 6, 2005
    Messages:
    3,687
    Likes Received:
    0
    Location:
    Rochester, NY
    here's my main function. maybe there's something wrong with it for me. above my main ive got a
    "int numberofcommittees(int n, int k);" prototype.


    it's probably something so stupid that im over looking. does this work for you?
     
  11. hurleyint1386

    hurleyint1386 Someone has sand in their vagina

    Joined:
    Jan 6, 2005
    Messages:
    3,687
    Likes Received:
    0
    Location:
    Rochester, NY
    bump

    almost finished, just a few problems
     
  12. hurleyint1386

    hurleyint1386 Someone has sand in their vagina

    Joined:
    Jan 6, 2005
    Messages:
    3,687
    Likes Received:
    0
    Location:
    Rochester, NY
    i still need some help. can anyone help me finish? im not sure why it's giving me incorrect answers :dunno:
     
  13. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    I did a copy & paste of your code. It compiles and works fine for me.
    Post a sample of the input and output you're seeing.
     
  14. hurleyint1386

    hurleyint1386 Someone has sand in their vagina

    Joined:
    Jan 6, 2005
    Messages:
    3,687
    Likes Received:
    0
    Location:
    Rochester, NY
    here's the program, the first time, i tried 3 people in a committee with 4 people, and the answer should be 4. then i tried doing 3 people to a committee with 3 people, which should be 1, but it says 3

     
  15. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    Carefully compare your code with what you posted.
    Make sure they are the same.
    Maybe even wipe out what you have and just copy and paste from this thread.
    It works for me.
     
  16. hurleyint1386

    hurleyint1386 Someone has sand in their vagina

    Joined:
    Jan 6, 2005
    Messages:
    3,687
    Likes Received:
    0
    Location:
    Rochester, NY
    you are my savior! you were right. i just had to copy, then paste into a new file and it worked perfectly. thanks a lot! you really helped
     

Share This Page