OOP in C++
Dr Robert Nu ̈rnberg
Driving Test 2012
Friday, 23 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 with a CC to yourself. You are then free to leave.
Username : ***** Password : *****
For some of the tasks you need to recall that for integers a and b, a % b evaluates to a modulo b, e.g.14 % 4evaluatesto2since14mod4=2.
1. Modulo [30 marks]
You are given the facts that for any positive integers a, b, m ∈ N it holds that
(a b) mod m = [(a mod m) (b mod m)] mod m and (a+b)modm=[(amodm)+(bmodm)]modm.
Write a program that can compute terms of the form • n!modm
• ab modm
and sums thereof. Here you may assume that m ≤ 106.
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 can compute the following functions. • M(l,r) = max c(a)
l≤a≤r
• Sn(l,r)= a
l≤a≤r c(a)=n
[Hint: Use the type unsigned long.]
OOP in C++ Dr Robert Nu ̈rnberg
3. Laurent series [40 marks]
Laurent series are an important tool in complex analysis, especially to investigate the be- haviour of functions near singularities. The formal definition of a Laurent series is f(z) = ∞n=−∞ an (z − c)n. As a first step towards Laurent series, implement a template
Laurent_polynomial, which defines “polynomials” of the form p(x) = Nn=−N an xn, so that the following code executes correctly.
Laurent_polynomial
Laurent_polynomial
double x(2.1), y(-1.25);
cout << "p(y) = " << p.value(y) << endl;
s = p + q;
// N = 2, a_n = 1.0, n = -N,...,N.
// value of polynomial p at y
for (int i = -s.getN(); i <= s.getN(); i++)
cout << "s[" << i << "] = " << s[i] << endl; // print coefficients a_n of s
cout << "s(x) = " << s.value(x) << endl;
Upon including the line #include
lowing code correctly.
complex
Laurent_polynomial
Laurent_polynomial
complex
cout << "u(w) = " << u.value(w) << endl;
t = u + v;
for (int i = -t.getN(); i <= t.getN(); i++)
cout << "t[" << i << "] = " << t[i] << endl;
cout << "t(z) = " << t.value(z) << endl;
[Hint: You can either define a vector
OOP in C++
Friday, 23 March 2pm – 4pm
Name
CID
Answer Sheet A 1. State the values of the following expressions.
2. State the values of the following expressions.
3. On replacing the first line of the code in the test with Laurent polynomial
what is the output of your program?
Finally, on replacing the corresponding line of the code in the test with
complex
what is the output of your program?
Value
80! mod 997
7128 mod 106
(1000 nn) mod 877 n=1
Value
c(201203)
M(104,105)
S256(1, 106)
Line
Output
cout << "p(y) = " << p.value(y) << endl;
cout << "s(x) = " << s.value(x) << endl;
Line
Output
cout << "u(w) = " << u.value(w) << endl;
cout << "t(z) = " << t.value(z) << endl;