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).
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.