Loops and repetition
"Computers never get tired and never complain" - Cute joke that my teacher used to make during the classes
Initially, when we learn how to use loops, we don't worry about the performance of the algorithms. To study the performance of algorithms is left to later, more advanced, disciplines, where search or sorting algorithms are studied. However, we can already think about performance like this: one extra iteration and our algorithm is slower than another algorithm that does the same task with one fewer iteration.
The logic of a loop is: something is executed while some conditional is not satisfied. Or, something is executed many times until some conditional is satisfied.
Errors of logic:
- The condition of the loop is never satisfied, the loop is never executed;
- The condition of the loop is satisfied and the loop is executed, but after that, the condition to stop the loop is never satisfied and it never never ends;
- The condition of the loop is satisfied, but not when you wanted it to be.
- A variation of the algorithm that tests if a number is odd or even, this time without using conditional structures:
int a;
printf("Type an even number: ", a);
scanf("%d", &a);
/* While the user doesn't input an even number, keep asking for an even number */
printf("The number %d is odd, type another: ", a);
scanf("%d", &a);
}
/* If the user has inputted an even number, print this */
printf("The number %d is even, terminating program...", a);
WHILE. It's the most simple loop type. There is no counting, because the number of occurrences of "odd number" is unknown.
Inside the loop we need another scanf() call, else the program will not "go back". Once inside the loop, the only way to get out of it is by making the conditional false at some point. Without a scanf() inside the loop the program keeps printing a message on the screen endlessly.
PS: for now we are omitting what's inside the scanf() that makes the program "pause" because scanf() is a function.
- A program to calculate the sum of the first n integers:
int num, count = 0, sum = 0;
/* count from zero to the desired number */
count = count + 1;
sum = sum + count;
}
printf("The sum of the first %d positive integers is: %d", num, sum);
It's a pretty simple problem that already depicts the difference between doing calculations on paper and on the computer. On paper, the sum of the first three integers is 1 + 2 + 3, two sum operations. But on the computer there are two things to count: the sum and the numbers to be summed. Another difference is about the memory: on paper or if done mentally, the sum is requiring memory space in our brain; on the computer the variable represents a memory space in which values are assigned, the computer cannot memorize anything by itself. That explains why 'count' and 'sum' are initialized with zero, not one.
Any confusion in here can be solved by tracking that loop on paper.
Let's see the same loop, but this time beginning the sum with one, not zero:
int num, cont = 1, sum = 0;
/* count from one to the desired number */
while (cont <= num) {sum = sum + cont;
cont = cont + 1;
}
As an exercise, try to count in descending order.
- The same counting, but with FOR instead of WHILE:
int num, count, sum = 0;
/* for count equal to zero, count another one from zero till the desired number */
for (cont = 1; count <= num; count++;) { sum = sum + count; }
The difference between 'for' and 'while' lies in the syntax, just that. 'for loops' are used when we need to count iterations.
Flexibility. The counter can be initialized before the loop (but not inside it!). The loop's conditional doesn't need to be related to the counter. For example: there are cases in which the conditional is an approximation of some value and the number of steps required to get close enough isn't fixed. The conditional can even be omitted altogether, but then we have to use a break statement to stop the iterations at some point. According to the language's syntax the increment operation is always the last one to be done in the loop. It's permitted to omit the increment from the parenthesis and place it directly in the loop, this way we can control when the increment operation is done in a loop.
- A second problem about counting numbers, sum the first n prime numbers:
#define YES 1
#define NO 0
/* variable number is the quantity of primes to be summed is_prime denotes when a number is prime or not found_one counts how many primes have been found till now sum stores the sum of prime numbers prime counts odd numbers */
int number;
int is_prime;
int found_one = 0, sum = 0;
int prime;
int divisor, remainder;
/* sum primes, from one to n. Skip all even numbers. */
for (prime = 1; found_one < number; prime += 2) {
/* every odd number might be prime */
is_prime = YES;
/* 1 is odd but it's not prime */
if (prime == 1) is_prime = NO;
/* 3 is prime, skip the prime number test 2 is prime but it's even, an exception. Count it without doing the prime number test */
else if (prime == 3) {found_one++;
sum = 2;
}
/* if the number is neither 1 or 3, it can only be prime and odd or odd but not prime. Check the divisibility only of odd numbers and up to half of the number. If the remainder is zero, the number is not prime */
for (divisor = 3;
divisor < prime / 2;
remainder = prime % divisor;
is_prime = NO;
break;
}
}
}
/* if number is prime, count and do the sum */
if (is_prime == YES) {found_one++;
sum = sum + prime;
}
}
The algorithm relies on "brute force" to do the sum because there is no formula to find all prime numbers. If there was one, then the problem would be a matter of using some ready to apply formula. Nonetheless, some mathematical properties come in handy to optimize the code:
- With the exception of number 2, all primes are odd;
- No prime is divisible by two;
- The loop that checks the divisibility of an odd number is broken in the first odd divisor found. The loop is optimized to stop looking for possible odd divisors at half of the number being tested.
'break' only interrupts the current iteration in which it's in, if the broken loop is nested in another, the outer loop continues unchanged.
Notice that the algorithm is a combination of two smaller algorithms, one that does the sum and another that checks whether a number is prime or not. In problems like these it's a good idea to split the task in two, solve the smaller pieces first, this way the final solution is a combination of the two smaller solutions.
The variable 'is_prime' could had started with the negative value 'NO'. But if it did, then we'd have to change the prime number test to assign the value 'YES' to the var, in case of no divisor of the tested number being found.
- An algorithm that does the sum of the first n numbers, skipping multiples of 3 and 5
int num, count, sum = 0;
/* count in increments of one. If the number is multiple of 3 and 5, skip the sum. */
if (count % 3 == 0 && count % 5 == 0) continue;
}
Usage of 'continue' is pretty similar to the usage of 'break'. If the conditional is satisfied, 'continue' makes the loop skip everything that comes after this command. In other words, it literally means "continue to the next iteration". This type of structure is not elegant so to speak. It's not demanded in the algorithms studied in the introduction. In fact, it's always possible to not use 'continue'.
Be careful! If the counter's increment operation is moved from the parenthesis to anywhere after the 'continue' statement, an infinite loop is created.
Let's see the same algorithm without using the 'continue' statement:
int num, count, sum = 0;
/* Count in increments of one. Do the sum only and only if the number is not divisible by 15. */
for (count = 1; count <= num; count++) { if (count % 15 != 0) sum = sum + count; }
A little modification, a number that is divisible by 3 and by 5 is divisible by 15.
