OOP in C++
Dr Robert Nu ̈rnberg
Driving Test 2018
Wednesday, 21 March 2pm – 4pm
Using the account details given below, attempt all 3 tasks. Write one C++ file per task. Make sure to fill in the answers to each question on the Answer Sheet. Also make sure that the codes you submit will produce all the answers from your answer sheet when compiled and run. Once you have finished, save the 3 files taskN.cpp, N=1…3, to a directory or to the Desktop, and contact the invigilator. Do not log off! Hand in your answer sheet and present your files. The invigilator will then reconnect 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. Final digits of Fibonacci [20 marks]
The Fibonacci numbers are defined by the recurrence relationship
Fn=Fn−1+Fn−2, n≥2, whereF0 =0andF1 =1,andso,forexample,F10 =55.
Write program with a non-recursive (!) function that can compute the last five digits of an arbitrary Fibonacci number. Here you may use the fact that
Fn modp=(Fn−1+Fn−2)modp=[(Fn−1 modp)+(Fn−2 modp)modp], for arbitrary p ∈ N.
2. Collatz conjecture [30 marks]
We define the following function on the set of positive integers:
a/2 a is even,
f(a) =
3a+1 aisodd.
Although it has not been proved yet, the Collatz conjecture states that for all natural numbers a ∈ N the sequence
a, f(a), f(f(a)), f3(a), …
≡f2(a)
eventually reaches the number 1. With this in mind, we define the function
c(a) := min{n ≥ 0 : fn(a) = 1}. Hence c(1) = 0, c(2) = 1 and c(3) = 7.
Write a program that, given a, can compute c(a). Moreover, given l < r, it should also be able to compute maxl≤a≤r c(a).
OOP in C++ Dr Robert Nu ̈rnberg
3. Quaternions in R4 [50 marks]
The real vector space R4 (with the usual vector addition) can be equipped with a noncommu- tative multiplication to yield an algebra over R that is almost a field, and which is denoted by H.
In particular, for a = (a1,a2,a3,a4) ∈ H and b = (b1,b2,b3,b4) ∈ H we define ab ∈ H by ab = (a1b1 − a2b2 − a3b3 − a4b4,
a1b2 + a2b1 + a3b4 − a4b3, a1b3 − a2b4 + a3b1 + a4b2, a1b4 +a2b3 −a3b2 +a4b1).
Note that H can be thought of as an extension of the complex numbers C, i.e. formally R ⊂ C ⊂ H, and so it is common to introduce the notations
1 = (1,0,0,0), i = (0,1,0,0), j = (0,0,1,0), k = (0,0,0,1). With these definitions it then holds that
i2 =j2 =k2 =ijk=−1. Moreover, the conjugate a∗ of a ∈ H is defined by
a∗ =−1 (a+iai+jaj+kak)∈H, 2
which, on noting that a∗a = aa∗ ∈ R≥0, yields the usual definition of the norm of a as
∥a∥=√a∗a=√aa∗ =a21 +a2 +a23 +a24. Finally, the inverse a−1 = 1/a of a ∈ H is defined by
a−1= 1 a∗. ∥a∥2
Note that a is not well-defined, since in general ab−1 ̸= b−1a. b
Write a program that can perform numerical computations for quaternions in H. In partic- ular, your code should be able to compile the following instructions.
int main() {
quaternion i(0, 1, 0, 0), j(0, 0, 1, 0), k(0, 0, 0, 1), c;
quaternion a, b;
cout << i*a*j*b*k << endl;
cout << a*a - b*b << endl;
c = i*a*j + j*b*k;
cout << c.conj() << endl;
cout << a.inv() << endl;
cout << b.inv() * a << endl;
cout << a * b.inv() << endl;
return 0; }
// add constructor values for a and b
OOP in C++
Wednesday, 21 March 2pm – 4pm
Name
CID
Answer Sheet A
1. State the last five digits for the following Fibonacci numbers Fn:
2. State the values of the following expressions.
n
last five digits of Fn
1001
180321
107 + 1
a
c(a)
318
210318
l, r
maxl≤a≤r c(a)
m with c(m) = maxl≤a≤r c(a)
99, 199
4000, 5000
3. Let a = − 1 + 4i − k and b = 6j − 3k. State the values of the following expressions. Display 5
all values to 4 decimal digits.
value
iaj bk
a2 − b2
(iaj + jbk)∗
a−1
b−1 a
ab−1