Classroom practice: Arrays

Considerations leading to the solutions

• We obviously need a loop to read the numbers from the standard input.
• Every possible number (between 1 and 10) has an associated counter, which has to be incremented when the numbers appears on the input.
• We need a mapping between the numbers read and the counters.

To store the counters it is reasonable to define an array. Since the numbers on the input all fall between 1 and 10, the length of the array will be 10. The numbers to count are all integer numbers, hence finding the appripriate mapping is straight forward: for a number read from the input we use the counter that is given by the number itself, hence the number read from the input will serve as the index of the array. However, the smallest possible number is 1 and the arrays are indexed from 0, thus the array index will be given by number-1. The data structure used in the program is depicted by the table below.

Observe that we apply the theorem of counting here, with two modifications: instead of only one, we have multiple (10) counters here; and while we saw conditional counting on the lecture, we need unconditional counting here.

#include <stdio.h>

int main(void) {
    int t[10];

    for (int i = 1; i <= 10; i += 1)        /* fill array with 0 */
        t[i-1] = 0;

    printf("Enter numbers between 1 and 10, then something that is not a number!\n");
    /* while we succeed to read the numbers from the input */
    int number;
    while (scanf("%d", &number) == 1) {       /* processing */
        if (number >= 1 && number <= 10)
            t[number-1] += 1;
        else
            printf("The numbers must be between 1 and 10!\n");
    }

    for (int i = 1; i <= 10; i += 1)        /* display the array */
        printf("%d: %d\n", i, t[i-1]);

    return 0;
}

The scanf() function, besides obtaining and storing the number, returns a value as well. The value returned is the number of inputs that were successfully read, or an error code. In our program we have asked scanf() to obtain just a single input (%d, a decimal number), hence the value returned can be either 0 or 1 or EOF. In case the number was successfully read, it returns 1, while, in case of the input could not be converted to a decimal number, it returns 0. If an end-of-file event occurs while reading the input, an EOF constant is returned. We could have written while (scanf("%d", &number) != EOF) to our program, too, but to also cover the issues related to invalid input type it is better if check for return value 1 instead.

The steps of the solution

The algorithm is given, we just have to write down the corresponding C source code. We need to make decision on how the data should be represented: how to store that a given number is still in the list, thus it is potentially a prime, or if it has already been removed.

About the data structure: the elements of the array are logical values in this exercise. The array is indexed by the number itself, thus prime[2] stores the logical value true, if number 2 is prime, and 0 if it is not prime. The first two elements (index 0 and 1) will not be used, which seems to be a waste of memory, but, at the other hand, this decision makes the program simpler and easier to read. To find prime numbers up to 999, the size of the array shall be prime[1000].

After running the algorithm the content of the array is as follows:

At indices 0 and 1 the true ("t") value was kept, and at indices 4, 6, 8, 9, … the algorithm has assigned a false ("f") value indicating that they are not primes.

The loop searching for the primes can be run till the square root of the number, since above that we can be sure that the divisor has a pair below the square root (e.g. if the number is 1000: 2×500, 4×250, etc.).

#include <stdio.h>
#include <stdbool.h>

int main(void) {
    bool prime[1000];

    /* everything is assumed to be a prime initially */
    for (int n = 0; n < 1000; n += 1)
        prime[n] = true;

    /* the sieve */
    for (int n = 2; n < 1000; n += 1) {    /* traversing the sieve */
        if (prime[n]) {                 /* we found a prime */
            for (int t = n*2; t < 1000; t += n)
                prime[t] = false;
        }
    }

    /* displaying the result */
    for (int n = 2; n < 1000; n += 1)
        if (prime[n])                   /* it remained true -> prime */
            printf("%d ", n);
    printf("\n");

    return 0;
}

An alternative loop to mark the multiples as false:

int multip;

multip = 2;
while (i*multip < 1000) {
   prime[i*multip] = false;   /* the multiples are not primes */
   multip += 1;
}

The primes found can also be printed during the search.

The principle of the solution:

• The computer does not now the number of days in a month, we have to provide this info in the program.
• Let us create an array to store the length of the months!

#include <stdio.h>

int main(void) {
    /* the table to store the length of the months */
    int months[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    /* the input of the user */
    int which;

    printf("Which month?\n");
    scanf("%d", &which);
    printf("The %d th month has %d days.\n", which, months[which-1]);

    return 0;
}

We need to take care of the indexing: the index should be month-1, since the length of the first month (January) is stored at index 0 in the array. This is the reason we used months[which - 1] in the program.

Principle of the solution

• We have to add the lengths of all the months covered by the date, and then add the day. For instance, March 5 is = 31 (January) + 28 (February) + 5 (fifth) = the 64th day of the year.
• We have already stored the lengths of the months in an array in the previous exercise.
• In leap years February has 29 days, that has to be taken into consideration if the given date falls beyond February.

#include <stdio.h>
#include <stdbool.h>

int main(void) {
    /* the array with the lengths of the months */
    int months[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    /* auxiliary variables */
    int which, i;
    bool leapyear;
    /* this is the date for which the day of the year is calculated */
    int year = 2018, month = 9, day = 21;

    /* For the given month the length of the month does not have to be added,
       hence the limit of the loop is i<month. However, the array is indexed
       from 0, hence we have to subtract 1 from the index! If we currently
       consider January, index 0 is taken. */
    which = 0;
    for (int i = 1; i <month; i += 1)
        which += months[i-1];
    /* It is a leap year if the year is divisible by 400 or it is divisible
       by 4 and not by 100. If we have a leap year and the month is beyond
       February, we add +1 extra day. */
    leapyear = year%400==0 || (year%100!=0 && year%4==0);
    if (leapyear && month > 2)
        which += 1;
    /* finally, add the days */
    which += day;

    printf("%4d.%02d.%02d. is the %d th day of the year.\n", year, month, day, which);

    return 0;
}

According to the solution, the banknotes are sorted in descending order, and the ATM machine always give back from the highest valued banknote as much as possible. This algorithm is called a "greedy" algorithm, it trys to improve as much as it can in every step.

#include <stdio.h>

int main(void) {
    /* a 0 marks the end of the array */
    int banknotes[] = {20000, 10000, 5000, 2000, 1000, 500,
                    200, 100, 50, 20, 10, 5, 0};
    int howmuch;
    printf("How much is the change? ");
    scanf("%d", &howmuch);

    printf("The machine gives:\n");
    /* assume the banknotes are sorted in a descending order in the array.
       We start giving banknotes with higher values first. */
    for (int i = 0; banknotes[i] != 0; i += 1) {
        int pcs = howmuch/banknotes[i];
        if (pcs > 0) {
            printf("%d pcs %d Ft banknote.\n", pcs, banknotes[i]);
            /* Multiplying back by "pcs" we have the amount given out so far. */
            howmuch -= pcs*banknotes[i];
        }
    }
    if (howmuch != 0)
        printf("There is no such small coin/banknote: %d Ft\n", howmuch);
    return 0;
}

Typically, it is necessary to store / to know the exact length of an array. In this example, however, it is not nvecessary. The end of the array is marked by a value 0, that makes it possible to use a loop condition banknotes[i] != 0, which does not include the array size. The only reason we can do this is that the value 0 is not meaningful in case of banknotes, thus we can use it as an end-of-array symbol. Value -1 could be just as appropriate as value 0, or whatever value, that can be distinguished from the useful content of the array.

The result of expression howmuch/banknotes[i] is integer, e.g. 2100/1000=2. In the C language, dividing two integer numbers always given an integer number as a result, that we exploited in the program.