Your most important tool for discovering algorithms is common sense. Think about how you would solve a problem by hand. Try examples. Then work out how to express your hand algorithm so that a computer can carry it out.
Some problems break naturally down into a sequence of a fixed number of steps. The steps themselves can be big ones, each involving an algorithm of its own, but the big picture is a sequence of steps.
As an example, consider the problem of writing a nonnegative integer i using at least n characters by adding spaces as required. But instead of padding with spaces on the left, we will add spaces to the right end. For example,
writePadded(25,4);
writePadded(725,4);
writePadded(9,4);
printf(".");
writes
25 725 9 .using 4 total characters for each number, but with the added spaces to the right of the number. (If i uses more than n characters, then writePadded(i, n) just writes i, without any added spaces.)
(It would be possible to use printf to do this job. A simple definition of writePadded is as follows.
void writePadded(int x, int n)
{
printf("%-*i", n, x);
}
but our purpose here is not so much about writing a definition
of writePadded, but instead of using it to illustrate algorithm
design, so we avoid using printf.)
The steps to do writePadded(i,n) are as follows.
The individual steps still need to be solved, but you don't need to worry about that right away. Breaking the problem down into steps has yielded some simpler problems.
At this point in writing a definition of writePadded, you might hope to find a function in the library that carries out step 1 and another that carries out step 2. But you do not always find one. In that case, the principle of top-down design suggests that you should imagine that suitable functions are already available, and use them. Then work out how to solve them; write them yourself. Of course, in order to do this, you need to know exactly what each of the imagined functions is supposed to do. So you need a contract and heading for each one. It is the function bodies that you fill in later.
For writePadded(i, n), here are some obvious tools, one for doing step 1 and the other for doing step 2.
writeInteger(i) writes nonnegative integer i and returns the number of characters written.
writeSpaces(n) writes n spaces.
Using those tools yields a simple definition of writePadded.
void writePadded(int i, int n)
{
int k = writeInteger(i);
if(n > k)
{
writeSpaces(n - k);
}
}
Notice that it is clearly two steps, one after
the other.
If a problem involves doing a variable number of steps, a loop is an obvious tool to use. For example, how would you write n spaces? It suffices to write one space n times. That is a simple repetition.
void writeSpaces(int n)
{
for(int i = 1; i <= n; i++)
{
putchar(' ');
}
}
We will encounter other algorithms that are
naturally expressed as loops.
Some problems break down into two or more cases. For example, to find the larger of x and y, you know that
int larger(int x, int y)
{
if(x > y)
{
return x;
}
else
{
return y;
}
}