OOP in C++
Dr Robert Nu ̈rnberg
Driving Test 2010
Friday, 26 March 2pm – 4pm
Using the account details given below, attempt all 3 tasks. Write one C++ file per task. As your working directory you may choose C:\temp\OOP your name. Make sure to write in the answers to each question on the Answer Sheet. Once you have finished, save the 3 files TaskN.cpp, N=1. . .3, to a directory, e.g. to C:\temp\SUBMIT your name, and contact the invigilator. Do not log off! Hand in your answer sheet and present your submission directory. The invigilator will then reconnect the network cable so that you can email your solutions to rn@ic.ac.uk and to yourself. You are then free to leave.
Username : ******
Password : ******
Domain : MA215-xx or MA410-xx (this computer)
1. Fibonacci numbers [40 marks]
The generalized Fibonacci numbers are defined by the recurrence relationship
Fn=Fn−1+Fn−2, n≥2,
where F0, F1 ∈ N, with F0 + F1 > 0, are given initial values. For the classical Fibonacci
numbers we set F0 = 0, F1 = 1, which yields e.g. F10 = 55. It is known that limn→∞ Fn+1 = √ Fn
φ := 1+ 2
φ (a) given n, computes Fn.
(b) givenε,computesnε :=min{n∈N:| Fn −φ|<ε}andFnε. Fn−1
(c) given N and x, computes sN (x).
(d) given ε and x, computes Nε := min{N ∈ N : |sN (x) − sN −1 (x)| < ε} and sNε (x).
To this end, your program should contain the following functions.
(a) int fibonacci(int n, int F0, int F1)
(b) int flimit_phi(double epsilon, int F0, int F1)
(c) double s_N(double x, int N, int F0, int F1)
(d) int limit_s(double x, double epsilon, int F0, int F1)
2. Fractions [40 marks]
Implement a class fraction so that all of the statements below are executed correctly. Use only private member data and do not use friend functions.
int a = 4, b = 3;
fraction f(1,123), g(1,321), h(1,3), res;
cout << f - h << endl;
res = a * f - g * b;
res = - res + f * h;
cout << res << endl;
f += g / h;
cout << f << endl;
Hint: The following function computes the greatest common divisor (gcd) of two nonnegative numbers: int gcd(int a, int b) { return ( b == 0 ? a : gcd(b, a % b) ); }
5 . The corresponding power series
s(x) = lim sN(x), where sN(x) = Fk xk ,
N→∞
is known to converge for |x| < 1 ≈ 0.618. Write a program that
N k=0
OOP in C++ Dr Robert Nu ̈rnberg
3. Gibonacci numbers [20 marks]
The Gibonacci numbers are defined by the recurrence relationship
Gn=Gn−1+Gn−2, n≥2,
where G0, G1 ∈ Q, with G0+G1 > 0, are given initial values. It is known that limn→∞ Gn+1 =
√ Gn
φ := 1+ 2
N→∞
is known to converge for |x| < 1 ≈ 0.618. Write a program using templates that, in
φ
conjunction with your code from 2., can be used to (a) given n, compute Gn.
(b) givenε,computenε :=min{n∈N:| Gn −φ|<ε}andGnε. Gn−1
(c) given N and x, compute rN (x).
(d) given ε and x, compute Nε := min{N ∈ N : |rN (x) − rN −1 (x)| < ε} and rNε (x).
To this end, your program should contain the following template functions, where T, T1, T2 are typename placeholders.
(a) T gibonacci(int n, const T& F0, const T& F1)
(b) int glimit_phi(double epsilon, const T& F0, const T& F1)
(c) T2 r_N(const T2& x, int N, const T1& F0, const T1& F1)
(d) int limit_r(const T2& x, double epsilon, const T1& F0, const T1& F1)
Of course, when implemented correctly, then the new template functions gibonacci
Note: In (b) it is easiest to overload the operator for double = fraction – double.
5 . The corresponding power series
r(x) = lim rN(x), where rN(x) = Gk xk ,
N k=0
OOP in C++
Friday, 26 March 2pm – 4pm
Name
CID
Answer Sheet A
1. On setting F0 = 3, F1 = 4 and ε = 10−6, use your program to compute the following
values.
Variable
Values
F20
nε and Fnε
s10 (0.1)
Nε, for x = 0.5, and sNε (0.5)
2. On replacing the second line of the code in the test with fraction f(1,45), g(1,54), h(1,5), res;
what are the outputs of your program?
3. On setting G0 = 1, G1 = 1, use your program to compute the following values (as
fractions!).
Line
Output
cout << f - h << endl;
cout << res << endl;
cout << f << endl;
23
Variable
Values
G20
nε, for ε = 10−6, and Gnε
r5(3) 8
Nε, for ε = 0.003, x = 1, and rNε(1) 44
Finally, list the output of your program for the following computations.
Variable
Values
gibonacci
gibonacci
gibonacci
gibonacci