PE1 (AY18/19)

Problems

1. Vote

This is a "give-away" question.

2. Newton

In math.h library in C, there is a function called fabs(x), which will return the absolute value of a floating-point argument x.

We may need the idea of getting $\epsilon$ when we want to judge whether two double are equal. However, if we only want to know which double is bigger enough, we can just use the operators $>,<,\geq,\leq$, that's enough.

3. Goldbach*

The good way to write prime.

prime.c

#include "cs1010.h"

bool is_prime(long n)
{
    for (int i = 2; i * i <= n; i += 1)
    {
        if (n % i == 0)
        {
            return false;
        }
    }
    return true;
}

Note that using this method (i * i <= n) can save us from the trouble of dealing with type casting when using the sqrt() from math.h library.

However, below is mine version of prime.c, which may be a little bit faster.

prime_optimized.c

#include "cs1010.h"

bool is_prime(long num)
{
    if (num == 2)
    {
        return true;
    }
    if (num % 2 == 0)
    {
        return false;
    }
    for (long i = 3; i * i <= n; i += 1)
    {
        if (num % i == 0)
        {
            return false;
        }
    }
    return true;
}

4. Digits*

The most important idea in this probelm is to define two variables (so that we won't use arrays here) to store:

1. The digit(0-9) of the longest sequence

2. The length of the longest sequence

This idea comes from the exercise we have done, which is in Problem 2.1 about finding the maximum number in a list. Here we just use two variables to store the properties of the "largest" structure we want to find.

There is a trivial case that may be ignored in this probelm if you use while loop. That is when you input num as $0$. To deal with this case correctly, you should initialize the variables correctly and use do-while loop.

goldbach.c

long longest_consecutive_digits(long n)
{
    long longest_count = ­-1;
    long longest_digit;
    long current_count = 0;
    long current_digit = n % 10;
    do
    {
        // Increase the counter if we see the same digit.
        // Otherwise reset counter to 1.
        if (n % 10 == current_digit)
        {
            current_count += 1;
        }
        else
        {
            current_count = 1;
        }
        
        // Checks if we find a longer (or equally long)
        // consecutive sequence. Update longest_digit
        // and longest_count if so.
        if (current_count > longest_count)
        {
            longest_digit = current_digit;
            longest_count = current_count;
        }
        else if (current_count == longest_count)
        {
            if (current_digit < longest_digit)
            {
                longest_digit = current_digit;
            }
        }
        
        // Update the current digit to the last digit of n
        // and shorten n by one digit.
        current_digit = n % 10;
        n = n / 10;
    } while (n > 0);
    return longest_digit;
}

In this program, the use of current_digit is awesome! Actually, it serves the purpose of previous_digit and n % 10 at the first of the loop acts as the true current_digit. Initializing the current_digit to be n % 10 deals with the problem of there is no previous_digit at the start in an elegant way.

The use of do-while loop also guarantees that we will enter the loop at least once, which deals with the trivial case of $0$ as well.

5. Square

The "heart" of this problem is pattern recognition. Below are the patterns that are crucial:

1. The first and last rows (row == 1 || row == width) are where we have to draw ##...#

2. The second and penultimate rows (row == 2 || row == width - 1) are where we have to draw #...#

3. The rest (row == 3 && row <= width - 2, where we have to draw #...#, but with inner squares with the recursion print_square(row - 2, width -4).

Tips

1. Always regard real numbers as double type variable!

2. Include the function prime in your cheatsheet!

3. When to pay attention to the Big Number input in the question involving prime? The rule of thumb is to pass all the test cases, these cases should be strick enough! Also, the is_prime(num) function provided here 3. Goldbach* should be quick enough!!!