OOP in C++
Dr Robert Nu ̈rnberg
Driving Test 2014
Friday, 28 March 2.15pm – 4.15pm
Using the account details given below, attempt all 4 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 4 files taskN.cpp, N=1. . .4, 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 recon- nect the network cable so that you can email your solutions to robert.nurnberg@imperial.ac.uk with a CC to yourself. You are then free to leave.
Username : ***** Password : *****
1. Factorization [20 marks]
Write a program that, given a composite number n ∈ N, finds two numbers a, b ∈ N with 1 < a, b < n, such that n = a b.
2. 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
5 . The corresponding power series
s(x) = lim sN(x), where sN(x) = Fk xk ,
φ (a) given n, computes Fn.
(b) givenε,computesnε :=min{n∈N:| Fn −φ|<ε}andFnε. Fn−1
(c) given N and x, computes sN (x).
To this end, your program should contain the following non-recursive (!) 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)
Hint: Recall that 1 / 2 == 0, while 1 / (double) 2 == 0.5.
φ := 1+ 2
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. Fractions [20 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;
Here you should recall that the correct signature for the insertion operator is ostream &operator<< (ostream &os, const fraction &f).
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) ); }
4. 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 3., 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).
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)
Of course, when implemented correctly, then the new template functions gibonacci
Hint: 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, 28 March 2.15pm – 4.15pm
Name
CID
Answer Sheet A
1. State the values of a, b that your program finds for the following n.
2. On setting F0 = 3, F1 = 4 and ε = 10−6, use your program to compute the following values.
3. 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?
4. On setting G0 = 1 , G1 = 1 , use your program to compute the following values (as fractions!). 23
Finally, list the output of your program for the following computations.
n
a,b
97343
2539619
Variable
Values
F20
nε and Fnε
s10 (0.1)
Line
Output
cout << f - h << endl;
cout << res << endl;
cout << f << endl;
Variable
Values
G20
nε, for ε = 10−6, and Gnε
r5(3) 8
Variable
Values
gibonacci
gibonacci
gibonacci
gibonacci