Description
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 vectors, sets, 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 nth 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 bth power (for positive b).
int tri(int n);
Returns the nth triangular number. Triangular numbers are, informally
1 .
.
3 . .
.
. .
6 . . .
and so on. More formally, the nth 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 nth 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
