## 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, informally`1 . . 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-01`std::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;`

.