C++ Program you are going to play around things in the reversing order and implement program for calculating Fibonacci numbers.

1. Reversing the input As the rst part, you are going to implement a class called Reverse which has two recursive functions reverseDigit and reverseString. int reverseDigit(int value): The function takes in an non-negative int value and reverse the digits using recursion. The reversed int is then re-

turned. For example, reverseDigit(12345) returns 54321. string reverseString(string letters): The function takes in a std::string

and returns the reversed string. Note that, you must make use of recursion in both functions. This means you need to work out how to reduce the problem and what the base case should be. 2. Calculating Fibonacci Numbers In mathematical terms, the sequence of Fibonacci numbers is dened by the recur-rence relation

Fn = Fn 1 + Fn 2,

where F0 = 0 and F1 = 1 . (More details are available at http://en.wikipedia.org/wiki/Fibonacci_number) First think about how to recursively determine the values of specic Fibonacci numbers. You are required to construct a class called Fibonacci that reads in a number n and outputs the n-th Fibonacci number Fn. 3. More Ecient Fibonacci Calculation In order to calculate Fn, you need to recursively calculate Fn 1 and Fn 2. Then, to calculate Fn 1, we need Fn 2 (again!) and Fn 3. This means that many Fibonacci numbers may be calculated multiple times. Reproduce your Fibonacci class in another class called EfficientFibonacci. Make this class ecient by storing calculated numbers. The recursive function should not be called for a number that has already been calculated. 4. Handling errors Your program may encounter errors, and it should be able to handle them. Modify your code so that when errors do occur, it prints out ERROR and does noth-ing more for that part of the test. For instance, for input A to reverseDigit function, the output would be ERROR (since A is not a non-negative integer). For now, you do not need to consider integer overow. That is, you are safe to assume that you will only be asked to calculate small Fibonacci numbers. 5. Main function You are asked to create a main function (main.cpp). It takes one line of input. The input consists of a non-negative integer i, a string s, a non-negative integer n1 and another non-negative integer n2. The string and integers will be separated by spaces. The output should be in one line as well. It should be the reverse of i, the reverse of s and the two values of Fn1 and Fn2 calculated using Fibonacci and

EfficientFibonacci respectively. The output should be separated by spaces as well.

Sample input 1: 12345 apple 6 6

Sample output 1: 54321 elppa 8 8

Sample input 2: -1 appa 20 3

Sample output 2: ERROR appa 6765 2