Computer programming - Lab 2

If any questions remain about these problems, please ask during office hours.

1. Write a function that given a natural number computes the value resulting from the digits of its decimal representation when interpreted as a hexadecimal number. Example: f(312) = 3 * 256 + 1 * 16 + 2 = 786
Hint: use the same recursive decomposition, but when reconstructing the number, use the new base (16).

2. Write a function that takes an unsigned number n and returns a number formed by some of the digits of n, e.g.: all digits on even positions / odd positions, all digits with a given property (odd/even/greater than 5, etc.)

3. Write a function that takes a natural number as argument and returns the value of the number read backwards (with the decimal digits in opposite order): f(3125) = 5213.
Hint: have one more accumulator parameter that contains the partial number already reversed, starting from the last digit. (After the first step, 312 remains, 5 is the partial result). At each step, the last digit 'cut' from the remaining number is added behind the partial result (next step: 31 remains, 52 is the partial result. This simulates the reversal of a list of digits.

4. Function root. Write a recursive function that computes a root of a given continuous function f in an interval [a, b] with a given precision using the bisection method, assuming f(a) and f(b) have opposite signs.
What to do:
If the interval length does not exceed the required precision for the root (say, 10-6, which can be written 1e-6), we can return as answer any point from the interval (a, b, the midpoint, etc.).
Otherwise, compute f in the midpoint of the interval, (a+b)/2. If f(a) * f((a+b)/2) ≤ 0 (the function changes sign), find the root by calling the function recursively on the left half-interval. Otherwise, there must be a root in the right half [(a+b)/2, b], so recursively find the root in that interval.
Why this works
Denote m = (a+b).2. We prove by contradiction that f(a) * f(m) ≤ 0 or f(m) * f(b) ≤ 0 (or both).
If both were > 0, by multiplication we'd get f(a) * f(m)2 * f(b) > 0. We divide by f(m)2 which must be strictly positive, since the entire product is, and we get f(a) * f(b) > 0 contrary to the problem statement that they have opposite signs.
Note that we do not need a zero check for the endpoints nor the midpoint, the reasoning above shows that the chosen checks suffice.

5. Write a program, similar to the one done in class, that draws the Koch curve, as described here.
The curve can be drawn without lifting pen from paper, so there is no need to issue commands to move the cursor, each segment starts from where the other left off. Segments have different orientation: the two central of four subfigures are tilted clockwise and counterclockwise with π/3 with respect to the orientation of the enclosing larger figure. Thus, a figure will have size and orientation (angle) as parameters.

6. If p is a prime number, and a is not divisible by p, the sequence a, a2, a3, ... will eventually reach 1 when computed modulo p (i.e., we take the remainders when dividing by p).
For example, let p = 7, and a = 4. Then a2 = 16 ≡ 2 (mod 7), and a3 = a2 * a ≡ 2 * 4 ≡ 1 (mod 7).
Write a function that takes as parameters an unsigned number p (assumed to be prime, no check needed) and an unsigned number a and returns 0 if p divides a, or else the smallest number n such that an ≡ 1 (mod p).
Hint: accumulate and pass as arguments the current exponent k and ak, until you reach 1 (mod p).


The following problem was not assigned in the lab. It is a good exercise for recursive decomposition into simpler problems, and the solution is a short rather direct translation of the hint.

7*. Write a recursive function that returns the number of ways in which a natural number can be written as a sum of ones, twos and threes, irrespective of order.
Example: 5 = 1 + 1 + 1 + 1 + 1 = 1 + 1 + 1 + 2 = 1 + 2 + 2 = 1 + 1 + 3 = 2 + 3 (5 combinations).
Hint: If we use a value of 3, we are left with writing n - 3 in all possible ways. If we do not use 3, we must write n using only ones and twos (we can write another function for this problem).
Does the function perform wasteful computation ? Generalize for three arbitrary values instead of 1, 2, and 3.

Marius Minea
Last modified: Tue Nov 29 21:25:00 EET 2016