PE0 (AY22/23)

Problems

1. Bus

This problem is quite similar to the exercise 01 taxi.

Note that the trickest part in this problem is to deal with the distance, it follows the rule that any distance smaller than 1km will be treated as 1 km. For example, $33.707$ km is treated as $34$ km.

To solve the trickier part above, there are two methods

1. Treat distance as integer and write a function called num_of_segments(). See Method 1

2. Treat distance as floating numbers and use ceil() from math.h. See Method 2

Method 1

We can utilise the fact that if the remainder of the distance of 1000 is not zero, that means we should add 1 to our segment. This is known as the correct way to ceil a number.

long num_of_segments(long distance) {
    long segments = distance / 1000;
    if (distance % 1000 != 0) {
        segments += 1;
    }
    return segments;
}

Method 2

Use ceil() to our current distance that is over a specifc distance. For example, to calculate the normal fare for a normal bus that bigger that 6.2km but smaller than 20.2 km, the code should be

double fare = ceil((double)(dist - 6200) / 1000.0) * 0.1;

2. Simple

The iterative solution for this method is similar to PE1 AY18/19 4. Digits*. Let's only talk about the more elegant solution, which will use recursion.

To do so, suppose we can find the simplified version of $n'$ , a number that is one digit less than $n$ (i.e., $n/10$), then we can find the simplified version of $n$ by simply (pun intended) considering two cases:

1. If the last digit of the simplified $n'$ is the same as the last digit of $n$, then we can just drop the last digit of $n$. Otherwise,

2. we append the last digit of $n$ to the simplified version of $n'$

long simplify(long n) {
    if (n / 10 == 0) {
        // one digit remaining
        return n;
    }
    if ((n / 10) % 10 == n % 10) {
        // last two digits are the same
        return simplify(n / 10);
    }
    // last two digits are different
    return simplify(n / 10) * 10 + n % 10;
} 

3. Root*

The part regarding finding a and b are "give-away". The trickest part lies in how to find b and c. Here, I will provide two ideas to solve this. However, any of these two methods need us to find the pattern that lies in the expression. Let's find this pattern first,

1. When $k=1$, we have $r/2a$, so $b_1=r$ and $c_1=2a$.

2. When $k=i, i > 1$, we have

$$\frac{b_i}{c_i}=\frac{r}{2a+\frac{b_{i-1}}{c_{i-1}}} \\ =\frac{c_{i-1}r}{2ac_{i-1}+b_{i-1}}$$

Thus, $b_i=c_{i-1}r$, and $c_i=2ac_{i-1}+b_{i-1}$. Using this pattern, we can form our iterative solution and recursion solution.

After finding the b and c, the remaing part is similar to what we have seen in PE1 AY21/22 3. Fraction, that is using gcd() to get the simplest form.

Iterative Method

long b = r;
long c = 2 * a;
for (long i = 1; i < k; i += 1) {
    long temp = c;
    c = 2 * a * c + b;
    b = temp * r;
}

Recursive Method

The recursive method is more trickier since one recursive function will call the other recursive function

long find_b(long a, long r, long times)
{
    if (times == 0)
    {
        return 0;
    {
    if (times == 1)
    {
        return r;
    }
    return r * find_c(a, r, times - 1);
}

long find_c(long a, long r, long times)
{
    if (times == 0)
    {
        return 1;
    }
    if (times == 1)
    {
        return 2 * a;
    }
    return 2 * a * find_c(a, r, times - 1) + find_b(a, r, times - 1);
 }

4. Largest*

The trickiest question till now!!!

Before doing this question, let's recap the three basic ideas of using wishful thinking to solve a problem recursively:

1. Assume, by wishful thinking, that we can solve this problem for a smaller $n$;

2. Use the solution for smaller $n$ to solve for the original $n$; and

3. Solve this problem for the simplest $n$

By wishful thinking, let’s say that we can rearrange the digits of a number smaller than n to achieve its largest value. An obvious choice for a smaller number is n / 10 (i.e., removing its last digit). How can we combine largest(n / 10) with the last digit n % 10 ?

There are two cases. The easy case is that if the last digit is smaller than the last digit of largest(n / 10) , then we just append. Otherwise, we need to insert this last digit into its proper place in largest(n / 10) .

How do we insert a digit into a number? You have seen this before in the problem 2. Insert* from PE1 AY21/22. The only difference is that in that question, you were asked to insert into a specific position, and here, we need to insert based on a specific condition (the relative values of the digits).

Finally, consider the solution for the simplest n. When n has only one digit, then we just need to return that digit. This translates to the code below:

long insert(long n, long digit)
{
    if (n % 10 > digit) {
        return n * 10 + digit;
    }
    if (n == 0) {
        return digit;
    }
    return (insert(n / 10, digit) * 10) + (n % 10);
}

long largest(long n)
{
    if (n < 10) {
        return n;
    }
    return insert(largest(n / 10), n % 10);
}

The code above solves the problem for positive numbers. For negative numbers, we need to rearrange the digits in reverse order. But you have seen how to do that in the problem 3. Reverse* from AY20/21, so I will omit the details here.

Some useful functions

A recursive way to find the largest number in a given number

long find_largest(long num)
    {
    if (num < 10)
    {
        return num;
    }
    long max = find_largest(num / 10);
    if (max >= num % 10)
    {
        return max;
    }
    return num % 10;
}

A recursive way to find the number of zero in a given number

long find_zero(long num)
{
    if (num == 0)
    {
        return 0;
    }
    long ans = 0;
    if (num % 10 == 0)
    {
        ans = 1;
    }
    ans += find_zero(num / 10);
    return ans;
}