Sample Assignment: Fun with Recursion


rec_fun.cxx:
This file should contain the implementations of the five
functions described below. You might also want to put the functions
prototypes in a separate file rec_fun.h and write a test program
that includes rec_fun.h.
All function should be in the namespace mry2270 to make it easier for michael, robert and yingdan to grade the work. You must use the exact prototypes shown below, please!
void triangle(ostream& outs, unsigned int m, unsigned int n) // Precondition: m <= n // Postcondition: The function has printed a pattern of 2*(nm+1) lines // to the output stream outs. The first line contains m asterisks, the next // line contains m+1 asterisks, and so on up to a line with n asterisks. // Then the pattern is repeated backwards, going n back down to m. /* Example output: triangle(cout, 3, 5) will print this to cout: *** **** ***** ***** **** *** */Hint: Only one of the arguments changes in the recursive call. Which one?
#include <string> void numbers(ostream& outs, const string& prefix, unsigned int levels);The function prints output to the ostream outs. The output consists of the string prefix followed by "section numbers" of the form 1.1., 1.2., 1.3., and so on. The levels argument determines how may levels the section numbers have. For example, if levels is 2, then the section numbers have the form x.y. If levels is 3, then section numbers have the form x.y.z. The digits permitted in each level are always '1' through '9'. As an example, if prefix is the string "THERBLIG" and levels is 2, then the function would start by printing:
THERBLIG1.1. THERBLIG1.2. THERBLIG1.3.and end by printing:
THERBLIG9.7. THERBLIG9.8. THERBLIG9.9.The stopping case occurs when levels reaches zero (in which case the prefix is printed once by itself followed by nothing else).
The string class from <string> has many manipulation functions, but you'll need only the ability to make a new string which consists of prefix followed by another character (such as '1') and a period ('.'). If s is the string that you want to create and c is the digit character (such as '1'), then the following statement will correctly form s:
s = (prefix + c) + '.';This new string s can be passed as a parameter to recursive calls of the function.
This question involves a game with teddy bears. The game starts when I give you some bears. You can then give back some bears, but you must follow these rules (where n is the number of bears that you have):
For example, suppose that you start with 250 bears. Then you could make these moves:
Write a recursive function to meet this specification:
bool bears(int n) // Postcondition: A true return value means that it is possible to win // the bear game by starting with n bears. A false return value means that // it is not possible to win the bear game by starting with n bears. // Examples: // bear(250) is true (as shown above) // bear(42) is true // bear(84) is true // bear(53) is false // bear(41) is falseHint: To test whether n is even, use the expression ((n % 2) == 0).
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *With recursive thinking, the function needs only seven or eight lines of code (including two recursive calls). Your prototype should look like this:
void pattern(ostream& outs, unsigned int n, unsigned int i); // Precondition: n is a power of 2 greater than zero. // Postcondition: A pattern based on the above example has been // printed to the ostream outs. The longest line of the pattern has // n stars beginning in column i of the output. For example, // The above pattern is produced by the call pattern(cout, 8, 0).Hints: You do not need to check the precondition. Think about how the pattern is a fractal. Can you find two smaller versions of the pattern within the large pattern? Here is some code that may be useful within your function:
// A loop to print exactly i spaces: for (k = 0; k < i; k++) outs << ' '; // A loop to print n asterisks, each one followed by a space: for (k = 0; k < n; k++) outs << "* ";
Write a recursive function whose input is an STL multimap where the keys and values are both integers (see page 797 of the text). The return value of the function is true if there is a sequence of (key,value) pairs in the multimap of the form (a0,a1), (a1,a2), (a2,a3),...(an1,an) such that both the first key (a0) is s and the last value (an) is t. Otherwise, the return value is false. Make sure that your function does not go into an infinite loop.
Prototype:
bool path( const multimap<int,int>& m, int s, int t, set<int>& already_tried );The last parameter is a set of integers that the function has already tried to use without success (similar to the set of people who had already sat down when we did a backtrack algorithm in class).