3GL Step-Form Algorithm
- Exercise 1
Design a step-form algorithm to count the pages in a book.
Your first step should be the investigation step:
-
Identify the processes
-
Identify the major decisions
-
Identify the loops
-
Identify the variables
What processes are implied in the problem? At the first attempt I came
up with:
-
Get a book
-
Increment a counter for pages
What decisions need to be made?
-
How do we know when we have reached the end of a page?
-
How do we know when we have reached the end of the book?
-
How do we know when we are at the beginning of the book?
What loops are implied in the problem?
-
Since for each page in the book we do the same thing - count it - then
there is a major loop which starts at the beginning of the book and finishes
with the last page.
What variables are implied?
-
counter
-
end of page
-
end of book
-
and probably beginning of book
The next step is the preliminary step:
-
Devise a "high level" algorithm
-
Step through the algorithm. Does this "walk-through" reveal any major problems?
If it does correct the problems.
Here is my first attempt:
-
Get book
-
Find first page
-
Go to end of page
-
Increment counter
-
If not last page then go to step 2
If you walk through this attempt you can see that it is a bit clumsy. The
last step states that if we are not at the end of the book then go back
to step 2 so that the page counting can continue. But step 2 points us
at the first page and what we really want to do is to get to the next page
and count that.
The third step in the strategy we are using is the refinement step:
-
Incorporate any refinements indicated in step 2.
-
Group together processes where appropriate
-
Group together variables where appropriate
-
Test the algorithm again by stepping through it
Here is a simple change as a first refinement:
-
Get book
-
Find next page
-
Go to end of page
-
Increment counter
-
If not last page then go to step 2
Now when step 5 terminates we automatically get the next page. This algorithm
implies that at the start of the algorithm the book is open just before
the first page but it is not very clear. What about making this a bit clearer?
-
Get book
-
Open at first page
-
Go to end of page
-
Increment counter
-
Find next page
-
If not last page then go to step 3
It is better but does it have any problems? What happens if in step 6,
after doing a Find next page step the page we have is the last page?
The last page won't be counted. Perhaps we could fix it this way:
-
Get book
-
Open at first page
-
Go to end of page
-
Increment counter
-
Find next page
-
If not last page then go to step 3
-
Increment counter
It seems OK but what if we have a book which has no pages? or a book which
has only 1 page?
Here is another attempt!
-
Get book
-
Open book
-
Find next page
-
If there is no next page go to step 7
-
Increment count
-
Go to step 3
-
Finish
Return to lesson
and may not be reproduced by any means without the
written
This publication is copyright David Beech and Learning Systems 1997-2002
and may not be reproduced by any means without the written permission of
David Beech.
9 Wyndella Street, Tasmania, Australia
db@codelearn.com