Formulating Algorithms

Now that we have learnt about two of the control structures, we shall see how we can formulate algorithms using theses structures. We do have another group of control structures- branching statements, about which we shall see later on. We have two basic approaches, each of which is used for a particular situation. The first is counter controlled repetition and the other is sentinel controlled repetition. Counter control repetition is followed when we know in advance the number of times the loop has to be executed while the sentinel controlled approach is taken when this number is not known before entering the loop. We will deal with the problem of adding numbers to understand these two approaches.

Counter Controlled Repetition

We have already used controlled repetition when discussing the basics of loops. This example would make the approach more clear. This is the problem: the number of numbers to be added is to be first taken as an input. The user is then prompted for the numbers which will be added by the program. The sum of the numbers entered is then displayed on the screen. This is the program which performs the task:

import java.util.Scanner;

Public class AddNumbers {

Public static void main(String args[]) {
Scanner s = new Scanner(System.in);
System.out.print(“Enter the number of numbers that you wish to add: “);
int count = s.nextInt();
int sum = 0;
for (int i = 1; i <= count; i++) {
System.out.print(“Enter number ” + i + “: “);
sum = sum + s.nextInt();
}
System.out.println(“The sum of the numbers is ” + sum);
}
}

Given below is a sample output:

Enter the number of numbers that you wish to add: 4
Enter number 1: 34
Enter number 2: 7
Enter number 3: 4
Enter number 4: 347
The sum of the numbers is 392

As you can see in the program above, we have taken the count as an input from the user. The loop is executed these many number of times. A counter, i is used to keep track of the number of numbers that have been added. Each time, the value of i is also displayed along with a prompt for the number. Within the for loop itself, the number taken as input is added to sum.

Sentinel Controlled Repetition

Sentinel is a value which the user enters to indicate that there is no more input to be given to the program. For example, you can take input from the user as long as he doesn’t enter the number 0. In that case,0 is called the sentinel since entering this value causes to the program to stop taking the input. Given below is a program which uses a while loop driven by a sentinel to calculate the sum of numbers entered by the user.

import java.util.Scanner;

Public class AddNumbers {

Public static void main(String args[]) {
Scanner s = new Scanner(System.in);
int sum = 0;
int num;
do {
System.out.print(“Enter a number (0 to stop): “);
num=s.nextInt();
sum=sum+num;
}while(num!=0);
System.out.println(“The sum of the numbers is ” + sum);
}
}

And here is a sample output:

Enter a number (0 to stop): 3
Enter a number (0 to stop): 4
Enter a number (0 to stop): 7
Enter a number (0 to stop): 34
Enter a number (0 to stop): 0
The sum of the numbers is 48

Note that we have used a do while loop instead of a while loop or a for loop. We could have used them also and modified the program accordingly. In this particular program, we are first adding the number entered by the user to sum and then checking if it is the sentinel. Since the sentinel is 0, it doesn’t make any difference if we add the number first and then check or check the number and then add it to sum. However, if the sentinel is another value like -1, then the order does matter. In that case, we can take several approaches. One is to subtract the sentinel from the sum after coming out of the loop and before displaying the sum. But this doesn’t look quite good and therefore we present below, a few alternate versions to be used when the sentinel is a value other than 0.

Version 1:

int sum = 0;
int num = 0;
do {
sum = sum + num;
System.out.print(“Enter a number (0 to stop): “);
num = s.nextInt();
} while (num != 0);

Version 2:

int sum = 0;
System.out.print(“Enter a number (0 to stop): “);
int num = s.nextInt();
while (num != 0) {
sum = sum + num;
System.out.print(“Enter a number (0 to stop): “);
num = s.nextInt();
}

Out of all the above versions, the preferred is the last one. This is because in all other cases, we need to know the identity number which when accumulated with the existing result doesn’t change the value of result. In this particular case, where we are adding numbers, that number is 0. If we were to multiply the numbers entered instead of adding them, we would have initialised num to 1. But for an operation whose identity value isn’t known, version 2 is the only approach that can be taken.