OOP in C++
Dr Robert Nu ̈rnberg
Driving Test 2015
Wednesday, 25 March 2pm – 4pm
Using the account details given below, attempt all 4 tasks. Write one C++ file per task. 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 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. Word score [20 marks]
Let M = {A,B,C,…,Z} denote the alphabet. Let g : M → N0 = N∪{0} denote the letter score, which is defined by
g(A)=0, g(B)=1, g(C)=2, …, g(Y)=24, g(Z)=25. Now for an n-letter word w = (w1,…,wn) ∈ Mn we define the word score
n
s(w) = i g(wi) = g(w1) + 2 g(w2) + 3 g(w3) + . . . + n g(wn) .
i=1
For example, s(”Y OU”) = 112 and s(”ME”) = 20.
Write a program that can compute the word score for words in Mn, n ∈ N. [Hint: The statement cout << (int) (’C’ - ’A’); outputs 2 on screen.]
2. Terras conjecture [30 marks]
We define the following function on the set of positive integers:
a/2 a is even,
f(a) =
(3a+1)/2 a is odd.
Although it has not been proved yet, a 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) = 5. Write a program that can compute the following functions.
• M(l,r) = max c(a) l≤a≤r
• Sn(l,r)= a l≤a≤r
c(a)=n
3. Polynomials [30 marks]
Write a class polynomial that implements polynomials of the form p(x) = nk=0 ak xk, whereak ∈R,k=0,...,n,andn∈N0. Forpolynomialsp,q,andα∈R,m∈N0,the following operations should be defined: p·q, p+q, αp, pm. You should also be able to return the value of the coefficient ak of xk in p, as well as p(x) for some x ∈ R.
OOP in C++ Dr Robert Nu ̈rnberg
4. Prime field [20 marks]
The finite field Zp, where p is prime, consists of the equivalence classes {0, 1, . . . , p − 1}. Addition, subtraction and multiplication are defined as usual, but modulo p. On recalling Fermat’s little theorem, we observe that 1/a = a−1 = ap−2 for any a ∈ Zp, i.e. the multi- plicative inverse of a is ap−2.
Write a template class primefield
that implements Zp with the mathematical operations +,−,·,/. Herewenotethatb/a=b·(1/a)=b·a−1.
The following code should compile and execute correctly. Moreover, your answers on the answer sheet must be obtained with a program that uses a template class as described above.
#define PRIME 2017
int main() {
primefield
for (unsigned int i = 1; i <= 50; ++i) {
partial_sum += primefield
}
cout << "sum_i=1^50 1/i = " << partial_sum << endl;
unsigned int aa, bb;
cout << "a, b = "; cin >> aa >> bb;
primefield
cout << "a + b = " << a + b << endl;
cout << "a - b = " << a - b << endl;
cout << "a * b = " << a * b << endl;
cout << "a / b = " << a / b << endl;
cout << "a^10 = " << power(a, 10) << endl;
cout << "a! = " << factorial(a) << endl;
return 0;
}
[Hint: You will need the syntax template
OOP in C++
Wednesday, 25 March 2pm – 4pm
Name
CID
Answer Sheet A
1. State the following word scores.
2. State the values of the following expressions.
3. Let{xi}5i=1 ={−3,−1,0,2,3}anddefinep(x)=4 x−xi andq(x)=2(x−x5). Finally, i=1 x5 − xi
let r(x) = [p(x)]2 q(x). State the following values to five decimal digits.
[Hint: Note that p(xi) = 0 for i = 1,…,4 and p(x5) = 1.]
4. Consider Zp for p = 79. State the following values computed in Zp.
word
score
ZEOULOUS
TRANSPORTER
LECTURERS
Value
c(201503)
M(2·105,3·105)
S99(1, 105)
value
coefficient a3 of x3 in p
coefficient a7 of x7 in r
r(−2)
value
5310
3/21 + 5/67
3/21 − 5/67
50!
50 1/k k=1