Application of logic - planning and writing algorithms
From Programming In C
| Table of contents |
Planning and writing algorithms
Throughout this course you will be required, in both labs and assessments, to write algorithms to solve a particular problem. When planning and writing the algorithm it is useful to consider the following points:
General algorithm design and structure
In general, before writing an algorithm, it is useful to spend a few minutes thinking about the problem and how you would go about solving it without a programming language. One question you can ask yourself is if I had to solve this problem with a pen, paper and pocket calculator how would I go about doing it? Some students find it useful to sketch a simple flow diagram during this process.
In all cases you should be clear about the exact sequence of commands that the algorithm has to perform. It must be possible to follow an algorithm step-by-step. The instructions must be given in the correct order and there must be some way of telling when to finish one instruction and begin another. This is particulary important for programs that involve repeating a process several times (see Session 3 on looping). Similarly, your algorithm must have a definite stop condition. Often this is a trivial thing like outputting a calculated value. However, some care has to be given to ensure that a program will stop.
Writing and checking the algorithm
When writing your algorithm it is a very good idea to compile the source code regularly, after each few lines of code have been added. In this way you are able to spot any compilation errors immediately. Another reason why this is good practise is that it forces your code to be saved regularly so that if your computer crashes you do not lose hours worth of editing.
As you develop the algorithm you may want to add simple printf statements to write out values along the way to check that your code is doing what you expect it to.
Other things to bear in mind whilst developing your algorithm include
- Think carefully about the type of each variable, in particular, don't use double or float for variables that can only have integer values - you may run into rounding error problems. You should never use real numbers as for loop indices.
- Think carefully about initialisation of variables. If you start adding numbers to an uninitialised variable you may well get a meaningless value. In lots of cases it makes sense to initialise to 0 but this is not always the case (consider, e.g. how you initialised for Exercise 3.2 which calculated a factorial).
- Where appropriate, any data read in or written out must be checked if it makes sense. A good example of this is in the Day of week exercise which is part of this topic. You are asked to enter a date in the month and a month in the year. Clearly entering 55 then 9 for the 55th of September makes no sense. Your algorithm should always check for this type of error. If such checks are missing you will lose marks in an assessment.
Testing the final algorithm
Once you have finished writing your algorithm and you are confident it is working correctly you will want to check it is working OK. Sometimes an assessment may give you some example values to check. Otherwise, you can always modify your code to check values that you know.
Creating an algorithm: a step-by-step example
Perfect numbers
The following is an example of a previous PHY225 assessment
According to Wikipedia a perfect number is defined as follows:
In mathematics a perfect number is defined as an integer which is the sum of its proper positive divisors (factors), that is, the sum of the positive divisors not including the number itself.
The simplest example of a 'perfect number is the number 6. The "proper positive divisors" of 6 are those numbers (including 1 but excluding 6 itself) that divide exactly into 6 with no remainder. These are: 1, 2 and 3
If we add 1, 2 and 3 together then 1+2+3=6. This fact makes 6 a perfect number.
The next perfect number is 28. Since the positive integers 1, 2, 4, 7 and 14 divide exactly into 28 then they are the proper positive divisors of 28. Furthermore 1+2+4+7+14=28 and so 28 is also a perfect number.
There are 2 perfect numbers between 400 and 10000. Write a program to find them.
A careful read of the question will already give some hints on how to proceed, for example:
- This is a problem only involving integers, not real numbers
- It would appear that some form of integer division is going to
A suggested next step would be to apply the rule "what would I do if I had to solve this problem with just a pen, paper and calculator?'. In this way it is possible to start to build a 'recipe' for the algorithm that is needed. A step-by-step approach would involve doing the following:
- Take the first integer you are considering as a possible perfect number (400 in this case)
- Try dividing it by every integer between 1 and 399 inclusive
- Each time the division is exact (proper positive divisor) write that number down on your piece of paper
- Once you've finished identifying all the proper positive divisors add them together
- If sum of the proper positive divisors is the same as the integer you started with it is a perfect number
- Move onto the next number you are considering
Now is the time to translate this "recipe" into computer code. The important thing here is to identify what is happening in your "recipe" and look for the analogous action in the C programming language.
As always it is a good idea to start with a template program just containing the basics such as:
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
int main (void)
{
system("pause");
return 0;
}
At the moment this program doesn't do anything but it provides a blank skeleton which you can add to. As mentioned above, an important part of developing code is to compile the code regularly. That way, if you make a mistake you pick it up very quickly. If you type 20 lines of code before you compile it then it may be difficult to spot a very simple error.
Now let's go back to the "recipe" and break it down into steps. The first thing that the assessment asks us to do is to consider all of the integers from 400 to 10000 inclusive and test each one for being a perfect number. This requires some sort of loop. Since we know, already, exactly when the loop should start and end it is sensible (but not essential) to use a for-loop here:
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
int main (void)
{
const int istart = 5;
const int ifinish = 28;
int i;
for (i=istart; i<=ifinish; i++)
{
}
system("pause");
return 0;
}
Notes:
- here I have included the loop parameters as const int since we do not want these values to change
- I have not used the values of 400 and 10000 as given in the question (yet) as I want to check that my code is working OK so I am using a range of integers that I know the answer for. This is very good practise, often the assessment question will give you useful information like this.
Next we need to implement the next step of the "recipe" and divide our integer (i) by every integer between 1 and (i-1). This requires a second for-loop as follows:
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
int main (void)
{
const int istart = 5;
const int ifinish = 28;
int i,j;
for (i=istart; i<=ifinish; i++)
{
for (j=1;j<=i;j++)
{
}
}
system("pause");
return 0;
}
Notes:
- I am using indentation here to improve the readability of the code
- You can always add one or more printf statements in your code to check all is working OK
Next we need to check for a proper positive divisor. We can do this with the integer division via the remainder operator (%). If the result of the operation equals zero then the division has no remainder and so j is a proper positive divisor. The code then becomes:
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
int main (void)
{
const int istart = 5;
const int ifinish = 28;
int i,j;
for (i=istart; i<=ifinish; i++)
{
for (j=1;j<i;j++)
{
if (i%j == 0) printf(" %d divides perfectly into %d\n",j,i);
}
}
system("pause");
return 0;
}
Note:
- This time the for-loop runs to j<i and not j<=i
- At this point I've just put a printf statement into the code to check if my logic works correctly - again this is good practise
Compiling and running the code now would give something like:
1 divides perfectly into 5 1 divides perfectly into 6 2 divides perfectly into 6 3 divides perfectly into 6 1 divides perfectly into 7 1 divides perfectly into 8 2 divides perfectly into 8 4 divides perfectly into 8 1 divides perfectly into 9 3 divides perfectly into 9 ... etc. etc.
The simple addition of a printf statement here helps debug the code and shows that it is working correctly.
Now we need to sum the proper positive divisors by introducing a new integer (called sum). When introducing a variable like sum it is very important to consider 'initialisation. One of the most common reasons for lost marks in an assessment is the lack of initialisation, the incorrect initialisation or the improper placing of an initialisation statement.
In this case sum needs to be reset to zero each time we consider a possible new perfect number, i.e. between the two for-loops.
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
int main (void)
{
const int istart = 5;
const int ifinish = 28;
int i,j,sum;
for (i=istart; i<=ifinish; i++)
{
sum=0;
for (j=1;j<i;j++)
{
if (i%j == 0) sum+=j;
}
}
system("pause");
return 0;
}
Once all the possible proper positive divisors have been summed up a final check needs to be made to see if the sum equals the original integer that is being considered as a perfect number, if it is then print a message:
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
int main (void)
{
const int istart = 5;
const int ifinish = 28;
int i,j,sum;
for (i=istart; i<=ifinish; i++)
{
sum=0;
for (j=1;j<i;j++)
{
if (i%j == 0) sum+=j;
}
if ( sum == i ) printf("%d is a perfect number\n",i);
}
system("pause");
return 0;
}
Running this code now with 5 as the starting number and 28 as the final number gives the following output:
6 is a perfect number 28 is a perfect number
So you are now confident that the code is working correctly and can change the values of istart and ifinish in the code to 400 and 10000 respectively.
Once the code is complete and working correctly if you have any further time it is worth seeing if there are any improvements to be made to the code.
In this particular example there are 2 obvious improvements that can be made:
- 1 is always a proper positive divisor
- There is never a proper positive divisor greater than the number divided by 2
These two modifications are implemented in the final version of the code
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
int main (void)
{
const int istart = 400;
const int ifinish = 10000;
int i,j,sum;
for (i=istart; i<=ifinish; i++)
{
sum=1;
for (j=2;j<=(i/2);j++)
{
if (!(i%j)) sum+=j;
}
if ( sum == i ) printf("%d is a perfect number\n",i);
}
system("pause");
return 0;
}
Further Reading
A Book on C, Kelley and Pohl
- Revise Chapters 1 to 4 inclusive, attempt some of the Exercises in Chapters 3 and 4
