Description
Requirements
This project is to be done in groups.
You are allowed to write everything in one file this time, so long it is organized and the file is not too long. If the file gets too long, please split it into multiple .h
 and .cpp
 files, and have a main.cpp
 that #include
s the .h
 files, and can be used to call the test functions prototyped in them. I recommend having one pair of .h
 and .cpp
 files for Parts 1–3, and another pair for Part 4 (and the challenge, if you choose to take it).
All the files you produce must be able to exist within a single project. You will submit these files via github as normal.
Part 1
- Read about exceptions (either here, or you may find another source).
- Come up with the most interesting (readable) example of using them that you can. This should take an hour or less.
Part 2
- Read about templates (I suggest starting here and reading till you feel like you’ve read enough).
- Come up with the most interesting (readable) example of using them that you can. This should take an hour or less.
Part 3
- Think about a time when you really wanted a variable length array, or a list that was always sorted, or something similar.
- Read aboutÂ
vector
s,Âset
s, and one other STL container that looks interesting to you. This might be a good place to start, but you may also need to google around a bit. - Come up with the most interesting (readable) example of using them that you can. This should take an hour or less.
Part 4
Write definitions for as many of the following functions as you can in roughly 3 hours. Be sure to label the base case and recursive case in each function.
int gcd(int a, int b);
Returns the greatest common divisor of two integers using Euclid’s algorithm. This function has the following properties:
gcd(a,0)
 evaluates toÂabs(a)
gcd(a,b)
 is equivalent toÂgcd(b,a)
gcd(a,b)
 is equivalent toÂgcd(abs(a),abs(b))
gcd(a,b)
 is equivalent toÂgcd(a-b,b)
 is equivalent toÂgcd(a,b-a)
Pseudocode for this function might look like the following:
- NormalizeÂ
a
 andÂb
 by making them positive - IfÂ
a
 orÂb
 isÂ0
, return the one that is nonzero - IfÂ
a > b
 returnÂgcd(a-b, b)
- Otherwise returnÂ
gcd(a, b-a)
where line (2) is the base case, and lines (3) and (4) are the recursive case.
int fib(int n);
Returns theÂ
n
th Fibonacci number. Recall that the Fibonacci sequence is defined as follows:fib(1)
 evaluates toÂ1
fib(2)
 evaluates toÂ1
fib(n)
 evaluates toÂfib(n-1) + fib(n-2)
int pow(int a, int b);
ReturnsÂ
a
 raised to theÂb
th power (for positiveÂb
).int tri(int n);
Returns theÂ
n
th triangular number. Triangular numbers are, informally1 . . 3 . . . . . 6 . . .
and so on. More formally, theÂ
n
th triangular number, forÂn > 0
, is the sum of the integers betweenÂ1
 andÂn
, inclusive.Note that there is a closed form expression for finding theÂ
n
th triangular number (and a famous story about Gauss coming up with it, as a child); but for this assignment, please find the answer algorithmically :-).
Part 5
Rewrite the functions you wrote in Part 4 as iterative functions (append _iter
 to your name for the recursive version of the function).
Challenge
std::string int_to_roman(int n);
A recursive version of theÂ
int_to_roman()
 function from assignment-01std::string int_to_words(int n);
A recursive function taking in any integer,Â
n
, and returning a string containing the English representation of that number. For example, the following code:cout << 0 << " == " << int_to_words(0) << endl; cout << 1 << " == " << int_to_words(1) << endl; cout << -1 << " == " << int_to_words(-1) << endl; cout << 123 << " == " << int_to_words(123) << endl; cout << 123123 << " == " << int_to_words(123123) << endl; cout << 123000123 << " == " << int_to_words(123000123) << endl; cout << 123123000 << " == " << int_to_words(123123000) << endl;
should produce the following output:
0 == zero 1 == one -1 == negative one 123 == one hundred twenty three 123123 == one hundred twenty three thousand one hundred twenty three 123000123 == one hundred twenty three million one hundred twenty three 123123000 == one hundred twenty three million one hundred twenty three thousand
While writing this, remember the use ofÂ
const
 arrays in the in-class solution to assignment-01. A similar technique may save you a lot ofÂif ... else
 statements.Also, if you find it useful, you may modify the function signature slightly.
As a general approach to solving this problem, I would recommend starting by writing a function that can correctly handle all the numbers from 1–999, then extending it to handle all possible numbers by splitting the original number into groups of 3 digits, recursively passing these smaller groups to itself, and appending the correct suffix (e.g. “thousand”) to each group.
std::string magic_number(int n);
Ponder this:
1 is 3 3 is 5 5 is 4 4 is the magic number! 7 is 5 5 is 4 4 is the magic number! 13 is 8 8 is 5 5 is 4 4 is the magic number!
Why is 4 the magic number? Is 4 always the magic number?
Once you figure it out, write a recursive function that generates the above example given the following:
cout << magic_number(1) << endl; cout << magic_number(7) << endl; cout << magic_number(13) << endl;
Requests
(None)
Assumptions
(None)
Style
- Place your solution in aÂ
solution--YOURNAME
 subdirectory (whereÂYOURNAME
 is your GitHub username). - Include your copyright and license information at the top of every file, followed by a brief description of the file’s contents, e.g.
/* ---------------------------------------------------------------------------- * Copyright © 2016 Ben Blazak <[email protected]> * Released under the [MIT License] (http://opensource.org/licenses/MIT) * ------------------------------------------------------------------------- */ /** * A short program to print "Hello World!" to standard output. */
- Use “include guards” in allÂ
.h
 files. Be sure to give the preprocessor variable a name corresponding to the file name. For example, inÂpoint.h
:#ifndef POINT_H #define POINT_H // ---------------------------------------------------------------------------- // ... everything besides the copyright information and file description // ---------------------------------------------------------------------------- #endif // POINT_H
main()
 must have its ownÂ.cpp
 file. I suggest calling itÂmain.cpp
.- Classes must have bothÂ
.h
 andÂ.cpp
 files, with member functions defined in theÂ.cpp
 files unless they are truly trivial. If it makes sense, you may put multiple classes into one pair ofÂ.h
 andÂ.cpp
 files. - Declare member functions and function arguments asÂ
const
 when appropriate (in general, whenever possible). - Document and format your code well and consistently. Be sure to clearly document the source of any code, algorithm, information, etc. that you use or reference while completing your work.
- Wrap lines at 79 or 80 columns whenever possible.
- End your file with a blank line.
- Do not useÂ
using namespace std;
. You may get around typingÂstd::
 in front of things or with, e.g.,Âusing std::cout;
.