#1
  1. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2003
    Posts
    2
    Rep Power
    0

    Recursive Problem need help


    im still learnin c++
    while my teacher gave me this hard problem dont know how to work with this

    Code:
    Write a recursive solution to the robbers homework 
    This program should have a main function that calls robber.  Robber will be a recursive function that returns an array of size 20, which contains the solution to the problem for n<=20 robbers. The number of robbers should be input by the user. 
    Remember that all arrays are passed by reference in C++, and this may not be what you need.  It might be easier to make a local copy of the array and copy the array item by item, to avoid pass by reference. I had success returning an array of ints indicating the proposal for any number of robbers (up to 20).  You can fill the array from either end and fill any empty slots with 0ís, but your method may differ.  I am less concerned with these details and more with an effective and concise recursive solution. 
    
    
    
    #include <iostream> 
    using namespace std; 
    
    void main() 
    {    
       results = robbers(num_robbers); 
       for (int parse = 0; parse < 20; parse++) { 
          cout << results[parse] << " "; 
       } 
    
    }  // end main 
    
    int* robbers(int number_of_robbers) { 
        
    } // end robbers
    & this program should run on this web-compiler

    http://www.cs.unt.edu/~irby/wbcRoden/wbcHome.html
    [/code]
  2. #2
  3. Contributing User

    Join Date
    Aug 2003
    Location
    UK
    Posts
    5,073
    Rep Power
    1802
    Maybe you should have just listened harder in class.:rolleyes: Learning is not about getting people to do your homework. If that doesn't annoy anyone who mignt otherwise help, the lack of line wrapping in your post will!:mad:

    The specification does not actually explain what the "the solution to the problem for n<=20 robbers" is! I assume you must at least know that? Since we are not told, you cannot expect an answer.

    Other than that, recursion is simple. The function must call itself with a lower order parameter, such that the problem is expressed in terms of the value passed, and the simpler function call, until the simplest value is passed in, which case (the terminal case), a specific answer is output. You must ensure that the terminal case is always met, otherwise you will get a stack overflow, which may still happen if the terminal case is not met soon enough; which is why recursion is usually avoided in real code and over-emphasiesd in computer science courses. (IMHO).

    Example:
    Calculate factorial (n!), eg. 3! = 3 * 2 * 1 = 6

    Code:
    unsigned int factorial( unsigned int val )
    {
        unsigned int ret_val ;
    
        if( val <= 2 )              // terminal condition
        {
            // answer is 2, 1, or zero (i.e. val)
            ret_val = val ;
        }
        else
        {
            // answer is val * (val-1)!
            ret_val = val * factorial( val - 1 ) ;
        }
    
        return( ret_val ) ;
    }
    Often you'll see recursive solutions with multiple returns rather than the assignment to a temporary value (ret_val) as I have done. Which is another horror that CS courses are seem to encourage.

    Clifford
  4. #3
  5. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2003
    Posts
    2
    Rep Power
    0
    Code:
    Five robbers have stolen one hundred bearer bond 
    certificates and they have to divide the certificates between 
    themselves. The most senior robber proposes a distribution of 
    the certificates. (Robber 5 is most senior, Robber 1 is least 
    senior) He suggets that the robbers all vote and if at least fifty 
    percent accept the proposal, the certificates are divided as 
    proposed. Otherwise, the most senior robber will be executed, 
    and the remaining robbers will start over again with the next 
    senior robber. What solution does the most senior robber 
    propose?
    so
    1st robber gets 1
    2ed robber gets 0
    3ed robber gets 1
    4th robber gets 0
    5th robber gets 98

IMN logo majestic logo threadwatch logo seochat tools logo